| Previous | Table of Contents | Next |
Of course, it is ludicrous to estimate computing power 35 years in the future. Breakthroughs in some science-fiction technology could make these numbers look like a joke. Conversely, physical limitations unknown at the present time could make them unrealistically optimistic. In cryptography it is wise to be pessimistic. Fielding an algorithm with an 80-bit key seems extremely short-sighted. Insist on at least 112-bit keys.
| Table 7.1 Average Time Estimates for a Hardware Brute-Force Attack in 1995 | ||||||
|---|---|---|---|---|---|---|
| Length of Key in Bits | ||||||
| Cost | 40 | 56 | 64 | 80 | 112 | 128 |
| $100 K | 2 seconds | 35 hours | 1 year | 70,000 years | 1014 years | 1019 years |
| $1 M | .2 seconds | 3.5 hours | 37 days | 7000 years | 1013 years | 1018 years |
| $10 M | .02 seconds | 21 minutes | 4 days | 700 years | 1012 years | 1017 years |
| $100 M | 2 milliseconds | 2 minutes | 9 hours | 70 years | 1011 years | 1016 years |
| $1 G | .2 milliseconds | 13 seconds | 1 hour | 7 years | 1010 years | 1015 years |
| $10 G | .02 milliseconds | 1 second | 5.4 minutes | 245 days | 109 years | 1014 years |
| $100 G | 2 microseconds | .1 second | 32 seconds | 24 days | 108 years | 1013 years |
| $1 T | .2 microseconds | .01 second | 3 seconds | 2.4 days | 107 years | 1012 years |
| $10 T | .02 microseconds | 1 millisecond | .3 second | 6 hours | 106 years | 1011 years |
If an attacker wants to break a key badly enough, all he has to do is spend money. Consequently, it seems prudent to try to estimate the minimum “value” of a key: How much value can be trusted to a single key before it makes economic sense to try to break? To give an extreme example, if an encrypted message is worth $1.39, then it wouldn’t make much financial sense to set a $10-million cracker to the task of recovering the key. On the other hand, if the plaintext message is worth $100 million, then decrypting that single message would justify the cost of building the cracker. Also, the value of some messages decreases rapidly with time.
Software Crackers
Without special-purpose hardware and massively parallel machines, brute-force attacks are significantly harder. A software attack is about a thousand times slower than a hardware attack.
The real threat of a software-based brute-force attack is not that it is certain, but that it is “free.” It costs nothing to set up a microcomputer to test possible keys whenever it is idle. If it finds the correct key—great. If it doesn’t, then nothing is lost. It costs nothing to set up an entire microcomputer network to do that. A recent experiment with DES used the collective idle time of 40 workstations to test 234 keys in a single day [603]. At this speed, it will take four million days to test all keys, but if enough people try attacks like this, then someone somewhere will get lucky. As was said in [603]:
The crux of the software threat is sheer bad luck. Imagine a university computer network of 512 workstations, networked together. On some campuses this would be a medium-sized network. They could even be spread around the world, coordinating their activity through electronic mail. Assume each workstation is capable of running [the algorithm] at a rate of 15,000 encryptions per second.... Allowing for the overhead of testing and changing keys, this comes down to...8192 tests per second per machine. To exhaust [a 56-bit] keyspace with this setup would take 545 years (assuming the network was dedicated to the task twenty-four hours per day). Notice, however, that the same calculations give our hypothetical student hackers one chance in 200,000 of cracking a key in one day. Over a long weekend their odds increase to one chance in sixty-six thousand. The faster their hardware, or the more machines involved, the better their chance becomes. These are not good odds for earning a living from horse racing, but they’re not the stuff of good press releases either. They are much better odds than the Government gives on its lotteries, for instance. “One-in-a-million”? “Couldn’t happen again in a thousand years”? It is no longer possible to say such things honestly. Is this an acceptable ongoing risk?
Using an algorithm with a 64-bit key instead of a 56-bit key makes this attack 256 times more difficult. With a 40-bit key, the picture is far more bleak. A network of 400 computers, each capable of performing 32,000 encryptions per second, can complete a brute-force attack against a 40-bit key in a single day. (In 1992, the RC2 and RC4 algorithms were approved for export with a 40-bit key—see Section 13.8.)
A 128-bit key makes a brute-force attack ridiculous even to contemplate. Industry experts estimate that by 1996 there will be 200 million computers in use worldwide. This estimate includes everything from giant Cray mainframes to subnotebooks. If every one of those computers worked together on this brute-force attack, and each computer performed a million encryptions per second every second, it would still take a million times the age of the universe to recover the key.
Neural Networks
Neural nets aren’t terribly useful for cryptanalysis, primarily because of the shape of the solution space. Neural nets work best with problems that have a continuity of solutions, some better than others. This allows a neural net to learn, proposing better and better solutions as it does. Breaking an algorithm provides for very little in the way of learning opportunities: You either recover the key or you don’t. (At least this is true if the algorithm is any good.) Neural nets work well in structured environments where there is something to learn, but not in the high-entropy, seemingly random world of cryptography.
| Previous | Table of Contents | Next |