Re: [dsfjdssdfsd] What has gone wrong with RNGs in practice

[Arnold Reinhold <[e-mail]>]

On Nov 16, 2013, at 7:32 PM, Russ Housley <[e-mail]> wrote:

> Arnold:
> 
>>> == What has gone wrong in practice and led to actual working attacks:
>>> 
>>> A. Not actually using randomness at all for something that needs some
>>> or all of the properties of a random bitstring.
>>> 
>>> Example: Sony's implementation of ECDSA failed to actually change the
>>> k value between signatures; they just had a constant.[1]
>>> 
>>> 
>> ....
>>> * Underdocumented, underexplained randomness requirements.
>>> 
>>> Before you sniff too loudly at Sony's mistake in [1]: Pretend that you
>>> are a programmer in a hurry looking at FIPS 186-2, or your favorite
>>> (early) standards-body description of DSA. How well does it explain
>>> the importance of making 'k' completely unpredictable for each
>>> message, and how well does it explain the consequences for failing to
>>> do so?
>>> 
>> 
>> I has also been suggested that Sony's failure to generate unique k's could have been caused by a compiler that optimized the k=crypto_random(); call out of a loop.  Whether that happened or not in the Sony case, the possibility should be dealt with in any RNG standard, as the consequence of a repeated k is easy recovery of the private key. Perhaps there should be a requirement that two (or more) test signatures be generated at application startup to verify independent k's are being generated, as code that worked initially could later be recompiled with different optimization settings for a new release.. 
> 
> There should be a self-test part of the specification that detects this type of failure.  It should not be hard to turn the FIPS 140 test suite into a good-enough-to-continue / fail test.  This would envolve generating 10,000 random bits and doing some statistical checks.

The FIPS 140 statistical test suite won't detect that a complier has optimized a RNG call out of a loop. A special test is require here. Also since any RNG likely to be recommended will either generate or whiten bits using a crypto primitive such as SHAx or AES, statistical tests on the output of such RNGs are of little worth. The output these primitives is guaranteed pass any such test even if their input has be tampered with to allow a small search space.

The place where statistical tests would be very useful is in checking a true random noise source. Here a trustworthy entropy source SHOULD exhibit some deviation from pure randomness. Unfortunately many true random bit generators have built in whitening circuits that prevent downstream software from testing the underlying noise source.  As I understand it, this is the case with Intel's x86 hardware RNG instructions. The lack of access to raw digitized noise makes such RNGs impossible to audit.

We are entering an era where many mission-critical internet devices use solid state mass storage and lack other peripherals that can be used to obtain entropy (such as audio inputs and cameras). There will be a strong tendency to rely solely on random bit generators built into billion-transistor CPUs or SoCs, which can have surreptitious back-doors inserted during production by organizations with enough clout.

Any standard that attempts to deliver real security must include some guidance on choosing hardware that includes more than one independent, auditable entropy source, each capable of delivering at least 128 bits at start up when brand new, at first power up.

Arnold Reinhold