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?

  • $\begingroup$ This sounds like it could be very useful, perhaps as part of an InterPlanetary File System (IPFS). I look forward to good answers. $\endgroup$
    – David Cary
    Feb 23 '16 at 18:52
  • $\begingroup$ When I derive a key from the password, I prefer to use a key-derivation function (KDF) rather than a HMAC. $\endgroup$
    – David Cary
    Feb 23 '16 at 19:03
  • $\begingroup$ 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. $\endgroup$
    – pg1989
    Feb 23 '16 at 21:32
  • $\begingroup$ 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. $\endgroup$ Feb 23 '16 at 23:18
  • $\begingroup$ 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. $\endgroup$ Jul 22 '16 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.