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