How many plaintext-ciphertext pairs would be needed to guess with probability, say $p=0.5$, the key $k$ of AES under ECB mode?

Most of the articles that I found tried attacks on single plaintext-ciphertext pair. How would the chances on attack on key increase with increase in number of plaintext-ciphertext pairs.

Link to document or discussion thread about various attacks would be highly appreciated.

  • Those articles talk about a single pair, because having more doesn't aid brute-force key recovery attacks. – CodesInChaos Nov 2 '15 at 13:08
  • Won't presence of multiple plaintext-ciphertext pairs increase the chance of breaking the system by use of crypt-analysis attacks? Moreover, why use other modes of operation if ECB is invulnerable in case of multiple plaintext-ciphertext pairs. – Baruntar Nov 2 '15 at 13:39
  • 3
    1) Having more known plaintext helps with crypto-analysis. But since there is no known attack against full AES used with a proper key, this doesn't help you. 2) The problem with ECB is not that it allows key recovery attacks, it does not. The problem is that it leaks which plaintext blocks are identical. – CodesInChaos Nov 2 '15 at 13:43
up vote 4 down vote accepted

As CodesInChaos notes in the comments, having more ciphertext–plaintext pairs doesn't help with brute force guessing attacks.

Well, that is, except for the minor issue of unicity. Basically, to narrow the results of your brute force attack down to a single key, you do need to have enough ciphertext–plaintext pairs that the length of the known plaintext exceeds the length of the key (by some reasonable amount — but one extra cipher block is more than enough).

For example, if you were trying to break AES-256 using just one block (i.e. 128 bits) of known plaintext (and somehow had a magic supercomputer that could actually test 2256 keys by brute force), you'd end up with about 2128 false positives — wrong keys that produce the correct ciphertext for the known plaintext block just by chance — in addition to the correct key. Testing a second ciphertext–plaintext block pair would narrow that down to just one false positive (on average; you might get none, or you might get two or even more if you're unlucky), and a third pair would almost certainly (with probability about 1 − 1/2128) eliminate the false positives completely.

So you do need at least two, and preferably three, blocks of ciphertext–plaintext pairs to uniquely determine the correct key for AES-256. For AES-128, one block may be enough if you're lucky, but you preferably want two.

All that said, having even more ciphertext–plaintext pairs than that won't help with brute force attacks — once you've got enough to uniquely identify the correct key, any more is useless.


Having more known plaintext does typically help with cryptanalytic attacks. For example, the biclique attacks of Bogdanov, Khovratovich and Rechberger can, given 256 ciphertext–plaintext pairs, speed up AES key recovery by a factor of about four (4 = 22) compared to simple brute force. Obviously, this is still a completely infeasible attack in practice, but it does mean that, technically, having more ciphertext–plaintext pairs does make AES key recovery faster. (Well, that is, except for the fact that the extra complexity of the biclique attack would almost surely slow it down by far more than the factor of 4 that it theoretically gains over plain brute force, were anyone to try to actually implement it. But in principle it works...)

Similarly, the related-key attack by Biryukov and Khovratovich requires about 299.5 ciphertext–plaintext pairs, encrypted under distinct keys satisfying a specific relationship, to recover the actual keys for AES-256. This is still not a practical attack, and using properly chosen keys (generated randomly or using a secure KDF) defeats it completely, but it is technically an example of a situation where having more (suitably chosen) ciphertext–plaintext pairs helps to recover the key.


In any case, the reason why you should not use ECB mode has nothing to do with key-recovery attacks. (In fact, ECB is generally no worse than any other mode of operation in this respect.) Rather, the reason ECB mode is insecure is simply that it leaks which plaintext blocks are identical, and thus isn't semantically secure.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.