[1127] in cryptography@c2.net mail archive
Re: Better DES challenge update
daemon@ATHENA.MIT.EDU (Matt Blaze)
Sun Jun 29 19:06:28 1997
To: Eli Brandt <eli@gs160.sp.cs.cmu.edu>
cc: cryptography@c2.net
In-reply-to: Your message of "Sun, 29 Jun 1997 00:10:00 EDT."
<199706290410.VAA26082@blacklodge.c2.net>
Date: Sun, 29 Jun 1997 18:44:45 -0400
From: Matt Blaze <mab@crypto.com>
Eli Brandt wrote:
> Matt Blaze wrote:
> > 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. [...]
>
> [Clever challenge technique deleted]
>
> This is a solution to the second problem, right? From the response to
> DESCHALL's success, the first seems more pressing. The general
> response I saw was "three months and *how* many computers?". (So much
> for Sameer's nicely-spun press release.) I think people who will
> raise the second issue probably how just how small 2^56 is, and don't
> need to see a "challenge".
>
Agreed. The first problem is more serious.
> Hmm, I'll donate 1024 bits to building a low-end DES-cracking machine,
> contingent on a plausible plan. After a demonstration, the consortium
> sets a deadline at which des-is-dead.penet.fi goes online with a free
> forms-based service, first-come/first-served. Strong crypto vendors
> should fall all over themselves for ad space.
>
> Okay, so maybe I'm getting a bit ahead of myself. How much design work
> would have to be done first?
Frankly, I don't understand why someone hasn't done this already. According
to the rough estimates we came up with for the 1995 "minimum key length"
study (<ftp://research.att.com/dist/mab/keylength.txt>), based on Michael
Wiener's ASIC-based and Eric Thompson's FPGA-based designs, this should
be do-able within the budget of a small company or group of individuals.
In particular, for about $50k it should be possible to throw together an
almost off-the-shelf FPGA array that would produce DES keys at the rate of
about one per couple of months or so. An FPGA-based design, although far
less economical over the long run for this purpose than a dedicated ASIC
design, has the advantage of being easily retargetable for use on other key
search and non-key-search problems (and is also easy to build).
According to our 1995 estimates, $300k worth of FPGA-based hardware will
buy you a DES key every 19 days; improvements in FPGA price/performance cuts
the price to about $150k today. So you should be able to get one key every
80 days for about $50k. And when you get bored with key cracking, you
can use the hardware for something else.
An online service would probably want an ASIC-based design, which starts to
look attractive with at an investment around $200k or so, and could produce
over one key per minute.
Maybe someone with really high consulting rates (Perry...) would consider
financing such a machine...
-matt
