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 ?
1 Answer
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...
2^56
keys, the block size is 64 bit so we have2^64
ciphertexts. The first 24 bit are known so we have2^64 / 2^24 = 2^40
possible ciphertexts. We also know that there are2^56 / 2^40 = 2^16
ciphertexts per key. With an additional intercepted message we can reduce the previous value to2^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$