Confidentiality and Authenticity of the Key in a Key-Value Store

Question

What, if anything, can be used to provide confidentiality and authenticity guarantees for the storage keys used to store data in a key-value store?

To be clear what I mean by the storage keys - I mean the "key" in "key-value" store - I do not mean an encryption key.

The key-value store is something like Amazon S3 and is not trusted.

The storage keys have to be considered to be just as sensitive as the value objects.

But the storage keys are used to retrieve data from the store so they must also have a construction which is repeatable.

I'm using PHP and libsodium (via ParagonIE's Halite) to encrypt the data and ideally I would use the same library to construct the storage keys.

A related question mentions HMAC, but I don't know if that is useful.

---

Based on the answers given so far, the following could be a good solution:-

use \ParagonIE\Halite\Symmetric\Crypto.authenticate
use \ParagonIE\Halite\Symmetric\Crypto.encrypt
use \ParagonIE\Halite\Symmetric\Crypto.decrypt

// put
map.put(
  authenticate(storage_key, secret_signing_key),
  encrypt(concat(storage_key, value), secret_encryption_key)
)

// get
ciphertext = map.get(
  authenticate(storage_key, secret_signing_key)
)
plaintext = decrypt(ciphertext, secret_encryption_key)
// ensure that the key that was hashed equals the key that was encrypted
assert(equals(storage_key, substring(ciphertext, 0, len(storage_key)))

return substring(ciphertext, len(storage_key)) // just the data

Answer 1

If I understood your goal correctly, consider following. Since you want to have "confidentiality and authenticity" of the keys, encrypt them. If you choose an encryption method that is not fast enough, consider using something other instead of map keys and store tuple of (original encrypted key, original value). For instance use a hash of the original key or, if this is critical for you from the security point of view, use a KDF key as a map key. So, consider following approaches:

map.put(encrypt(key), value)

map.put(hash(key), tuple[encrypt(key), value])

map.put(argon2(key), tuple[encrypt(key), value])

Of course the map should be able to deal with collisions.

Answer 2

If you're dealing with just one trusted computer and any number of key-value-store servers, then confidentiality is pretty easy. You want to use a PRF with a long enough output to prevent collisions. (HMAC with at least 256 output bits, for example.) The trusted computer can replace writes of each pair (k, v) with (hmac(secret_crypto_key, k), v). Likewise with queries for k.

By definition, PRF output is going to look random to anyone that doesn't know the key. Output is a deterministic function of the (secret) key and message (lookup key). It also isn't possible to determine PRF output without the secret key.

This is a one way operation. For HMAC you can't reverse the process even with knowledge of the secret key. That's not a problem for key-value stores unless you want to enumerate the original lookup keys.

If it is, then deterministic encryption is necessary. That's a very tricky thing to do. I don't think it is directly supported by libsodium. However, encryption can leak the length of the key unless the original lookup keys were padded to all be the same length. PRFs don't require fixed length inputs because all outputs have the same length.

---

If untrusted parties must be able to make queries without any trusted party, then there isn't a way to maintain confidentiality unless you know all original lookup keys come from a distribution with high min-entropy. (Which means that the most probable lookup key is still very unlikely. Unlikely enough to make guess-and-check attacks impossible.)

This same issue is present in unsalted password hashing. Applying a one way function is sufficient to protect users with unrealistically strong passwords. It doesn't matter for them whether the function used is fast or doesn't use a salt. Users with typical passwords, on the other hand, are even more vulnerable since password crackers only need to hash each candidate password only once to build a lookup table capable of targeting the entire user base.

You have the same problem with key confidentiality if any person can make the conversion between original lookup keys and confidential lookup keys. It doesn't matter if encryption or hashing is used.

One serious and common mistake is believing applying a one way function to data is sufficient to anonymize entries. Examples of low min-entropy values that people try to anonymize this way include names, dates, timestamps, street addresses, email addresses, and credit card numbers. Guess-and-check methods are an effective way to deanonymize things because the universe of possible inputs is too small or too predictable.

Someone like Amazon can build a database of matches to deanonymize lookup keys. There is no good way to work around that for low min-entropy inputs. Not even using a slow hash algorithm is a particularly good hack for this kind of thing.