8
$\begingroup$

This was a question that was posted on the information security exchange but was suggested I may get a better answer here.

The link suggested in the original post is similar, but I think a search index for a simple comparison here is potentially not efficient.

I have a scenario where text values that are considered sensitive (not passwords) need to be encrypted for persistence onto a database.

The key requirement here is being able to identify if a value being received has been received in the past.

One solution that is being considered is to Encrypt the each value using the AES encryption algorithm with the same key and IV to generate the same cipher for each value received making it easy to detect if this value has been received in the past. However I have concerns regarding the strength and security of this solution.

The amount of data to be encrypted is quite small, < 50 characters

So the question is, what other options are available to meet these requirements in a better way?

$\endgroup$
  • $\begingroup$ How many data items will be stored in the database? How efficient does it have to be to check whether a new data item matches one previously stored in the database? There are multiple solutions, with different tradeoffs between security vs performance, so you should edit the question to tell us as much as you can about the context. $\endgroup$ – D.W. Jan 5 '17 at 5:34
  • 3
    $\begingroup$ Don't compare cypher text - compare hashes. Create a one-way hash of the data (e.g. SHA-2) and compare it to the stored hash. If the hashes match then the content is the same, if the hashes are different, then the content is different (and you can encrypt the new content with AES). This will be significantly faster to check than encrypting to AES, and also remove the risk of an attacker being able to divulge the plain text. As other answers have suggested, a feature of a secure encryption implementation is to obfuscate messages so that identical messages produce different cypher text. $\endgroup$ – Luke Van In Jan 5 '17 at 13:10
  • $\begingroup$ @LukeVanIn Wouldn't the advantage you talked about (different output for same plaintext) be completely removed by storing the SHA? In addition to that - wouldn't that also be a potential security risk as some SHA hashes are public knowledge? (e.g. a file you downloaded somewhere might have a SHA you can find through e.g. Google) $\endgroup$ – Florian Wendelborn Jan 5 '17 at 17:31
  • $\begingroup$ @LukeVanIn This was an option I was considering, a type of hybrid creating a one way hash on the input and persist that along side the AES cipher then I should be able to use different IV $\endgroup$ – Andrew Conn Jan 6 '17 at 2:49
  • 2
    $\begingroup$ @Dodekeract Assuming the data is hashed without modification then yes, the attacker could just compare it against a set of well know data. This is easily solved using a "salt", which is some random data that is combined with the original data before hashing. The attacker would then need to know the hashes of the data using that specific salt. The salt for each record is unique, and is stored along with the hash. $\endgroup$ – Luke Van In Jan 6 '17 at 8:55
10
$\begingroup$

First, it is important to note that one important property of encryption is that you cannot determine if the same ciphertext is encrypted twice. However, assuming that you wish to give up on this property but you want it to be completely secure otherwise, then you still have to be careful.

Using regular encryption with the same IV is problematic. If you are using CTR mode then this completely breaks the encryption. If you are using CBC mode then if the first block is the same but the second is different, then you will be able to detect this.

The best solution is to use the AES-SIV or AES-GCM-SIV modes of operation with a fixed IV/nonce. These modes have the property that when encrypting different messages with the same IV, then you cannot learn anything apart from the fact that the plaintexts are different. Of course, if you encrypt the same message with the same IV then you get the same result.

$\endgroup$
  • $\begingroup$ "The best solution" - This is a quite good solution with good security and good performance and easy to implement, but depending on what you mean by "best", it's not necessarily the best. Using a different random IV/nonce for each ciphertext can yield even better security (leak less information), at the cost of worse performance (linear instead of constant time, to check whether a new item is already present in the database -- you have to try encrypting the new item under each possible IV/nonce and check whether the result is present). Perhaps it is worth presenting both schemes? $\endgroup$ – D.W. Jan 5 '17 at 5:35
  • 1
    $\begingroup$ Depending on the use case it could also be an idea to use also consider deterministic schemes for asymmetric message encryption (possibly augmented with the symmetric schemes mentioned by Jehuda Lindell, of course). $\endgroup$ – Maarten Bodewes Jan 5 '17 at 9:54
  • $\begingroup$ @MaartenBodewes thanks, I tried avoiding using the word "best" due to it's subjective nature, then I found I used the word in the title. Now corrected $\endgroup$ – Andrew Conn Jan 6 '17 at 4:34
  • $\begingroup$ Can't you use CBC if IV is a partial salted SHA256 of the message? IVs remain quite random/unique per message if you only have a few millions entries in your db. $\endgroup$ – Alain Tiemblo Dec 13 '17 at 9:51
10
$\begingroup$

Probably the best you can do is compute a privacy-preserving message authentication code (such as HMAC) of each value, using a randomly generated secret key (with, preferably, 256 bits of entropy or more).

As long as you keep the secret key secret, HMAC will be effectively indistinguishable from a random mapping from the input strings to the output hash values. Thus, the only thing an attacker can really learn just by looking at your database is whether any two values are identical (which you scheme reveals by design, anyway).

Note, however, that the security of this scheme rests on two assumptions:

  1. that the secret key (and/or the database itself) stays secret, and
  2. that an attacker cannot use your application as an oracle, by feeding it guessed input values and seeing whether it finds a matching entry or not.

If these assumptions are not met, this system is no more secure than just plain old cryptographic hashing — which is to say, it's vulnerable to brute force attacks if your inputs are potentially guessable, but may remain secure if the inputs are e.g. sufficiently long random strings.

Implementing secure key management is far from a trivial challenge, and not really within the scope of this answer. However, one important aspect of it is isolating, as far as possible, the systems that have access to the key from any systems that an attacker might compromise.

For example, if possible, you could store the key inside a hardware security module that only provides an interface for taking in byte strings and returning their MAC. You should also consider setting up some kind of rate limiting within the security module (or whatever system you decide to implement the MAC computation with), so that even if other parts of your system are compromised, the module is of minimal utility as an oracle.


It's also be possible to make you scheme somewhat more resistant to brute force guessing attacks, even if the secret key is compromised, by replacing (or combining) the MAC with a deliberately slow key derivation function like those recommended for password hashing (PBKDF2, scrypt, Argon2, Catena, Balloon hashing, etc.).

However, such key stretching methods are fundamentally limited by the fact that they also slow down legitimate MAC computations. Thus, for example, if your legitimate system needs to be able to process, say, 100 inputs per second, then an attacker will also likely be able to test at least 100 guesses per second (and probably more, since they may have access to more efficient special purpose hashing hardware and algorithms).

Thus, while key stretching is definitely something you should do, if at all possible, it's not very effective by itself unless your inputs already are fairly hard to guess. Thus, to maximize security, you really should combine key stretching with a secret MAC key.

(There are various ways to do that, but e.g. simply first running then inputs through a slow password hashing function, and then through HMAC with a secret key, should be perfectly fine, and would allow you to offload the final HMAC calculation to a separate security module.)


Also note that, unlike the cipher-based solutions suggested by Yehuda Lindell, the MAC-based solution I suggested above is not guaranteed to generate distinct outputs for distinct inputs. However, as long as the length of the final MAC output is sufficient — say, 256 bits or more — the odds of an actual collision ever occurring are astronomically small.

Also, unlike AES-SIV or other deterministic cipher modes, a MAC cannot be decrypted to directly recover the original input, not even if the secret key used to compute it is known. In your case, I would consider that a feature.

$\endgroup$
  • $\begingroup$ Depending on the use case it could also be an idea to use also consider deterministic schemes for signature generation. $\endgroup$ – Maarten Bodewes Jan 5 '17 at 9:55

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.