Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

[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?]

share|improve this question
    
This seems odd. Usually there is a plaintext index to a row that contains minimal descriptive information. Maybe your example isn't indicitative of your real problem but it doesn't look like you need to encrypt the DISPLAY_NAME. Is DISPLAY_NAME used for anything other then finding the correct row? –  this.josh Jun 17 '11 at 1:07
    
"Is DISPLAY_NAME used for anything other [than] finding the correct row?" Yes. This is part of a service that stores its persistent data in files and I have to change it to use a database instead. This persistent data is actually metadata for other tables (including users and privileges). So everything has to be encrypted, to prevent people granting themselves extra privileges. –  Null Pointers etc. Jun 17 '11 at 20:16
    
Can you use the filename as a row identifier? Or if the filename is not unique, the filename and enough of the path to make it unique. –  this.josh Jun 17 '11 at 20:55

3 Answers 3

up vote 11 down vote accepted

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.

share|improve this answer
    
It makes sense for storing passwords (which I'm going to have to store in the table as well) to use random IV's in the application that I'm doing. What I'm worried about is that the application (which knows how to encrypt and decrypt) may need to search the table for a particular display name, and that it would have to do that search by SELECT ENC_DISPLAY_NAME FROM MY_TABLE and decoding every ENC_DISPLAY_NAME until you find the right one. I'm thinking it would be faster to encrypt the name that I need and query the database for the encrypted string. –  Null Pointers etc. Jun 16 '11 at 17:15
    
But given a string like "Darren's projects", how will you find the relevant encrypted row in the database if the IV is random and different for each row ? My understanding is that you will need to encrypt the plain text (user input your are looking for) for each random IV of each row, and compare the encrypted blobs wich will take quite some time. –  ixe013 Jun 16 '11 at 17:23
    
I believe CBC mode IVs are supposed to be unpredictable, and not just unique. I'd have to look up the IV requirements for the other modes. –  jww Aug 23 '13 at 21:46

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.

share|improve this answer
    
I don't recommend storing a salted hash of the plaintext data, as that will allow anyone who gets access to the hash to mount a dictionary attack on the plaintext. In this case, since the plaintext is the display name and the display name has relatively low entropy, I think a dictionary attack is a significant risk. –  D.W. Jun 16 '11 at 17:47
    
You are right about low entropy, dictionnary and rainbow tables are real risk. But is there efficient way to search for a random IV cipher text from a plaintext, when each IV is different (as stated in the question) ? –  ixe013 Jun 16 '11 at 18:08
1  
yes, there is, but it is more complex. One way is to build an encrypted index. For instance, imagine building a hash table where the hash is a keyed cryptographic hash. In other words, there are n buckets, the string S is stored in the bucket cryptohash(K,S) mod n, and the entire contents of every bucket are encrypted. Then lookups are O(1)-time, and dictionary attacks are prevented. –  D.W. Jun 16 '11 at 18:26
    
Makes sense. I edited my answer with an encrypted hash, but I made it up from my self-educated crypto background. I will read on encrypted indexes (I beleive cryptohash is something like RFC2104?) –  ixe013 Jun 16 '11 at 20:40
1  
by cryptohash, I just meant a cryptographic hash function, like SHA256 or SHA2 or somesuch. As far as encrypted indexes, I'm not sure you're going to be able to find anything especially great to read on that topic. –  D.W. Jun 17 '11 at 4:17

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.

share|improve this answer

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.