AES in ECB mode weakness

Question

In a project that I'm currently working on, we are encrypting some data using AES with ECB mode in a database. Each piece of data being encrypted is very small, no more than 10 characters long.

Very importantly, each entry of that database is encrypted using a different and unique key. Would we gain any security if we switched to AES with CBC mode in this specific scenario?

Also, imagine now that we use AES in ECB mode to encrypt the data in the database, but we now use the same key to encrypt every single entry. If an attacker breaks into our database and steals our data, how many entries would he need to exploit ECB weaknesses and be able to decrypt the information?

For this last scenario, I guess that what I want to find out is if an attacker can decrypt some AES ECB encrypted data if he only has, let's say, around 10 encrypted messages.

Thanks!

Answer 1

Given only what you've said, and assuming the keys are created and stored in a strong manner, using a different key to encrypt database entries mitigates the problem of ECB mode. Namely that identical plaintext, when encrypted with the same key, always outputs the same ciphertext. No security is gained by switching to CBC mode (assuming you can easily store all the keys securely, but see what @Thomas Pornin had to say about that). The practical gain by switching to CBC mode is that you only have to store one key securely. The IV's don't typically need to be protected.

In the second scenario where the exact same key is used for all entries in ECB mode, the advantage the attacker gains is that if he knows a plaintext/ciphertext pair, he now knows everywhere that plaintext appears in the entire database.

For example, lets say the attacker's own info happens to be in the database. He can look up the encrypted version of his gender. He now knows the gender of everyone else in the database (if the ciphertext is the same as his, he knows the entry is for a male, otherwise it is for a female). This same idea can be extended to other fields (age, first name, last name, etc). The key to this advantage is though that the attacker must have plaintext/ciphertext pairs.

Answer 2

The trouble with ECB begins when you encrypt two blocks with the same key. If every slot in your system has its own key which is ever used to encrypt only one block (which means that when you modify one of your pieces of data, you also use a new key), then there is no problem with ECB. If you reuse a key, if only time-wise (you update an entry with a new value, which is encrypted with the same key than the previous value), then you hit the ECB issues.

However, this begs the following question: if you can securely store that many keys, why would you use AES anyway ? You could store the pieces of data themselves at that place.

I suppose that your different keys are actually dynamically generated from a given master key and a kind of counter which is associated with each database line (e.g. an "autoincrement" field with MySQL). In that case, if the key derivation process, which combines the master key and the counter value into a line-specific key, is decently secure (e.g. this is HMAC/SHA-256, computed over the counter with the master key as key), then you could even dispense with the AES altogether: just XOR the generated line-specific "key" with the data to encrypt or decrypt. On the other hand, if the key derivation process is cruder, then there may be hidden problems, even with AES. Using similar keys with AES exercises resistance of AES against related-key attacks, and AES has not been designed to resist that (it was not part of the selection criteria).