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
$ididentities 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!