23
$\begingroup$

Common FDE software (TrueCrypt, BitLocker, dm-crypt) doesn't authenticate ciphertext stored on the disk. The commonly cited reason is "it would take too much space", reasoning that you would need an authentication tag for every sector and that would eat significant percentage of available space.

With 512-byte sectors and HMAC-SHA256 for authentication, you would consume roughly 6 % of disk space if each sector was fully authenticated. I could understand that someone would consider this amount to be too much, but if that's the case, you could simply truncate the HMAC tags, for instance to 64 bits (still better than nothing, right?), and use less than 2 % of total space.

With 4096-byte sectors, space is a complete non-issue, less than 1 % is spent on per-sector HMAC tags. Especially for AES-CBC-ESSIV where malleability is a significant risk, this seems like a price well worth paying.

Given that with CBC you need to re-encrypt the whole sector every time anyway, I don't see how authentication would matter even in terms of performance.

So, are there reasons for not using authentication that I'm missing?

$\endgroup$
  • 1
    $\begingroup$ But then you'd need to have non power-of-two sectors either on disk or in what you present to the OS. I doubt either will be happy about that. $\endgroup$ – CodesInChaos Nov 3 '16 at 22:45
  • 2
    $\begingroup$ Also you'd need a merkle-tree for proper auth. $\endgroup$ – CodesInChaos Nov 3 '16 at 22:46
  • $\begingroup$ Is there some attack that the extra authentication can prevent? An attacker can modify your (encrypted) disk and modify the data, but it'll decrypt as garbage; file checksums (e.g. ZFS or a file IDS) would detect this tampering. $\endgroup$ – Ian Howson Nov 4 '16 at 1:39
  • 2
    $\begingroup$ Some file systems have this feature. For example ZFS uses 256-bit hash. $\endgroup$ – v7d8dpo4 Nov 4 '16 at 8:32
  • 1
    $\begingroup$ @v7d8dpo4 ZFS can be configured to use SHA-256. At least ZFS on Linux appears to use a 32-bit Fletcher checksum by default (it calls it fletcher4). It can also be configured to do no checksumming at all. $\endgroup$ – a CVn Nov 4 '16 at 22:11
12
$\begingroup$

With 4096-byte sectors, space is a complete non-issue, less than 1 %

Problem 1: 10GB per TB is not a "complete non-issue" for many people.

Problem 2:

If the checksums are inside of their data blocks, there is a huge compatibility problem. The data per block is less than 512/4096, but many (really many) programs and kernel parts of pretty much all important OS rely on that. (either for working at all, or for speed. And exactly that number, not just because it's a power of two or something like that).

Given that someone adapts all kernel parts "below" Truecrypt etc., the other parts and userland programs relying on this would suddenly slow down extremly. If something before read block 1,2,3; it will now read 1,2,2,3,3,4; ie. two times the needed block count and (much more important) non-sequential => slow.

If the checksums are outside of the data blocks, ie. a full checksum block for each X data blocks ... let's say eg. 1 checksum block for each 256 data blocks. Then, for reading/writing 1 byte in block 1, the disk needs block 1 and 256. Again non-sequential to it's best.

And problem 3:

What's the attack scenario? Someone steals the disk and gives it back later? In this case, a single check run before using it normally again is enough. And for that, many file systems already have per-file checksums (not per block, but not really necessary). Meaning, per-block checksums are useless in the first place.

$\endgroup$
  • $\begingroup$ Problem #2 is probably insurmountable. Too much software breaks hard if you break the single sector write atomicity rule. Old IDE disks used to have a read long / write long that permitted direct access to the ECC bits. In theory you could have implemented it on those bits but at great cost to reliability. $\endgroup$ – Joshua Nov 4 '16 at 16:22
  • $\begingroup$ #3 - I'd be more concerned about overwritten bootloader assuming you don't use secureboot. $\endgroup$ – Maciej Piechotka Nov 4 '16 at 19:08
  • 1
    $\begingroup$ Storing the checksums in some location other than that of the data itself is one of the foundational ideas behind ZFS' use of Merkle tree data structures to ensure data integrity. Combining the fact that data in stored in one place and its checksum in another with ZFS' copy-on-write behavior, and using disks that implement proper write barriers, all but guarantees that any corruption will be detected (but yes, there is a performance trade-off; ZFS, especially on spinning rust, is not the file system of choice when high performance is required). I believe Microsoft's ReFS works very similarly. $\endgroup$ – a CVn Nov 4 '16 at 22:24
  • 1
    $\begingroup$ Problem 1 is rarely a problem. Storage is cheap; 1% is a tiny cost. Problem 2 is not really a problem: you want a new feature, you write a new driver for it. Time is a much bigger problem: integrity or even authenticity protection has only a tiny space overhead, but it has a significant time overhead, because no matter how you do it you need to read and write multiple blocks each time a block is read/written. $\endgroup$ – Gilles 'SO- stop being evil' Nov 7 '16 at 1:47
  • 1
    $\begingroup$ A late note to my answer: Of course block checksums are not completely useless - they are useful to detect bit rot etc. But that's not related to malicious attacks. $\endgroup$ – deviantfan Jan 11 '17 at 10:50
16
$\begingroup$

Authentication and probabilistic encryption are two desirable features which each take up a small amount of extra space. And you are absolutely right that the percentage of space consumed is of no concern in most scenarios.

But as the other answers also point out that means you can no longer fit a logical sector inside a physical sector of the same size. That is a significant practical problem.

In terms of reading it is not a major issue. For example if every 512 byte logical sector requires 592 bytes to be physically stored on disk, you could simply store every group of 32 contiguous logical sectors in 37 contiguous physical sectors.

In such a layout you have the small percentage of slowdown for sequential reads which is to be expected. And each seek is also slightly more expensive because you would need to read one extra physical sector each time you have done a seek.

The real problem is writing. Most of the time when writing a range of logical sectors the first and last sector will only need to be partially written. That means the encryption layer has to read the original, update it, and write it back. That costs expensive additional seeks. Moreover the encryption layer might not know beforehand which is the last sector to be written, so it might end up doing the read-modify-write cycle for sectors in the middle of the range to be updated.

But it gets worse. If the operation is for some reason interrupted (for example kernel freeze or power failure), the cycle may not have been completed, which can corrupt your data.

If the physical disk guarantees atomic updates, the logical layer would not guarantee atomic updates. Instead the logical layer would potentially leave you with a logical sector which produce read errors on every attempt to read.

If the physical disk does not guarantee atomic updates, it gets even worse. The last physical sector written could contain data related to two or more logical sectors. If it got corrupted because of a power failure during write, the logical layer would not only lose the logical sector being written but also other nearby logical sectors which were not even being written to at the time of the power failure.

Very similar problems exist at the file system layer, where one common solution is a journal. But introducing another journal at the block layer means more slowdown and extra disk space usage.

This overhead could be mitigated by moving the encryption to the file system layer. But storage encryption is difficult enough to get right as it is, integrating it with the file system layer makes it a lot more complicated and thus more error prone.

There is another layer of complexity once you realize that protecting the integrity of individual sectors is not even sufficient. If each sector is individually protected by a MAC (or similar) an adversary could selectively revert individual sectors to an earlier point in time.

By selectively reverting a subset of sectors the adversary can construct contents which does not match any earlier point in time.

To see why this is bad imagine a file was deleted and the sectors it covered were reused for a different file. The adversary could combine the metadata from when one file existed with the data sectors from when the other file existed. This means the adversary has successfully moved the protected data from one file to another. If one of the files was highly confidential and the other was one that you would happily share with anybody, the adversary would be able to trigger a leak of confidential data.

You could protect against this by computing a hash-tree over the disk and storing a MAC of the root of this tree. This makes updates even more complicated, and updating a sector is now going to take logarithmic time rather than the constant time we were used to.

The worst problem however is that you still need to protect the integrity of the crypto code. If the code to do all the cryptography is not protected, an adversary could simply modify that code to bypass all the security measurements. And not only the crypto code itself, but also all the code used to bootstrap the system to the point where it can start reading the encrypted disk needs to be protected.

$\endgroup$
  • $\begingroup$ About the hash tree: then comes someone taking a full disk image and writing it back at a later time... :) $\endgroup$ – deviantfan Nov 3 '16 at 20:30
  • 1
    $\begingroup$ @deviantfan Yes. But in that case the adversary can only write back an exact image of a chosen point in time. If the adversary can pick and choose sectors that can possibly be exploited to leak data. $\endgroup$ – kasperd Nov 3 '16 at 20:35
  • $\begingroup$ Yes ... (my comment was just meant to agree with your answer that the whole idea is a problem) $\endgroup$ – deviantfan Nov 3 '16 at 20:40
  • 1
    $\begingroup$ Your edit just made me realize some completely different (but important) for a program I'm writing :D Thank you; a shame I can't upvote multiple times. $\endgroup$ – deviantfan Nov 3 '16 at 20:47
  • 1
    $\begingroup$ @JonCallas But the best opportunities with SSD would be if the wear leveling, encryption, and file system journaling layers could be better integrated. It would be possible to achieve better security, reliability, and performance if these layers were working together. That is something which isn't possible with the current block layer interface. However I haven't worked enough with it to say what exactly the design of such a new interface would look like. $\endgroup$ – kasperd Nov 8 '16 at 22:01
14
$\begingroup$

So, are there reasons for not using authentication that I'm missing?

I believe that the real reason is not actually space, but time.

As you said, storing the tags would not require that much space. However, the tags need to be stored somewhere, and whenever you read the sector, you also need to read the sector containing the tags as well. So, unless you can magically increase the size of the sector (which the disk manufacturer can do, by formatting the disk media properly, but no one else can), you need to actually need to read two sectors when the OS asks to read one.

$\endgroup$
  • 2
    $\begingroup$ ... or you need to shrink the sector size by the size of the tag and report the new size to the OS, but this leads to awkward sector sizes of 496 bytes and the alike. $\endgroup$ – SEJPM Nov 3 '16 at 19:29
  • $\begingroup$ @SEJPM: not all OS's can deal with odd-sized sector sizes like that... $\endgroup$ – poncho Nov 3 '16 at 19:30
  • $\begingroup$ Those tag blocks could be cached by the FDE driver. This does increase the risk of data loss (because all writes are incomplete until their associated tag blocks are updated as well), but modern filesystems need to deal with similar issues anyway (such as write-reordering). $\endgroup$ – Rhymoid Nov 4 '16 at 10:25
  • 1
    $\begingroup$ Time is only one of the problems, and storing the tags isn't the main problem. The real problem is that you need to store tags for the tags, etc... and that chain is going to terminate somewhere and what do you do then? See kasperd and my answer. $\endgroup$ – Gilles 'SO- stop being evil' Nov 7 '16 at 1:45
  • 1
    $\begingroup$ @Gilles: that's a more valid criticism; yes, rollback attacks are harder to address. $\endgroup$ – poncho Nov 7 '16 at 20:06
7
$\begingroup$

The threat it protects against is uncommon

Encryption protects against an attacker who gains hold of the data. The typical threat is the theft of a laptop or a backup tape, the compromise of a remote backup server, etc. Who cares whether the attacker can modify the data? You aren't going to use that copy of it anyway.

Once the attacker has gained access to the compromised system, that system is no longer trustworthy. Once they've had access to your computer, it isn't really your computer anymore. Even if the data on it is integrity-protected, the integrity of the system itself is at risk. The attacker may have inserted a hardware keylogger or other spying device, for example. So usually it is not necessary to try to recover data from a compromised system.

Integrity protection protects against evil maid types of attack, where the attacker gains access to a system without being detected. These are a lot rarer than simple theft or (detected) remote compromise. It isn't worth protecting against a rare threat if it has a significant cost, and it's even less worth attempting to protect against a threat if you can't do it properly. And as I wrote above, in many scenarios, the integrity hardware itself may be compromised, which makes data integrity meaningless. But let's assume that the hardware isn't compromised. Can you protect the integrity of the data? That's not so easy!

It's usually impossible anyway

Confidentiality protection can be done with cryptography alone. The same does not hold for integrity protection.

How do you trust trust?

Consider a system with full-disk encryption. Despite the literal meaning of “full-disk”, there actually has to be some data in there that isn't encrypted, namely the necessary code to boot the system, disk and console drivers, code prompt for a password or other credentials and decrypt the data. This code doesn't need to be confidential, it's a part of the operating system that anybody can see anyway.

But when the goal is integrity or authenticity rather than confidentiality, you have a problem: the bootstrap code does need to be protected. Otherwise the attacker can replace the bootstrap code by a wrapper that pretends that everything is fine but in fact forwards all your data to big-brother.gov.oceania.

How do you do protect the bootstrap code? You can't use cryptography, because something has to verify the security the verification code before it can be used to verify the code. Catch-22.

If you do trust the hardware, then you can get integrity protection by putting the bootstrap code in ROM. Cryptography isn't needed since ROM code is physically protected. (This assumes that ROM is really ROM — that's the case on ARM platforms, but x86 typically boots from flash, which makes it more of a problem.) Typically, the ROM code is a tiny piece of code that loads a second bigger piece of code from disk or flash and verifies it before executing it, and that code in turn verifies and executes another piece, etc. This is called a secure boot chain.

Authenticty is not integrity

Assuming that you have ROM code that verifies the signature of a bootloader loaded from disk/flash before executing it, that only verifies the authenticity of the bootloader, not its integrity. Typically the ROM verifies a signature and not a hash in order to allow the bootloader to be upgraded — if the ROM verifies a hash then it might as well contain the bootloader code since only one version of the bootloader code will every be possible. But if the bootloader can be upgraded, then it can also be downgraded. In particular, if there is a security vulnerability in an older version of the bootloader, then the adversary can install that version and exploit the vulnerability.

With ROM alone, it's impossible to protect against such a downgrade attack. You need to have at least a little bit of mutable, persistent storage to record which versions of the bootloader are authorized. Flash memory is fine, if you can prevent the attacker from accessing that flash memory, which is not always possible depending on the environment. A TPM is the usual solution on a PC. Some devices such as some smartphones have a special flash partition called RPMB (Replay-Protected Memory Block, see e.g. 1) for this purpose.

If you don't have this mutable persistent storage then the best you can do is protect the authenticity of the data, not its integrity.

The cost is not just space overhead

Let's assume that you've solved the trust bootstrap problem. You assume that the attacker can't modify your hardware. It may or may not be a realistic assumption depending on the scenario, but let's go with it. And either you have the protected storage to detect integrity violations, or you've resigned yourself to only have authenticity protection. Now you want to work on your system and modify files, which requires updating their authenticity/integrity data. How does this work?

When the threat model is that an attacker steals the storage device and then accesses it, you only need resistance against chosen-plaintext attacks at most (the adversary may convince you to store certain files prior to stealing your disk), which is easy to achieve. In particular, a cipher mode where the IV is implicitly derived from the block location is ok, and that saves the cost of having to save the IV somewhere. That cost isn't just a matter of disk space, it's also a matter of having to update the location where the IV is stored, or having filesystem blocks that are smaller than the blocks of the underlying storage media.

When the attacker can see multiple versions of the storage (for example, they steal multiple disk-level backups), things get more complicated, even for confidentiality protection; for example you must never reuse an IV, because that leaks information about what data gets changed. Even letting the adversary know which blocks on the disk are changing leaks information; there's no miracle remedy for that.

For integrity or authenticity, the integrity data has to be stored somewhere, so you can't escape the overhead. But you need more than that. You also need to tie the integrity data to what it protects and to the overall version of the filesystem. So you can't just take a MAC of block_number || block_content: that would allow the attacker to substitute an older copy of the block — a block-level downgrade attack.

There's a standard solution to this: hash trees. Organize the blocks in a tree structure, where a block's parent contains the integrity data of its children. Every time a block is updated, its parent needs to be updated as well, and so on up to the root of the tree. If you have physically-protected storage, use it to store the integrity data for the root; otherwise the best you can to is to authenticate the root, which means that the filesystem can be downgraded (rollback attack), but at least it can only be rolled back to a valid older version.

The need to update integrity data has a cost. This goes beyond the simple arithmetic cost of having more data to store and load. It also seriously hurts parallelization and reordering. It's insecure to start processing data in a block before the integrity of that block has been verified (or if you do, you have to keep track of data dependencies and roll back any dependency on data that turned out to have been corrupted). Writes can't be reordered for performance anymore unless you fully trust the stability of the system and its power supply, because write reordering is based on the assumption that the data makes sense either way. If integrity data is written out of order and the system crashes, there's no way to distinguish legitimate not-quite-up-to-date data from an outright attack, unless you keep some information about old data around in which case you pay the cost of maintaining that extra information.

In most scenarios, it isn't worth paying that cost since you can't guarantee integrity or even authenticity anyway. In some scenarios, such as remote backup, there's a local trusted system that can verify the integrity of the backup, but that's a very different use case which typically isn't accessed through a filesystem interface. That's why encrypted filesystems rarely offer integrity protection.

$\endgroup$
2
$\begingroup$

The technical arguments (space /performance) are actually red herrings. Authentication can be implemented in many ways, and not necessarily on a per sector basis. It's mainly files that require authentication, not sectors anyway. MACs don't have to be stored alongside their relevant corset. Your 6% overhead is inconsequential in today's permanent storage market.

The actual reason is likely to be that disk authentication serves very very little purpose. OS file system integrity checking is all that is required for the storage device to operate. A file verification tool like TRIPWIRE can also be used. There is no serious man in the middle attack on a disk that you own. You won't be teleporting it to someone else allowing the spooks to alter it whilst passing through the aether.

Authentication requires a password just as does encryption. If you have one, you can reasonably count on having the other. If you have neither the spooks are stuck. Although in jurisdictions like the USA and China it's probable that they will obtain the passwords anyway, but there have been exceptions.

So it would have to be tampered with whilst believing that you have full control over it. So spy software installed on your machine. Therefore anything is possible and they just spoof the output from the reporting components to keep telling you that all is ship shape, whilst they have full control. We know from Snowdon that some disk firmware has been factory compromised as part the NSA Bullrun program. If you're faced with this level of budget /influence, there's not a lot you can do to circumvent it and this again undermines the need for authentication.

Though they probably just didn't think of it when they invented it.

You might get more authoritative comment by cross posting this to security.SE.

$\endgroup$
  • $\begingroup$ I basically agree, except for your judgement about the MITM probability. It's not uncommon to have an encrypted drive (container) on a USB thumb drive. If I lose the device, my data is safe. However, anyone who gets a hold of that USB stick, or any software on any host I plug it into, can easily alter any (encrypted) data they want on that drive. Of course, without the key, the alterations will be random ones only, but may still go undetected for some time. $\endgroup$ – JimmyB Nov 4 '16 at 15:30
  • $\begingroup$ @JimmyB I may have not sufficiently explained this form of MITM attack against a hardware device. The thief would have to nick your stick, alter it's contents (randomly or not) AND then physically pass it onto the person who you were originally going to give it to, convincing them that it came from you. Remember we're talking authentication on the physical storage device, not electronic copies in transmission. $\endgroup$ – Paul Uszak Nov 4 '16 at 23:32
  • 1
    $\begingroup$ The overhead for performance is not negligible. But the biggest problem is indeed that there's no point in paying it when you can't ensure the integrity of the integrity verification code. $\endgroup$ – Gilles 'SO- stop being evil' Nov 7 '16 at 1:49
2
$\begingroup$

In order to create anything but garbage sectors in an encrypted file system, you need to have the secret key anyway, so there is only little gain.

The only use case would be when you want to give data to others who should be able to read, but not modify it. That's only useful if you have run out of storage media so you cannot make more copies, want to distribute the data to multiple people who should get it in turn, the data needs to be encrypted in transit, and you do not trust the people in between not to silently modify the data before passing it on.

That doesn't leave too many applications.

This is a different thing from signing individual binaries, which has other uses.

$\endgroup$
  • 2
    $\begingroup$ “In order to create anything but garbage sectors in an encrypted file system, you need to have the secret key anyway” — no, just no. You don't need to know the content of a file to apply an “interesting” modification to it, for example flipping a privileged/unprivileged bit (and corrupting other data you don't care about in the process). $\endgroup$ – Gilles 'SO- stop being evil' Nov 7 '16 at 1:52
  • 1
    $\begingroup$ @Gilles, but all I can do without the key is flip a random selection of bits. If there is a "privileged" bit, then I have a 50% chance of flipping it, but at the same time I will also change the sector address of the first data sector, which is stored next to it, making the file useless. Without the key, I cannot even test what I just did. $\endgroup$ – Simon Richter Nov 7 '16 at 6:07
  • 2
    $\begingroup$ “improbably hard” — no, that's the point. If the file happens to contain a CRC, then yes, that makes the attack harder, but not necessarily impossible: it only takes about 2^32 attempts to get a CRC32 right, and that might take only a few minutes of computation. You're completely missing the point that the attacker doesn't need to know what the changed block is, they only need to get one small part of it right, and they can make a very large number of attempts. $\endgroup$ – Gilles 'SO- stop being evil' Nov 7 '16 at 20:00
  • 4
    $\begingroup$ @SimonRichter In many commonly used encryption modes it is possible to flip one bit of the cipher text and know with certainty that you have flipped one particular bit of the cleartext. CBC, CFB, and CTR are the first three examples that come to my mind. In two of those modes the flipped bit will also cause corruption to some nearby data, but not the block in which the adversary wanted to flip a bit. In CTR mode the adversary can flip any desired bit without corrupting other data. $\endgroup$ – kasperd Nov 8 '16 at 8:17
  • 1
    $\begingroup$ There happens to be a question on this topic today: crypto.stackexchange.com/questions/41325/… $\endgroup$ – Gilles 'SO- stop being evil' Nov 8 '16 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.