What is the complexity for attacking 3DES in linear or differential cryptanalysis?

Question

I know that 3DES is NOT vulnerable to DC , LC . But is it because the attacks requires too many input\output pairs ? Or because it's impossible ? (i.e requires more than 2^64 pair )

Answer 1

"Not vulnerable" is not how I would describe it, but my understanding is that the existing attacks on DES cannot directly not work with 3DES.

At the moment, the best attack against single DES is a linear attack which requires $2^{43}$ plaintext-ciphertext pairs, and has a time complexity of at between $2^{39}$ and $2^{43}$ operations.

Linear cryptanalysis works by trying to approximate the functionality of the cipher with some linear function, e.g. "if I plug all of the input and output bits into this polynomial I discovered, I can determine the value of the 26th bit of the key with a confidence of 72%". Given such approximations, an attacker with access to enough plaintexts and corresponding ciphertexts for a single key may be able to recover the entire key, or enough of it to make a bruteforce on the remainder feasible.

Many block ciphers, including DES, introduce non-linearity with an S-box. While it may be possible (or even trivial) to produce linear approximations of a single round of a block cipher, doing so for larger numbers of rounds becomes significantly more difficult. Assuming a good design, as you add more rounds, the number of possible internal states of the function increases, and the statistical significance of linear approximations decreases. This increases the number of plaintext-ciphertext pairs and operations you need, often to the point of making it less feasible than a brute-force attack.

Differential cryptanalysis works in a similar way. By observing how changes in input propagate through each round to the output, it may be possible to identify behaviours that leak information about the round keys. For example, one might select a pair of similar message values $m_1$ and $m_2$, and then compare $m_1 \oplus m_2$ and $f_r(m_1, k_r) \oplus f_r(m_2, k_r)$, where $f_r$ and $k_r$ are the round functions and round keys respectively. Statistical analyses of each separate round, in relation to their reactions to small changes in input, can be combined together to demonstrate properties that can be used to determine information about the values of the round keys in the full-round version of the cipher, or in a reduced-round variant (though this would not constitute a break).

The thing to keep in mind here is that attacks such as these rely upon the attacker having access to a large number of plaintexts and their associated ciphertexts for a key that they wish to recover. Removing this ability, or inhibiting it sufficiently, makes it incredibly hard to find practical attacks against even mediocre ciphers.

Now, the important question to answer here is as follows: can the existing attacks on single DES be reconstructed in a way that allows them to function against 3DES, where the attacker only has access to an oracle against the entire encryption process? (i.e. the values of the intermediate steps in 3DES are unknown to the attacker). The answer is essentially no. Since the attacks require the attacker to know a large number of plaintext-ciphertext pairs for each DES operation, but the intermediate values of the 3DES operation are unknown to the attacker in this scenario, the original attacks are no longer directly relevant - it isn't possible to just "run the attack three times".

Instead, new attacks had to be formulated against 3DES, using the same observations in previous attacks as building blocks, but applying them to a full 3DES operation. 3DES can be thought of as a 48-round variant of DES, as each round of DES is identical (aside from the key schedule, but that is irrelevant for LC and DC attacks). This now means that a full-round attack against 3DES requires linear approximations across all 48 rounds, or differential properties that can be correlated across the full 48 rounds. This is remarkably difficult to do - much moreso than against single DES itself.

The "typical" attack against triple encryption is what's known as a meet-in-the-middle attack. In such an attack against 3DES, we treat each DES operation separately, and attack a single plaintex-ciphertext pair. First, we perform decryption operations against the ciphertext for every possible $2^{56}$ keys, and store the resulting decrypted blocks in a list. This requires $2^{56} \times 64$ bits of space, or 512 petabytes. Next, we perform the first two DES encryption operations against the plaintext for every possible key (i.e. brute-force the entire 112-bit keyspace) until we reach an output that matches an entry in the previously computed list. Once we find a match, we know we've found the correct key. The time complexity of this attack is $2^{112} + 2^{56}$, which can be approximated down to $2^{112}$ due to the massive difference in exponent.

This basic idea has been improved upon somewhat for DES specifically - the best known attack requires $2^{32}$ known plaintexts, $2^{113}$ operations (consisting of $2^{90}$ DES encryptions and the remainder much faster operations), and $2^{88}$ memory. While, numerically speaking, this has more operations than the direct meet-in-the-middle, the vast proportion of those operations are much faster in practice. As such, the number of operations itself doesn't tell the full story in terms of actual computational cost, and the attack is faster than a naive meet-in-the-middle.