A while back I designed a protocol for en encrypted key/value service. My main goal was to minimize the value of a breached database by using cryptographic algorithms where a brute-force cracking would be infeasible for, say, 30 years. I was happy with the pattern I developed, but I'm no expert, so thought at least an informal review here might help me avoid dumb mistakes.

Here's the pattern, in brief:

  • Use SHA-256 with a salt to hash lookup keys. One salt applies to all lookup keys for consistency of lookup, and is deployed with the application, never the database

  • Use XChaCha20-Poly1305 (or, previously, GCM) to encrypt values, using a cryptographic random function to generate the nonce for each value, and store the result in the database as a single payload, formatted as $id$nonce$tag$ciphertext. It inputs a hash of the lookup key as additional data in order to prevent swapping values between lookup keys. The $id identities the key configuration used to encrypt the value, so that keys can be rotated (and algorithms changed). As with the lookup key salt, the encryption key is deployed in the application configuration, not the database itself.

  • The same encryption algorithm also encrypts the lookup key, using the same encryption key (but a newly-generated random nonce, always), so that when rotating keys, the lookup key can be hashed with a new salt. The resulting table configuration using a RDMBS back end is three columns: Hashed Lookup key, encrypted lookup key, and encrypted value.

  • Rotation can be performed by deploying a new key config with a new ID to the service. The config has a new lookup key salt, lookup key encryption key, and value encryption key, and may adopt different hashing and/or encryption algorithms. New records are encrypted with the new keys, but old records can still be decrypted with the old keys. A background process gradually decrypts old records with the old keys and re-encrypts them with the new keys, replacing the old records. Once all records have been re-encrypted, the old key config can be removed from the service.

One signifiant question: does it make sense to store the nonce along with the ciphertext? I've seen that pattern with older block ciphers and IVs, but have found less information about this pattern for a streaming cipher like GCM or XChaCha20, where there is more of an expectation of a shared counter when exchanging messages. That pattern makes a lot of sense for, say, a messaging platform, but less feasible for an encrypted database.

But other than that, how flawed is this design? Are there any obvious ways in which it could improved? Or is it fairly sensible?

PS: Holy cow is the term “key” overloaded!

  • 1
    $\begingroup$ There's no issue with storing the nonce along with the ciphertext. Also, don't roll your own! $\endgroup$ – forest Jan 18 at 6:42
  • $\begingroup$ Certainly not rolling my own crypto libraries (been messing with rust crypto), but am assembling the parts into a value to store as a single blob. $\endgroup$ – theory Jan 18 at 16:56
  • $\begingroup$ Nonces can generally be considered public data, so storing them with the ciphertext is totally fine and a common practice. For your encrypted data store, it may not be a bad idea to take inspiration from the ciphersweet design. $\endgroup$ – Frank Denis Jan 22 at 20:04
  • $\begingroup$ Yeah, ciphersweet looks interesting, though I'm strictly sticking to a key/value design for now, relying on hashing for the lookup key, and allowing no other kind of searching. $\endgroup$ – theory Jan 22 at 21:11

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.