Crypto-shredding a file by erasing the IV instead of erasing the Key

Question

Imagine an authenticated, encrypted file system, which uses AES-256-CTR to encrypt a 64 KB file sector, then uses HMAC-SHA256 to authenticate the 64 KB file sector (including the IV). IVs are 128-bit, randomly generated.

The global 256-bit encryption and 256-bit authentication keys are independent of each other, and are used across all files (i.e. no per-file keys).

The file system needs to be able to crypto-shred individual files, and needs to sustain 100,000 IOPS.

How would you implement crypto-shredding without deriving per-file keys per operation (or without caching thousands of derived per-file keys in memory)?

Instead of deriving per-file keys, would XORing the stored public sector IV with a secret per-file SALT be adequate? In other words, the random IV (which is stored on disk) would be XORed with a secret per-file SALT when encrypting or decrypting. Assume the per-file SALT can be erased when the file needs to be crypto-shredded.

This should avoid the need for 100,000 HKDF or PRF calls per second to derive per-file keys.

Crucially, since the system is garbage collected, this would also avoid having 100,000 derived per-file keys scattered throughout memory at any point in time, and avoid bugs related to the caching and versioning of these keys.

Crypto-shredding usually operates by erasing the key, but erasing the SALT used to generate the final IV seems to make more sense. I don't know if I'm missing something here?

Answer 1

No, just erasing the AES-CTR IV is not enough to reliably render the file undecryptable.

To see why, consider what happens if the AES key is later compromised, and the attacker also happens to know at least one AES block (i.e. 16 bytes) of the "shredded" file's plaintext content. They can then XOR this known plaintext with the corresponding part of the ciphertext to obtain a block of the AES-CTR keystream.

Running this block through the AES block decryption function, using the compromised key, will then reveal the input block (i.e. nonce and counter) used to generate this block of keystream. Incrementing and/or decrementing the counter will then let the attacker decrypt all other blocks of the file.

Ps. Similar attacks are also possible on all the other classical block cipher modes of operation (CBC, CFB, OFB, CTR). I'll leave figuring out the exact steps needed as an exercise. (The diagrams on the Wikipedia page I linked to should be helpful.) With CBC and CFB modes, the first block of the file cannot be decrypted without knowing the IV, but on the other hand, those modes allow all the rest of the file to be decrypted even without knowing any of the plaintext in advance.

Modern AE modes aren't generally any more resistant to such attacks, either, especially as most of them simply combine one of the classical modes (usually CTR) with some message authentication scheme, and can thus be attacker just like the underlying classical mode.

The take-home message from all this is that the IV is not a secret, and hiding it is not sufficient to protect the message from decryption by anyone who has the key. More generally, modern encryption schemes are generally designed with the assumption that the only secret parameter of the system is the key, and with the goal of remaining unbreakable as long as the attacker does not know they key. The flip side of the coin is that, if the attacker does know the key, these schemes generally offer no security guarantees whatsoever.