Adam Shostack <adam@bwh.harvard.edu> writes: The skipjack review committe wrote: | second. At that rate, it would take more than 400 billion years to | try all keys. Assuming the use of all 8 processors and aggressive | vectorization, the time would be reduced to about a billion years
Could someone explain why jumping to 8 processors knocks the time down by a factor of 400, instead of a factor of 8? Is the 400 billion years a load of crap, intended to sound more impressive than 8?
Without seeing the algorithm we can't be sure, but that could be OK for ballpark: the 8 processors gives you 50 billion years, and the aggressive vectorization gives you the other factor of 50. Since they've said there are 32 rounds of <something> in there, I assume the point is to run those rounds in parallel... or overlap the output of that round of one key with the next round of a previous key, or some such dramatic stuff, and 32 is close enough to 50 for this level of estimate. Sounds aggressive to <me>, anyway -- how about you? But it's meaningless to ask how long today's hardware would take to solve this stuff. Extrapolations aren't much better, but at least they give a convenient exponential benchmark. Let's take Wiener's proposed design for 3.5-hour cracks on a $1M machine as the benchmark of solving a single key at acceptable expense. Note that the speed or power of machines has been doubling about once every 12-18 months. Wiener's machine brute-forces a 56-bit key in reasonable time, so if your bang/buck ratio keeps going at the current rate, in 24-36 years something equivalent would be able to brute-force an 80-bit key. That might explain why they chose 80 bits instead of 128... if the algorithm escapes, they don't lose contact with its product forever. Note that the Skipjack Review committee was not in fact using the billion years "load of crap" mode. In the executive summary, they say: 1. Under an assumption that the cost of processing power is halved every eighteen months, it will be 36 years before the cost of breaking SKIPJACK by exhaustive search will be equal to the cost of breaking DES today. I located and cut&pasted this after writing my previous paragraph, so we can call these independent findings. :) Note that they produced this before Wiener presented his design, so the cost of a break was not (publically) known at that point. Jim Gillogly Highday, 7 Astron S.R. 1994, 22:34