[1065] in cryptography@c2.net mail archive
A better DES challenge
daemon@ATHENA.MIT.EDU (Matt Blaze)
Mon Jun 23 18:56:19 1997
To: cryptography@c2.net
Date: Mon, 23 Jun 1997 16:03:49 -0400
From: Matt Blaze <mab@research.att.com>
I'm not a big fan of cipher ``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.
A more basic problem with challenges is that even when they are solved
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 56 bits (seven (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 ($7) 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
