Better DES challenge update

[Matt Blaze <mab@crypto.com>]

------- Blind-Carbon-Copy

To: challenge@crypto.com
Subject: Better DES challenge update
Date: Fri, 27 Jun 1997 18:01:53 -0400
From: Matt Blaze <mab@tpc.crypto.com>

The prize for solving the ``better DES challenge'' has grown to almost
$500 and continues to rise daily.  Here's the list of prize pledges I have
as of June 27; the current pot stands at 3984 bits (US $498.00).  I hope
to have a web page up sometime next week (on www.crypto.com) with the
latest challenge status.  (This will be the last update via email, unless
someone solves the challenge or pledges some huge prize or some such).

DATE	Name			Email				Bits Pledged
============================================================================
6/22/97	Matt Blaze		mab@crypto.com			56 bits
6/23	AT&T Labs (via mab)	mab@research.att.com		56
6/24	Steve Gibbons		steve@wyrm.AZTech.Net		56
6/24	Bill Stewart		stewarts@ix.netcom.com		112
6/24	Peter Trei		trei@process.com		288
6/24	Jim Thompson		jim@hosaka.SmallWorks.COM	512
6/25	Adam Shostack		adam@homeport.org		512
6/25	Eric Blossom		eb@comsec.com			1024
6/26	Jamie Lawrence		jal@acm.org			56
6/26	Bill Frantz 		frantz@netcom.com		512
6/27	Jon Leonard		jleonard@divcom.umop-ap.com	800
								=========
GRAND TOTAL (Bits)						3984
GRAND TOTAL (USD)						$498.00

Tell your friends!  Note that the pot seems to be growing roughly
exponentially.  If this keeps up, I may join the search myself...

[Unfortunately, due to singularly inexcusable incompetence on the part
of my soon-to-be-former ISP (PSINet), mail to me was bouncing last week
so I may have missed some of the ``Better DES Challenge'' pledge mail.
If you pledged a prize and aren't on the list above, please resend.]

Official rules attached below for reference.

- -matt

N.B.  The ``bit'' is an archaic unit of currency equal to 1/8 of a US
dollar (hence, ``pieces of eight,'' ``two bits,'', etc.).  It seems an
appropriate measure for prizes in key-cracking contests.

============================

From: Matt Blaze <mab@research.att.com>
Subject: A better DES challenge
Date: Mon, 23 Jun 1997 16:04:25 -0400

I'm not a big fan of these ``challenges'' in which a prize is awarded
to the first person who discovers the key that produces some
plaintext/ciphertext pair.  The effort required to produce a solution
tends to grossly overstate the actual difficulty of searching the
keyspace, since invariably the winner uses the idle time on
general-purpose computers, which are poorly-optimized for use as
keysearch engines.

Another problem with challenges is that even when they are broken
they don't really provide convincing proof that the keyspace was
actually searched.  For example, in the recent 56-bit RSA DES
challenge, RSA has no way to prove that it didn't ``leak'' some hint
about the solution to the winner. (I hasten to point out that I'm not
suggesting that anything like this actually happened, only that a
skeptic might raise the possibility, against which RSA has no real way
to defend itself).  A better challenge, then, would be one in which
even the challenger doesn't know the solution in advance (or would
have had to itself search the keyspace or otherwise cryptanalyze the
cipher in order to find it).  For example, a challenge for a one-way
collision-intractable hash function could simply ask for an example of
a collision, or could ask for the inversion of some well-structured
output (such as all zeros).

We can do the same thing for encryption functions.  I propose an
alternative DES challenge that can be solved only by searching a large
fraction of the keyspace or by cryptanalyzing the cipher.  The
structure of the challenge is such that most people would agree that
either I don't know the solution myself or that I've already searched
the keyspace or otherwise cryptanalyzed DES in some way.  In other
words, the only way I could covertly ``help'' the challenge winner is
if I've already done what the challenge is supposed to establish is
possible in the first place.

Recall that there are 2^56 DES keys that each select a different
permutation of the 2^64 codebook entries.  We expect that there's
about a 1/2^8 chance that there exists a DES key that converts any
given plaintext block to any given ciphertext block.

My challenge is to find a key such that a ciphertext block of the form
<XXXXXXXX> decrypts to a plaintext block of the form <YYYYYYYY>, where
X and Y represent any fixed eight-bit byte value repeated across each
of the eight bytes of the block.

Observe that I'm actually posing 2^16 different challenge
plaintext/ciphertext pairs, each with about 1/2^8 probability of
having a solution, where groups of 2^8 challenges can be searched for
simultaneously.  Each challenge may have no solution key, exactly one
solution key, or more than one solution key, but it is very likely
that there is at least one solution key to at least one of them (in
fact, one could expect to find about 2^8 solutions overall, assuming
DES produces good pseudorandom permutations).

The most obvious way to find a solution is try, for each
properly-formed ciphertext block, every key in the DES keyspace until
a plaintext block of the proper form is found.  Special-purpose
hardware, based on FPGAs or ASICs, would obviously be helpful for this
purpose.  (One might first consider the eight weak / semi-weak DES
keys that have 2^32 fixed points, on the chance that one of the blocks
of this form is a fixed point for one of them.  Unfortunately however,
none are.)

I will award a grand prize of fifty six bits ($7 US dollars) to the first
person to provide a solution key.  (The challenge ends when first key
is found).  While the prize money is admittedly trivial (this is out
of my own pocket, after all), I hope it will serve as ``seed money''
that encourages others to add their own prizes to a growing pot.

Of course, I cannot be completely sure whether there exist any
solutions at all.  In the (unlikely) event that there is no winner by
August 1, 1999, I will award the 56 bit prize to the person who submits
the key that produces the most ``interesting'' plaintext block from
the all-zero ciphertext block.  I will be the final judge of what
constitutes interesting.  This prize will be announced at the rump
session of CRYPTO'99.

Void where prohibited by law, etc.  Comments, questions and solutions
should be submitted by email, to <challenge@crypto.com>.  If others wish
to pledge additional prizes, please also let me know at that address
and I'll keep track of who is offering what, etc..

- -matt

------- End of Blind-Carbon-Copy