1996-10-17 - Re: Q.E.D.

Header Data

From: Steve Reid <steve@edmweb.com>
To: IPG Sales <ipgsales@cyberstation.net>
Message Hash: 2aa72c14bc2a8e2c15bd49ba5d6eaf5714a20f694b3325698f9ad0e13fa5ecb1
Message ID: <Pine.BSF.3.91.961016202322.466A-100000@bitbucket.edmweb.com>
Reply To: <Pine.BSI.3.95.961016194535.21030B-100000@citrine.cyberstation.net>
UTC Datetime: 1996-10-17 05:18:13 UTC
Raw Date: Wed, 16 Oct 1996 22:18:13 -0700 (PDT)

Raw message

From: Steve Reid <steve@edmweb.com>
Date: Wed, 16 Oct 1996 22:18:13 -0700 (PDT)
To: IPG Sales <ipgsales@cyberstation.net>
Subject: Re: Q.E.D.
In-Reply-To: <Pine.BSI.3.95.961016194535.21030B-100000@citrine.cyberstation.net>
Message-ID: <Pine.BSF.3.91.961016202322.466A-100000@bitbucket.edmweb.com>
MIME-Version: 1.0
Content-Type: text/plain


> hardware source, that is, it must be a pure random sequence
> of limitless entropy. Accordingly, they unbashfully assert
> that an OTP generated by a computer program is not possible.
> How do they know that? Does the Bible tell them so, or the
> Koran, or do they get it from the Torah? Why not cite the

No, not the Bible, or the Koran, or the Torah. Try information theory. 

> We stipulate the obvious fact that the encryptor stream
> generated by EUREKA is a PRNG stream, though we do consider
> it gross denigration to castigate it as ONLY a PRNG stream.
> It is a PRNG issue that also happens to be an extremely well
> behaved OTP sequence, with limited but ample entropy, as well.
> It meets each and every criteria rationally established for an
> OTP in all reasonable aspects. Subjected to any and all
> statistical analyses, the EUREKA PRNG stream manifests itself as
> being random, though we know, as a scientific fact, that it is
> not.

A PRNG is not a OTP.

A PRNG, like all cryptography (except the OTP) can be broken. Some
cryptography can be broken by cryptanalytic "shortcuts". _All_ ciphers can
be broken by brute force. If it is a strong cipher, there are no known
shortcuts, and the keysize is great enough that brute force is infeasable. 

A stream cipher operating in OFB mode _seems_ a lot like a one-time pad. 
With the stream cipher, you XOR the output of the PRNG with the plaintext,
which produces the ciphertext. With a OTP, it's the same, except you use a
true RNG instead of a PRNG. 

Implementation-wise, they seem almost identical, the only real difference 
being that key management with the stream cipher is a lot easier. 

Cryptanalysis-wise there is a _very_ big difference. 

> Think about that simple supposition for a moment. What do we
> mean by an OTP? We mean that an OTP is a stream of
> characters, or numbers, that cannot be derived in the
> absence of the key that was used to generate them, or
> alternately by trying all possibilities of that said key.
[snip]
> Another has suggested that if the key, and all the variables
> are hacked, then the system can be compromised. That is true,
> but again excuse me, does not that apply to any system,
> whether it be RSA, PGP, IDEA, and yes also a hardware sourced
> OTP.

No. Here we get to the difference between a OTP and a regular cipher: 

A OTP doesn't have a key, just a truely random stream.
A OTP is very difficult to use, because of the size of the random stream.
A OTP can't be broken AT ALL, not even by brute force.
A OTP is information theoritically secure.

A cipher has a key that produces a pseudo-random stream.
A cipher is not hard to use, because the key is relatively short. 
A good cipher can be broken by brute force, but the attack isn't practical. 
A good cipher is cryptographically secure.

Here's an example of a OTP...

----- From Applied Cryptography 2nd edition, pages 15-16 ----
If the message is
 ONETIMEPAD 
and the key sequence from the pad is 
 TBFRGFARFM 
then the ciphertext is
 IPKLPSFHGO
because
 O + T mod 26 = I
 N + B mod 26 = P
 E + F mod 26 = K
 etc.

Assuming an evesdropper can't get access to the one-time pad used to 
encrypt the message, this scheme is perfectly secure. A given ciphertext 
message is equally likely to correspond to any possible plaintext message 
of equal size.
Since every key sequence is equally likely (remember, the key letters are 
generated randomly), an adversary has no information with which to 
cryptanalyze the ciphertext. The key sequence could just as likely be:
 POYYAEAAZX
which would decrypt to:
 SALMONEGGS
or
 BXFGBMTMXM
which would decrypt to:
 GREENFLUID

This point bears repeating: Since every plaintext message is equally 
possible, there is no way for the cryptanalyst to determine which 
plaintext message is the correct one. A random key sequence added to a 
nonrandom plaintext message produced a completely random ciphertext 
message and no amount of computing power can challenge that.
----- End of excerpt -----

With a PRNG there are a limited number of outputs, so there might not be
any key to produce POYYAEAAZX or BXFGBMTMXM, and so by brute-force an
attacker may determine that the plaintext is not SALMONEGGS or GREENFLUID
or whatever else. With enough PRNG-encrypted ciphertext, it is possible to
rule out all but one possible plaintext. This is how a brute-force attack
works. With a OTP, brute-force won't work, because no plaintexts can be
ruled out. 

I took a quick look at the algorithm on your web page, and it is
definately a PRNG.





Thread