# Compute the AES-encryption key given the plaintext and its ciphertext?

I'm tasked with creating database tables in Oracle which contain encrypted strings (i.e., the columns are RAW). The strings are encrypted by the application (using AES, 128-bit key) and stored in Oracle, then later retrieved from Oracle and decrypted (i.e., Oracle itself never sees the unencrypted strings).

I've come across this one column that will be one of two strings. I'm worried that someone will notice and presumably figure out what those two values to figure out the AES key.

For example, if someone sees that the column is either Ciphertext #1 or #2:

• Ciphertext #1:

``````BF,4F,8B,FE, 60,D8,33,56, 1B,F2,35,72, 49,20,DE,C6.
``````
• Ciphertext #2:

``````BC,E8,54,BD, F4,B3,36,3B, DD,70,76,45, 29,28,50,07.
``````

and knows the corresponding Plaintexts:

• Plaintext #1 ("Detroit"):

``````44,00,65,00, 74,00,72,00, 6F,00,69,00, 74,00,00,00.
``````
• Plaintext #2 ("Chicago"):

``````43,00,68,00, 69,00,63,00, 61,00,67,00, 6F,00,00,00.
``````

can he deduce that the encryption key is "Buffalo"?

``````42,00,75,00, 66,00,66,00, 61,00,6C,00, 6F,00,00,00.
``````

I'm thinking that there should be only one 128-bit key that could convert Plaintext #1 to Ciphertext #1. Does this mean I should go to a 192-bit or 256-bit key instead, or find some other solution?

(As an aside, here are two other ciphertexts for the same plaintexts but with a different key.)

• Ciphertext #1 A ("Detroit"):

``````E4,28,29,E3, 6E,C2,64,FA, A1,F4,F4,96, FC,18,4A,C5.
``````
• Ciphertext #2 A ("Chicago"):

`````` EA,87,30,F0, AC,44,5D,ED, FD,EB,A8,79, 83,59,53,B7.
``````

[Related question: When using AES and CBC, can the IV be a hash of the plaintext?]

-

## migrated from programmers.stackexchange.comJul 16 '11 at 17:35

This question came from our site for professional programmers interested in conceptual questions about software development.

What mode are you using? If a stream mode such as CTR, you could get yourself into a situation where the key is not recoverable, but the plain text is recoverable. – jww Aug 23 '13 at 21:53

If I understood what you're saying, you're describing what is known as "Known-plaintext attack".

Modern ciphers are not susceptible to this kind of attack.

Quoting Wikipedia:

Modern ciphers such as Advanced Encryption Standard are not susceptible to known-plaintext attacks.

Of course, Bruce Schneier can break AES. Without knowing the cyphertext. Or the plaintext. Or the keys.

EDIT:

wvdschel, while I certainly wish you good luck, consider that if you solve this problem you'll be probably entitled to a Ph.D in computer science or mathematics. AES was designed to be extremely difficult to break (i.e. in the exponential order of the amount of bits) even if you know some minor details about the encrypted file.

Any attack that can lower the complexity from about 2 to the power of the bit-length of the key somewhat will be a great breakthrough. In the past, such attacks on DES (that merely lowered its strength by a few times) won their authors wide acclaim.

Read up on linear cryptanalysis of AES.

AES permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2^128 times more computational power than a 128-bit key. A device that could check a billion billion (10^18) AES keys per second would in theory require about 3×10^51 years to exhaust the 256-bit key space.

-
@Morons I don't understand. Rainbow tables doesn't find keys as far as I know - it precomputes hashes. AES is not a hashing function. I didn't understand your answer about salting either. AES is a symmetric key encryption system not a cryptographic hashing function. – Vitor Py Mar 11 '11 at 3:23
@Morons: You're not going to recover the key by brute force attack only using the entire resources of the solar system until it's all cold and dead, unless you're really really lucky. IIRC, AES encrypts units of 64 bits, so a rainbow table would need 2^128 entries, which you aren't going to be able to generate given said resources. The danger is that repeated plaintext will generate repeated ciphertext using AES naively, and that may give the attacker some information. – David Thornley Mar 11 '11 at 15:13
"Salting" with symmetric encryption is extremely important. Only, in symmetric encryption, the salt is called the Initialization Vector (IV). The IV is typically generated using a cryptographically secure PRNG. Different modes of operation will use the IV in different ways, but a typical way (CBC and others) is to treat it as the chained input (like a "carry" in addition) to the first block operation. If an IV is used to encrypt only a single plaintext stream, it is safe to prepend the IV to the ciphertext stream. – yfeldblum Jul 17 '11 at 3:50
@Morons is just wrong. With a random 128-bit (or 256-bit) key, neither rainbow tables, nor dictionary attack, nor exhaustive search, is going to recover the key within your lifetime. – D.W. Jul 18 '11 at 1:56
I'm sorry, but I have to downvote this. 1) The OP is describing a Ciphertext Indistinguishably attack, NOT a known plaintext attack. 2) Your answer of "Nah, everything's fine" is dangerously misleading without mentioning IVs, and making sure your PRNG has a good entropy source. – Mike Ounsworth Mar 15 at 1:27

That way there wont be any patters in your encryption. (There are other benefits too!)

http://stackoverflow.com/questions/5051007/what-is-the-purpose-of-salt

-
For encryption, the usual term is not Salt, but Initialization Vector or IV. en.wikipedia.org/wiki/Initialization_vector en.wikipedia.org/wiki/Block_cipher_modes_of_operation – Secure Mar 11 '11 at 9:18

For a block cipher with a n-bit key, if, given a plaintext block and the corresponding ciphertext, the key can be guessed in less than 2n-1 step on average, then that block cipher will be said to be "broken" and cryptographers will make a point of not using it. The AES is not broken (yet). So no worry.

A few things may still be said, though:

• Having a plaintext and the corresponding ciphertext allows an attacker to verify a potential key value.
• The 2n-1 value is actually half the size of the key space. The idea is that the attacker can try all possible keys, until one matches. On average, he will have to try half the keys before hitting the right one. This assumes that the key space has size 2n. You still have the possibility to reduce the key space: e.g., if you decide that your key is the name of a US town, then the number of possible keys is very much lower (there must not be more than 100000 towns in the USA). Hence, you get the promised 128-bit security only if your key generation process may indeed produce any 128-bit key.
• You apparently encrypt each value by stuffing it directly into an AES core. AES being deterministic, this means that two cells with the same value will yield the same encrypted block, and any attacker may notice that. In other words, you leak information about which cells are equal to each other. Depending on your situation, this may or may not be an issue; you should be aware of it.
• You do not say how you handle values longer than 16 bytes. This is not a simple issue. In all generality, this requires a chaining mode such as CBC, and an Initialization Vector (it depends on the mode; for CBC, a 16-byte random value -- a new IV for each encrypted value)(this can also fix the information leakage from the previous point).
-
According to your definition, AES is broken, since the computational complexity has been reduced by ~3 bits: schneier.com/blog/archives/2011/08/new_attack_on_a_1.html – deed02392 Mar 7 '13 at 9:58

AES is not as easy as just building a rainbow table. The first thing you have to realize is the table requires an initialization vector. As long as you're changing this on a semi regular basis building a rainbow table (which is not really realistic.) would take a very very long time. Orders of magnitude long. Since a typical rainbow table would be essentially 2 dimensions, you would essentially need a cube of result sets to figure out both the IV and key.

If you read Thomas Pornin's post he goes into pretty great detail as to what this means, in terms of brute forcing the result.

The realistic worry is that someone with access to the database would be able to inject a string from another field (presumably because you're not using a random padding value in the column per element. Or seeding. )

If you seed the value you won't have this issue, and the only (realistic) attack on the cipher-text itself is made much more difficult.

-

The answer: No, the AES key cannot be recovered in this scenario. AES is secure against known-plaintext attack. This means that, even if an attacker knows the plaintext and its corresponding ciphertext (its encryption under some unknown AES key), then the attacker cannot recover the AES key. In particular, the attacker cannot recover the AES key any faster than simply trying possible keys one after another -- which is a process that will take longer than the lifetime of our civilization, assuming that the AES key is chosen randomly.

P.S. I noticed that whatever you are using for encryption does not seem to use an IV. This is a security risk. I don't know what mode of operation you are using, but you should use a well-regarded mode of encryption (e.g., CBC mode encryption, CTR mode encryption) with a random IV. The fact that encrypting the same message multiple times always gives you the same ciphertext every time is a security leak which is better to avoid. You can avoid this leak by using a standard mode of operation with an appropriate IV. (You probably also should use a message authentication code (MAC) to authenticate the ciphertext and prevent modifications to it.)

-