Extracting a 3DES key from an IBM 4758

Some relevant sums

The DES cracker is searching a 2⁵⁶ 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 hours.

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 2⁵⁶ possible keys in the keyspace and 2¹⁴ possible matches.

Let the mean rate of matching be m = 2¹⁴ / 2⁵⁶ = 2^-42

The probability that any particular cell is empty is (m⁰ / 0!) e^-m

Simplifying this (m⁰ = 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 Bruce Christianson for assisting us to get this calculation right at long last!