RE: Brute Force DES
why not put together (a LOT of) disk space and we can build a table (read: "a cryptanalytic time-memory tradeoff") for cracking DES? Using the table, we could brute-search the DES keyspace in less time than it would take to do an exhaustive search of a 38 bit keyspace, according to the paper. 4 gigs is what, a couple of hundred nowadays? Making DES equivalent to a 40-bit crack would take approx. 500Gig, but publishing the table would push DES out usefulness. Certainly we could scale back (make DES equivalent to a 45-bit crack?) if we don't have enough disk... mattt
---------- From: Peter Trei[SMTP:trei@process.com] Sent: Monday, July 22, 1996 9:55 AM To: frissell@panix.com; cypherpunks@toad.com; trei@process.com Subject: 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.
On Tue, 23 Jul 1996, Matt Thomlinson wrote:
why not put together (a LOT of) disk space and we can build a table (read: "a cryptanalytic time-memory tradeoff") for cracking DES? Using the table, we could brute-search the DES keyspace in less time than it would take to do an exhaustive search of a 38 bit keyspace, according to the paper. 4 gigs is what, a couple of hundred nowadays?
Making DES equivalent to a 40-bit crack would take approx. 500Gig, but publishing the table would push DES out usefulness. Certainly we could scale back (make DES equivalent to a 45-bit crack?) if we don't have enough disk...
IMHO it's more expensive to go this route than to build a machine with dedicate DES cracking chips. 2^40 = 1,099,511,627,776 or about 1 terabyte worth of space, not 500G. 2^39 would be 500Gb. A 4Gb drive these days is $800, hardly a couple of hundred dollars. :) Even so, that's a ton of hard drives. Further you need machines to hook these drives up to. Infact, you need a farm of machines. Why? You can only put 7 on a chain, and maybe if you're lucky four chains in a machine using four controllers. A better idea might be to make small cheap computers, say based on 8086's or 68000's that replace the drive's controller card, or if that drive controller card is intelligent enough to be a CPU or contain one, burn EEPROMs. Have the EEPROMs be able to generate DES (or any other cypher's) keyspace given a range, and then have them able to search the whole drive for a match. Even so, if you build these drive boxes, all you've accomplished is to create a nice huge big searchable array. You still will need some sort of logic to figgure out when it finds the right key, and you still can't do 3DES or recusively encrypted files, nor know when you've found the key for data you can't recognize - or rather have these drives recognize. However: Reading a 4Gb drive end to end takes less than 2 hours. I know this because I have a RAID array of them, and it takes 2 hours to rebuild, so since rebuilding an array requires reading from two drives and writing to one drive, reading a whole 4Gb drive at full speed would be something like maybe 1 to 1.5 hours(???) You might be better off with 9.0Gb drives if you can afford them because you then have less controller logic cards to build. The drives alone will cost $204,800. $800*(2^40/(4*1024*1024*1024)). You could get a nice big discount if you buy that many, but this will also mean however much it will cost you to build the cpu cards for multiplied by 256 drives, plust the R&D cost, plus the network connection between all the CPU boards. At that point you also run into the MTBF of the drives which means that your drives will fail quite often. If you want to go dirt cheap on the CPU's while using this huge space method, you could just buy something like 37 Mac IIsi's, hook each up to 7 of the drives (you'll have to partition the drives as they won't support volumes that huge.) and network the machines using localtalk. You won't need a faster connection because all you need for networking is keyspace distribution and success reporting. But then IIsi's are sloooow machines and your searches will suffer a hit from the lack of the machine's speed, plus all the overhead of having an operating system and using the SCSI chain to talk to the drives. IIsi's go for $350-$500 nicely loaded... $14800 for 37 at $400 a pop, add the drives to that, plus the cost of writing the program and hooking all of this crap together and that'll be $219,600. Ya got that kinda dough to spare? ========================================================================== + ^ + | Ray Arachelian |FL| KAOS KERAUNOS KYBERNETOS |==/|\== \|/ |sunder@dorsai.org|UL|__Nothing_is_true,_all_is_permitted!_|=/\|/\= <--+-->| --------------- |CG|What part of 'Congress shall make no |=\/|\/= /|\ | Just Say "No" to|KA|law abridging the freedom of speech' |==\|/== + v + | Janet Reno & GAK|AK| do you not understand? |======= ===================http://www.dorsai.org/~sunder/========================= Key Escrow Laws are the mating calls of those who'd abuse your privacy!
participants (2)
-
Matt Thomlinson -
Ray Arachelian