Random Number Generators and tests
Oleg Goldshmidt
I figured that this is a good place to ask, hope this is not
terribly off-topic.
I am interested in a *good* (see below) implementation of a random
number generator (RNG). Uniform distribution between 0 and 1 will be
sufficient. I am using a couple currently, but at this stage I am
interested in researching the quality of what is available. I am not
an expert in the particular field of random numbers, but I do know the
basics.
Here is a tentative list of requirements:
1) The RNG will be incorporated into a commercial product (possibly
more than one), so it has to be appropriately
licensed. Furthermore, it has to satisfy a number of coding
requirements, thus source code has to be available and modifiable.
Thus, I am talking about something that is copylefted under GPL or
a similar license. Alternatively, I will consider writing my own
code given an algorithm, but a source code serving as an example of
implementation would help a lot, and using it in such a way should
be permitted.
2) The code should be in (ANSI) C, or possibly (standard) Fortran
77. It must be portable.
3) The quality of the RNG must be exceptional. It has to generate as
"random" a sequence as possible, satisfying the known tests of
quality (e.g. the list of tests in Chapter III of Knuth's "The Art
Of Computer Programming" and possibly more).
4) It must be very efficient - speed is a crucial factor.
I am trying here to tap the collective experience and knowledge of the
experts in the following areas:
1) Background. Pointers to literature describing the algorithms, the
requirements, the tests will be very much appreciated. By
literature I mean books (anything better / deeper / wider than
Knuth?), papers, Web resources (e.g. I am aware of
http://random.mat.sbg.ac.at/links/ and http://lib.stat.cmu.edu/)
that are important for real understanding of the subject.
2) Pointers to libraries available under the conditions described
above. Both RNGs and to libraries of statistical tests to run on
RNGs to assess quality. I am interested in expert assessment of the
quality of the RNGs and the reliability of the tests. We intend to
run the tests ourselves, but your experiences are of great interest
and importance. Is there an RNG that you have tested and used and
can either recommend for a mission-critical application? Or
something that failed the tests? Is there a set of tests that you
found to be comprehensive and reliable, easily applicable, etc?
3) In particular, the sites I mentioned above, and, presumably, other
sites that others will (hopefully) point to, seem to contain a fair
number of links to algorithms and implementations of RNGs. I would
like to get assessments of as many of those as possible, to help me
to pick good ones.
4) Anything commercial that could be aquired with source code?
5) All the same questions regarding "pseudo-random" sequences (Sobol
sequences, Halton sequences, etc).
To re-emphasize, I am trying to stress the quality side, answers like
"man rand, man srand" (dejanews is full of those) or "look up
Numerical Recipes" are not what I am looking for. "The RNG from
Numerical Recipes passed such and such test with flying colors but
failed such and such other test" is _much_ closer to what I'd like to
read. "Here are the results of the tests I ran on Mersenne Twister:"
would be just great.
If you think that something is not appropriate for the newsgroup (e.g.
your test result, benchmarks, etc), I will be quite happy to receive
a personal email at gold...@netvision.net.il.
Thanks a lot in advance to everybody who takes the trouble to reply.
--
Oleg Goldshmidt
gold...@netvision.net.il
Bob Wheeler
Since it is a commercial product, how much is the consultant fee? You get
what you pay for.
--
Bob Wheeler --- (Reply to: bwhe...@echip.com)
ECHIP, Inc
rwh...@nr.infi.net
In <34FD0E29...@echip.com>, Bob Wheeler <bwhe...@echip.com> writes:
>Since it is a commercial product, how much is the consultant fee? You get
>what you pay for.
Publications like "Consumer Reports" are based upon the proposition that
you DON'T necessarily get what you pay for. Did you ever read any benchmarks
concerning just how many viruses "Microsoft Antivirus" could actually detect, just
before Microsoft took it off the market?
--------------------------------------------------------------
"I would predict that there are far greater mistakes waiting
to be made by someone with your obvious talent for it."
Orac to Vila. [City at the Edge of the World.]
-----------------------------------------------
R.W. Hutchinson. | rwh...@nr.infi.net
Volker W. Elling
A discussion of random number generators (maybe not in-depth) and
lots of references can be found in
Bruce Schneier, Applied Cryptography, Wiley, 2nd edition
-- Volker W. Elling (http://lemming.stud.fh-heilbronn.de/~elling)
Nick Maclaren
In article <34FF29...@cc.gatech.edu>,
Volker W. Elling <ell...@cc.gatech.edu> wrote:
>A discussion of random number generators (maybe not in-depth) and
>lots of references can be found in
> Bruce Schneier, Applied Cryptography, Wiley, 2nd edition
A word of warning to all readers: do NOT confuse cryptographic pseudo
random number generators with statistical ones. The properties that
they require are ENTIRELY different, and it is possible for one to be
near-perfect for one of the purposes and absolutely useless for the
other. And, yes, I do mean ABSOLUTELY useless.
Nick Maclaren,
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Wayne Schlitt
>
> In article <34FF29...@cc.gatech.edu>,
> Volker W. Elling <ell...@cc.gatech.edu> wrote:
> >A discussion of random number generators (maybe not in-depth) and
> >lots of references can be found in
> > Bruce Schneier, Applied Cryptography, Wiley, 2nd edition
>
> A word of warning to all readers: do NOT confuse cryptographic pseudo
> random number generators with statistical ones. The properties that
> they require are ENTIRELY different, and it is possible for one to be
> near-perfect for one of the purposes and absolutely useless for the
> other. And, yes, I do mean ABSOLUTELY useless.
Excuse my ignorance, but how can cryptographically secure pseudo
random number generators *NOT* be very good statistically? (Vice
versa isn't true, but the pointer was to a CSPRNG.)
CSPRNGs are almost always used in stream ciphers, and while it is
always nice to be able to be able to recover the exact XOR stream,
there are *many* cryptographic attacks that exploit only obscure
statistical differences from an ideal random number stream. Any sort
of bias such as "take the output of the PRNG in groups of three and
find that the points lie in a plane", or "the bottom bit tends to
toggle between zero and one", or "it can be shown that this set of
numbers can not appear in the PRNG output" would all rule out the PRNG
as a CSPRNG.
Note, that like PRNGs, there are a lot of really bad crypto systems
out there, and just because bad PRNGs have been used in bad crypto
systems doesn't mean that CSPRNGs aren't excellent PRNG.
-wayne
--
Wayne Schlitt can not assert the truth of all statements in this
article and still be consistent.
Patrick Juola
In article <x4iupp3...@backbone.midwestcs.com> Wayne Schlitt <wa...@midwestcs.com> writes:
>In <6doefa$bt0$1...@lyra.csx.cam.ac.uk> nm...@cus.cam.ac.uk (Nick Maclaren) writes:
>
>>
>> In article <34FF29...@cc.gatech.edu>,
>> Volker W. Elling <ell...@cc.gatech.edu> wrote:
>> >A discussion of random number generators (maybe not in-depth) and
>> >lots of references can be found in
>> > Bruce Schneier, Applied Cryptography, Wiley, 2nd edition
>>
>> A word of warning to all readers: do NOT confuse cryptographic pseudo
>> random number generators with statistical ones. The properties that
>> they require are ENTIRELY different, and it is possible for one to be
>> near-perfect for one of the purposes and absolutely useless for the
>> other. And, yes, I do mean ABSOLUTELY useless.
>
>Excuse my ignorance, but how can cryptographically secure pseudo
>random number generators *NOT* be very good statistically? (Vice
>versa isn't true, but the pointer was to a CSPRNG.)
>
>CSPRNGs are almost always used in stream ciphers, and while it is
>always nice to be able to be able to recover the exact XOR stream,
>there are *many* cryptographic attacks that exploit only obscure
>statistical differences from an ideal random number stream. Any sort
>of bias such as "take the output of the PRNG in groups of three and
>find that the points lie in a plane", or "the bottom bit tends to
>toggle between zero and one", or "it can be shown that this set of
>numbers can not appear in the PRNG output" would all rule out the PRNG
>as a CSPRNG.
An ideal random number stream need not be uniformly distributed.
So you might have a "biased" stream that only outputs 40% ones, but
it's a cryptographically hard problem to determine which ones those
are.
-kitten
Volker W. Elling
Patrick Juola wrote:
> An ideal random number stream need not be uniformly distributed.
>
> So you might have a "biased" stream that only outputs 40% ones, but
> it's a cryptographically hard problem to determine which ones those
> are.
Maybe, but I don't know whether 40%-generators really appear in
cryptography or are of any use. If I recall right, Schneier also
describes some tricks for getting 50-50 distributions, by XORing
subsequent bits and the like.
macck
In article <x4iupp3...@backbone.midwestcs.com>, wa...@midwestcs.com
says...
>
>In <6doefa$bt0$1...@lyra.csx.cam.ac.uk> nm...@cus.cam.ac.uk (Nick Maclaren)
writes:
>
>>
>> In article <34FF29...@cc.gatech.edu>,
>> Volker W. Elling <ell...@cc.gatech.edu> wrote:
>> >A discussion of random number generators (maybe not in-depth) and
>> >lots of references can be found in
>> > Bruce Schneier, Applied Cryptography, Wiley, 2nd edition
>>
>> A word of warning to all readers: do NOT confuse cryptographic pseudo
>> random number generators with statistical ones. The properties that
>> they require are ENTIRELY different, and it is possible for one to be
>> near-perfect for one of the purposes and absolutely useless for the
>> other. And, yes, I do mean ABSOLUTELY useless.
>
>Excuse my ignorance, but how can cryptographically secure pseudo
>random number generators *NOT* be very good statistically? (Vice
>versa isn't true, but the pointer was to a CSPRNG.)
>
If a 'strong' PRNG is not very good statistically then you have to
question its strength. After all that is what cryptography is about.
Converting non-random data to a form which has no statistical dependence
on the input, otherwise we could guess a part of the data. I guess we
agree on this.
However some Monte Carlo analysis require VERY strong statistical
properties. An example that fails under some of these is DES used to
encrypt a counter. However this is due to the 64 bit cycle length of
such a generator. DES feed with a RWC generator can have strong
statistical properties AND strong cryptographic properties.
>CSPRNGs are almost always used in stream ciphers, and while it is
>always nice to be able to be able to recover the exact XOR stream,
>there are *many* cryptographic attacks that exploit only obscure
>statistical differences from an ideal random number stream. Any sort
>of bias such as "take the output of the PRNG in groups of three and
>find that the points lie in a plane", or "the bottom bit tends to
>toggle between zero and one", or "it can be shown that this set of
>numbers can not appear in the PRNG output" would all rule out the PRNG
>as a CSPRNG.
>
I am not sure if anyone has tried an attack related to the above
mentioned counter-DES PRNG but it seems that the structure might
be somewhat weaker than normal DES used to encrypt data.
>Note, that like PRNGs, there are a lot of really bad crypto systems
>out there, and just because bad PRNGs have been used in bad crypto
>systems doesn't mean that CSPRNGs aren't excellent PRNG.
I believe there was a paper about this fact called 'Cryptographic
Pseudo-Random Numbers in Simulation' by Nick Maclaren. The counter-DES
example I gave above fails in simulation after about 10**12 uses. That
is about 2**43 samples. Simulations may uses such a large percentage
of the DES space. In fact any 64-bit generator will probably fail for
such a large percentage of its space. Therefore 64 bits of state may be
satisfactory from a CSPRNG but not for simulations. Of course at the
present time it seems that 64 bits is a bit small for modern cryptography.
>-wayne
>
>
>--
>Wayne Schlitt can not assert the truth of all statements in this
>article and still be consistent.
>
--
Mack
See the three new X8 ciphers, including the technical paper X8.TXT
and the reference implementation (feedback requested):
http://www.users.zetnet.co.uk/hopwood/crypto/scott16/x8.zip
http://www.sni.com/~mpj/crypto.htm under Encryption Libraries as X8.ZIP.
Bill Simpson
Speaking of crypto and stat random number generators....
Has anyone out there written an implementation of the Blum-Blum-Shub RNG
using a GPL'ed big number library in C (there is a GNU one)?
So far as I know, the BBS would be an example of a generator that is both
cryptographically secure and excellent statistically. Its properties are
proven--no need for empirical tests.
Thanks for any help.
Bill Simpson
Wayne Schlitt
>
> However some Monte Carlo analysis require VERY strong statistical
> properties. [ ... ]
>
> I believe there was a paper about this fact called 'Cryptographic
> Pseudo-Random Numbers in Simulation' by Nick Maclaren. The counter-DES
> example I gave above fails in simulation after about 10**12 uses. That
> is about 2**43 samples. Simulations may uses such a large percentage
> of the DES space. In fact any 64-bit generator will probably fail for
> such a large percentage of its space. Therefore 64 bits of state may be
> satisfactory from a CSPRNG but not for simulations. Of course at the
> present time it seems that 64 bits is a bit small for modern cryptography.
Using DES to encrypt a counter is *not* a cryptographically strong
pseudo random number generator (CSPRNG). It has a least one obvious
flaw: since DES *must* be 1-to-1, for i,j < 2^64, DES(i,Ek) !=
DES(j,Ek). This is the basic equivalence of using DES in Electronic
Code Book mode (EBC), which is known to be an insecure way of using
DES.
Using DES to encrypt an arbitrary number using a counter as a key
would be much better, but the key size (and therefore the cycle length)
is only 2^56.
macck
In article <Pine.OSF.3.95.980309...@io.uwinnipeg.ca>,
wsim...@uwinnipeg.ca says...
I have yet to find anything. Even that which is proven.
That did not need empirical testing. BBS generators in
general are proven to have certain properties. These
properties are not necessarily sufficient. Validation
for any particular use is a necessary evil.
Nick Maclaren
In article <3a7ce$d10b...@NEWS.LINKNET.NET>, macck <ma...@linknet.net> wrote:
>In article <Pine.OSF.3.95.980309...@io.uwinnipeg.ca>,
>wsim...@uwinnipeg.ca says...
>>
>>Speaking of crypto and stat random number generators....
>>
>>Has anyone out there written an implementation of the Blum-Blum-Shub RNG
>>using a GPL'ed big number library in C (there is a GNU one)?
>>
>>So far as I know, the BBS would be an example of a generator that is both
>>cryptographically secure and excellent statistically. Its properties are
>>proven--no need for empirical tests.
>
>That did not need empirical testing. BBS generators in
>general are proven to have certain properties. These
>properties are not necessarily sufficient. Validation
>for any particular use is a necessary evil.
Well, I agree with the last sentence :-)
However, the belief that Blum, Blub and Shub generators are in any sense
'perfect' generators is completely and utterly misguided. The first
point is that the 'proof' of their properties are based on the assumption
that a particular problem is 'hard'. The second point is that even that
assumption leads only to the result that Blum, Blub and Shub generators
are asymptotically good. And when does 'asymptotic' start?
As I read the papers, the method is best regarded as a way of 'expanding'
M bits of randomness to N bits, where N is at least M^2 and definitely
less than 2^M (actually less than 2^(M/2), on other grounds). If anyone
knows of a paper or result that refines those bounds, please tell me!