From: "Perry E. Metzger" <perry@piermont.com>
Date: Thu, 22 Feb 1996 11:02:04 +0800
To: IPG Sales <ipgsales@cyberstation.net>
Subject: Re: Internet Privacy Guaranteed ad (POTP Jr.)
In-Reply-To: <Pine.BSD/.3.91.960221145534.3814H-100000@citrine.cyberstation.net>
Message-ID: <199602212200.RAA10175@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



IPG Sales writes:
> I find less and less disagreeement with your comments - with one major 
> exception - for a given message length - say 10 to the 500th power, a 
> OTP seeded algorithm, a better term would be to call it an OTP driven 
> algorithm,  can produce the exact same effect as an OTP of that length - 
> that is, the encrypted text can be any possible message of that length, 
> and it is not possible to predict in way what the RNG generated stream
> is - 

That is manifestly untrue. Read any information theory text.

There is only so much entropy in your stream of random numbers,
period. No amount of prayer, tantric meditation, or anything else will
generate more. It is not the "exact same effect" no matter how much
you might like it to be.

What you are flogging here is a pseudo-random number generator. You
are using this to produce what is properly called a stream cipher, NOT
a one time pad. We in the crypto community have been working with this
sort of thing for years.

If you start with 100 bits of entropy, your stream will have only 100
bits of entropy. If you start with 1024 bits, you will have a kilobit
of entropy, and so forth.

This may seem like a lot, but it really isn't.  Its easy to calculate
the unicity distance of a given key. The unicity distance is most
easily explained as the amount of ciphertext after which only one
possible decoding is possible and in theory brute force will extract
the key. The unicity distance is the information content of the key
(which is the log base two of the number of possible keys, or in this
case the equivalent, the number of bits of key) divided by the
redundancy of the language in question. The rate of english text is
somewhere around 1.3 bits per letter, so the redundancy of ASCII is
somewhere around 6.7 bits. For a 1024 bit key the unicity distance
will be, at best, around 150 characters. For a 5000 bit key, the
unicity distance would be around 746 characters. That means that there
is one, and only one, probable decoding of the ciphertext stream
resulting from your system after a fairly short period of time, and
one, and only one, possible key.

Now, finding that key is hard. Done right, it can be VERY HARD.
However, it is indeed possible given enough time.  There is a big
difference between something that is hard or very hard and something
that is information theoretically impossible. Breaking a PRNG is
always possible given enough compute cycles. Breaking a one time pad
is not. That is the difference.

Your phrase "can produce the exact same results as a one time pad"
are, in short, bogus. Claude Shannon proved this fourty years ago.

Perry