// COMPLETE THREAD

Re: Brute-forcing DES

4 expanded posts · every known parent and child

NODE 21ed9458Re: Brute-forcing DES tcmay@got.net (Timothy C. May)Tue, 23 Jul 1996 16:49:45 +0800

At 3:06 AM 7/23/96, Steve Reid wrote:
>> Any one up for a distributed brute force attack on single DES? My
>> back-of-the-envelope calculations and guesstimates put this on the
>> hairy edge of doability (the critical factor is how many machines can
>> be recruited - a non-trivial cash prize would help).
>
>Count me in. I've got a couple of net-connected Pentiums that are mostly
>idle.
>
>Did you consider the possibility of DES chips in your back-of-the-envelope
>calculations? They are hundreds of times faster than PCs. I don't know
>where to get them or how much they cost, though. I would expect they
>wouldn't be too expensive. The cash might be better spent on DES chips
>than on a prize.

Specialized DES-cracker chips have of course been considered. Diffie and
Hellman's nearly 20-year-old paper on cracking DES considered this.
Wiener's calculation of a few years ago did more that this: he also
architected a basic system. And the "how many bits is enough?" (sorry I
don't have the official name on the tip of my tongue) panel considered such
designs last year.

But actually building a DES cracker entails a level of commitment very
difficult to achieve in an informal, volunteer effort. Not exactly
something that 10 or 20 people can work on usefully.

The advantage of the cracks done last year, the French and Australian
cracks, and the MIT cracks, were that the "entry costs" for joining the
project were low.

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Licensed Ontologist         | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

NODE 8527d4e6Re: Brute-forcing DES mpd@netcom.com (Mike Duvos)Tue, 23 Jul 1996 17:33:55 +0800

"Peter Trei" <trei@process.com> writes:

 > Sadly, after further calculation, I'm not so sure if it's
 > doable just yet.

...

 > The fastest general purpose, freely available des
 > implementation I'm aware of is libdes. by Eric Young. With
 > this, I can do a set_key in 15.8 us, and an ecb_encrypt in
 > 95 us/block. That adds up to about 9,000 keytests/sec (this
 > is on a 90 MHz P5, running NT).

What you really want to do to sweep the DES keyspace is to
"schedule" the input and output block you are testing, performing
any static operations, and do only enough computation to see that
a given key fails.  Special purpose assembler to do this
particular function would probably run faster than any algorithm
which could also be employed to encrypt data.

 > What will make this brute doable, if not now, then in the
 > near future?

 > 1. Faster Processors

 > 2. More processors.

 > 3. More interest

4. Better code.

This is actually a problem I plan to analyze someday. Looking at
single DES as a function of the key bits with the input and
output fixed.  This can be viewed as a boolean function, whose
result depends upon whether the given key works to map the input
onto the output.  Viewing this function as a composition of
single bit operations and optimizing it would perhaps lead to
insights on how best to compute it on a typical 32 bit CPU with
the usual collection of operations.

A messy little project, but probably one worth doing if I get
some free time.

Single DES is certainly ripe for a spectacular public failure.  A
little analytic work could bring breaking it within range of
available computing power.  If you are going to use regular
encryption code to brute force the keyspace, then it probably is
just a tad beyond reach at this point.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

NODE 014c202fRe: Brute-forcing DES The Deviant <deviant@pooh-corner.com>Wed, 24 Jul 1996 18:28:12 +0800

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 22 Jul 1996, Mike Duvos wrote:

> Date: Mon, 22 Jul 1996 23:33:58 -0700 (PDT)
> From: Mike Duvos <mpd@netcom.com>
> To: cypherpunks@toad.com
> Subject: Re: Brute-forcing DES
> 
> "Peter Trei" <trei@process.com> writes:
> 
>  > Sadly, after further calculation, I'm not so sure if it's
>  > doable just yet.
> 
> ....
> 
>  > The fastest general purpose, freely available des
>  > implementation I'm aware of is libdes. by Eric Young. With
>  > this, I can do a set_key in 15.8 us, and an ecb_encrypt in
>  > 95 us/block. That adds up to about 9,000 keytests/sec (this
>  > is on a 90 MHz P5, running NT).
> 
> What you really want to do to sweep the DES keyspace is to
> "schedule" the input and output block you are testing, performing
> any static operations, and do only enough computation to see that
> a given key fails.  Special purpose assembler to do this
> particular function would probably run faster than any algorithm
> which could also be employed to encrypt data.
> 
>  > What will make this brute doable, if not now, then in the
>  > near future?
> 
>  > 1. Faster Processors
> 
>  > 2. More processors.
> 
>  > 3. More interest
> 
> 4. Better code.
> 

We also need to address the question of the code itself.  Just crypting it
won't work.  We need a good way to test _to see if we have an answer_, for
a non-known plaintext attack.

 --Deviant
Whatever occurs from love is always beyond good and evil.
		-- Friedrich Nietzsche


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMfW4+DAJap8fyDMVAQECmAf+Le7kpXqvGDOSMhRdUG6qluP/RkBE9oeR
1O0pmeHPHtMU1qAgL1c9YJ3fHAdb+naLIhff1x8K2Nt4LsVYiNHY1va3ogg3P6mx
G/1N+4iOtsL49XXhO+YnJfHxd8fYAdQKftWwcQc9DOpUbvHoD/yWIS94YHHnH6Zn
Uly5cQqKtpNh20uq5gCC6GcJWj+Dm6BjaKrYuUgSwBNrnYBSQ6nui7W26zawA4vh
GHtxKWIJQ9onBYWM025YuYhzTpRy852aLZifw1xPtAXXe1TypjcRojXcTtBL0iK0
oWVbtRWwxqKlzhmOiktec75jWjduREBoMve4OCE/3G0obILS84qxhA==
=f9OL
-----END PGP SIGNATURE-----

NODE 9b47d55dRe: Brute-forcing DES Phillip <root@adam.sp.org>Fri, 26 Jul 1996 18:43:16 +0800