Extracting a 3DES key from an IBM 4758
Some relevant sums
The DES cracker is searching a 256 key space (72,058,000,000,000,000 keys)
at a speed of 33.333 MHz (ie 33.333 million keys/second).
To search the entire key space would therefore take 68.50 years.
The DES cracker is actually searching for up to 16384 keys in
parallel. If the whole key space was searched it would find keys at
an average rate of one per 68.50/16384 years, which is one every 36.65
To calculate the expected time until the first key is found, one
treats the system as having a Poisson distribution. Since the linear
feedback shiftback register is walking the keyspace pretty much at
random this is a reasonable assumption.
So we have 256 possible keys in the keyspace and
214 possible matches.
Let the mean rate of matching be m = 214 / 256 = 2-42
The probability that any particular cell is empty is (m0 / 0!) e-m
Simplifying this (m0 = 1 and 0! = 1) we get the probability that a cell is empty = e-m
Let the probability that the first r cells are empty be p
Then p = (e-m)r [independent events]
So p = e-mr
Taking the natural log of both sides and solving for r we have
r = -ln(p) / m
So for a probability, p, equal to 0.5 (ie average luck) for our
value of m we need to
search r keys where r = 0.6931472 / 2.2737734E-13 = 3,048,497,000,000 keys.
At 33.333MHz this will take 25.40 hours.
Note carefully that if your luck is worse, then one time in a thousand
cracking attempts (ie: p = 0.001) then a lot more keys will need to be searched. In fact it
will take about 10.5 days at 33.333MHz.
In practice we've had cracks that ran in times between 5 and 37 hours -- so we've never
been especially unlucky
Our thanks to
for assisting us to get this calculation right
at long last!
Back to main page
last modified 29 OCT 2001 -- http://www.cl.cam.ac.uk/~rnc1/descrack/sums.html