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

[linux@horizon.com]

>> This, I do not recall.  I must have missed it.  Will you please show me
>> two inputs that, when fed to the SHA-1 in random.c, will produce
>> identical output?

> 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.)

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

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