RNG quality verification

Steven M. Bellovin smb at cs.columbia.edu
Fri Dec 23 12:15:24 EST 2005


In message <200512231609.17767.pg at futureware.at>, Philipp =?utf-8?q?G=C3=BChrin
g?= writes:
>Hi Peter,
>
>> Easily solveable bureaucratic problems are much simpler than unsolveable
>> mathematical ones.
>
>Perhaps there is some mis-understanding, but I am getting worried that the 
>common conception seems to be that it is an unsolveable problem.
>
>What is wrong with the following black-box test?
>
>* Open browser
>* Go to a dummy CA´s website
>* Let the browser generate a keypair through the <keygen> or cenroll.dll
>* Import the generated certificate
>* Backup the certificate together with the private key into a PKCS#12 
>container
>* Extract the private key from the backup
>* Extract p and q from the private key
>* Extract the random parts of p and q (strip off the first and the last bit)
>
>* Automate the previous steps with some GUI-Automation system
>
>* Concatenate all random bits from all the keypairs together
>* Do the usual statistical tests with the random bits
>
>Is this a valid solution, or is the question of the proper usage of random 
>numbers in certificate keying material really mathematically unsolveable?
>
(I am not a RSA specialist yet, I tried to stay away from the bit-wise details 
>and the mathematics, so I might be wrong)
>
>But I would really worry, if it is mathematically impossible to attestate the 
>correct usage (to a certain extent, I know about the statistical limitations) 
>of random numbers with the software I am using to get certificates.
>

It's really unsolvable, in several different ways.

First -- you just cannot tell if a single number is "random".  At best, 
you can look at a large selection of numbers and see if they fit 
certain randomness tests.  Even that isn't easy, though there are 
several packages that will help.  The best-known one is DIEHARD;
ask your favorite search engine for "diehard random".

However -- and it's a big "however" -- numbers that are "random enough" 
for statistical purposes are not necessarily good enough for 
cryptographic purposes.  As several people have pointed out already, 
there are processes involving cryptographic algorithms that produce 
very "random" sequences, but are in fact deterministic to someone who 
knows a secret.  In other words, if you don't control the generator, 
it's not possible to distinguish these two cases.  In fact, any cipher 
or hash function whose output was easily distinguishable from a true-
random source would be rejected by the cryptographic community.

Furthermore, even if the generator is good, if the machine using the 
certificates has been compromised it doesn't matter, because the 
malware can steal the secret key.  What this boils down to is that you 
either trust the endpoint or you don't.

Finally, even if it were possible for you to verify that p and q were 
"random", you *really* don't want to do that -- you *never* want to see 
users' secret keys, because that exposes the keys to danger and hence 
you to liability.

Let me make an alternative suggestion.  Pick two or three key 
generation packages -- as I recall, both Firefox and IE have such -- 
generate a lot of keys, and run them through DIEHARD.  Then warn your 
users to use only approved mechanisms for generating their certificate 
requests -- you just can't do any better.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



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



More information about the cryptography mailing list