`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 wellstudied, and validatetd in a number of different academic papers.  SoI prefer to stick with the basic architecture, even as it is scaleddown for speed reasons and beause the pool is smaller.One of the important things about the mixing function is that if theattacker knows the input values (of which the simplest example foranalytic purposes is if the input values are all zero), we want thereto be ample mixing across the pool.If you look at your proposed mixing function, in the case where theinput 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 casewhere the attacker knows what the input values are[1], but does not knowthe contents of the entropy pool, a very simplistic mixing functionbecomes relatively easy to analyze in the case where attacker knowsthe inputs and then outputs, and is trying to determine the internalstate 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 functionby a factor of six.  On my x86 laptop, I can run 10 millioniterations in 0.14 seconds, so that translates to 14ns per fast_mixcall.   (The original fast_mix function runs in 84 nanoseconds.)So there is a cost-benefit tradeoff that we need to balance here.  Ifyou have a system with 100k interrupts per second, performance isgoing to be poor no matter what, and it's not clear how common suchsystems really are.  Most modern hardware do have some kind of NAPI orother interrupt mitigation in place --- heck, even back in 1980'speople had figured out how to improve the 8250 UART with the 16550AUART, which introdued a FIFO to decrease the interrupt load caused byserial ports, and things have only gotten better since then.Out of curiosity, on your profiles, how many nanonseconds total is thetotal interrupt code path chewing up per interrupt?Regards,						- Ted[1] And on systems where we don't have get_cycles() orrandom_get_entropy(), it becomes much easier for the attacker to guesswhat 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/`