From: “Peter Trei” <trei@process.com>
To: trei@process.com
Message Hash: b00c2870555d4fa1417854d32f2c86b331327d542348697130b307db4b25d18e
Message ID: <199607222043.NAA06313@toad.com>
Reply To: N/A
UTC Datetime: 1996-07-23 07:56:49 UTC
Raw Date: Tue, 23 Jul 1996 15:56:49 +0800
From: "Peter Trei" <trei@process.com>
Date: Tue, 23 Jul 1996 15:56:49 +0800
To: trei@process.com
Subject: Re: Brute Force DES
Message-ID: <199607222043.NAA06313@toad.com>
MIME-Version: 1.0
Content-Type: text/plain
> Peter 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).
Duncan wrote:
> I volunteer my 120 MHZ Pentium. A lot more Pentiums are out there now than
> a year ago. That makes it more feasible. A lot more people with full net
> connections. Like most Americans, I have a flat rate net connection and a
> flat rate local phone connection so could run a cracking session permanently
> (as long as no one tells my ISP). We need a full test of the Winsock
> cracking client in any case. It wasn't working very well last time.
>
> DCF
<back-of-envelope>
In my terminology, 'hairy edge of doability" means we have a shot
at success, but I wouldn't bet the farm on it.
I thought that I might bet a couple hundred bucks, though.
Sadly, after further calculation, I'm not so sure if it's doable just yet.
What I'm looking at is a known plaintext attack on single ECB DES,
using a brute-force test to cycle through the key space. People
would get chunks of keyspace to test from a central server or
servers, and would be motivated to take part by a cash prize for
the lucky person who finds the key.
Lets do the numbers:
Single DES has the security of 56 bits of key - there are 64 bits in the
keys, but 8 of them are parity bits which add nothing to security.
2^56 = 7.205e16 keys (which is a whopping big number)
Let's guess that we can recruit the equivalent of full-time on 1000
machines.
7.205e13 keys/machine.
Let's guess that we have about a month before people start to lose
interest - so we want to be more than 1/2 done by then. Lets say
we want to sweep the whole space in 40 days.
1.8e12 keys/machine/day
~21,000,000 keys/machine/second
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).
I'm looking at ideas to speed up DES - if I'm willing to use
honking great lookup tables, the permutation steps can be done
more quickly than libdes. I'm also looking at implementing the
algolrithm in hand-optimized P5 assembler. (It's been years since
I've done a major assembler project - the P5 has some truely weird
features to be considered, but also has (some) internal 64 bit
registers to play with).
Let's guess that I can speed up a key-test up by a factor of 10. (This is
not a slur on Eric's code - it's extremely clever, but not optimized
for any particular processor, or for key-testing. Note that the keytest
described above takes about 10,000 cycles/test.)
That gets my workstation up to about 90,000 keys a second, which is
still almost a factor of 250 too slow.
I'm going ahead with my work on a faster DES keytester, but unless
optimizing gives an astounding win, I now think a distributed bruting
effort is a bit pre-mature.
What will make this brute doable, if not now, then in the near future?
1. Faster Processors - Moore's Law is still holding. A year ago, my
90 MHz Pentium was one of the faster machines taking part in the
40-bit RC4 crack. Now, it's passe.
2. More processors. The number of people on the internet continues
to grow rapidly.
3. More interest - Crypto awareness has greatly increased in the
last year, and a real cash prize (say, over $500) will generate both
publicity and interest.
These factors all multiply together. The number of cycles that could
probably be recruited is increasing at a fast rate. A major part of the
work will be a keyspace distribution mechanism which can handle
the load (this was a major stumbling block last year).
</back-of-envelope>
Peter Trei
trei@process.com
Disclaimer: This has nothing to do with my employer.
Return to July 1996
Return to “The Deviant <deviant@pooh-corner.com>”