```Path: cactus.org!milano!cs.utexas.edu!wupost!think.com!rpi!utcsri!eecg.
+     toronto.edu!colin
Newsgroups: sci.crypt
From: colin@eecg.toronto.edu (Colin Plumb)

Subject: Re: IBM-PC random generator, source included
Message-ID: <1992Jun26.075116.20752@jarvis.csri.toronto.edu>
Organization: University of Toronto
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+           <1992Jun24.164407.28468@cl.cam.ac.uk> <1992Jun25.071702.
+           8945@cactus.org>
Date: 26 Jun 92 11:51:17 GMT
Lines: 62

In article <1992Jun25.071702.8945@cactus.org> ritter@cactus.org (Terry Ritter) w rites:
> It should be obvious that if we have a well-designed 32-bit
> RNG and use it to produce "a few hundred thousand" consecutive
> 32-bit internal state results, there will be no duplicates at
> all.  A normal statistical RNG steps through (almost) its entire
> state without repetition.  But we may not agree that we have

Unfortunately, it's false.  You can expect a collision at around
the 64K mark.  Here's the proof: given n random numbers x_1..x_n
in some range 0..N-1, there are no duplicates if and only if each
of the n(n+1)/2 pairs is distinct.  Thus, it is equivalent to generating
n(n+1) random numbers and checking that each even-odd pair is distinct.
If n = 2^16, n(n+1) is just over 2^32, and if N is 2^32, the expected
number of duplicates is just over 1.

You can turn it around and say that if you want any duplicates, the
number of samples you need is proportional to the square root of the
number of possible values.  This is called the "birthday attack" on
authentication schemes.  Let's say that we are doing a secure coin-toss
protocol.  I pick heads or tails, add a lot of random junk to that
1 bit, push it through a one-way function, and send the result to
you.  You then, say, send me a guess as to which way the toss went, and
I reveal the result, by revealing the input to the function.

If the function is one-to-one, then it's theoretically possible for you
to figure out what the value I sent you was, and make that guess,
defeating the protocol.  If it's many-to-one, then you can't figure it
out, bu it's theoretically possible that I know two inputs, one heads
and one tails, which give the same output, so I can lie to you,
defeating the protocol.  There is no perfectly secure solution, but let
us assume we are using the second one.

Now, if I send b bits of signature to you, you think it would take
me on the order of 2^b work to find a heads input that will produce
the same output as a tails input.  If you have a fixed tals input,
that is true, but if you're allowed to generate lots of heads inputs
and lots of tail inputs and use any match, it takes 2^(b/2+1) work,
on average, to generate 2^(b/2) of each type of input and search for
a match among the outputs.

This is known as the "birthday attack" on authentication protocols and
it is why 64 bits is an absolute minimum size on authenticators where
being able to send almost any false message would be bad.
(If you're in a bank network, you need a message that includes an
account number you control, so finding any message won't do.)

> Let's do this, and compare the results.  Now, from "a few hundred
> thousand samples," can we distinguish between, say, 16, 24, 32
> or 40 bits (or more) of internal state in different RNG's?

Let's say 2^18 samples.  If the generator has fewer than 36 bits
of internal state, we can expect a few collisions, assuming infinitely
large output values.  (I.e. no collisions due to the limited range of the
outputs.)  The assertion was that the RNG given has significantly
less than 32 bits of internal state.  If so, we'd expect, from
2^18 samples, 2^4 = 16 collisions due to the 32-bit size of the output
and approximately 2^(36-n) collisions due to there only being n bits
of internal state.  If there are, say, 28 bits of internal state,
we expect 256.  The difference between 16 and 256 is quite detectable.
--
-Colin
```