Tamper resistant full-disk encryption
There are various problems with many of the common methods of applying full disk encryption (FDE) that isn’t always obvious right away. The common FDE programs also typically have a number of limitations or drawbacks that make them less than ideal.
One class of attacks one wouldn’t necessarily consider is called evil maid attacks (tampering with the ciphertext, altering the bootloader), another is comparing different versions of the ciphertext over time. One particular type of tampering attack is a ciphertext modification attack against certain implementations of CBC cipher mode, which allows the attacker to essentially replace parts of the plaintext by altering the ciphertext in a certain way (which however will randomly scramble the first block in the series that you tamper with). For most FDE variants you can see exactly which parts of the ciphertext has changed and which changes has been undone (a previously seen ciphertext block returns), and much more. There is also the risk of an attacker simply reversing selected parts of the ciphertext to a previous version, which in some cases could reintroduce vulnerabilities in software that is in the encrypted volume. Some methods of getting around the problems is highly complex, and don’t always solve all of the problems.
I’m suggesting one way of implementing full disk encryption that should be secure against a wide range of attacks, even against an attacker in full control of the storage space such as a compromised cloud storage host, both preserving secrecy/privacy and ensuring any tampering with the data can’t be undetected.
First of all we need to be able to encrypt blocks of an arbitrary size, because that’s one of the limitations with trying to implement efficient full disk encryption as the smallest writable block can have varying sizes. XTS mode handles this, has good performance and is widely used.
While it doesn’t allow you to tamper with it in a way that can control the plaintext (unlike CBC) one can see on the ciphertext when the plaintext have been reversed, and when used alone it don’t stop an attacker from reversing the ciphertext to a previous version or scrambling it (which could allow an attacker to reintroduce security holes in software, or to scramble plaintext undetected). So we need to add authentication to the encryption so that modified ciphertexts will be detected, and further add a method to make sure that no individual blocks can be reversed to previous states.
Exactly how it should be implemented isn’t my expertise, but the most simple (but inefficient) method would be to generate authentication tags through using HMAC on all XTS blocks, and then further HMAC that list of HMAC’s such that they can’t be individually reversed, and store it encrypted. The method I’m suggesting later will have some similarities to that method. Ideally I would want a type of authentication tag generation integrated into the XTS cipher mode, or some other efficient method of generating authentication tags. Another approach would be to generate something like a Merkle hash tree of the ciphertexts and HMAC that as the authentication method, which allows you to save space as you don’t need to store all the authentication tags (generating it might not be very efficient, however). Yet another option (in case it would end up performing better) would be to combine those two and use an authenticated version of XTS and generate a Merkle hash tree of the tags for storage rather than storing them directly. The ideal solution is some form of authenticated block cipher which can handle arbitary block sizes.
Then we need to make sure that any attacker can’t easily see what you have changed in the encrypted volume. To do this, I’m suggesting that each time you mount the disk as writable you generate a new encryption IV (or key) for that session, which is used to encrypt all blocks you edit. This IV is also used to generate the key for the encryption authentication for the session. All generated IV:s are encrypted with the master key, and there’s a means of tracking which block is encrypted with which IV (some form of database). The IV list is also authenticated together with the list of authentication tags such that modifying any single block in the volume, even replacing them with previous versions, would lead to the authentication of the ciphertext failing (as it would only validate if the the stored authentication tags for the latest version of that block verifies for that ciphertext).
To improve the security of this approach, one could use a form of ratcheting where each new IV or key is derived from the last key, a counter and fresh collected entropy. Using a counter together with the above approach of making sure everything is authenticated also enables you to ensure the entire volume is intact, and that nothing have been replaced with a previous version as all you need to see is that your software decrypts the volume successfully without warnings and that the counter is one number higher than last time, because an attacker can’t get your software to show a slightly higher counter value and also not warn about tampering without knowing your encryption password.
On top of that one can also add features like read-write access controls by adding in public key cryptography. Use a public key from a master keypair that is stored in the header, together with a signed ACL and signed public keys of everybody with editing rights. These keys would be required to sign the IV/key list as well, such that somebody who only have the decryption password but not a a keypair with editing rights can’t make any edits without the cryptographic authentication failing. Detailed ACL:s would require some form of support in the OS to not cause errors, potentially this could be done by treating sections with different access rules as separate volumes, some of which would be read-only.
One way to speed up detection of attemps to modify the ciphertext is random pre-boot verification of a subset of authentication tags. Checking a few hundreds to a few thousand tags can take less than a second, and has a high probability of detecting modifications if an attacker (or a disk error!) has caused any part larger than a few thousand blocks in a row being modified. After boot, on-access verification is performed and blocks which verification fails for is reported as corrupted to the OS.
Then further we need to make sure that an attacker can’t easily tell exactly which parts actually have been modified each time, and the easy way to do this is to randomly select additional ranges of blocks to reencrypt with the new session IV, which you didn’t touch yourself. Once a previous session IV no longer is used for any blocks (all blocks that was encrypted with it has been overwritten) it can be deleted from the IV list. Another way could be to randomly reorder sections of blocks, like reverse defragmentation.