Re: [PATCH,RFC] random: make fast_mix() honor its name

["Jörg-Volker Peetz" <jvpeetz@web.de>]

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!
>