# Tag Info

17

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

12

The academic and regulatory complexity of triple encryption with two keys is nowhere near that of a cipher with twice the key size. There is a line of thought that 2-key 3DES has like 80-bit or even down to 56-bit security in practice depending on the number of available plaintext/ciphertext pairs, see Chris J. Mitchell: On the security of 2-key triple DES, ...

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

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

6

Meet-in-the-middle attacks can indeed be used for block cipher (but also hash function) cryptanalysis. As mentioned in the question, this goes back to Diffie and Hellman's analysis of DES. However, when applied to primitives, one typically uses more sophisticated techniques. Since the literature around this topic is very extensive, I won't go into the ...

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

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

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

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

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

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

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

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

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

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

3

meet-in-the-middle attacks rely on storing the results in a map Only the naive version of MitM does. The impractical memory requirement (size and accesses) of naive MitM can be greatly lowered with a relatively modest increase in other computation costs, and the calculation distributed to independent devices. The reference paper is Paul C. van Oorschot and ...

3

TLS encrypts a channel, and that channel is between your browser or app and the Facebook server. You do not have a TLS connection to the friend you are sending a message to. There are messaging protocols that do support end-to-end encryption, but Facebook's is not one of them and TLS doesn't really ccome into it.

3

The question is not correct. Two people can establish direct connection between their laptops in the same network and use TLS (assuming they have share public key in advance). In such case TLS does provide E2EE. But such cases are rare in reality. Briefly: TLS provides security between 2 points only, i.e. on a single leg. Where as E2E connection between 2 ...

2

Let $b$ be the width of $E^{(1)}_{K_1}(p)$ and $D^{(2)}_{K_2}(p)$. For the block cipher DES that would be $b=64$, with $n=56$. I'll assume $n+4<b<2n-4$, which holds in this case and simplifies some approximations. Let $w$ be the width of the function iterated. The question as worded proposes $w=n+1=57$, and thus finds collisions fast, but with $w<b$...

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