DES attack with known partial plaintext

Angelo

4/29/24, 3:25 PM

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 + 2

des

known-plaintext-attack

poncho

4/29/24, 3:27 PM

What have you already attempted in solving this homework problem?

Angelo

4/29/24, 4:52 PM

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

Score:1

Crypto

poncho

4/29/24, 5:57 PM

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...

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: DES attack with known partial plaintext

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.