1
$\begingroup$

I saw a statement that the probability of finding a key $k'$ to simulate 3 keys $k_1$, $k_2$, $k_3$ is neglectable: $\mathrm{Enc}(k_3,\mathrm{Enc}(k_2,\mathrm{Enc}(k_1,x))) = \mathrm{Enc}(k′,x)$

When not considering MITM attack, the probability of brute forcing triple DES is $1/2^{168}$. According to the statement, does that mean the probability of finding $k'$ is also $1/2^{168}$ so it is negligible? Do I understand it correctly?

$\endgroup$
2
  • $\begingroup$ It's "negligible", please see here for a discussion on the subject. $\endgroup$
    – Maarten Bodewes
    Apr 9, 2023 at 22:48
  • $\begingroup$ Triple DES is usually defined as $\operatorname{Enc}(k_3,\operatorname{Dec}(k_2,\operatorname{Enc}(k_1,x)))$, see this. Independently: quoting the statement or linking to it would be useful. It's so easy to twist a statement when restating it! For example "probability of finding" is not the same as "probability that there exists", and depends on the effort made. Probability of brute forcing triple DES by trying a random key in a known-plaintext scenario is $1/2^{168}$, but without the extra detail the statement is too vague to be falsifiable. $\endgroup$
    – fgrieu
    Apr 11, 2023 at 10:13

1 Answer 1

3
$\begingroup$

No. In the triple encryption case, we expect that the chance of such a key existing at all is about $2^{56}/64!\approx 2^{-240}$ (assuming a 64-bit block size and 56-bit single key space). There's no particular structure that should make is treat the $2^{168}$ permutations corresponding to the different possible possible choices of 3 keys as anything other than a random permutation, likewise for the $2^{56}$ permutations corresponding to a single encryption.

(ETA: Poncho points out that there is some structure for four known DES keys for which encryption and decryption are the same. In the case, where $k_2$ is such a key and either $k_1$ or $k_2$ is also, then the triple encryption is equivalent to a single key encryption. This happens with probability roughly $2^{-109}$. There are also six pairs of semi-weak keys where encryption without one is the same as decryption with another, again if $k_2$ belongs to one of these pairs and either $k_1$ or $k_2$ then there is single key equivlance. This has additional probability roughly $2^{-107.4}$)

However, triple DES is not threefold encryption but rather DES-encryption with one key $k_1$, DES-decryption with another key $k_2$ and DES-encryption with a third key $k_3$. In the case $k_1=k_2$ this structure is equivalent to single DES-encryption with $k_3$ and in the case $k_2=k_3$ it is equivalent to single DES-encryption with $k_1$. If $k_1,k_2,k_3$ are chosen independently, uniformly at random the chance of one of these two occurrences is about $2^{-55}$, and as before we expect other triples to correspond to single keys with probability $2^{56}/64!$.

If there is an equivalent single key, we expect to be able to find it with $2^{56}$ work and one or two matched plain and cipher pairs. We do this just be exhausting the single key space. The chance of a false positive on one matched pair is about $2^{-8}$ and on two matched pairs is about $2^{-72}$.

$\endgroup$
2
  • 1
    $\begingroup$ Actually, DES has weak (self-inverse) keys. In the triple encryption case, this allows some 3DES/DES equivalent keys; if either the first two DES keys or the last two keys are the same weak key, then the entire 3DES structure is the same as the remaining DES key - there are four weak keys, and so this leads to a probability circa $2^{-109}$ $\endgroup$
    – poncho
    Apr 10, 2023 at 15:28
  • $\begingroup$ @poncho Good catch; now edited to add. There's even more chance of pathology from semi-weak keys. $\endgroup$
    – Daniel S
    Apr 10, 2023 at 16:11

Your Answer

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

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