Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 9 down vote favorite
1

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?

share|improve this question
Don't forget that while the cipher is "immune" to known plaintext attacks, you can always abuse it is such a way that known plaintext becomes a problem again. For instance, see "padding oracle attacks" where known plaintext clearly is a problem. – owlstead Dec 29 '11 at 19:12
@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. – jbtule Apr 25 '12 at 19:30
@jbtule Incorrect, see the recent attacks on XML encryption. – owlstead Apr 25 '12 at 19:36
@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. – jbtule Apr 25 '12 at 20:28
@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. – owlstead Apr 25 '12 at 20:48

3 Answers

up vote 13 down vote accepted

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 right one).

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".

share|improve this answer
up vote 4 down vote

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.

share|improve this answer
up vote 1 down vote

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 cyphertext, where "enough" can be as little as the key length (for sufficiently vulnerable cyphers). Resistant cyphers do internal mixing of the cypher 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.

share|improve this answer
1  
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.) – Paŭlo Ebermann♦ Dec 23 '11 at 22:14
the classic random number generators you find in Knuth have only a couple integers as their internal state. – ddyer Dec 23 '11 at 23:02
1  
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. – owlstead Dec 29 '11 at 18:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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