Ubuntu – How does FDE (Full Disk Encryption) work so quickly

dmcryptencryptionSecurity

I'm curious about how does Ubuntu's full disk encryption works under the hood. Here's an example:

Considering the following string as all the disk's content:

hello world

After applying some kind of encryption method it would look something like this:
(I've used Caesar cipher with an shift of +1 for this example, e. g. A → B; B→C…)

ifmmp xpsme

As I understand, when the computer is turned off, the drive's content would be the string above. But when it's turned back on, Ubuntu needs its content to be back again hello world in order to successfully boot.

What I don't really get is that in the real world the disk's content is way much more, and the encryption algorithm way more complex, and I find it difficult for the computer to completely encrypt/decrypt all of it in just a few seconds (it doesn't take longer to boot or to shut down).

How is this possible?

Best Answer

How does AES / Rijndael Encryption in general work?

This page has a fun A Stick Figure Guide to the Advanced Encryption Standard (AES) that looks easy to understand, though it looks to be 50+ images, for example these two:

enter image description here

and

enter image description here

It's far too much to duplicate it all here, but if you have to have an all-in-one image it's this one:

enter image description here


Or, there's a more compact explanation at http://www.password-depot.com/know-how/blowfish_and_rijndael.htm

The Rijndael encryption method is based on replacing, changing and performing xor operations on bytes. The method looks like this:

  • From the 128-bit key, Rijndael generates 10 keys of 128 bits each.
  • These keys are placed into 4x4 arrays.
  • The plain text is also divided into 4x4 arrays (128 bits each).
  • Each of the 128-bit plain-text items is processed in 10 rounds (10 rounds for 128-bit-keys, 12 for 192, 14 for 256).
  • After the 10th round the code is generated.
  • Each single byte is substituted in an S box and replaced by the reciprocal on GF (2 8).
  • Then a bit-wise modulo-2 matrix is applied, followed by an XOR operation with 63.
  • The lines of the matrices are sorted cyclically.
  • The columns of the matrix multiplication are interchanged on GF (2 8).
  • The subkeys of each round are subjected to an XOR operation.

The security level of this encryption method increases if Rijndael is performed several times with different subkeys.


How does Ubuntu's Full Disk Encryption work?

I believe it works by encrypting a partition with LUKS (default settings with AES), and then puts some volumes on it with LVM (like /, swap), and decrypts and mounts them at boot after you enter a passphrase. And there is a regular (not encrypted) boot partition that boots enough to ask for the passphrase.

the_simple_computer's Guide to Full Disk Encryption with Ubuntu (Updated June 28, 2015) says that's about how the default installer's encryption works, and mentions that dual-booting wouldn't work (at least not out-of-the-box), the drive must use MBR so "if your computer has UEFI, the distro will be installed in legacy BIOS mode so you can't use Secure Boot" and "also gives you a swap size equal to that of your system RAM (often unnecessary) and you have no choice over what kind of encryption is used."


How fast is encryption?

If you run cryptsetup benchmark it will run tests and tell you about how fast the encryption alone takes, watch for the (currently) default aes-xts lines:

#  Algorithm | Key |  Encryption |  Decryption
     aes-xts   256b    150.0 MiB/s    145.0 MiB/s

An average hard drive read speed could be 80-160 MB/s, so you won't be much longer than a regular read, and it's possible that the just-read sectors have already been decrypted while you're still be waiting for the hard drive to read more.

An SSD could possibly be faster, maybe 200-550MB/s, so you might notice it. But, random reads could be slower, and I've read that SSD speeds can slow down after use (maybe when the drive fills up completely and it has to start "erasing" sectors?)

How can the computer completely encrypt/decrypt all of the drive in just a few seconds (it doesn't take longer to boot or to shut down)?

It doesn't have to decrypt everything first. The encryption (LUKS) works on blocks of data, can randomly decrypt any block, and acts like a layer between the drive's encrypted data and what the filesystem sees.

When the filesystem wants to see any block of data, LUKS decrypts that block first and then gives the decrypted data to the filesystem. You first wait for the drive to read the block of data (just like without using encryption), and only have an extra delay for the decryption of that single block (or few blocks) of data - and if the decryption is faster than the drive can read, the decryption could be finished before the drive reads the next block of data.

So just like a regular filesystem does not need to read the whole drive to read a file, when encryption is added it doesn't need to read the whole drive either, and it doesn't make things a lot slower.

The data on the hard drive is always encrypted, so there's nothing to do at shutdown except forget the key.