# How to make a “zero knowledge” cache/key-value store

I'd like to use a possibly insecure cache for storing expensive-to-calculate sensitive information. My requirements are:

• If the cache ever gets compromised it should reveal nothing about its ids or values (except for the number of records/size of the database).
• If both the client and the cache are compromised, but not (all of) the ids, then attackers should not be able to get access to values they do not know the id of.

What would be a simple secure way of accomplishing this? I've tried to create a scheme matching these requirements:

1. Each client has their own strong password $P$.
2. A per-id encryption key is derived from the password: $K = HMAC(P||"key", id)$. (A HMAC with as key the password with the literal key appended and the actual id as message)
3. The plain text value $V$ is encrypted using AES-CTR into ciphertext $C$: $C = AES-CTR(key=K, message=V)$
4. Instead of using plain ids, they are one-way hashed: $I = HMAC(P||"id", id)$
5. The combination of $(I, C)$ is then stored in the cache.

To get a value from the cache we calculate $I$ and use it to retrieve $C$. We then recalculate $K$ and use it to decrypt the message.

Would this scheme be secure? Or is there a better way of solving this problem?

• This sounds like it could be very useful, perhaps as part of an InterPlanetary File System (IPFS). I look forward to good answers. – David Cary Feb 23 '16 at 18:52
• When I derive a key from the password, I prefer to use a key-derivation function (KDF) rather than a HMAC. – David Cary Feb 23 '16 at 19:03
• Using a human-generated password as the key of an HMAC is an extraordinarily bad idea. Use a password-based key derivation function instead of HMAC here. – pg1989 Feb 23 '16 at 21:32
• Perhaps password is a misnomer. I just mean some "secret" each client has, preferably of 256 bit entropy (e.g. 32 bytes from /dev/random). The reason I called it a password instead of a key, was to avoid confusion with the term key-value storage and the encryption key. – Daan Bakker Feb 23 '16 at 23:18
• I found out that this concept is very similar to "convergent encryption" as discussed in this question. The main difference being that I intended to use it as cache instead of general file storage. – Daan Bakker Jul 22 '16 at 16:00