Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

## Hot answers tagged meet-in-the-middle-attack

34

The main difference is that with two 56 bit keys the maximal security level is 112 bit, and thus an attack that has a cost of $2^{112}$ operations is no attack, whereas for three 56 bit keys the maximal security level is 168 bits, and an attack that has a cost of $2^{112}$ operations counts as an attack. This means that two-key 3DES is still a bit weaker ...

16

These are completely different things: Man-in-the-middle is an active attack to a cryptographic protocol, where the attacker is, effectively, in between the communications of two users, and is capable of intercepting, relying, and (possibly) altering messages. In this case, the meaning of "in the middle" is direct: the attacker is in the middle of two ...

14

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you have to check every entry, which is in both lists and try it with another plaintext-ciphertext pair. If you can successfully decrypt that, you are very likely to ...

9

For a meet-in-the-middle attack with known plaintext, you break all $K_i$ at the same time. The goal is to split the work into multiple sides, trading off some exponential work for some exponential space and some linear work. Split the encryption and decryption sides evenly. You need $(2^8)^4 \times 2 = 2^{33}$ block cipher calls, because you need 4 layers ...

9

Well, one assumption you appear to be making is that, with 2DES, there will be approximately $2^{56}$ possible key matches. Actually, there are an expected $2^{48}$ possible key matches; here's why: Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that ...

9

I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar). If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude. For example, the ...

9

Eli Biham examined this, along with a long series of other "internal chaining" modes in the paper "Cryptanalysis of Multiple Modes of Operation" in AsiaCrypt 1994. His conclusion was that there were ways of attacking such modes that were strictly easier than the standard "external chaining" mode that is now commonly used; his paper is the chief reason that ...

8

The original article rightfully neglects the cost of DES computations (there are less than $2^{90}$) and everything except memory accesses to its Table 1 and Table 2. I go one step further: considering that Table 1 is initialized only once and then read-only, it could be in ROM, and I neglect all except the accesses to Table 2. The attack requires an ...

7

The meet-in-the-middle attack still applies; instead of attack effort $2^{57}$ DES invocations, you just increased it by $2^{56}$ extra DES block encryptions, i.e. up to about $2^{57.6}$ in total: a mere +50% increase. On the other hand, you also made the overall block cipher (your two-key triple encryption) 50% more expensive to use, so the overall security ...

6

The computational complexity of the attack you describe is $2^{112}$, since that's how much work it takes to build the look-up table. In fact, for standard 2-key 3DES like you describe, an attacker capable of building such a look-up table could just as well store $C = E_{K_1}( D_{K_2}( E_{K_1}( P )))$ instead of just $D_{K_2}( E_{K_1}( P ))$ in the table, ...

5

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption: Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$. For each partition generate the inner encryption table. Run Grover's on ...

5

We are talking about attacking double-DES here, which encrypts a 64-bit block $P$ with two 56-bit keys $K_1,K_2$ as $C = E_{K_2}(E_{K_1}(P))$. As noted by Diffie and Hellman already in late 70s, to attack it with a one or two plaintexts as follows. Suppose we know that $P_0$ is encrypted to $C_0$, then for all possible $K_1$ compute $E_{K_1}(P)$ (partial ...

5

My question is, where do we get the $2^{64}$ mentioned in the very first sentence? There are a couple of equivalent ways of looking at the problem. One way is to treat 2DES with an incorrect key as a completely random mapping; there are $2^{112}$ possible keys, and each incorrect key will map our one known plaintext block to a random ciphertext block; ...

4

Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?

4

So is there any way to break XTS or a double application thereof in less time and/or space than expected? The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption. Yes, there are better attacks than that. With XTS a single sector is encrypted with a single $E_{K_2}(n)$ value, so ...

4

As mikeazo points out, a meet-in-the-middle (or any other known plaintext attack) against AES is believed to be infeasible; I'll generalize your question to "if we never reuse a key, why do we care about known plaintext attacks? If the attacker already knew the message, why do we care if he could decrypt it?" The reason is that the attacker might be able ...

4

Each half of the key is 28 bits long, so there will be $2^{28}$ possible choices for each of them. In the first part of your attack, you start with the known block of plaintext and encrypt it for the first 8 rounds using each possible left half of the key. This gives you $2^{28}$ "half-encrypted" 64-bit blocks. This is less than the birthday bound, so ...

4

yes,it is possible because in meet in the middle attack on 3DES,see below with Complementation Property of DES in red arrow,you can search $2^{55}$ key space instead of $2^{56}$,and for green arrow,you have $DEC_{K2}(ENC_{K1}(M))$ that without key Complementation Property,you need $2^{112}$ operations but with key Complementation Property of left ENC and ...

4

There may well be situations where Eve does not have to trick anybody; in the scenario in FIPS 202 the parties badly use the XOF so the mistake is not necessarily triggered by Eve. The equations in your question are really not needed. My guess is that you're making it more complex than it needs to be. Say that Alice and Bob use 3DES with 2 keys $f$ and $g$ ...

3

The meet-in-the-middle attack on ciphers like $C=E^2_K(P)=E_{K1}(E_{K2}(P))$ works as follows. Let's assume you're given a known-plaintext pair $(P_1,C_1)$ and a known-plaintext pair $(P_2,C_2)$ You now build a list (by brute-force) containing the pairs $(I,K1)$ for every possible value of $K1$ ($2^{56}$ for DES) with $I=E_{K1}(P_1)$. Constructing this list ...

3

The combination of Grover algorithm and man in the middle attack is the main subject of a paper (arXiv:1410.1434) published last year by Marc Kaplan (Full disclosure: Marc is a friend of mine.) In this paper beyond applying Grover to MITM to reduce the time needed to analyse double-encryption, he also looks at the time-space gain, which is different, and ...

3

I don't know what you mean by a 'meet-in-the-middle' attack. The obvious way to attack this cipher is a known plaintext attack, that is, encrypt any two distinct plaintexts $x_1, x_2$ (and hence two encryptions), getting their encryptions $y_1, y_2$ : $y_1 = (a x_1 + b) \mod m$ $y_2 = (a x_2 + b) \mod m$ and solve for $a, b$ as: $a = (y_1 - y_2) (x_1 - ... 3 You could protect the ECIES ciphertext with a superencipherment of DLIES, and you would not be weakening your security unless you slipped up and reused keys or used related keys. That means each step should be done carefully and thoughtfully as if it was the only protection step you would be taking. For example, when generating the cryptographically random ... 3 Concerning$(k_1, k_2, k_1)$vs.$(k_1, k_1, k_2)(k_1, k_1, k_2)$can be split into$(k_1, k_1)$with$2^{56}$possibilities and$(k_2)$with$2^{56}$possibilities, so the meet-in-the-middle attack has cost$2^{56}$.$(k_1, k_2, k_1)$can be split into$(k_1, k_2)$with$2^{112}$possibilities and$(k_2)$with$2^{56}$possibilities or into$(k_1)$... 3 That's an optimization for the attack. It would work without it, but slower. To do a Meet-in-the-middle attack, we need to encrypt a known plaintext with every possible key and save the resulting text (with the used key) in a list. Now we decrypt a known ciphertext with every possible key and look if we got the resulting text in our list. We want to know ... 3 In general (especially without knowledge what encryption you consider), it's not possible to detect "correct decryption of one layer", if that's all you have and this "middle ciphertext" is not in a specific format. However, from today's point of view this is almost entirely irrelevant, because stronger attacks are considered: Kerckhoff's principle states ... 3 To begin with 4: Remember Kerckhoff's principle. You should always assume that the attacker knows which algorithm is used to encrypt your data. All the algorithms used in practice are designed to be secure under this assumption, so you should consider that hiding the algorithm from the attacker is superfluous. But as a hypothetical... I can't think of any ... 3 My cursory glance says you are absolutely correct in your assumption, which is why the example was given in FIPS-202 to begin with, because it is problematic.$keymaterial$would still be safe, but$f$and$h$are recoverable, which would then allow a bruteforcing of$g$, all in a practical amount of time. If Alice and Bob realize the problem, they may not ... 2 The attacker splits the range of$2^{56}$keys for the first DES into$2^{17}$ranges of size$2^{39}$. He will then run$2^{17}$times the following meet-in-the-middle attack, once for each range: For all the keys in the range, the attacker computes the first DES on the known plaintext, yielding$2^{39}$64-bit words, for a total size of$2^{45}$bits. The ... 2 I believe this question is only answerable if$F_k$is easily invertible. In other words, if you can compute$M=F^{-1}_k(F_k(M))$. Then a standard meet-in-the-middle attack applies. Given message$M$, ciphertext$C = E_k(M)$for unknown$k \in \{0,1\}^{128}$, an efficiently-computable function$X$such that$k = X(k_1, k_2)$for some$k_1, k_2 \in \{0,1\}^{...

Only top voted, non community-wiki answers of a minimum length are eligible