Re: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random

[Jean-Luc Cooke <jlcooke@certainkey.com>]

On Mon, Sep 27, 2004 at 12:50:33AM -0000, linux@horizon.com wrote:
> > SHA-1 without padding, sure.
> 
> > hash("a") = hash("a\0") = hash("a\0\0") = ...
> > hash("b") = hash("b\0") = hash("b\0\0") = ...
> > hash("c") = hash("c\0") = hash("c\0\0") = ...
> 
> And how do I hash one byte with SHA-1 *without padding*?  The only
> hashing code I can find in random.c works 64 bytes at a time.
> What are the other 63 bytes?
> 
> (I agree that that *naive* padding leads to collisions, but random.c
> doesn't do ANY padding.)

And I guess it is my fault to assume "no padding" is naive padding.

> > I see.  And in the -mm examples, is the code easily readable for other
> > os-MemMgt types?  If no, then I guess random.c is not the exception and I
> > apologize.
> 
> The Linux core -mm code is a fairly legendary piece of Heavy Wizardry.
> To paraphrase, "do not meddle in the affairs of /usr/src/linux/mm/, for
> it is subtle and quick to anger."  There *are* people who understand it,
> and it *is* designed (not a decaying pile of old hacks that *nobody*
> understands how it works like some software), but it's also a remarkably
> steep learning curve.  A basic overview isn't so hard to acquire, but the
> locking rules have subtle details.  There are places where someone very good
> noticed that a given lock doesn't have to be taken on a fast path if you
> avoid doing certain things anywhere else that you'd think would be legal.
> 
> And so if someone tries to add code to do the "obvious" thing, the
> lock-free fast path develops a race condition.  And we all know what
> fun race conditions are to debug.
> 
> Fortunately, some people see this as a challenge and Linux is blessed with
> some extremely skilled VM hackers.  And some of them even write and publish
> books on the subject.  But while a working VM system can be clear, making it
> go fast leads to a certain amount of tension with the clarity goal.

Freightning ... but informative thank you.

> > And the ring-buffer system which delays the expensive mixing stages untill a
> > a sort interrupt does a great job (current and my fortuna-patch).  Difference
> > being, fortuna-patch appears to be 2x faster.
> 
> Ooh, cool!  Must play with to steal the speed benefits.  Thank you!

I'll have a patch for a "enable in crypto options" and "blocking with entropy
estimation" random-fortuna.c patch this week.  My fiance is out of town and
there should be time to hack one up.

JLC