Sunday, August 14, 2011

TRIM & dm-crypt ... problems?

Some SSDs (Solid State Drive) implement TRIM command which is used to inform the disk (block device) that sectors are no longer used. If you are using software FDE (Full Disk Encryption) with such device, TRIM could have some side and unexpected effects. Linux kernel 3.1 (with user space support in cryptsetup 1.4.x) will optionally support TRIM on dm-crypt encrypted disks.

This short article shows illustrative example what you can expect after you enable TRIM support with your encrypted disk.

Disk & Sectors

Disk (SSD, flash or similar device) is block device which uses blocks as atomic units. Device allows to read or write only multiple of blocks. All reads or writes of blocks are independent.

Because blocks can have different meaning in the encryption layer (as cipher blocks), I will always use "sector" in the following text (hardware sector can have different size but block encryption, as implemented in current kernel, always works with 512 bytes sector).

TRIM

TRIM is operation where upper layer (e.g. filesystem) informs the device which sectors are no longer used (do not contain valid data anymore) and that device do not need to keep data content.

In Linux terminology is this operation called discard. In SCSI world you can see UNMAP command. In principle, all these names describe the same operation.

Discard operation can be used for two purposes:
  • for Thin Provisioning (informs that data area can be returned to allocation pool)
  • for SSD operation optimization
We are mainly interested in the second case.

Internal architecture of SSDs uses larger blocks than sectors. These blocks must be erased before write can be performed and information about sectors which do not need to keep data is very useful for the drive firmware. Drive than can very effectively organize blocks such way that data fragmentation is avoided and the disk lifetime is maximized (also see wear-leveling).

Fig. 1: TRIM block rewrite


This is simple example what happens when SSD need to rewrite a sector with and without TRIM.

On the other side, TRIM is usually overrated. Drive itself should keep good performance even without TRIM, either by using internal garbage collecting process or by some area reserved for optimal writes handling.



Forensic analysis

Very important is that TRIM decreases ability to recover data after an admin error.

TRIM practically eliminates using of standard recovery and forensic analysis tools for data recovery of "erased" areas of disk.

Imagine a situation that you wrongly recreate partition table. This mistake is easy to fix but not when the data area is completely erased by previous TRIM command.

What really happens with the sectors after TRIM depends on disk firmware. It could be still possible to recover some data from the NAND chips.

Most of the SSDs do not define what read operation returns if sector was discarded. Usually it returns empty data (sectors full of zeroes) but without explicit support kernel cannot rely on it.

Example

Next figure shows 8GB disk partition with some pseudo graphical representation (every 512 bytes sector was represented by one pixel in original image).

Disk was wiped with specific pattern and test program later tags sectors according to detected data (zeroed sectors, non-random, random-like data). 
Detection of random data is only approximate, in fact the test uses check for number of bits set and trivial Chi-square test with nonstandard boundaries.


This partition contains copy of /usr and also it contains 512MB image of Truecrypt device (in file).

Fig. 2: Used fs image
Now the same but after TRIM operation executed with fstrim(8).
Tested SSD always returns zeroes after TRIM here.

Fig.3: Used fs image with TRIM


And yet again, now with all files removed from filesystem.
Fig. 4: Erased fs image with TRIM




It is clearly visible that TRIM did its job. Discarded areas depend on filesystem type (other filesystems on test system did not supported TRIM unfortunately).

Disk encryption

Disk encryption on the sector level is fully transparent. For example, filesystem can work with encrypted disk without any changes required. Encryption layer is simple inserted between underlying device and upper layers.

In other words, disk contains encrypted sectors which are decrypted and upper layer see virtual block device where sectors are already decrypted. The disk containing encrypted sectors is called ciphertext device, virtual disk with decrypted sectors plaintext device.

For explaining TRIM it is not important which algorithm and encryption mode is used (for more info see FDE description).

Important is that ciphertext data (encrypted sectors) cannot be distinguished from random data without key knowledge. If the ciphertext device is wiped off using random data (or sectors are at least once written though encryption layer) it is not possible to say which sectors contain data and which are unused.

Ciphertext device without using TRIM from Figure 2 would be just black box (all sectors have random data characteristic, disk was wiped before use).

Ciphertext of Figure 3 is more interesting. Here is the first problem - unused sectors are clearly visible (discarded sectors contains detectable pattern - zeroes).

Fig.5: Used ciphertext device with TRIM

And now the same with erased files. It is apparent that even without key we can say that disk contains almost no data and according to some metadata patterns we can even guess used filesystem.

Fig.6: Erased ciphertext device with TRIM
And now see how sector test looks like for ciphertext device and virtual plaintext device (note plaintext device is virtual device over ciphertext device - e.g. LUKS mapping).
Fig.7: ciphertext and plaintext device with TRIM



The TRIM command is forwarded directly to the ciphertext device. But reads from discarded areas are processed as the same as normal reads (thus decrypted) and for the plaintext device these are not empty areas but areas full of "random noise" data (in fact decrypted sectors with zeroes as ciphertext).

The upper layer must not rely on zeroed areas after TRIM even if underlying device announces such function. For dm-crypt it is guaranteed by setting "discard_zeroes_data" to zero always.

But if some forensic analysis tool tries to find something here... Good luck.

Conclusion?
  • If there is a strong requirement that information about unused sectors must not be available to attacker, TRIM must be always disabled.
  • TRIM must not be used if there is a hidden device on the disk.
    (In this case TRIM would either erase the hidden data or reveal its position.)
  • If TRIM is enabled and executed later (even only once by setting option and calling fstrim), this operation is irreversible.
    Discarded sectors are still detectable even if TRIM is disabled again.
  • In specific cases (depends on data patterns) some information could leak from the ciphertext device.
    (In example above you can recognize filesystem type for example.)
  • Encrypted disk cannot support functions which rely on returning zeroes of discarded sectors (even if underlying device announces such capability).
  • Recovery of erased data on SSDs (especially using TRIM) requires completely new ways and tools.
    Using standard recovery tools is usually not successful. 

If you decided to turn on TRIM for your device... You have been warned ;-)

10 comments:

  1. Which tools/functions need to read data from unused blocks (in the "plaintext device") and assume they are zeroes? I've never seen something like this. Doesn't every sensible FS read its own structures and only read data based on that (read: only used blocks) ?

    For the most common practical case (user wants all his files and metadata on the FS encrypted transparently) enabling TRIM is OK AFAICT, because information about unused blocks or FS type is not a big deal. And relying on data recovery is never a good idea. Backups are better :)

    ReplyDelete
  2. If one accepts that the security is not as good, for the reasons you outline, with encryption on an SSD, what is the best way to set up encryption from a performance and wear leveling persepctive? Is it better to not write random data to the drive first, as one would usually do? Leave some part of the drive unallocated (as some suggest)? Do a secure erase on the SSD first and then not write random data? Thanks for any help. I've been searching around a lot and asking questions, but can't seem to get a good answer to this question.

    ReplyDelete
  3. From what I understand, erasing an SSD by writing data to every cell (be it zeros or random bits) will deplete cell life across the drive by one write and, depending on the TRIM algorithm, possibly force TRIM to mark every sector as empty. Thus the penalty of erasure, random or zero-fill, is the same: the life of every cell is shortened by one write. Performance will not be affected, but drive life will be diminished by a smidgen.

    If you want to ensure plausible deniability, then you cannot use TRIM or wear leveling for reasons provided by the inline TrueCrypt links. Hopefully this will change in the near future and manufacturers and OS creators will design wear leveling and TRIM algorithms with plausible deniability in mind.

    If you are not concerned with plausible deniability, then from a performance perspective you are better off simply running a complete TRIM across the drive and skip erasing unless you suspect that sensitive unencrypted data was already written to the disk from previous usage.

    ReplyDelete
  4. Thanks turtle. So if I don't first write random data and am not concerned about plausible deniability, what are the remaining risks? The post above mentions that the filesystem type could be recognized. That's not a big deal to me. I think I saw elsewhere that you might be able to tell the size of deleted files. Is there other information that could leak or risks? Thanks.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  5. If you have not erased the drive before installing the encrypted system then old files could be recovered. TRIM does not securely delete files so you will have tho shred files just as you do on hard disks. Other than that, if you are confident no private data was ever stored on the disk in the past then skipping erasure and utilizing TRIM and wear leveling poses no problems other than the ones already mentioned.

    ReplyDelete
    Replies
    1. afaik you can't shred files like that, on ssds, the shred will just write new data on a different block because of the way ssds internally write data; if you really want the same data to be overwritten(like shred would do) you'd need to fill the entire disk but that simply does first a trim(or a block erase) on it anyway and then writes the new data in its place
      if trim is enabled just removing the file(s) should be enough, or to be sure that trimmed data is overwritten(u don't really needs this though) u'd have to fill the disk's freespace with data (the freespace on all partitions or even unpartitioned space which is already trimmed or marked as unused as such)

      Delete
  6. Thanks again turtle. Just to be clear on one point. If I erase the drive, then set up an encrypted system, then when you said I'd have to shred files, this would not apply to files on the encrypted system would it? Even if the file is not securely deleted, the leftover information there would still be encrypted. So the only thing someone could figure out is the size of the file? Correct?

    ReplyDelete
    Replies
    1. Unfortunately wear leveling makes it almost impossible to be certain that the whole drive is properly encrypted when you first encrypt the disk. Short of using forensic SSD analysis tools, you cannot be sure everything was encrypted. From the TrueCrypt wear leveling article:

      "TrueCrypt cannot reliably perform secure in-place encryption of existing data on such a drive; however, after the partition/drive has been fully encrypted, any new data that will be saved to it will be reliably encrypted on the fly."

      To my knowledge no one has beaten this problem without resorting to securely zeroing the disk prior to encrypting it.

      Delete