Proving the randomness of a random number generator?

leichter_jerrold at emc.com leichter_jerrold at emc.com
Fri Dec 2 15:03:20 EST 2005


| Hi,
| Apologies if this has been asked before.
| 
| The company I work for has been asked to prove the randomness of a random
| number generator. I assume they mean an PRNG, but knowing my employer it
| could be anything.. I've turned the work down on the basis of having
another
| gig that week. However, it raised the issue of just how this could be
| achieved. As far as I'm aware there are no strong mathematicians in the
| team, so it will get thrown out to the first available person (cool idea,
| eh?). There will most likely be very little time allocated to do it.
| 
| So, the question is, how can the randomness of a PRNG be proved within 
| reasonable limits of time, processing availability and skill?
It can't be *proved*, for any significant sense of that word, regardless of 
the availability of resources.  At best, you can - if you are lucky - prove 
*non-randomness*.  In practice, one makes attempts to prove non-randomness 
and, if "enough" of those fail - "enough" being determined by available 
resources - one just asserts randomness.

There are basically two kinds of tests one can do:

	- Various kinds of statistical tests.  These look at things like
		average numbers of 0's and 1's (assume a series of random
		bits), correlations between successive bits, and so on.
		There are a number of test suites out there, the best known
		of which is probably the Diehard suite.  (I don't have a
		link, but you should have no trouble finding it.)

	  Testing like this looks for "statistical randomness":  That is,
		the "random number generator" produces outputs that have the
		same statistical properties as random numbers.  They say
		*nothing* about predictability by someone who knows how the
		numbers have been generated.  For example, any good PRNG
		will pass most or all of these tests, but if you know the
		starting key, you can predict the outputs exactly.  So if
		your interest is *cryptographic security*, statistical
		randomness tells you little (though *lack* of it is
obviously
		a red flag).

	- Attack attempts.  This is mainly relevant for cryptographic random
		number generation, and is like cryptanalysis:  Look at the
		generator and try to "break" it, i.e., predict its output.
		The techniques and expertise needed are as varied as the
		techniques used to construct the generators.  If the
		generator uses measurements of system events, you need to
		know, at a deep level, what causes those system events,
		how an attacker might observe them, and how an attacker
might
		influence them.  If the generator is based on some
electronic
		circuit, e.g., a noise diode, you need to understand the
		physics and electronics.  In almost all cases, you need to
		understand how one attacks electronics, at various levels of
		abstraction.

	   A thorough analysis like this is likely to be very expensive, and
		is prone to miss things - it's just the nature of the beast.

							-- Jerry

		

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



More information about the cryptography mailing list