Triple AES-128 encryption with 2 keys

Question

We have a system where two devices communicate. Due to restrictions on one of them, we can only use AES-128 (so no AES-256) for encrypting the communication. However, new requirements on these kinds of systems have recently come up where > 200 bits encryption is required for the data communicated between the devices. So we need to adhere to it. So to my question.

Does triple encrypting using AES-128 with two different keys, using K1, K2, K1 (similar to 3DES) make the complexity (for a bruteforce MITM) go from ~2^127 to ~2^255, or are there differences between how DES and AES work that makes it not function like that for AES? If so, what would be the best suggestion for achieving this requirement with only AES-128 at hand.

EDIT

Our current implementation with double encryption is as: C = ENCk2(ENCk1(P)) and P = DECk1(DECk2(C)). Both ENC and DEC uses aes128 and takes k1/k2, IV and C/P as input. Using MITM we can get DECk2(C) = ENCk1(P) and thus they can brute force in more or less the same time as regular aes128.

Our idea now is to use k1, k2 and IV and generate two session keys: k'1 and k'2. Could use them all as input to sha256 and use the first half of the result as k'1 and the second as k'2. This way the MITM approach would give DECk'2(C) = ENCk'1(P). What an attacker then can do is to start guessing k'1 and k'2 and eventually if the have enought C/P pairs they can figure them out. However, these session keys will be useless for any future communication. So to get the actual keys k1 and k2 they would simply have to guess for all the combinations, making it effectually ~2^2*128. Is this a reasonable line of thought?

And to clarify, perhaps it sounds stupid to use two 16-byte keys + IV in a sha256 to create two new 16-byte keys and then run aes128 twice with those two. However, our hardware limits us to aes128 so that is the reason we have to use it. We do have access to sha256 so then we can do that combination.

Answer 1

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, in IEEE Transactions on Information Theory, 2016, and this quote of the superseded SP 800‑57 Part 1 Rev. 4

Determining the security strength of an algorithm can be nontrivial. (..) For 2TDEA, if exhaustion were the best attack, then the strength of 2TDEA would be 56 × 2 = 112 bits. This appears to be the case if the attacker has only a few matched plain and cipher pairs. However, the security strength of 2TDEA decreases as the number of matched plaintext/ciphertext pairs increases. If the attacker can obtain approximately $2^{40}$ such pairs and has sufficient memory and computational power, then 2TDEA can provide an estimated maximum security strength of about 80 bits; if the attacker has $2^{56}$ plaintext/ciphertext pairs, with significantly more memory and computational power, then the estimated maximum security strength would be about 56 bits.

See this for a partial rationale and more references.

My assessment is that even with DES, attacks against 2-key triple encryption require so much memory and memory accesses (a fair fraction all DRAM ever built and accesses thereof) that they are extremely impractical (see this for more). And that such attacks against AES are pure fiction, for the same reasons, plus the amount of plaintext/ciphertext pairs needed. But facing a regulatory requirement, my assessment won't stand.

The best known generic attack is still essentially Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption, in proceedings of Eurocrypt 1990. Translated to AES-128, it has expected cost over $2^{256-k}$ encryptions when there are $2^k$ blocks of known plaintext.

Triple AES-128 with two keys (in K₁/K₂/K₁ order, perhaps preferably all encryption rather than EDE) is practically safe from meet-in-the-middle attack. In an embedded context, the risks are plain negligible compared to side channels attacks and other non-purely-cryptanalytic methods of key extraction. There remains to convince whoever holds the rubber stamp. Being able to put a reasonable limit on the number of plaintext blocks corresponding to the same key that an adversary could obtain may help (see last section).

---

Later references that extend to variants of basic triple encryption (with 3 or 2 keys) include Eli Biham's Cryptanalysis of Triple Modes of Operation, in Journal of Cryptology, 1999; and Helena Handschuh and Bart Preneel: On the Security of Double and 2-Key Triple Modes of Operation, in proceedings for FSE 1999.

---

I advise against double AES-128 (as in the question's current implementation), even with a very limited amount of ciphertext per session key. No reasoning concluding that this gives near 200-bit security can stand competent examination. There is a straightforward attack, requiring only 3 plaintext/ciphertext pairs, feasibly little memory and communication, showing this can't have more than about 130-bit security, by applying techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

---

What would be the best suggestion for achieving this requirement («the wireless communication needs at least 200-bit encryption») with only AES-128 at hand?

A reasonable option could be:

• Use as building block triple AES-128 encryption with two keys, with encryption of 128-bit $X$ under two 128-bit keys $K_1$, $K_2$ per $E_{(K_1,K_2)}(X)\underset{\text{def}}=E_{K_1}(E_{K_2}(E_{K_1}(X)))$
• Demonstrate that any 256-bit key for that is used less than $2^{48}$ times, by the sheer time it would take to exceed that limit (if the overall system has no safeguard against multi-target attacks, it might be best to show that all the devices an attacker could use won't reach that $2^{48}$ limit).
• Assert that this gives (with some headroom) $256-48>200$ bitof security against key recovery by known cryptanalytic attacks, citing Mitchell confirming earlier analysis by van Oorschot and Wiener, and the NIST advice (see above references). Be aware that an operative word is known, and there are many caveats, including the fact that the last AddRoundKey of an encryption step and the first AddRoundKey of the next reduce to a single one, denting any rationale considering AES-128 as a black box.

If use of the rubber stamp is decided by reason, there is good chance the focus will move to examination of if the key can leak otherwise, if IV can't get reused even facing deliberate attacks attempting to cause that, how the key is drawn and shared, and other real problems.