RNG quality verification

[Philipp Gühring]

Hi Travis,

> The only thing is, you cannot test in randomness, 

That´s true, but I can test non-randomness. And if I don´t detect 
non-randomness, I can assume randomness to a certain extent.

> and it is an abuse 
> of statistics to make predictions about individual events -- 

Wasn´t that one of the reasons, why statistic was invented?

> they 
> describe populations.  The best thing you could do is combine them
> with a truly random source that you control.  

I don´t control the software everyone is using on this world.

> Of course then your 
> users may not trust you, so you have to do a cryptographically strong
> combination such that control of one of the inputs doesn't translate
> into control of the outputs.  For example, you cannot simply XOR them
> or you could force the key to be anything of the same length by
> choosing an appropriate stream.  Also, you could not do this with
> small input spaces or else exhaustive search is trivial (try every
> input until the output is what you want).

The problem is that I have to live with COTS (Common-off-the-shelf) software 
out there, that is generating the certificate requests. The only thing I can 
do is create a blacklist or a whitelist of known bad or known good software, 
to tell the users: Use this software, or don´t use that software.

> The best you could do is examine (reverse engineer) the RNGs in the
> products, and whatever seeds them, and then create tests for their
> nonrandom properties, and then see if the tests work.  This would,
> however, not tell you anything you didn't already know once you had
> examined the internals.  

Has anyone done this yet?

> You might be able to find structure in their 
> outputs through blind application of general-purpose statistics, but
> it will likely take a great deal more output, even with supposedly
> sensitive statistics like double-sided Kolmogorov-Smirnof.

Hmm, every key should deliver about 1000 bits of randomness, I guess. How many 
bits should I collect for the tests in your opinion?

> As a pathological example, my RNG may output the text of the King
> James Bible, encrypted with AES-CBC using a counter as the key, and
> uniquified across instances by using a processor serial number or
> licence number as an IV.  Unless you knew this, you would be
> hard-pressed to tell they were not random and in fact totally
> predictable to anyone who knows the "secret".  If a general statistic
> could distinguish this from a random stream, I think it would imply a
> weakness in AES-CBC.  The tests would likely fail until enough output
> was generated that it started to repeat itself.  On the other hand, I
> could decrypt it with a counter and see what pops out, and all I'd
> have to do is distringuish the KJV from a random stream.

I guess someone would have noticed already, if Microsoft, Mozilla or OpenSSL 
had done that.

Wait. How many LOC(lines of code) does the King James Bible have? Mozilla had 
something like 13 Mio. LOC as far as I remember ... perhaps they really hid 
the KJ Bible in it! ;-)

> I'd look at seeding techniques first, as that's an easy win.
> Predictable seed -> predictable output.  If that bootstrap is wrong,
> you can treat everything else as an oracle and still get a good
> distinguisher.

Contrary to the normal challenge of developing a new random number generator, 
I don´t have the possibility to change the existing software, I just have to 
evaluate them, and find out, whether it´s ok or not.

I first thought about a black-box test, by simply tracing in the operating 
system where the software gets its numbers from. A open("/dev/random") 
systemcall at the time of key generation might be a good hint for good random 
numbers. But as Netscape proofed some years ago, you can 
ch=read(stream,&ch,1) one perfectly random number, and overwrite it with the 
value 1 (which is not soo random anymore) in one single line of error, and 
invisibly to the operating system failing to use the random numbers given.
So since the random numbers might be modified between gathering and using for 
the keypair, I thought that I need to evaluate the quality at the end of the 
keypair generation.

Best regards,
Philipp Gühring


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com