At least it's my understanding that AES isn't affected by known-plaintext. Is it immune to such an attack, or just resistant? Does this vary for chosen-plaintext?
$\begingroup$
$\endgroup$
3
asked Dec 20, 2011 at 20:03
-
$\begingroup$ @owlstead I think it's a stretch to say that a padding oracle attack is a known plain text attack, because while there is "plain text" that is known (ie the padding algorithm) knowing the plain text message isn't really helpful except for the fact that you wouldn't need the attack in the first place. $\endgroup$– jbtuleApr 25, 2012 at 19:30
-
$\begingroup$ @owlstead You are going to have to be more specific, because I'm still only seeing padding or validation oracles that let you recover the plain text with chosen-cipher-text-attacks. $\endgroup$– jbtuleApr 25, 2012 at 20:28
-
$\begingroup$ @jbtule Can we agree that a padding oracle attack requires knowledge about the plain text (the padding) and choosen cipher text? I just put in the comment to show that known plain text may help with some attacks. That's different than a known plain text attack, it's just a warning to the asker. With the XML encryption attack even more knowledge about the plain text could be inferred. $\endgroup$– Maarten Bodewes ♦Apr 25, 2012 at 20:48
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
3
A known-plaintext attack (i.e. knowing a pair of corresponding plaintext and ciphertext) always allows a brute-force attack on a cipher:
- Simply try all keys, decrypt the ciphertext and see if it matches the plaintext.
This always works for every cipher, and will give you the matching key. (For very short plaintext-ciphertext pairs, you might get multiple matching keys. Then you need to try more pairs to eliminate the wrong ones).
If you have no known plaintext, only the ciphertext, you can do it similarly, but you also need a function which says whether what you decrypted is a plausible plaintext.
The problem with try all keys is that for every modern cipher (i.e. key sizes of 128 bit or more) the key space is that large that you need much more time than the remaining lifetime of the universe to check a significant portion of all keys.
So, the question is, are there any attacks which are faster than brute-force?
For now, there seem to be some attacks which are slightly faster (like needing only $2^{125}$ steps instead of $2^{127}$ for brute-force, a bit better for the 256-bit-key version) and needing either a really large amount of chosen plain- or ciphertexts (and knowing the result), or even larger amounts of known plaintexts. These are still not practically doable in our world.
There are no proofs that AES (or any block cipher) is really secure, only the heuristic "many smart people tried to break it and until now, nobody was successful" (or at least, nobody who succeeded told the public).
answered Dec 20, 2011 at 21:11
-
15$\begingroup$ "nobody was successful" 2013/nsa update: "as far as we know..." $\endgroup$– LucSep 16, 2013 at 18:54
-
4$\begingroup$ I read the OP's question as asking specifically, the reasons why and how AES is resistant to plaintext attacks - and this answer doesn't really answer that at all (I don't personally consider brute-force attacks as "plaintext attacks"). The question could be rephrased as "how does AES's design prevent trivial attempts at deriving the encryption key from known plaintext?" - consider Engima/Bletchley Park's Crib-based approach to find "Wetterübersicht" in messages, for example. $\endgroup$– DaiJan 11, 2019 at 3:14
-
$\begingroup$ @Dai if you have a small key space, the brute-force trying of all keys to see whether your known plaintext matches the known ciphertext is actually doable, and a bit better than with unknown plaintext (where you need to check whether the deciphered result is something sensible). I'm not an expert on cipher design, so I can't answer your question. $\endgroup$ Jan 11, 2019 at 10:47
$\begingroup$
$\endgroup$
Well, the answer to 'why is AES resistant to known-plaintext attacks' is that, well, lots of really bright people have thought hard about how to break AES, and no one has come up with a practical way, either assuming known plaintext or chosen plaintext. See how-much-would-to-cost-to-brute-force-AES for a discussion on what it would take, given the current state of knowledge.
So, the answer to 'is it immune', the answer is, yes, as far as we know, it is.
$\begingroup$
$\endgroup$
Differential cryptanalysis is a form of a plaintext attack. The Wikipedia article on Differential cryptanalysis says that AES has been designed with resistance against this attack in mind. Wikipedia even say this resistance can be proven mathematically, but do not source it.
$\begingroup$
$\endgroup$
1
Since no one really answered the question:
AES is only resistant to known-text attacks if you always use a different randomized initialization vector (IV) for every single message.
To oversimplify a bit, AES combines the Key with the IV to produce the cipher, and the cipher is rotated in blocks throughout the length of the message based on the previous block. So long as the IV is unique to the message (it needn't be secret), then not only can the Key not be recovered, but the knowledge of matching plaintext-ciphertext somewhere in a message provides no information about anything anywhere else in the message.
On the other hand if the Key and IV are reused between messages then the same plaintext will lead to the same ciphertext, so you can potentially decrypt a message using a sufficiently large corpus of known matching plaintext/ciphertext pairs, even without ever recovering the key.
-
2$\begingroup$ (1) You're talking about AES with a mode of operation (CBC), but the question and the other answers just about the block cipher without the mode. Are you saying that the answer is different for AES with a mode of operation? (2) What definition of known-plaintext attack are you using? Whether the ciphertext appears random for every encryption with the same key should not make a difference to the attack. $\endgroup$ Dec 7, 2015 at 20:50
$\begingroup$
$\endgroup$
4
The classic attack using known plaintext essentially runs the encryption backwards and constructs the key. No brute force is needed, you just need enough matching plaintext and ciphertext, where "enough" can be as little as the key length (for sufficiently vulnerable ciphers). Resistant ciphers do internal mixing of the cipher state so this is not possible.
The first encryption system you ever thought of is probably to XOR the plaintext with the output of a pseudorandom number generator. This encryption system has only about 64 bits of hidden state, 8 of which are revealed by each encrypted letter. You get the idea.
-
3$\begingroup$ How do you come to your calculation of 64 bits of state, and how are 8 of those revealed? (Also, I think I thought of encryptions systems before I ever heard of XOR or bits/bytes.) (By the way, using a cryptographically secure PRNG is a secure way of encrypting, as long as you don't reuse a seed.) $\endgroup$ Dec 23, 2011 at 22:14
-
$\begingroup$ the classic random number generators you find in Knuth have only a couple integers as their internal state. $\endgroup$– ddyerDec 23, 2011 at 23:02
-
2$\begingroup$ That says more about the random number generator than anything else. Secure random number generators certainly don't have this property (they normally use outside entropy as seed - with continuous reseeds - and a looped secure hash function). That said, a random pad as cipher is certainly not resistant against known plain text as it will return the key stream data. $\endgroup$– Maarten Bodewes ♦Dec 29, 2011 at 18:49
-
$\begingroup$ Actually my first was xor with key1 directly (using mod when the text exceeded the key) followed by key2 for >> 64 bits of state but very weak. $\endgroup$– JoshuaDec 15, 2014 at 22:37
$\begingroup$
$\endgroup$
6
We can actually do one better than:
"lots of really bright people have thought hard about how to break AES, and no one has come up with a practical way, either assuming known plaintext or chosen plaintext"
Assume you have plaintext a that is encrypted into ciphertext z. AES has two steps that work together to thwart a known-plaintext attack.
The actual round key and sbox steps simplified for explanation purposes would be something like for key k, ciphertext z = sbox(a * k) where the sbox is a simple substitution through a lookup table. Every byte is replaced with the corresponding byte from the table.
Imagine AES encryption was equal to sbox(a) * k. A known plaintext attack would occur as follows: \begin{equation} sbox(a) \cdot k = z\\ k = \frac{z}{sbox(a)} \end{equation} The key has been calculated. However, AES is set up more like sbox(a * k), so a known plaintext attack would look like this: \begin{equation} sbox(a \cdot k) = z \end{equation} There is no way to isolate k because we need to know the value of k to know what the substituted value is. In other words, we have an expression a * k that we cannot yet solve for a number because we don't know k. An expression cannot be substituted in an sbox, so the key cannot be calculated. Hence, the known plaintext attack has been thwarted.
-
3$\begingroup$ Actually, if AES were that simple, it'd be easy; $k = \text{sbox}^{-1}(z) \cdot a^{-1}$. Of course, AES is actually considerably more complex; how do we know that there isn't a more complicated way of rederiving the key -> well, it comes down to what I said "lots of bright people have thought about it; no one has come up with a practical way" $\endgroup$– ponchoNov 16, 2018 at 4:33
-
$\begingroup$ @poncho, you have a valid point. My example was a huge simplification to make this easy to understand all. In reality, AES has steps after the sbox. So a more accurate, but still large simplification of AES would be as follows: $$z = {sbox(a \cdot k_1) + k_2}$$ $$sbox(a \cdot k_1) = z - k_2$$ $$sbox^{-1}(sbox(a \cdot k_1)) = sbox^{-1}(z - k_2)$$ $$a \cdot k_1 = sbox^{-1}(z-k_2)$$ $$k_1 = \frac{sbox^{-1}(z-k_2)}{a}$$ $$Where\ k_1\ and\ k_2\ are\ derived\ from\ key\ k.$$ I'm sure you can see now how the sbox thwarts known plaintext attacks. Please comment for more clarification. $\endgroup$ Nov 17, 2018 at 17:16
-
$\begingroup$ No, I don't see how your example proves how AES is immune to KPA. In your example, if we have two plaintext/ciphertext pairs $(a, z)$ and $(a', z')$, we have $z' - z = sbox( a' \cdot k_1) - sbox( a \cdot k_1 )$; a simple scan over the possible $k_1$ values will recover it (and $k_2$ can be easily covered again. Again, AES is actually considerably more complex; how do we know that there isn't a still more complex key recovery mechanism? I still conclude that my answer of "lots of bright people..." is still the only real answer we have. $\endgroup$– ponchoNov 17, 2018 at 19:11
-
$\begingroup$ Maybe I'm not understanding your question, but a "simple scan" over the possible $k_1$ values would not be very simple. In the simplest version of AES (AES 128 ECB) $k_1$ and $k_2$ would each be 16 bytes (128 bits) long. A scan of every possible $k_1$ value would have to go through $2^{128}$ (340 trillion trillion trillion) different combinations. Granted, this is a worst-case scenario, but still. On top of this, in AES 128 CBC, each cipher block is dependent on the cipher block before it. This would mean that there would be an additional variable that changes between blocks. $\endgroup$ Nov 18, 2018 at 23:13
-
2$\begingroup$ I don't know if there is an attack that has not been found yet. What I am saying is that the main line of defense against KPA has been the sbox. If not for the sbox, cryptographers would have successfully performed a KPA on AES by now. The reason is that the sbox ensures AES cannot be expressed as a linear equation. If AES could be represented in this fashion, then a system of equations could easily be solved for the key. $\endgroup$ Nov 20, 2018 at 3:07