I want to store a large number of relatively short-lived symmetric keys

Question

Each encrypted blob will have a well-defined, but different lifetime. Some will be around for 5 minutes, some for a day, some for a week, none for over a month.

I would like to be able to "delete" the file by discarding the key, even if the file is no longer under my control, e.g. on a backup medium somewhere, or stolen by an attacker (oh my!).

On the other hand, I do need each key to persist in the face of a crash until its lifetime expires.

Confidentiality is more important than availability: "It's gone forever" is usually better than "Eve has it".

---

So I have this crazy idea:

• A 128 GiB file is generated from a secure PRNG. The seed is stored securely offline. (Eve gets the seed = game over)
• When a new key is needed, a random 32-bit number will be generated. (or 31 bits plus a G bit for the current generation.)
• This 32 bit number is an index into this keyfile where the actual key material is stored.

Advantages:

An attacker would have to copy the entire file to be able to decrypt files offline.

4 bytes is potentially easier to atomically store/erase than 32 bytes

The key file could be stored in a raw block device without filesystem layers.

Online key generation might require less entropy.

Disadvantages:

It may be more complex than simply storing a key from /dev/{u,}random in a file as it is generated.

Would the disk seeks expose a side channel? I plan to run the application exclusively on bare metal, so I'm not extremely worried about this.

The space occupied by the keyfile might be put to other (better) uses.

Would I be wasting my time trying to implement this because there is a well-known better way?

Answer 1

The only security improvement from your scheme (over the situation where you do not apply it) lies on the following:

An attacker would have to copy the entire file to be able to decrypt files offline.

The rest is just secondary considerations on performance issues. The core of the idea, from a "security" point of view, is that you make it difficult to obtain the whole key file through its sheer size. Indeed, there are two kinds of attacks that you worry about:

• Online attacks: the attacker subverts your server, and since the server can decrypt all data files, then the online attacker can do the same as long as he maintains control of the server.

• Offline attacks: the attacker grabs some data from the server and uses that to decrypt files after the attacker has been evicted from the server.

Your point is about making like harder for offline attackers, i.e. making them strictly less powerful than online attackers. I would then argue that your idea does not work well. Indeed, it is not true that the attacker would need to "copy the entire file". The attacker would need the whole file in order to be able to decrypt all files; but if he gets only 128 MB out of the whole file, he can still decrypt one file every thousands. Moreover, depending on how the attacker breaks in, "downloading" the entire key file might not be a problem for him. In particular, attackers sometime retrieve old, discarded hard disks from dumpsters: if the electronics of your disk failed, then you cannot easily wipe the contents, but a motivated attacker could recover the disk, replace the electronic board, and read the whole file. 128 GB are no bigger than 128 bytes under these conditions: that's just a disk, which fits in the palm of his hand.

There is a better solution here, which entails using some tamper-resistant hardware, e.g. a smart card or a hardware security module (the latter is much more expensive, but offers much better performance). That device will happily decrypt asymmetrically-encrypted blobs on behalf of your server, but it will never give its private key. In this setup, the device contains an asymmetric key pair (say, RSA); when a file is to be encrypted, a random symmetric key K is generated, and that key is used to encrypt the file with some symmetric encryption algorithm. The symmetric key is also asymmetrically encrypted with the device RSA public key. When a file is to be decrypted, the device is invoked to recover the symmetric key K and decrypt the file. K itself is kept in RAM only for the few milliseconds needed for encryption or decryption of the file data, and each file gets its own K.

By construction, an online attacker can use the device to decrypt files, but once offline, he has nothing left. This is a much more thorough protection system than assumptions on the alleged hardness of downloading some gigabytes from an Internet-connected server.