From: ichudov@algebra.com (Igor Chudov @ home)
Date: Sat, 18 Jan 1997 12:10:57 -0800 (PST)
To: blake@bcdev.com (Blake Coverett)
Subject: Re: One time pads and randomness?
In-Reply-To: <01BC0543.DBB9DCF0@bcdev.com>
Message-ID: <199701182006.OAA00886@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


By the way, did anyone try to run "all randomness tests" on a sequence
of digits of, say, decimal representation of "e"?

igor

Blake Coverett wrote:
> 
> > 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
> 



	- Igor.