Re: Brute Force DES

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

I have to offer an RS/6000 (PowerPC) and a P150 working full-time and
another RS/6000 and 10-15 Pentiums working nights and weekends.

Michael

"I can contribute an 286 full time and a powerPC on evenings."

Thats just great.  Really.  Thanks so much.  With 15 machines working
nights and weekends, it should take only another 100,000 messages like
that one to get us to the point where we can crack DES in a year.

I don't want to slam people offering machines.  But there will be a
time & place to pony up for keyspace to start searching.  Now is not
that time.

Adam


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

"Peter Trei" writes:
> 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'll point out that like most DES implementations, Eric's tries to
spend a lot of time in key setup to save time later on in
encryption/decryption. This tradeoff would probably be very different
if you didn't plan on trying more than one or two blocks of decryption
after getting a key.

Perry

Perry E. Metzger said:
> 
> "Peter Trei" writes:
> > 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'll point out that like most DES implementations, Eric's tries to
> spend a lot of time in key setup to save time later on in
> encryption/decryption. This tradeoff would probably be very different
> if you didn't plan on trying more than one or two blocks of decryption
> after getting a key.
> 

For instance if you had a DES encrypted gzipped file. The first 2 bytes
plaintext will be Ox1f8b. You'd only have to try to fully decrypt 
1 out of 65535 keys.

-- 
Kevin L. Prigge                     | "I rarely saw people sitting at
Systems Software Programmer         |  computers producing real code
Internet Enterprise - OIT           |  wearing ties." - Philippe Kahn
University of Minnesota             | (speech at Software Development '90)

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

On Tue, 23 Jul 1996, Kevin L Prigge wrote:

> Date: Tue, 23 Jul 1996 11:02:06 -0500 (CDT)
> From: Kevin L Prigge <Kevin.L.Prigge-2@tc.umn.edu>
> To: perry@piermont.com
> Cc: trei@process.com, cypherpunks@toad.com
> Subject: Re: Brute Force DES
> 
> Perry E. Metzger said:
> > 
> > "Peter Trei" writes:
> > > 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'll point out that like most DES implementations, Eric's tries to
> > spend a lot of time in key setup to save time later on in
> > encryption/decryption. This tradeoff would probably be very different
> > if you didn't plan on trying more than one or two blocks of decryption
> > after getting a key.
> > 
> 
> For instance if you had a DES encrypted gzipped file. The first 2 bytes
> plaintext will be Ox1f8b. You'd only have to try to fully decrypt 
> 1 out of 65535 keys.
> 

Buy the point is to prove that DES shouldn't be used, not that it CAN
be brute forced.  A known-plaintext attack doesn't show that.  We hafta
attack something we've never seen. (i.e. talk Netscape, or some other
company, into generating a DES'd message, and keeping the keys safe)

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


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

iQEVAwUBMfXEpjAJap8fyDMVAQGKQQf/VSnWcM4CwKnAuOjASUIkXLPw6CIjhjh5
pg1MQ9+H8phzJexzMj5PyQgC5onSdjXn8CVfSHGK/iFXmUW1ZddkkSJT7g5IAto8
IiN9UY6XitFQMfP6MLgKc8ynd91qE57+NGrknrMopFiBwbh5B7j1zJ6gVWQvrlox
BkyJhveuC821Y1ziWXUBtxc+UWhZUHaUtOyUhliXKAGpHv7nOVbYhPeH3r7UzAoR
LGs/7uP/9hLGexbpS3WAFcV7yWQAkyaPg3xoGhLGrTO6XLF3dOgp9CW75lZBtuGQ
rG3Wj+G/BPIUuls2DvGCsv++SObemtj+Xvw+DLwYF806WMajWQEbpw==
=b2PJ
-----END PGP SIGNATURE-----

The Deviant writes:
> Buy the point is to prove that DES shouldn't be used, not that it CAN
> be brute forced.  A known-plaintext attack doesn't show that.  We hafta
> attack something we've never seen. (i.e. talk Netscape, or some other
> company, into generating a DES'd message, and keeping the keys safe)

Known plaintext isn't needed. You just need a plaintext with some
decent statistical properties.

Dave Wagner has some information on this.

Perry

"Perry E. Metzger" <perry@piermont.com> writes:

> 
> The Deviant writes:
> > Buy the point is to prove that DES shouldn't be used, not that it CAN
> > be brute forced.  A known-plaintext attack doesn't show that.  We hafta
> > attack something we've never seen. (i.e. talk Netscape, or some other
> > company, into generating a DES'd message, and keeping the keys safe)
> 
> Known plaintext isn't needed. You just need a plaintext with some
> decent statistical properties.

May I suggest that a better demonstration for the public would be to allow any
person take a pre-determined text (such as "cypherpunks"), encrypt it wtih a
key of their choice (40-bir or 56-bit, depending on what we're trying to prove),
(i.e. demonstrating that some 40-bit key scheme is unsafe may be sufficient )
send the cyphertext to a GruborBot via e-mail or Web page, and get back within
reasonable time the key(s) that were used.  I think this is feasible; whether
it's all lookup table or some lookup and some computation is details.

---

Dr.Dimitri Vulis KOTM
Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps

Most protocols give you stereotyped headers, which are
perfectly valid for known plaintext attacks.  The rc4 cracks were done
on the Netscape rc4(md5(key+salt) used in ssl.  They were based on
known plaintext in the HTTP headers.

	(Incidentally, we might want to test the key distribution &
reporting mechanisms on a crack of vanilla rc4-40, or another SSL
crack.  Cracking des will not be cheap, and we should do some test
runs first.)

Adam

The Deviant wrote:

| > For instance if you had a DES encrypted gzipped file. The first 2 bytes
| > plaintext will be Ox1f8b. You'd only have to try to fully decrypt

| Buy the point is to prove that DES shouldn't be used, not that it CAN
| be brute forced.  A known-plaintext attack doesn't show that.  We hafta
| attack something we've never seen. (i.e. talk Netscape, or some other
| company, into generating a DES'd message, and keeping the keys safe)


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

> 
> 
> "Peter Trei" writes:
> > 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'll point out that like most DES implementations, Eric's tries to
> spend a lot of time in key setup to save time later on in
> encryption/decryption. This tradeoff would probably be very different
> if you didn't plan on trying more than one or two blocks of decryption
> after getting a key.
> 
> Perry

90 us is several times longer than 15.


-- 
"Of all tyrannies a tyranny sincerely  exercised for the good of its victims  
 may be the most  oppressive.  It may be better to live under  robber barons  
 than  under  omnipotent  moral busybodies,  The robber baron's  cruelty may  
 sometimes sleep,  his cupidity may at some point be satiated; but those who  
 torment us for own good  will torment us  without end,  for they do so with 
 the approval of their own conscience."    -   C.S. Lewis, _God in the Dock_ 
+---------------------+--------------------+----------------------------------+
|Julian Assange RSO   | PO Box 2031 BARKER | Secret Analytic Guy Union        |
|proff@suburbia.net   | VIC 3122 AUSTRALIA | finger for PGP key hash ID =     |
|proff@gnu.ai.mit.edu | FAX +61-3-98199066 | 0619737CCC143F6DEA73E27378933690 |
+---------------------+--------------------+----------------------------------+