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 of code. As far as I understand the task of fast_mix() is just to collect random bits 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" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/