Messages in this thread
 Date Mon, 23 Sep 2013 09:39:43 +0200 From Jörg-Volker Peetz <> Subject Re: [PATCH,RFC] random: make fast_mix() honor its name
`Thanks for your patience and elaborated answer.Theodore Ts'o wrote, on 09/22/2013 23:27:> On Sun, Sep 22, 2013 at 11:01:42PM +0200, Jörg-Volker Peetz wrote:>> just out of interest I would like to ask why this mixing function has to be that>> complicated. For example, even if the input is always 0 and the pool is seeded>> with pool[0] = 1 (as in your test program) this algorithm generates some>> (predictable) pseudo-random numbers in the pool. Is this necessary?>>>> To just mix in some random input filling the whole pool (seeded again with>> pool[0] = 1) something as "simple" as>>>>           f->pool[0] = rol32(input[0], f->pool[2] & 31) ^ f->pool[1];>>           f->pool[1] = rol32(input[1], f->pool[3] & 31) ^ f->pool[2];>>           f->pool[2] = rol32(input[2], f->pool[0] & 31) ^ f->pool[3];>>           f->pool[3] = rol32(input[3], f->pool[1] & 31) ^ f->pool[0];>>>> would suffice, although I didn't do any statistical tests.> > The structure of the mixing functions in /dev/random has been well> studied, and validatetd in a number of different academic papers.  So> I prefer to stick with the basic architecture, even as it is scaled> down for speed reasons and beause the pool is smaller.I'm not arguing so much for speed but for simplicity and comprehensibility ofcode. As far as I understand the task of fast_mix() is just to collect randombits in a small buffer separated from the random pool?Once in a while these collected bits are then mixed into the main random pool.For that purpose, justifiably, a strong mixing function is used.> One of the important things about the mixing function is that if the> attacker knows the input values (of which the simplest example for> analytic purposes is if the input values are all zero), we want there> to be ample mixing across the pool.> > If you look at your proposed mixing function, in the case where the> input values are all zero, it devolves into:> >            f->pool[0] = f->pool[1];>            f->pool[1] = f->pool[2];>            f->pool[2] = f->pool[3];>            f->pool[3] = f->pool[0];> > Yes, I know the input values will never be all zero, but in the case> where the attacker knows what the input values are[1], but does not know> the contents of the entropy pool, a very simplistic mixing function> becomes relatively easy to analyze in the case where attacker knows> the inputs and then outputs, and is trying to determine the internal> state of the random driver.> > Measuring the speed of the fast_mix function which I put together,> it's already been speeded up compard to the original fast_mix function> by a factor of six.  On my x86 laptop, I can run 10 million> iterations in 0.14 seconds, so that translates to 14ns per fast_mix> call.   (The original fast_mix function runs in 84 nanoseconds.)> > So there is a cost-benefit tradeoff that we need to balance here.  If> you have a system with 100k interrupts per second, performance is> going to be poor no matter what, and it's not clear how common such> systems really are.  Most modern hardware do have some kind of NAPI or> other interrupt mitigation in place --- heck, even back in 1980's> people had figured out how to improve the 8250 UART with the 16550A> UART, which introdued a FIFO to decrease the interrupt load caused by> serial ports, and things have only gotten better since then.> > Out of curiosity, on your profiles, how many nanonseconds total is the> total interrupt code path chewing up per interrupt?> > Regards,> > 						- Ted> > [1] And on systems where we don't have get_cycles() or> random_get_entropy(), it becomes much easier for the attacker to guess> what at least half of the input values will be!> --To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`

Last update: 2013-09-23 10:01    [W:0.086 / U:10.060 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site