RNG quality verification

[Philipp Gühring]

Hi,

Ok, now I did the first test.
I took OpenSSL, generated 10000 RSA keys, and took them apart.
First I analyzed the raw keys:

--------------------------------------------------
~~> ./ent RNGQA/openssl-keys-raw.random
Entropy = 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 = random).
Monte Carlo value for Pi is 3.177609302 (error 1.15 percent).
Serial correlation coefficient is -0.016663 (totally uncorrelated = 0.0).
--------------------------------------------------

Then I stripped off the first 2 bytes and the last byte:

--------------------------------------------------
~~> ./ent RNGQA/openssl-keys-stripped.random
Entropy = 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 = random).
Monte Carlo value for Pi is 3.145266667 (error 0.12 percent).
Serial correlation coefficient is 0.000327 (totally uncorrelated = 0.0).
--------------------------------------------------

It isn´t perfect random quality, but I also don´t see any big problems with 
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, 
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.  

Has anyone tested yet, how much samples are needed to detect those PRNGs?

> In fact, any cipher 
> 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 
qualified certificate request mechanism. 
But in the scenario, I am currently working on, the assumption is that we only 
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 
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 
(Firefox, IE, Opera, OpenSSL), and I also want to offer a guideline (or even 
the testing software) for the advanced users that they can test their own 
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´s exactly what I wanted to do. (Sorry if I didn´t wrote that clear enough 
yet.)

Best regards,
Philipp Gühring


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