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.
participants (2)
-
doug＠netcom.com -
tcmay＠netcom.com