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

From: Theodore Ts'o
Date: Fri Sep 24 2004 - 16:36:54 EST


On Fri, Sep 24, 2004 at 01:59:29PM -0400, Jean-Luc Cooke wrote:
> > If they only want crypto-secure random numbers, they can do it in
> > userspace. Information secure random numbers is something the kernel
> > can provide, because it has low-level access to entrpoy sources. So
> > why not try to do the best possible job?
>
> Sure. I hate Brittney Spears, but I will not deny people the choice.

The principle of avoiding kernel bloat means that if it doesn't have
to be done in the kernel, it should be done in userspace. If all
you're providing is an CRNG, the question then is why should it be
done in kernel, when it could be done just as easily in userspace, and
using /dev/random as its input?

> > This is another red herring. First of all, we're not using the hash
> > as a MAC, or in any way where we would care about collisions.
> > Secondly, all of the places where we take a hash, we are always doing
> > it 16 bytes at a time, which is SHA's block size, so that there's no
> > need for any padding. And although you didn't complain about it,
> > that's also why we don't need to mix in the length in the padding;
> > extension attacks just simply aren't an issue, since the way we are
> > using the hash, that just simply an issue as far as the strength of
> > /dev/random.
>
> Woh there. Didn't you just say "see, these hashes are weakened. That's
> bad". Now I just demonstrated the same thing with your SHA1 implementation
> and you throw that "red-herring" phrase out again?

No, what I'm saying is that crypto primitives can get weakened; this
is a fact of life. SHA-0, MD4, MD5, etc. are now useless as general
purpose cryptographic hashes. Fortuna makes the assumptions that
crypto primitives will never break, as it relies on them so heavily.
I have a problem with this, since I remember ten years ago when people
were as confident in MD5 as you appear to be in SHA-256 today.

Crypto academics are fond of talking about how you can "prove" that
Fortuna is secure. But that proof handwaves around the fact that we
have no capability of proving whether SHA-1, or SHA-256, is truly
secure.

In contrast, /dev/random doesn't have this dependence, which (a) is a
good thing, and (b) why it doesn't bother with the SHA finalization
step. It's simply not necessary.

- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/