Re: Replace /dev/random input mix polynomial with Brent's xorgen?

[Greg Price]

On Sun, Dec 15, 2013 at 05:09:10PM -0500, George Spelvin wrote:
> Well, /dev/urandom is documented as being *deliberately* slow.  It's meant
> only to produce 128 to 256 bits of seed material for CPRNG.  I don't
> know if Ted considers speeding it up to be goal or an antigoal. :-)

Hmm, I don't think I've seen that documentation.  I don't see anything
about that point in the comments of drivers/char/random.c.  The
urandom(4) man page says /dev/urandom "is designed for security, not
speed, and is poorly suited to generating large amounts of random
data."  Which is quite different from being designed for slowness!

The great thing about the state of cryptography in 2013 is that we
don't have the kind of tradeoff between speed and security that we had
in the past.  Skein and Salsa20 and some other hashes and ciphers from
within the past decade are all very fast, and they've also been
attacked hard by cryptanalysts (motivated by competitions), and held
up very well.  From my understanding of the literature, moving to
either one from our current SHA-1-based scheme would only increase the
level of confidence one should have in the security of the random driver.

I think it would be great to be able to change the documentation to
"is designed for security and is also very fast and well suited to
generating large amounts of random data".  Users are always tempted by
speed, and if we can reduce that temptation by making our CSPRNG
faster (and still secure), it will be good for security.


> BTW, if it helps on 32-bit platforms I can get you rotate constats for
> a 32-bit version of threefish.  I haven't generated a key scheduling
> constant, though.

Interesting.  So, the generic Skein implementations in the SUPERCOP
testing/benchmarking suite are about four times slower on x86_32 than
x86_64.  Which means Skein should still be about 6x faster than the
current /dev/urandom implementation, but it'd be nice to be faster
still.  I imagine the same rough comparisons will hold on other 64-bit
and 32-bit architectures, though the gap between x86_32 and x86_64 is
probably wider because of the scarcity of registers on x86_32.

I wouldn't want to compromise on security to do it, though.  My
confidence in Skein/Threefish's security comes mostly from the SHA-3
competition, where many expert cryptanalysts attacked it and didn't
get very far except in understanding why it seems to be hard to break.
To make, or even evaluate, a 32-bit variant of Threefish seems like
it'd require much deeper understanding of the design of Threefish and
its cryptanalysis than I've tried to develop.  How do you plan to
evaluate the security of your 32-bit Threefish?

Regards,
Greg
--
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/