[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: One time pads and randomness?



as i have writ before, the sources i have read say that 
digits of the transcendentals are THOUGHT to be uniformly
and 'randomly' distributed --- in quotes because there are
many criteria for randomness and i don't mean to imply a 
specific one.  however, this supposision is no stronger
than a conjecture.  has not been proven, AFAIK.

At 02:06 PM 1/18/97 -0600, Igor Chudov @ home wrote:
>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.
>
>