1
$\begingroup$

I am trying to understand how to calculate the average key search time given a specific scenario:

Suppose we have a program that uses standard DES with 56 key bits, and we can test 10^6 keys per second.

The key consists of 8 characters, a simple concatenation of the 8 ASCII characters yielding 64 = 8*8 key bits. With the permutation PC-1 in the key schedule, the least sig. bit of each 8-bit character is ignored, giving us 56 key bits.

What is the size of the key space if all 8 characters are randomly chosen 8-bit ASCII characters?

My thought is the key space is 2^56.

How long does an average key search take?

We can test 10^6 keys per second, and 2^56 is roughly 7.2058 x 10^16. I don't know if this is proper way to do it, I estimated ~3 seconds.

I am assuming there is much more accurate mathematical approach but I'm not familiar with it, could anyone shed some light on this for me?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

At $10^6$ keys per second, going through the full $2^{56}$ keys would take $2^{56}/10^{6}$ seconds, or about 2200 years; the average time would be half that (or a bit more than 1000 years).

Obviously, this is longer than anyone would be willing to wait. So, why is DES considered brute-forcible? Well, we can throw considerably more resources at the problem than a single laptop...

Improve this answer
$\endgroup$
2
  • $\begingroup$ Quick question, sorry. What would the key space be if the 8 characters are randomly chosen 7-bit ASCII characters (ie. the most sig. bit is always 0)? 8*7 = 56, so isn't it still 2^56? $\endgroup$
    – Talen Kylon
    Oct 5, 2015 at 22:13
  • $\begingroup$ @TalenKylon: well, the most significant bits contribute to the key value (it's the lsbits that are ignored), and so that would reduce the key space to 48 bits. Also, when someone says "ASCII character", they often mean "printable ASCII character", that is, a value between 0x20 and 0x7e; that would reduce the keyspace somewhat more. $\endgroup$
    – poncho
    Oct 6, 2015 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.