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