From: "Perry E. Metzger" <perry@piermont.com>
Date: Wed, 16 Oct 1996 19:40:25 -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: <199610170240.WAA01645@jekyll.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



[I'm not on cypherpunks, so I won't see replies sent only to there. I
have bcc'ed coderpunks to prevent replies from being sent there accidently.]

IPG Sales writes:
>          Some of you have sardonically written to say "Nihil Est
>          Demonstrandum," N.E.D. because an OTP must be derived from a
>          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
>          source of their certainty instead of advancing an unsupported
>          proposition.

See Claude Shannon's papers on information theory. [Available as: C.E.
Shannon, Collected Papers: Claude Elmwood Shannon, N.J.A. Sloane and
A.D. Wyner, eds., New York: IEEE Press, 1993.]

Shannon invented information theory in 1948 and 1949. Part of his
papers discuss the information theory of cryptosystems. He
mathematically proved that only a O.T.P. using non-reused physically
random numbers could provide what he termed "perfect secrecy".  I
accept mathematical proofs above the Koran or the Bible. (The Torah is
a subset of the Bible.)

>          I do not mean to be rude,

You are anyway.

>          but excuse me, what
>          scientific proof can they offer for that immovable avowal?

See above.

>          There is no scientific proof whatsoever, none at all,

See above.

>          except
>          for the words and their steadfast, and maybe self serving,
>          postulate.

See avove.

>          Accordingly, obviously it is they, not us, who are
>          the ones that have "Nihil Est Demonstrandum," in this matter.

See above.

>          There is not one scintilla of sustainable evidence to support
>          such a doctrine.

See above.

>          While the vast majority of people knowledgeable about
>          cryptography have not heretofore believed that it is possible
>          for software to produce an OTP,

It is not possible.

The information content, or entropy, of the key stream is necessarily
no larger than its keyspace. That is, if you have a software
pseudo-random number generator using an N bit seed, the entropy of the
keyspace is necessarily never greater than N. This is mathematically
certain -- no amount of prayer on your part can change that.

>          that does not make it a
>          scientific fact,

Sorry, its even better -- a MATHEMATICAL fact.

>          In support of their position, some have pointed out that John
>          von Neumann, to paraphrase, stated that ARITHMETIC cannot
>          produce random numbers,

von Neumann meant any deterministic algorithm, actually.

>          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.

If it is a PRNG, you do not have a One Time Pad, period. What you have
is a stream cipher.

Furthermore, past examination has shown you have a POOR stream cipher.

>          It is a PRNG issue that also happens to be an extremely well
>          behaved OTP sequence, with limited but ample entropy, as well.

If the entropy is limited, you do not have a One Time Pad, period, end
of discussion, its over.

>          It meets each and every criteria rationally established for an
>          OTP in all reasonable aspects.

Set by WHOM? By you? Your criteria bear no resemblance to those
accepted in general. Are you one of those people who sells someone a
loaf of bread and says "this is an automobile, by every criterion I
have set for automobiles"?

>          Think about that simple supposition for a moment. What do we
>          mean by an OTP?

Something different from what everyone else means, so it makes no
difference. 

>          Not only that, but you can prove it to yourself, Q.E.D.  We
>          maintain that it is discernible to any knowledgeable person
>          who probes the algorithm, that the only analytical tack that
>          can be mounted against EUREKA is brute force and that is
>          patently impossible.. One of your Cpunk colleagues says he
>          uses Triple DES, 168 bits, and he does not believe that it
>          can be brute forced - I agree, 3-DES, 10^50+ possibilities,
>          cannot be brute forced now, or in the foreseeable future -
>          then what about the EUREKA's 10^34322 possibilities,
>          10^34271+ greater than 3-DES? No way, not now, not ever.
>          Furthermore, EUREKA is an order, or more, magnitude faster
>          than triple DES, easier to use, much more secure, etal.

I believe that we have already established that your cipher is easy to
crack, so your claims that it is hard to crack really don't matter.

Perry