3

I understand the the statement that "AES is not currently vulnerable to known-plaintext attack" but I assume that there is an implicit rider in that statement that should be read "when used in an appropriate mode AES is not currently vulnerable to known-plaintext attack".

Note: we do not currently do this and I am just trying to build an argument (if valid) to show why we will continue to not do this....

If we have a database that stores short strings (less than 256 bits). Each plain-text input needs to have the same cipher - this rules out use of nonces or IVs and any chaining that uses multiple blocks other than the two required to store the string.

We assume that an attacker can determine the original plaintext for any given cipher text (for reasons I wont go in to, but it seems like good practice).

In this case, where we have removed some of the additional inputs, and we are left with just the key, the known-plaintext and the known-cipher text: why is AES still safe? What am I missing in my understanding that means the algorithm cannot be reversed?

EDIT: The response from John Deters make it very clear that if the system is available to the attacker then they are able to "fish" for the plain-text:cipher pairs. But I am going to assume that we would notice such activity (i.e. the system logs usage and this cannot be subverted, may be an unsafe assumption but I am comfortable with it for the moment as I want to focus on areas outside of my control).

So I would rephrase the question: Assume we have given away / lost some of the cipher values to an external party who has no access to the system itself. Assume the third party can guess one or more of the plain-text values and associate those with their ciphers.

Are (and if so why) the rest of the ciphers still secure? Why cant the key be calculated and the rest of the ciphers decrypted? Does the whole key need to be determined?

  • Cause if an attacker has the plain-text and can get its corresponding cipher-text, he can't recover the key, therefore he can't decrypt a cipher-text for which he doesn't know the plain-text (Unless he's bruteforcing the key) – Mr. E Sep 29 '16 at 13:34
  • The part I am still missing is: why cant the attacker recover the key? What part of AES cannot be reversed? Does the whole key need to be recovered i.e. even if there were a stage that was not reversible, could not that stage be omitted and its output determined by reversal and then used as the input for future decryption? – user2195559 Sep 29 '16 at 14:07
  • It's in the inners of AES. Basically what it does is expanding your key to 11 different keys and then xoring, substituting, permutating and mixing with your plaintext to get the ciphertext. All of those steps are made to prevent an attacker from recovering the key with a known plaintext and its ciphertext. That being said if you have enough plaintexts+ciphertexts you could bruteforce it or if you have some way to abuse the impractical AES256 related key attack – Mr. E Sep 29 '16 at 15:39
  • How do the number of plaintext+ciphertext relate the speed to bruteforce? Is there a number at which the process becomes practical? – user2195559 Sep 29 '16 at 15:50
  • 1
    Thanks for the clarification. I think between you and John Deters I am pretty happy that I have understood enough to get to a laymans appreciation of the situation. – user2195559 Sep 29 '16 at 21:20
5

You've described an Electronic Code Book (ECB) system, which is inherently vulnerable regardless of the encryption algorithm used to encrypt the data. With an ECB system, an attacker doesn't care what cryptographic algorithm is used, he just passes plaintext in to the system, then compares the ciphertext results against the rest of the already encrypted data, looking for a match. It is irrelevant if the system encrypts the data with AES, DES, uses a SHA-256 hash, or even uses the plaintext as a key to look up a random number from a database.

Conversely, that means that this type of attack reveals virtually no information about the encryption used. Therefore, it isn't revealing any information that could be used to recover the key.

EDIT:

Based on your comments below, you're interested in what is called an "Adaptive Chosen-Ciphertext Attack", which is where the attacker can obtain the plaintext for any cipher message desired, and use it to attempt to recover information about the key, and then request further information based on what is learned from earlier iterations. This is the "most powerful" of the family of attacks on cryptographic algorithms. Encryption algorithms are specifically designed to resist the exact kinds of attack you're describing.

To have mathematical proof that an algorithm is secure against this is to pass an "indistinguishability test". Given two ciphertext messages and one plaintext message, and the knowledge that the plaintext was encrypted to create one of the two messages, the attacker must not be able to do any better than making a 50/50 guess which encrypted message is associated with the plaintext. Despite over 20 years of intense research by legions of well-respected cryptographers and mathematicians, no one has demonstrated the ability to attack AES-256 (or even AES-128) in this way.

Plenty of cryptosystems that use AES have been broken, of course, but those are due to other factors: weakness in protocol designs (the POODLE attack, the BEAST attack, etc.); weaknesses in protocol implementations (the heartbleed attacks, cache-timing attacks, etc.), and weaknesses in implementations that lead to side channel attacks, (the Bouncy Castle timing attacks, differential power analysis, etc.)

The strength of AES (and most block ciphers) comes from cycling the plaintext through "rounds" of encryption. Each round is where the bits of plaintext are scrambled differently according to the bits of the key. This scrambled data is then fed back into the scrambling algorithm again and again. After 10, 12, or 16 rounds of scrambling, the scrambled output is considered encrypted to the point where every single bit is indistinguishable from random data.

A different way to think of it might be to look at a chess board after a game has been played. Does the final state tell you exactly each move that was used to arrive there? To a novice, no, but a chess expert could probably figure it out. So you take that mixed up chess board, leaving all the pieces still on it and add more pieces and play another game on top of the previous one; mixing all the pieces together again and again, and repeat that 9 more times. Even a grand master chess player can't unwind the final state of the board after all those mixed up games.

Much research has been done using "reduced rounds" attacks on the algorithm, where they deliberately weaken AES by reducing the number of loops to the point at which they can identify bits of the key. For example, AES-128 normally iterates for 10 rounds, but instead they may iterate only 8 times, and then learn enough about the key so they can beat the indistinguishability test. But nobody has been able to unwind the full algorithm itself in such a way that they have learned anything about the keys.

  • This is a very good argument and makes it very clear that any system that consistently maps from plaintext to cipher text allows an attacker access to the protection system is vulnerable. But if we keep the original assumptions and assume that the protection system is not available but we allow the cipher-text and enough information to guess the plain-text for one cipher a public domain - e.g. we share it with a partner company who looses it. In that case: why cant an attacker determine the key from the given data? AES is "just" an algorithm and it looks like each step can be reversed? – user2195559 Sep 29 '16 at 14:03
  • @user2195559, I updated the answer to include information that nobody (so far) has been able to reverse the AES algorithm. AES was designed to be resistant against someone trying to do exactly that. – John Deters Sep 29 '16 at 18:08
  • Thats perfect. Thanks for taking the time to lay it out so clearly. The chess game analogy was the light bulb moment for me. – user2195559 Sep 29 '16 at 21:18
  • :-) As I was writing it, I began to contemplate assigning various chess moves as key bits from the scrambling algorithm, and wondering if it's possible to make a workable human analog encryption tool using a chess board (kind of like the Solitaire Encryption invented by Bruce Schneier, and as described in the book Cryptonomicon by Neal Stephenson.) – John Deters Sep 29 '16 at 22:09
  • 1
    This is what I was grasping for: XSL Attack en.wikipedia.org/wiki/XSL_attack . While the chess analogy seemed to work, it left a nagging doubt - for chess there are many possible routes from start to end but for AES there is only one and if there is only one and its reversible then its theoretically possible to solve and the only safeguard is the expense of the effort. ? – user2195559 Sep 30 '16 at 21:37

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.