[19394] in cryptography@c2.net mail archive
Re: RNG quality verification
daemon@ATHENA.MIT.EDU (Steven M. Bellovin)
Fri Dec 23 13:40:39 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Steven M. Bellovin" <smb@cs.columbia.edu>
To: Philipp =?utf-8?q?G=C3=BChring?= <pg@futureware.at>
Cc: Peter Gutmann <pgut001@cs.auckland.ac.nz>,
cryptography@metzdowd.com
In-Reply-To: (Your message of "Fri, 23 Dec 2005 16:09:15 +0100.")
<200512231609.17767.pg@futureware.at>
Date: Fri, 23 Dec 2005 12:15:24 -0500
In message <200512231609.17767.pg@futureware.at>, Philipp =3D?utf-8?q?G=3D=
C3=3DBChrin
g?=3D writes:
>Hi Peter,
>
>> Easily solveable bureaucratic problems are much simpler than unsolveab=
le
>> mathematical ones.
>
>Perhaps there is some mis-understanding, but I am getting worried that t=
he =
>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=C2=B4s 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 rand=
om =
>numbers in certificate keying material really mathematically unsolveable=
?
>
(I am not a RSA specialist yet, I tried to stay away from the bit-wise de=
tails =
>and the mathematics, so I might be wrong)
>
>But I would really worry, if it is mathematically impossible to attestat=
e the =
>correct usage (to a certain extent, I know about the statistical limitat=
ions) =
>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@metzdowd.com
