Re: Internet Privacy Guaranteed ad (POTP Jr.)

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 - 

We can prove that to your or anyone eleses satisfaction - 
It obviously fails to do that somewhat short of infinity, but not short of 
what is  needed to prove system integrity for practical limits. If all 
the paricles in the Universe, 10 to the 80th, were Cray T3Es, and they 
had been calculating since the big bang, according to my rough 
calculations, it would still take over 10 to the 370th power years to 
just generate the message possibilities -for a 10 to the 500th power 
message length possibilities - we assert that if it can do that, and it 
can, it functions like a OTP of that length - and is unbreakable 

We also have a light, but only a slight disagreement, about whether the 
the key is truly symmetrical - we assert that because of the aprticlaur 
data feedback system employed it is not symmetrical, but that is entirely 
beside the point, we believe 10 to the 500th, or whatever should be 
sufficient 

Appreciatively, 

Ralph

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

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "IPG" == IPG Sales <ipgsales@cyberstation.net> writes:

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

First, what you describe is commonly called a keyed RNG. Such a system
is provably less secure than an OTP, because the number of possible
plaintexts from any given ciphertext is limited by the number of
possible keys. This makes an exhaustive search of all keys possible,
because it is very unlikely that a given ciphertext decrypts to
multiple plaintexts that make sense. In contrast, with a OTP there are
as many keys as there are possible plaintexts, so any given plaintext
can be reached, making it impossible to recognize the correct
plaintext. Of course, searching the whole keyspace might be impossible
if the number of possible keys is large enough.

But there are other ways of attacking a croyptosystem besides trying
all possible keys. Your cryptosystem seems to be based on what is
called a linear congruential generator in combination whith an
RC4-like 8*8 S-box, although somewhat simpler.

I don't want to make any claim about the security of the algorithm,
but linear congruential generators can't be considered secure for any
cryptographic use. Your only chance is that the security of that
algorithm does not depend on the generator, but I doubt that.

For further reference, go out and buy "Applied Cryptography" by Bruce
Schneier.

The pseodo-code snipped describing your algorithm, for other people's
reference:

    IPG> Bi=(Bi+Ci MOD Di) Mod 256              Large prime numbers
    IPG> ENCRYPTEXTi=OTP[Bi] XOR PLAINTEXTi     Encryption
    IPG> OTP[Bi]=ENCRYPTEXTi                    Makes the OTP Dynamic

Andreas

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface

iQCVAgUBMSu6OEyjTSyISdw9AQGKIQP+MqE5Scq99kGfLT8CdN3h9abJZNhj9qzm
rUFGsnXfdAvyRzfLz6v8FsfLHgnkgu10MG++NABFBz0I+U0iGFi8Zivkd3Ae9/6J
qOHqbGjiS4r3QN8IOLDwAW6eO6pF4Z0A/+FqLVR+zB+OZF/7TzUmgWpa8+cLWQkH
Hndr5tAVekw=
=bY+f
-----END PGP SIGNATURE-----

Perry E. Metzger writes:
 > 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.

...and note that IPG does us the favor of ensuring the keys conform to
this elaborate battery of statistical tests.  Thus, there are bunches
of keys that "aren't random enough" and thus not among the set to be
considered when trying to break one.

______c_____________________________________________________________________
Mike M Nally * Tiv^H^H^H IBM * Austin TX    * I want more, I want more,
       m5@tivoli.com * m101@io.com          * I want more, I want more ...
      <URL:http://www.io.com/~m101>         *_______________________________

> ...and note that IPG does us the favor of ensuring the keys conform to
> this elaborate battery of statistical tests.  Thus, there are bunches
> of keys that "aren't random enough" and thus not among the set to be
> considered when trying to break one.

I wouldn't fault them on that.  For example, let's say they have a
sample of 1000 bits.  They count the number of 1 bits, and discard
any samples that have less than 450 or more than 550.

They have thrown away a number of bits of entropy here.  Somewhere
between 10 and 100 at a guess -- my combinatorics is nonexistant.
So what?  There are plenty of bits there still.  If they really
are using 5600 bit keys, they can afford to lose some and still be
invulnerable to brute-force attacks.

What they have gained is the knowledge that their random number source
isn't broken.  If your RNG started spewing 0 bits by the thousand would
you say "This stream is just as likely as any other stream that I can
imagine so there is no problem", or "My RNG is broken".  Of course,
in nice mathematical abstractions your RNG never breaks, but we live in
a nasty world of thermal failiures and cold solder joints.

On Thu, 22 Feb 1996 11:08:37 -0500, SINCLAIR DOUGLAS N
<sinclai@ecf.toronto.edu> wrote:

> What they have gained is the knowledge that their random number source
> isn't broken.  If your RNG started spewing 0 bits by the thousand would
> you say "This stream is just as likely as any other stream that I can
> imagine so there is no problem", or "My RNG is broken".  Of course,
> in nice mathematical abstractions your RNG never breaks, but we live in
> a nasty world of thermal failiures and cold solder joints.

No, they really haven't.  Their initial post indicated that they are
throwing away some 50% of their generated sets of "random" data.  This
indicates either their random number generator is seriously broken, or
their analysis of the numbers produced is seriously broken.  Either
way, they have a significant problem which they are NOT addressing.


In any truly random data stream, you would expect a certain percentage
of blocks to have statistics outside whatever you decide is the
"typical" range.  If their generator is producing significantly more
or less than the expected number of "atypical" blocks, it is broken.
If is producing about the expected number of such blocks, it is likely
working as designed, and such blocks are still TRULY random.

In any case, throwing away some selected portion of its output is NOT
an appropriate cure for a broken random number generator.

The proper cure is fixing the generator.


As a separate issue, if your cryptosystem has a set of "weak keys" it
may make sense to screen your random numbers to prevent use of such
weak keys.  This, however, appears not to be what IPG is doing.