NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/crypt/4629

Text File | 1992-11-11 | 6.2 KB | 118 lines

Newsgroups: sci.crypt
Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!malgudi.oar.net!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: Re: Disclosing a new encryption method (the other side)
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Wed, 11 Nov 1992 21:34:52 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References:  <[e-mail]>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 103

In article<[e-mail]> Dane C. Butzer
writes

< lots of stuff about keeping an encryption algorithm secret for
  patent protection reasons deleted>

>1) Run a challenge with a large amount of known plaintext and ciphertext
>(like 50K to 100K), a nice reward ($500?), but do not publish the
>encryption method.  Let this test run 3 months.  The idea here is to see if
>Rcrypt is very EASILY broken.  The expectation would be the "experts" would
>throw some of the simpler/standard (automated?) attacks at it.  They would
>spend a relatively small of time on it, like a few hours (qv. "Hey Bob,
>lets try cracking this ya-hoo's encryption method.  Shouldn't take long.
>Worth $500...")  Also offer the working object code to anybody in the US
>that wants it (provided publishing object code != publishing the source
>code/method in a legal sense - the lawyer gets some $$$ here).

>2) If . . .(no one succeeds). . .patent it.

>3) Post the encryption scheme, and re-run the challenge.  Also, make the
>actual source code available via US mail.

Nice try, but I think you under-rate the problem.  It is quite true that
newcomers can make fine contributions to cryptography, but it is not
true that the unstudied can make such contributions any more than one
can make contributions to differential calculus without study.

Certainly, a system which _can_ be beaten for a couple hours of work isn't
worth $500, but the converse, the premise that a system costing more than
$500 to beat is good enough to patent is not true,
and so the cost is much greater than $500 to decide about patenting.  It is
probably better to try and patent the thing (and see if you can get some
free "vetting" from the government via the patent office) than to try this.

Cryptography's big problem is that it _looks_ easy, but is no easier
than any other thing in mathematics.

Basically, you are describing someone without enough capital to discover if
they have a serious crypto-system.  There have been folks who have done
what you describe.  Jim Button of PC-File fame did it and I do not know
how good the system really was, because he simply published one very
small (100 byte) encrypted data base file and said "go at it" and I decided
after about an hour that there was not enough material to be worth my
trouble on those terms.  I was not mad/interested enough to buy his product
to try a fairer "break".  However, had I bought his product, I might well have
gotten somewhere; any DB encrypt package would surely have to
overcome a chosen plaintext attack.  A recent Cryptologia article
showed how devestating that attack is to secret methods tacked onto some pretty
well-known PC products.  In that example, chosen plaintext attacks
revealed the system and, after it was known, how known plaintext could
beat the systems described.  Yet, they may have survived PC-File like
challenges which are not well enough designed to tell the owner anything.
There also used to be a PC-based product with a $1,000 "challenge" cipher which
may or may not have been broken.  It eventually disappeared from the market.
The "challenge" cipher was ludicrously short and, of course, the algorithm
was not published.

The trouble is, encryption of a short file, even with a $100,000 challenge
on it, is not much of a test of the system's strength.  True, if it is
totally trivial, you will lose the money, but there are plenty of known systems
that no one would use anymore that would still likely defeat very good
cryptographers working against a totally _unknown_ (especially short)
plaintext.  But, that does not at all correspond to the test case of
real interest, where the plaintext may be known, to varying degrees.  Thus,
one could publish an arbitrary ciphertext, keep one's $100,000 and still have
a product that fails in the marketplace.  Remember, not everyone who breaks
your cipher will tell you.  They may be waiting for bigger fish to fry.

Nippon Telephone and Telegraph, a while back, published a much more
serious challenge for its Feal-8, an 8 round, DES-like system.  I have a
sneaking suspicion that any 8 round system is not quite good enough, but
I can't back it with the analysis that says so.  It may be very fine
indeed.

However, NT&T did the following things:

1.  It published the algorithm.  They obviously did enough work, in house,
  to do the patent stuff first.  I'm afraid this is a practical requirement,
  so one-man garage store inventors are at a natural disadvantage, sorry.

2.  It published a long plaintext.  At least 10,000 characters, if memory
  serves.  The plaintext was reasonably relevant to the system's strength
  and weaknesses.

3.  It published the corresponding ciphertext.

4.  It offered a credible amount of money to the first person to recover
  the key.

Whether Feal-8 is good or bad, I leave to the more talented.  However, in
terms of the challenge, NT&T had their act together.  I thought that the
challenge was pretty reasonably well constructed for the type of system they
were selling.  It was not quite a chosen plaintext attack, but resaonably close
and with a serious amount of material.  Moreover, one had ample information
to construct any attack whatever and show NT&T why the system was
vulnerable to (say) chosen plaintext and settle for glory, even though the
challenge cipher might not happen to be solveable by those same means.  Some
methods, after all, depend upon quirks which may show up infrequently, but
then reveal a lot of text given the practical reality of key reuse.

--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer