From: thompson@sun425.nas.nasa.gov (Keith C. Thompson)
Subject: Re: New Encryption Method - A Challenge!
Organization: NAS, NASA Ames Research Center, Moffett Field, California
Date: Sat, 14 Nov 92 01:38:28 GMT

In article <n0e47t@ofa123.fidonet.org> Erik.Lindano@ofa123.fidonet.org writes:
>Writes jim@rand.org (Jim Gillogly):
> 
> > I was one of the people who replied directly, and I pointed out 
> > that if you want us to tell you how strong the algorithm is, you 
> > should tell us what the algorithm is.
> 
> Not a chance, at least for the time being. Posting such information 
> here would automatically make it a public-domain program, not to 
> speak of other implications. Not quite ready to do such a thing.

This is incorrect, posting it here would not make it a public domain
program.  A minor technicality, as your friend would effectively lose
the ability to control its distribution, which I assume is his primary
concern.  Posting a description of the algorithm should not be a
problem, as far as "other implications" go.

> 
> > I would be interested in the challenge -- but without seeing the 
> > algorithm, I don't know whether it's worth the trouble to try it.
> 
> What could be easier than discovering ONE SINGLE SHORT ENGLISH
> WORD in the context of hundreds of English words whose plain
> and encrypted equivalents will all be supplied to you? C'mon,
> you probably could guess it just by *looking* at the file!

Well, if we could guess it by looking at the file, that is not very
interesting.  It does not help to understand the cryptosystem, which
would be the primary interest in the first place.

And, there is one small problem.  The issue is the unicity distance of
the algorithm.  It is impossible to decrypt ciphertext that is shorter
than the unicity distance of the algorithm.  For instance, the
ciphertext DFJUG resulting from a simple substitution could be any five
letter word that had no repeated letters.  It is possible that the
surrounding context is insufficient to determine the correct decryption.
For instance, it could be a proper noun that does not appear anywhere
else in the plaintext.

> 
> I mean, if a cryptologist can't do THAT, what good is cryptology?
> Why mess around with all the DES and RSA and PGP stuff? You can't
> even decrypt ONE SINGLE SHORT WORD in the midst of hundreds?
> Gosh.

Cryptanalysis is quite ineffective in some circumstances.  This is also
precisely what we have been trying to tell you, although obviously we
have not succeeded in that endeavor.  However, the reason to "mess"
around with DES, RSA and PGP is obvious.  These algorithms have been
disclosed, subjected to a large amount of analysis, and found to be
relatively secure.  Ie., it would take the resources of a government
agency to be a serious threat to the security of those particular
algorithms, given the current technology.  People are still working on
analysing them, as technology may very well change their suitability or
the size of keys required for relative security.

> 
> > So -- if you want us to tell you how strong your algorithm 
> > is, tell us what your algorithm is.
> 
> Then let's say that I no longer want you to tell me how strong it 
> is, or how weak. I just would like to know whether you can pass a 
> childishly simple test. (That's really not what I had in mind when
> I posted the original challenge, but the conversation here seems to 
> be boiling down to such simplistic approach...)
> 

There is no way to know if anybody could do it.  This is what we have
been trying to tell you, although ineffectively.  The real question, is
can you and your friend make a suitable challenge such that people are
willing to take you up on it.  After all, you are essentially asking
others to expend a potentially large amount of effort for little or no
reward.  Think of it as a challenge...

- Keith
Newsgroups: sci.crypt