Score:1

Triple DES 1 key to simulate 3 keys

lc flag
pXN

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?

Maarten Bodewes avatar
in flag
It's "negligible", please see [here](https://english.stackexchange.com/questions/202832/is-there-a-difference-between-negligible-and-neglectable) for a discussion on the subject.
fgrieu avatar
ng flag
Triple DES is usually defined as $\operatorname{Enc}(k_3,\operatorname{Dec}(k_2,\operatorname{Enc}(k_1,x)))$, see [this](https://crypto.stackexchange.com/q/2060/555). 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.
Score:3
ru flag

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

poncho avatar
my flag
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}$
Daniel S avatar
ru flag
@poncho Good catch; now edited to add. There's even more chance of pathology from semi-weak keys.
I sit in a Tesla and translated this thread with Ai:

mangohost

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.