From: Matt Thomlinson <mattt@microsoft.com>
Date: Wed, 24 Jul 1996 21:01:29 +0800
To: "'Ray Arachelian'" <sunder@dorsai.dorsai.org>
Subject: RE: Brute Force DES
Message-ID: <c=US%a=_%p=msft%l=RED-77-MSG-960723231822Z-3820@tide21.microsoft.com>
MIME-Version: 1.0
Content-Type: text/plain


well, first of all, I wasn't computing 2^40, I was computing something
like 2^(56*0.667) * 8bytes/each or somesuch, I don't recall exactly as I
don't have the paper in front of me. In any case, it was the tradeoff
between time and space -- 2^40 in time was something like 2^38th in
space. But don't trust my numbers, get the paper and rattle them off
yourself. 

It just seems like if we're going to browse all of the way through the
DES keyspace, we _ought_ to take notes along the way -- that means
building a table. I don't care how big the table is; if it is only 2^30
entries (about 1G entries, each 8 bytes = 8Gig) we reduce our next DES
crack by a factor of 8. If we keep 2^31 entries (16Gig) we can cut it
down to 2^50, or a factor of 16. If we have 4 - 9 Gig drives (or perhaps
three drives and some wiggling, described below) we can save about 2^32
entries and the search becomes a measly 2^48. :)

To whittle this down to a 40-bit workload, we'd have to save 2^36
entries* 2^8 bytes/entry = 2^39 Bytes = 512 Gig. Yes, admittedly large.
What's the cheapest form of storage, magtape? How much can you store on
magtape? The entries can be sorted so that lookup doesn't take long even
when you have to mount tapes. 

Wiggling: 
We may be able to save less than 2^8 bytes/entry because we know the
quality that made the point interesting enough to save (say we only keep
points where the top 32 bits were zeros -- no need to save these zero
prefixes) but I suppose we'd only be able to cut this storage factor
down by a factor of two at most.


If you don't have Hellman's paper handy, the apropos formulas are:
Total time=T, memory=M, search space=N

Time/space tradeoff:
M=mt , T=t^2, m*t^2=N

In our case, N=2^56; M, T variable. 

mattt
>----------
>From: 	Ray Arachelian[SMTP:sunder@dorsai.dorsai.org]
>Sent: 	Tuesday, July 23, 1996 3:16 PM
>To: 	Matt Thomlinson
>Cc: 	'trei@process.com'; 'cypherpunks@toad.com'
>Subject: 	RE: Brute Force DES
>
>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!
>