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