When using AES and CBC, can the IV be a hash of the plaintext?

Question

[Originally on programmers.stackexchange.com with title: Can you encrypt with AES+CBC and search the encrypted data]

Basically, I'm going to go with Advanced Encryption Standard with either Cipher-Block Chaining mode or Cipher Feedback mode or Output Feedback mode (I haven't decided yet). Each mode requires an initialization vector. The thing is that I want to make the encrypted string "searchable" like this:

Suppose I have a list of database tables together with a "display name" for each table. Conceptually the list would look like this (I've used {xxx} to mean the encrypted form of xxx, and [IVx] to mean an initialization vector):

ENC_DISPLAY_NAME         | ENC_TABLE_NAME
------------------------ | -----------------
[IV1]{John's table}      | [IV2]{TABLE_3574}
[IV3]{Eric's list}       | [IV4]{TABLE_3100}
                         |
[IV5]{Darren's projects} | [IV6]{TABLE_2823}
[IV7]{Paul's contacts}   | [IV8]{TABLE_5843}

Now suppose that I want to allow a search on ENC_DISPLAY_NAME. (Equality searches are all that are needed.) I need to have some way of knowing what initialization vector is used on the display name I want to find.

I think that I should compute a 128-bit hash (maybe a CRC) of the display name, and use that as the IV to compute the encrypted string. That is, if I want to store "Darren's projects", I should do something like this:

AESKey key = ...;
String str = "Darren's projects";
CRCType crc = ComputeCRC(str);

BinaryString enc = crc.ToBinaryString ( ).Concat
    (EncryptWithAESandCBC(str, key, (IVType)crc));

INSERT INTO MY_TABLE(ENC_DISPLAY_NAME,ENC_TABLE_NAME) VALUES(enc, ...);

If I want to search for the string instead, do the same steps except the last, and then SELECT * FROM MY_TABLE WHERE ENC_DISPLAY_NAME=enc.

Has this been tried before? Are there any (security) risks?

[Related question: Compute the AES-encryption key given the plaintext and its ciphertext?]

Answer 1

A hash computed over the plaintext would have the right characteristics for an IV, as far as "uniform randomness" is concerned. This is for a cryptographically secure hash function, not a CRC. Rather, something like SHA-256. A CRC is in no way secure enough for cryptography.

However, the IV must be known to whoever will decrypt, so it must be stored along the encrypted message. If the IV is computed with a hash function from the plaintext, then this allows performing a dictionary attack on the plaintext (trying possible plaintext until one which matches the hash is found). Defeating dictionary attacks is already hard enough for passwords, which are meant to be secure and random-looking; so, for something as utterly non-random as a display name, you should really use an IV generated from a properly secure cryptographic random number generator, not a hash computed from the plaintext. It will not change your storage costs, since the IV must be stored anyway, regardless of how you generate it.

Answer 2

Short answer : IV must be random and sent in the clear.

You must be carefull not to leak information about the plain text in your hash. It must not be possible to get to the plain text with a rainbow table of your hash. So a salt value, stored in a configuration file, not the database, is in ordre.

With that being said, I suggest this :

• Use a random IV, stored like you do now
• store a salted hash of the plaintext data a another column
• search for the salted hash to retreive the random IV and cipher text

So in your example, you would have this :

NC_DISPLAY_NAME                                            | ENC_TABLE_NAME
-----------------------------------------------------------+------------------
hash(salt+"Darren's projects"), [IV5]{Darren's projects}   | [IV6]{TABLE_2823}

Of course, salted hash is not without risks. It is lower than what you what you were first trying to avoid, but still present. If that risk is to high, you could encrypt the plain text hash (with another AES key) in ECB mode and search for that. So your table will look like this :

NC_DISPLAY_NAME                                               | ENC_TABLE_NAME
--------------------------------------------------------------+------------------
{k1 hash("Darren's projects")}, [IV5]{k2 Darren's projects}   | [IV6]{TABLE_2823}

Doing the hash gives you the entropy (input whitening) equivalent to using an IV (but I don't have the math power to confirm it). Encrypting gives you protection againts rainbow tables and dictionnaries.

You know you will have a speed security tradeoff when brute forcing your search index will take longer than brute force the random IV encrypted ciphertext.

Answer 3

If you're going to put the hash of the content right there, then realize your encryption is going to just give you another copy of the data. If all you're using it for is a lookup, then all you need is the hash (barring collisions, anyway). So any attacker who is looking for a specific row based on its name can find it without knowing the key by just ignoring the encrypted part of the data and just looking for the hash of what he's looking for.

Now if the digest you're using is an HMAC, and not just CRC or a hash, you might be OK. But realize that you do need to be careful to not divulge additional information with it.