How does FDE (Full Disk Encryption) work so quickly?

Question

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?

Answer 1

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:

and

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:

---

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.

• There's more details on Disk encryption theory on Wikipedia

Answer 2

This will be a bit of a simplification, but I'll try to go through the process of accessing a file on an encrypted filesystem.

For example, let's say a the beginning of the encrypted filesystem there's a file table; let's say we want to read /foo.bar. So, the first thing we do is read the beginning of the partition, decrypt it, and look through it for the file we want; let's say it says the file starts at 0x10000000 bytes. So to read, we start reading from the disk at that location and decrypting it; similarly, to write, we can encrypt the new contents, and write them at that new location.

Hopefully this helps clear up any confusion on the process.

Answer 3

The processor uses dedicated instruction set. It is possible because of it, AES-NI. It enables fast encryption and decryption or you can say it cuts the overhead. It is fast because it is hardware implementation, as explained here.

You can check about performance impacts here and they are worth it for added security.

Answer 4

Modern computers can do billions of operations per second, so it doesn't surprise me that encryption and decryption are fast.

This is how I would intuitively rank how fast computers are at doing things:

1. Doing calculations within memory (especially L1 and L2 memory), extremely fast
2. Reading from local storage, less fast (solid state disks are faster than hard disks)
3. Reading from the network, even less fast.

The other key bit to understand is that the operating does not need to decrypt the entire hard disk to boot the system. Rather, the operating system knows how to decrypt only the parts of the hard disk that it needs on the fly, and the same goes for writing.

So intuitively, I am not surprised that full disk encryption does not have much of an impact on performance, since I imagine the bottle-neck to be the disk.

Of course, these intuitions don't always match reality. For instance, in reality, there have been cases where full-disk encryption has caused a noticeable performance hit. But usually these are solved after the developers go through a few rounds of developing optimisations.