How secure is Linux's random number generator? • Hacker News Board

Re: How secure is Linux's random number generator?

#61

Post by caf » Sun, Jul 14, 2013, 1:55 AM UTC

wtallis wrote: post #57

pbsd wrote: post #47

Earlier quoted context omitted.

In NIST parlance (SP800-90{A,B,C}), RDRAND is a DRBG, while /dev/random should be a NRBG. For what it's worth, the RDSEED instruction has been announced by Intel a while back (but not yet on current processors), which means to be an NRBG as well.

RDRAND does have non-determinism. The problem is that you can't directly measure or monitor how much non-determinism. The values you get from RDRAND come from a DRBG that is periodically and automatically re-seeded from a NRBG, but if you call RDRAND many times in rapid succession, then the DRBG may not have been re-seeded between each invocation. RDSEED differs only in that it guarantees that the DRBG is re-seeded b…

This comment in linux/arch/x86/kernel/cpu/rdrand.c claims:

    /*
     * Force a reseed cycle; we are architecturally guaranteed a reseed
     * after no more than 512 128-bit chunks of random data.  This also
     * acts as a test of the CPU capability.
     */

Re: How secure is Linux's random number generator?

#62

Post by tptacek » Sun, Jul 14, 2013, 2:05 AM UTC

vilda wrote: post #49

tptacek wrote: post #38

So this is logic that more or less rules out all hardware encryption, including HSMs, right?

No. In fact it's a matter of trust. You can trust Skype that calls are encrypted and cannot be eavesdropped, you can trust Verizon that your cellphone metadata are not passed to government automatically, and you can trust Intel that their rnd is not backdoored. Or you don't.

Help me understand how someone who believes rdrand might be backdoored could trust any HSM?

Re: How secure is Linux's random number generator?

#63

Post by pbsd » Sun, Jul 14, 2013, 2:20 AM UTC

caf wrote: post #61

wtallis wrote: post #57

Earlier quoted context omitted.

RDRAND does have non-determinism. The problem is that you can't directly measure or monitor how much non-determinism. The values you get from RDRAND come from a DRBG that is periodically and automatically re-seeded from a NRBG, but if you call RDRAND many times in rapid succession, then the DRBG may not have been re-seeded between each invocation. RDSEED differs only in that it guarantees that the DRBG is re-seeded b…

This comment in linux/arch/x86/kernel/cpu/rdrand.c claims: /* * Force a reseed cycle; we are architecturally guaranteed a reseed * after no more than 512 128-bit chunks of random data. This also * acts as a test of the CPU capability. */

FTR, that limit is also mentioned in the Intel manual [1, 3.2.3], and in the Cryptography Inc report [2, 2.4.2].

[1] http://software.intel.com/en-us/articles/intel-digital-rando...

[2] http://www.cryptography.com/public/pdf/Intel_TRNG_Report_201...

Re: How secure is Linux's random number generator?

#64

Post by chiph » Sun, Jul 14, 2013, 2:49 AM UTC

tptacek wrote: post #62

vilda wrote: post #49

Earlier quoted context omitted.

No. In fact it's a matter of trust. You can trust Skype that calls are encrypted and cannot be eavesdropped, you can trust Verizon that your cellphone metadata are not passed to government automatically, and you can trust Intel that their rnd is not backdoored. Or you don't.

Help me understand how someone who believes rdrand might be backdoored could trust any HSM?

You can't, if you're that serious/paranoid about it.

It's possible that the HSM maker wasn't approached by the NSA and is secure, but there are very few of them in the US so chances of the NSA having missed one is very low. Plus, without a STM to inspect the silicon and reverse-engineer it, how would you know?

So what if you buy one made outside the US? Say, China. Well, there's the obvious possibility that the Chinese authorities have backdoored the silicon. But my guess is that the Chinese maker just cloned one of the US vendors, including the portions inserted by the NSA...

Re: How secure is Linux's random number generator?

#65

Post by bigiain » Sun, Jul 14, 2013, 2:55 AM UTC

tptacek wrote: post #62

vilda wrote: post #49

Earlier quoted context omitted.

No. In fact it's a matter of trust. You can trust Skype that calls are encrypted and cannot be eavesdropped, you can trust Verizon that your cellphone metadata are not passed to government automatically, and you can trust Intel that their rnd is not backdoored. Or you don't.

Help me understand how someone who believes rdrand might be backdoored could trust any HSM?

I'd -consider- "trusting" a random number generator that collects entropy from a Chinese, a Russian, and a US based HSM manufacturer…

An "array of mutually untrustworthy opponents", if you like…

Re: How secure is Linux's random number generator?

#66

Post by snogglethorpe » Sun, Jul 14, 2013, 3:00 AM UTC

marshray wrote: post #25

oellegaard wrote: post #22

Earlier quoted context omitted.

Maybe no-one would have noticed if it was closed source. I bet if Microsoft released everything as Open Source there would be billions of bugs discovered.

The Debian RNG bug was noticed by folks who found identical certificates in the wild, not by code inspection. Similar RNG weaknesses are commonly found in closed systems as well, so it doesn't seem to be a particularly open/closed source thing.

It's true that merely the ability for widespread code inspection doesn't mean all the code really gets widespread inspection [although I'm surprised by the number of messages I see on mailing lists like Q: "Hi, I'm a Chinese grad student and have been reading the gcc source... I don't understand how XXX can work, given that YYY... can you explain? thanks" A: "oh, hmm, actually, that seems to be a bug..."]

Still, I think a common pattern is (1) notice funny symptom, (2) go look at code, puzzle through it for a while, and then "oh!" You're now in a much stronger position to fix the problem or petition for a fix.

With closed-source code, step (2) is a lot harder unless you're in a privileged position...

Re: How secure is Linux's random number generator?

#67

Post by AlexFinks » Sun, Jul 14, 2013, 3:01 AM UTC

olympus wrote: post #5

Just because something is closed source doesn't mean it's insecure. RdRand meets various standards for RNGs and the dieharder tests don't show anything of concern. While you can't be 100 percent sure of the reliability of RdRand because you can't audit it, I feel safe trusting it for all but the most critical of applications. Here's a blog post describing testing RdRand with dieharder: http://smackerelofopinion.blogs…

I think that transparency and opaqueness provide different kinds of security, but they are related to security. It would be wrong to say that they are independent simply because an opaque system can still have the ability to be extremely secure.

Re: How secure is Linux's random number generator?

#68

Post by pronoiac » Sun, Jul 14, 2013, 3:07 AM UTC

pronoiac wrote: post #55

What does it take to reverse engineer the silicon? I thought I'd seen an project for automating it, but I can't find it.

Ah. Some relevant information on reverse engineering silicon:

* Degate, a somewhat automated "aid in reverse engineering of digital logic in integrated circuits" - http://www.degate.org/

* Silicon Zoo offers a tutorial / background info on this - http://siliconzoo.org/tutorial.html

* A blog about IC reverse engineering - http://uvicrec.blogspot.com/ (from the owner of http://siliconpr0n.org/ , which is currently down)

Re: How secure is Linux's random number generator?

#69

Post by cambecc » Sun, Jul 14, 2013, 4:00 AM UTC

So... taking this line of reasoning to its logical conclusion, if you don't trust RDRAND, then you should also not trust _any_ of the hardware the OS runs on. I imagine there would be much easier ways for Intel to implement backdoors to the system than through the non-deterministic random number generator.

Re: How secure is Linux's random number generator?

#70

Post by nullc » Sun, Jul 14, 2013, 5:04 AM UTC

olympus wrote: post #5

Just because something is closed source doesn't mean it's insecure. RdRand meets various standards for RNGs and the dieharder tests don't show anything of concern. While you can't be 100 percent sure of the reliability of RdRand because you can't audit it, I feel safe trusting it for all but the most critical of applications. Here's a blog post describing testing RdRand with dieharder: http://smackerelofopinion.blogs…

AES of a counter and a key set from a table based on your CPU serial number also "meets various standards for RNGs and the dieharder tests don't show anything of concern".

And, of course, if you make it the kernel /dev/random you're making it the source of randomness recommended for long term keys and other important things... while you don't know what the users will use it for, you can safely assume it will include some of "the most critical of applications".