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 ;-)