Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.

Can I recover that key?

If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?

  • 1
    $\begingroup$ Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext? $\endgroup$ – ymbirtt Nov 12 '18 at 11:26
  • $\begingroup$ @ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB! $\endgroup$ – Richard Jones Nov 12 '18 at 14:24
  • $\begingroup$ @Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used. $\endgroup$ – Klaws Nov 12 '18 at 16:43

Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.

Can I recover that key?

No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.

  • $\begingroup$ So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right? $\endgroup$ – Richard Jones Nov 12 '18 at 21:43
  • $\begingroup$ Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode. $\endgroup$ – kiwidrew Nov 13 '18 at 1:42

What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour. However, reaching $2^{128}$ is beyond classical computing.

In brute-force with only one key, the number of elements in your list is not really important, a few will be enough to uniquely determine the key.

In your case, the problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;

for each k in possible keys
   if E(k,P1) == C1

Once you found you can verify with the other plaintext-ciphertext pairs.

  • If you would have different keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{128}/t$.

Note: there are other types of attacks (related-key attacks which are not related to your case.) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.

  • $\begingroup$ So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key? $\endgroup$ – Richard Jones Nov 11 '18 at 18:59
  • $\begingroup$ Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack. $\endgroup$ – kelalaka Nov 11 '18 at 19:03
  • $\begingroup$ @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message). $\endgroup$ – Clockwork-Muse Nov 12 '18 at 3:29
  • 1
    $\begingroup$ This doesn't really answer the meat of the question—does knowing many plaintext/ciphertext pairs help? The related-key setting is not relevant to any halfway serious protocols, so is not relevant here, but in the multi-target setting—which is relevant to essentially all practical protocols—the expected cost to break one of $t$ AES-128 targets is $2^{128}/t$, far below $2^{128}$; for a billion targets, the cost would be below $2^{100}$ and the time would be below $2^{70}$. (Nothing special about AES: this applies to any cipher with a 128-bit key.) $\endgroup$ – Squeamish Ossifrage Mar 11 '19 at 21:26
  • $\begingroup$ @SqueamishOssifrage Yes related key attacks are not affecting a serious protocol. They are effective if the block cipher is initiated as a hash function. For Multi-target, absolutely. $\endgroup$ – kelalaka Mar 11 '19 at 21:31

As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.

As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.

The use of ECB mode gives us a credible attack. Recall the operation of ECB:

A diagram showing ECB-mode's operation

Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.

AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!

Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.

Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.

  • 1
    $\begingroup$ Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key. $\endgroup$ – Klaws Nov 12 '18 at 16:51
  • $\begingroup$ The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective. $\endgroup$ – symcbean Dec 18 '18 at 0:10
  • $\begingroup$ @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information. $\endgroup$ – ymbirtt Dec 18 '18 at 9:17
  • $\begingroup$ @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem. $\endgroup$ – ymbirtt Dec 18 '18 at 9:21
  • $\begingroup$ Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext. $\endgroup$ – symcbean Dec 18 '18 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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