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:
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.