Need Suggestions for Random Numbers

Greetings from the Galapagos islands!

I am working on a PC implementation of a one-time pad cipher, and
am trying to develop a way to produce an "acceptable" random file
to be xor'd with the plaintext.

I have seen here and elsewhere descriptions of hardware random
number generators (Geiger counters measuring random nuclear
decay, microphones picking up background hiss etc.), but I need
something that can be implemented entirely in software.

I recognize that there is probably no "perfect" software
solution, but some techniques are better that others.  (i.e.:
I want to avoid making a REALLY stupid mistake here!)

Listed below are a few ideas I have come up with, but I need some
feedback from more knowledgeable sources.    Any suggestions or
comments would be greatly appreciated.  If you reply to me
directly, I will summarize for the list.

Please don't suggest book/journal references that are not
accessible via the internet.  It would take me about 6 months to
order books from here.  (Everything I know about the
outside world arrives via my Pegasus/KA9Q mailer :-)

Also, can anyone recommend a statistical test for randomness, or
for detecting repeating patterns in a "random" file?

(I remember some years back someone demonstrated the Apple II random
number generator was flawed by converting the random numbers to
screen coordinates and "painting" the screen.  No matter how long
you ran the program, certain areas of the screen were never filled
in. In other words, certain numbers were never generated.)

Thanks in advance for any assistance.


Jim Pinson                    Galapagos Islands, Ecuador.
jpinson@fcdarwin.org.ec       PGP public key available by finger


----------Possible methods------------
(note: using the Borland C++ compiler)

- Generate a random file using Borland's random number
  generator, then run the output through an encryptor (PGP,
  DES etc.).   Possible variation: running through several
  different encryptors or multiple passes through a single
  encryptor.

- Generate two random files using different random number
  generators, then xor'ing the two files together to
  produce the final file.

- Generate a "bunch" of small random number files, reseeding the
  generator before each run.  The resulting files would then be
  concatenated to produce the final file.  (my thought here is to
  keep the random files small enough to avoid the eventual repeat
  of sequences that I understand occur in random number
  generators).

- Combinations of the above?

- Other:  Suggestions welcome.

-------------end-------------

On the subject of using audio input for generating random
numbers:  has any one tried using an audio file created by the
Windows sound recorder program?

What would be a good source of random meaningless sound? (an
quiet room, ocean surf, repeats of Gilligan's Island, old
presidential speeches (pick your favorite president). :-)

jpinson@fcdarwin.org.ec writes:

> I am working on a PC implementation of a one-time pad cipher, and
> am trying to develop a way to produce an "acceptable" random file
> to be xor'd with the plaintext.

My favorite is the fibbonachi (sp?) series.  You've probably seen this
before: The series begins with the first two numbers being ones, and
each number after if being the sum of the two preceeding numbers. 
Therefore, we have:

1,1,2,3,5,8,13,21,34,55,89,144,233...

Taking modulo 10, we get:

1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8...

Which gives a fairly random distribution of numbers from 0 to 9.  You
can take a different mod value to adjust the range of numbers produced. 
This will eventually repeat (in the mod 10 example example I believe it
will repeat after around 60 numbers - you'll never be able to get all
possible combinations, for example 0,0 is not possible) but the
distribution is fairly random.  Increasing the randomness, (and the
legnth before it will repeat) is easy.  For example if you make the
series the sum of the first two of the last five numbers you get (modulo
10 for simplicity):

1,1,1,1,1,2,2,2,2,3,4,4,4,5,7,8,8,9,2,5,6,7,1,7,1,3,8...

Although this starts off slowly, the randomness picks up, and this will
generate a series which will go for thousands of digits without
repeating.  By the way, I don't reccomend adding more than two numbers
together to get the next number in the series.  If you try adding three,
four, or more numbers together, it causes the series to increase faster,
which causes it to reach the point where it repeats sooner, plus it
complicates your software and slows down the computation.

Anyway, if after extending the series, it's still not random enough, try
this: Change your program so that after it adds the first two numbers,
it looks at the third number.  If this third number is greater, less
than, or equal to some arbritrary value, add the fourth number to the
first two and then uses that as the next digit in the series.  This will
greatly increase the random effect.  This makes an excellent cipher, as
you can generate different series based on what substitutions you make
in the series.  Of course, your ideas about randomizing further by
combining random noise files is good, just be careful when using xor,
because you could end up cancelling out the beginnings of your serieses,
(since all these series begin with 1,1, xoring them would give you
zeros.)  Of course also try changing the initial conditions of the
fibbonachi series, just be sure you don't use something that will lock
the series (such as 5,5 which will produce 5,5,0,5,5,0,5,5,0...) 
Re-encrypting the noise file is also a good idea, multiplying each byte
by three and then doing a mod 256 works well for these purposes.

> (I remember some years back someone demonstrated the Apple II
> random number generator was flawed by converting the random
> numbers to screen coordinates and "painting" the screen.  No
> matter how long you ran the program, certain areas of the screen
> were never filled in. In other words, certain numbers were never
> generated.)

Well, I've programmed on Apple II computers for years, and there were
two very common systems used for random number generation.  Applesoft
Basic simply read bytes in the ROM and used them as random numbers. 
6502 code looks pretty random when you're just looking at the numeric
opcodes and data.  The other popular thing to do was to read the video
count.  This works best when your program is interacting with a human,
because people don't always respond to prompts in exactly the same
amount of time every time, so the position the video circuitry was
scanning would be different almost every time the program was run.  This
method works best for providing a seed for a series generator like the
ones described above.  If your computer has a clock, just read the time,
and that will have the same random effect.

> From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
> 1,1,2,3,5,8,13,21,34,55,89,144,233...
> 
> Taking modulo 10, we get:
> 
> 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8...
> 
> Which gives a fairly random distribution of numbers from 0 to 9.

This is a very simple linear congruential generator:
	a_n = a_n-1 + a_n-2	mod 10
It is decidedly *not* suitable for "producing an `acceptable' random
file to be xor'd with the plaintext."  It's not a cryptographically
strong PRNG (it's not even a particularly good PRNG).  To break such
a system, try Boyar's paper, "Inferring Sequences Produced by
PRNGs", in JACM 36(1): 129-141.  I believe it takes time logarithmic
in the modulus, which is not a recipe for security.

   Eli   ebrandt@jarthur.claremont.edu

Eli Brandt <ebrandt@jarthur.Claremont.EDU> writes:

> This is a very simple linear congruential generator:
> 	a_n = a_n-1 + a_n-2	mod 10
> It is decidedly *not* suitable for "producing an `acceptable' random
> file to be xor'd with the plaintext."  It's not a cryptographically
> strong PRNG (it's not even a particularly good PRNG).

The pseudo-random number generator:

     a_n = a_n-1 + a_n-2   mod 10

is easy to break.  One could guess the pattern from only a few numbers
of the series.  My point is that that series can be used as a basis for
better PRNGs.  I suggested using something like:

     if a_n-2 < 195  then  a_n = a_n-4 + a_n-3   mod 256
     if a_n-2 > 194  then  a_n = a_n-4 + a_n-3 + a_n-1   mod 256

This is considerably less easy to break.  Even if one could surmise that
the (n-1) term was being added in sometimes and not others, you'd still
have to examine a large section of the series to figure out exactly what
method was being used to determine when the extra term was being
inserted (you'd have to see an example where a_n-2=194 and note that the
term was not included, and you'd have to see the situation a_n-2=195 and
note that it was included.  Plus, double-encryption could be used to
increase the security.

What PRNGs would you suggest using?

> From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
>      if a_n-2 < 195  then  a_n = a_n-4 + a_n-3   mod 256
>      if a_n-2 > 194  then  a_n = a_n-4 + a_n-3 + a_n-1   mod 256
> 
> This is considerably less easy to break.

True.  However, there are some fairly general attacks on
congruential PRNGs, and I wouldn't be willing to place much of a
prize on the unbreakability of schemes such as the above.  There
are simple techniques whose security is better tested.

> What PRNGs would you suggest using?

I'm hardly the person to ask, but here's a simple one:
  Given a cryptohash function hash(), and a key K,
  generate your series S as S_i = hash(K+i).
There are plenty of other games you can play with a secure hash
function.  They have a practical advantage over PRNGs built on
top of ciphers: there's no problem exporting them.  There are
also "pure" cryptographically-strong RNGs, but I don't know
anything about them.  (The name "Blum-Blum-Shub" springs to
mind, but how could it not?)

   Eli   ebrandt@jarthur.claremont.edu

Matthew J Ghio says:
> What PRNGs would you suggest using?

Don't use PRNGs for one time pads. To quote Don Knuth, anyone using
software methods to generate random numbers "is living in a state of
sin."

One time pads require REAL random numbers. If you are willing to, say,
use DES to generate your random numbers, you might as well encrypt
with DES instead of pretending that you have random numbers.

If you want a one time pad, do the logical thing -- go out and buy or
build a hardware random number generator. Don't pretend that if you
only make things "complicated enough" your numbers will be effectively
random, because they won't. See Knuth's huge section on random numbers
in "The Art of Computer Programming" for a demonstration of how a
really obscenely complex algorithm can yield bad numbers.

Perry