lkml.org 
[lkml]   [2013]   [Sep]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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 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 majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please 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