1
$\begingroup$

Consider a system where DES is used to encrypt HTTP GET requests. The first three bytes correspond to the character sequence "GET". How many encrypted messages is it necessary to intercept to be sure to guess the key used to encryption ?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ What have you already attempted in solving this homework problem? $\endgroup$
    – poncho
    Apr 29 at 15:27
  • $\begingroup$ The key size is 56 bits, so we have 2^56 keys, the block size is 64 bit so we have 2^64 ciphertexts. The first 24 bit are known so we have 2^64 / 2^24 = 2^40 possible ciphertexts. We also know that there are 2^56 / 2^40 = 2^16 ciphertexts per key. With an additional intercepted message we can reduce the previous value to 2^16/2^40 = 2^-24. In this way if we find a valid key, it will be the correct key. I am not sure about my solution beacuse increasing the number of fixed bits would require more intercepted messages $\endgroup$
    – Angelo
    Apr 29 at 16:52

1 Answer 1

Reset to default
1
$\begingroup$

You don't have things quite right; I suspect focusing on the DES block size is confusing you.

Here is the way I found useful when addressing this situation: we model our decryption such that if we decrypt the ciphertext with the correct key, we get the correct plaintext; if we decrypt with an incorrect key, we get an essentially random plaintext. As far as we know, this is a decent way to model DES.

So, in this situation, an incorrect guess at the key happens to have the first three characters of the plaintext as "GET" with probability $2^{-24}$ (because we have 24 known bits).

So, if that is our only way of testing whether a guess of the key is correct, how many ciphertexts would we need to reduce the probability to close to zero that there exists an incorrect key that decrypts all the ciphertexts to something plausible?

Also, I feel compelled to note that, for the situation under discussion, just testing the first three characters need not be the only test on a potential decryption (although it would likely be the first, as it is the easiest). An "GET" in an HTTP GET request is followed by a valid URL; a random string (which would get produced by an incorrect decryption) is quite unlikely to happen to be a valid URL; hence we are likely to need fewer test challenges than what the exercise calls for. On the other hand, the exercise writer wasn't expecting you to think about that...

Improve this answer
$\endgroup$
0

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.