Re: Breaking DES

pmetzger@lehman.com said:
>Karl Lui Barrus says:
>> plaintext with 2^56 keys, and decrypt the ciphertext with 2^56 keys.
>
>Tell you what, Karl -- when you build the device that can store 2^56
>encryptions, let us know.

2^56 bytes equals 10^7 gigabytes. At roughly $1000 per gigabyte,
that equals 10^10 bucks...10 billion dollars. Or say there's a quantity
discount in orders totalling a million units, and you get the whole
capacity for 1 billion dollars.

Well, that's a bit steep for me, but there's no question but that the
NSA could afford it. Still, what do you say I wait a few years until it
comes down to 10 million dollars, which I happen to have available in
the year 2003 in my company budget? Ten years should do it, estimating
conservatively.

> Also let us know how you'll index and fetch the encryptions
>in any reasonable time while you are at it, but by comparison thats a
>tiny problem.

That ten years also means that rather than searching 10^7 units in parallel,
we will then be searching only 10^5 units in parallel. It'll still take
a few hours, but that's ok.

This all suggests that the NSA could do such a thing *now* if they *really*
cared to, and could do so fairly trivially in 10 years.

>> The work for this attack is 2^56 + 2^56 = 2^57, which suggests that
>> double encryption doesn't increase the complexity of breaking your
>> text very much.
>
>Karl, are you sure that you want people to think you believe this?

I did a double take on this at first too, since naively one would expect
the search to be (2^56)^2. However, this can be improved, for instance
by sorting each set in N lg N time (56 * 2^56 operations), and then doing
interleaved comparisons in N lg N time again, which can be mostly parallelized
over those 10^5 computers that are running those 10^5 disks, so that the
total time would be (since 10^16 = 2^56) 10^16 / 10^5 machines = 10^11 cycles,
and given 10^3 MIP machines, this gives 10^4 seconds (20 minutes) for each
phase...call it an hour total.

(In other words, as a first approximation, Karl is accurate to assume
linear rather than quadratic speed for this.)

This neglects coordination of the networked machines, which one might
expect to add a factor of 5 to 10 to those numbers.

This rough analysis demonstrates that Karl's scenario is merely expensive
now, and "cheap" (by NSA standards) ten years from now, rather than
completely inconceivable.

I guess the weakest point of the above back-of-the-envelope estimate
is that each e.g. plaintext & cyphertext is assumed to be representable
within one byte, but that's *not* fatal. You could use hashing to get
down to one byte, and when a hit is detected, try again using two
bytes. When hits are detected there, use four bytes...and so on. That
approach allows the real world scheme to be reasonably close to the
back of the envelope gross assumptions.
	Doug

Doug Merritt wrote:

> 2^56 bytes equals 10^7 gigabytes. At roughly $1000 per gigabyte,
> that equals 10^10 bucks...10 billion dollars. Or say there's a quantity
> discount in orders totalling a million units, and you get the whole
> capacity for 1 billion dollars.
> 
> Well, that's a bit steep for me, but there's no question but that the
> NSA could afford it. Still, what do you say I wait a few years until it

Probably. But I suspect we'd know it had been built.

Norm Harrdy described for us his experiences with the "Harvest"
machine at NSA in the early 60s. (Bamford also describes this in some
detail...worth taking a quick look at, I think.)

Harvest was built by IBM as a special-purpose add-on, or auxiliary
processor I suppose, to the IBM "Stretch," then the fastest computer
in the world.

Harvest was quite impressive for its time, as Norm explained it to us.
A 300 nanonsecond cycle time, with a 64-bit word. Lots of core memory,
special tractor tape drives to load in data.

The Harvest machine was particularly good at brute force breaking of
Hagelin-type rotor machines, the "DES of its day" (the NSA had
encouraged foreign governments to buy surplus U.S. rotor machines,
assuring them that changing to their own rotor settings would make
them good as new...this did not, and NSA's knowledge of the machine
designs gave them a headstart on cracking the ciphers).

So, I would imagine that the effort put into Harvest in 1962, and
later into the financing of both Cray Research (confirmed) and
Thinking Machines (suspected by many), would possibly be put into the
breaking of modern ciphers.

Cost for Stretch (in 1962 dollars): $13 million.
Cost for Harvest (in 1962 dollars): $13 million.
Cost for special tape drives:   $5 million

Total Cost (in 1962 dollars): approximately $30 million.
Total Cost (in 1993 dollars): approximately $100-200 million,
depending on what inflation index one uses.

Would NSA spend $200 million on cipher-busting machines?

Well, modern spy satellites often cost upwards of a bilion apiece, so
this seems possible.

Note that NSA contracted with National Semiconductor several years
back to have a dedicated wafer fab in a secure area of Fort Meade, to
supply custom chips. 

But could such a project escape notice--and publicity--outside the
NSA? CPU desiginers would have to be brought it, and no doubt much of
the work would be contracted out.

Any rumors floating around?

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.