[19502] in cryptography@c2.net mail archive
Re: RNG quality verification
daemon@ATHENA.MIT.EDU (Philipp =?iso-8859-1?q?G=FChring?=)
Tue Jan 3 13:44:47 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Philipp =?iso-8859-1?q?G=FChring?= <pg@futureware.at>
To: "Steven M. Bellovin" <smb@cs.columbia.edu>,
cryptography@metzdowd.com
Date: Tue, 3 Jan 2006 18:13:24 +0100
In-Reply-To: <20051223171524.D804A3C0198@berkshire.machshav.com>
X-MDaemon-Deliver-To: cryptography@metzdowd.com
Hi,
Ok, now I did the first test.
I took OpenSSL, generated 10000 RSA keys, and took them apart.
=46irst I analyzed the raw keys:
=2D-------------------------------------------------
~~> ./ent RNGQA/openssl-keys-raw.random
Entropy =3D 7.992782 bits per byte.
Optimum compression would reduce the size
of this 2580000 byte file by 0 percent.
Chi square distribution for 2580000 samples is 38940.74, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 127.2214 (127.5 =3D random).
Monte Carlo value for Pi is 3.177609302 (error 1.15 percent).
Serial correlation coefficient is -0.016663 (totally uncorrelated =3D 0.0).
=2D-------------------------------------------------
Then I stripped off the first 2 bytes and the last byte:
=2D-------------------------------------------------
~~> ./ent RNGQA/openssl-keys-stripped.random
Entropy =3D 7.999932 bits per byte.
Optimum compression would reduce the size
of this 2520000 byte file by 0 percent.
Chi square distribution for 2520000 samples is 236.33, and randomly
would exceed this value 75.00 percent of the times.
Arithmetic mean value of data bytes is 127.4632 (127.5 =3D random).
Monte Carlo value for Pi is 3.145266667 (error 0.12 percent).
Serial correlation coefficient is 0.000327 (totally uncorrelated =3D 0.0).
=2D-------------------------------------------------
It isn=B4t perfect random quality, but I also don=B4t see any big problems =
with=20
it.
You can get the program and the extracted data here:
http://www2.futureware.at/~philipp/RNGQA-light.tar.bz2
> It's really unsolvable, in several different ways.
Perhaps I should have stated the quality demands for possible solutions:
Since I am working on a practical solution, and not a theoretical solution,=
=20
the following demands apply:
* A 99.999% solution is ok.
> 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".
Sure.
> 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. =20
Has anyone tested yet, how much samples are needed to detect those PRNGs?
> In fact, any cipher=20
> or hash function whose output was easily distinguishable from a true-
> random source would be rejected by the cryptographic community.
Yes, sure.
> 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.
Sure. To secure against compromised machines, you need Hardware Tokens with=
a=20
qualified certificate request mechanism.=20
But in the scenario, I am currently working on, the assumption is that we o=
nly=20
have a software engine, and that the machine of the user is not compromised.
But still the quality of the random number generator and the correct usage =
of=20
the random numbers for the certificate request are not known yet.
> 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.
I will not ask the users to send in their private keys for testing!
As you write below, I would like to test the standard generation packages=20
(Firefox, IE, Opera, OpenSSL), and I also want to offer a guideline (or eve=
n=20
the testing software) for the advanced users that they can test their own=20
generation package, if they really want to.
> 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.
That=B4s exactly what I wanted to do. (Sorry if I didn=B4t wrote that clear=
enough=20
yet.)
Best regards,
Philipp G=FChring
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
