I'd like to use a key-value store (cassandra, redis, ...), but I don't trust the server.
The clients have a shared secret, and I'm using that to encrypt the stored values. But what is the proper way of encrypting the keys (not the crypto-keys, the key-value store keys)?
The store compares keys in queries, so each plaintext-key must have only one corresponding encrypted-key.
Obviously, if an attacker gets hold of the encrypted-key, it must be as good as impossible to find out the plaintext-key.
Less obviously, if an attacker can guess the plaintext-key, it must be impossible to get the encrypted-key without the secret. I don't want an attacker to be able to confirm if a certain key is present in the key-value store.
Collisions (different plaintext-keys with equal encrypted-key) should be so rare that they cannot be created on purpose by an attacker.
Symmetric encryption with Random initialization vectors or hashing with salts is prohibited by (1). A hash of the plaintext-key without salt does not meet (3).
I see two options:
encrypt with a static IV.
hash(secret || plaintext-key)
The first feels very much like improvising a hash function with a cipher. It would also allow decryption, which I don't need. Edit: Since the IV isn't random, plaintext keys with equal prefix will still have the same prefix in ciphertext, with may allow reasoning about the plaintext.
The later one is storing the hashed secret, but without the usual precautions, such as salting and key stretching. Edit: it is also vulnerable to Length_extension_attacks.