Re: A better DES challenge

[Mike Duvos <enoch@zipcon.net>]

Matt Blaze <mab@research.att.com> writes:

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

Really.  It appears that the DESCHALL frivolities actually
enhanced the reputation of DES, fluffy press releases by C2 and
Security Dynamics notwithstanding.

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

This is a problem which I have been pondering in recent days. How
would someone in the future demonstrate that they have broken
DES, now that the RSA DES Challenge is behind us, and trusted
parties offering to generate and keep secret ciphertext/plaintext
pairs are no where to be found.

It would seem to me that the best way to demonstrate that one has
broken a block cipher without releasing ones algorithm would be
to generate and publish some key collisions, in which a
ciphertext/plaintext pair is mapped by more than one key.

If one encrypts plaintext with a known key to generate
ciphertext, cryptanalysis of the resulting ciphertext/plaintext
pair for a key other than the one used to generate it should be
comparable in difficulty to cryptanalysis of a
ciphertext/plaintext pair provided by a trusted third party.

The ability to generate such collisions at will clearly
demonstrates that one can calculate keys from
ciphertext/plaintext pairs.

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

A step in the right direction.  We should develop ways of
demonstrating cryptanalysis which do not require one person to
solve a problem provided by another person without the
possibility of collusion.

[snip]

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

I like this.  It is somewhat cleaner than the key collision trick
suggested above.

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

Let me know when the money reaches $10k.

 > Of course, I cannot be completely sure whether there exist
 > any solutions at all.

If there were to be no solutions at all, given the alleged
pseudorandomness of DES, this would probably be an even more
interesting result than solving the problem posed.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     enoch@zipcon.com   $    via Finger                       $