From: Blake Coverett <blake@bcdev.com>
Date: Sat, 18 Jan 1997 10:31:35 -0800 (PST)
To: "'Cypherpunks'" <cypherpunks@toad.com>
Subject: RE: One time pads and randomness?
Message-ID: <01BC0543.DBB9DCF0@bcdev.com>
MIME-Version: 1.0
Content-Type: text/plain


> I want to use a one time pad pased crypto system. I understand that the
> randomness of the pad genorator is key to security(other than lossing the
> keys). What I want to know is if I use a psuedo-RNG that maybe repeats its
> self every 1000 characters and use it to only encrypt messagase that are
> 100's of charaters long, will this be a major security risk? 

I'm afraid you've fallen into one of the standard traps.  A PRNG can *not*
make a OTP no matter how you use it.  

The total amount of entropy in a PRNG is the amount of entropy in the seed 
you use to key it.  All the other bits are directly derived from that seed.

A true OTP is completely secure from an information-theory point of view
because every byte has a full eight bits of entropy.  A PRNG can never
have this.

Having said all this, it is possible to make a good cipher from a PRNG.
RC4, for example, is exactly that and the variable sized key is the
seed for the PRNG.  It is however very difficult to come up with a
good algorithm for that cryptographically sound PRNG and you would
be much further ahead to use an existing one rather that trying to
roll your own.

> Say I create a 1 million character one time pad that passes all of the
> randomness tests. It is "truely random". I place it on two computers. Now
> when these two computers want to send email computer "A" grabs a chunk of the
> one time pad  starting at a random point and encrypts it. It labels the email
> with the random starting point and sends it to "B". There "B" moves to the
> random point and begins decryption. During to process both computers mark
> that section of the OTP used so that they don't retransmit with it. I realize
> this has a limited amount of messages before it is used up. But would this be
> secure? Any suggestions, complaints, big gapping holes I missed? 

I don't see anything wrong as such, but there is nothing to be gained either.
If your random data is real OTP material there is no need to skip to a random
byte within it, just start at the beginning and use it in sequence.  If your random
data is the output of a PRNG like the above then random starting point doesn't
buy you much additional security because the entire set of keying material can
be recreated from the seed.  It may increase the work-factor of searching for
the key, but it also imposes the practical problem of keeping all that keying
material secure.

More importantly don't confuse statistically random with cryptographically
random.  Just because a bunch of bits passes all the randomness test
you can think of doesn't mean it contains 100% entropy.  Consider the
digits of an irrational number like sqrt(2) or pi, the digits appear statistically
random but they can be recreated from just a tiny bit of knowledge.

A good litmus test is to ask yourself if there is any way you can
reproduce those bits.  If there is, they aren't a one time pad.
(Of course even if you can't it doesn't mean they are good. :-)

regards,
-Blake