TODO

(Yeah, the presence of this paragraph means that the document isn't finished yet)

Preamble

Few consider the implications of laptop theft. If you have private data on your laptop (which would in example include your GnuPG private key), you should really really not have it lying around in an unencrypted location, which may easily be stolen. If you consider it this way, I wouldn't see an actual choice.
Anyway. It's your own descision whether you want encryption on your laptop. This document describes how I did it.

However, note that most of what is done in this guide may now be done directly in the Debian Installer. Simply note the structure and recreate it -- or use the guide for setting up encrypted LVM2 (which will make you overwrite your volume with urandom data -- you may or may not want this).

This guide is very old. It describes how to set up encrypted root while circumventing the Debian Installer's way of doing it. Really, in a new setup, you should use the Debian Installer's way of doing this.

This guide will remain here, deprecated, as a background story.

Description of the setup, when done

The setup is based on LUKS-aware cryptsetup and LVM2, with or without a portable keyfile. The guide aims to do this in a Debianish way, and doesn't require that you roll your own kernel -- the stock kernel will do. The keyfile can be retrieved from portable media either by having the keyfile on an USB Mass Storage Device (which is dedicated to the purpose) or on a CD (which could easily be credit-card sized).
The installation is done from another Debian installation on the same hard disk. This installation is then abandoned, and it's space is wasted. That is ugly, but the only applicate way to do this, as I see it. At some time I saw somebody working on ``partman-crypto'' that would enable this sort of thing to be done during the very installation of Debian. The hierarchy of devices is as so:
This is a flexible setup, since it in essence gives you ``root on LVM'', which is desirable even without the encryption layer. Also, the ciphers are block ciphers which guarantee that the disk contains ``at most constant less capacity'' -- data won't grow because they're encrypted, and you'll have mostly the same disk capacity.
You can use the LVM2 utilities to resize your logical volumes (but for this to be effective you want resizable filesystems on these logical volumes (ext3 is best supported) -- or you will need to recreate the filesystems in their new sizes and restore the data on them from backup). That means that you don't need to reinstall if you find out you made some partition too small.

0. Preparation

Take backup

Since this is a complete clean install, you'll obviously need some sort of data storage to restore data from. If you're serious about the security of the system you're about to set up, you'll also be serious about the handling of this backup.

Preparation of the disks

In order to prevent a so-called full-scale cryptographic attack, it's recommended that you write random data to your disk at first. Since that is a slow process you want to do it on a fast machine, or simply have enough time to do it on a slow such. If you use a livecd, you can do something like: 
shred -vn1 /dev/sda
This, however, does not put anything but some constant pattern into the device. Therefore to obscure the cryptographic contensts even further, you need to put pseudo-random data into the device, like this: 
dd if=/dev/urandom of=/dev/sda & PID=$! ; while ps -p$PID >/dev/null; do kill -SIGUSR1 $PID; sleep 3; done

1. Installation of unencrypted Debian

First you'll need to go through your usual Debian-installation, where you do a very minimal install with only two partions: Once the installation is done, you should install the necessary software. Also, you should use `install-keymap` to install your favourite console keymap. (But since you use a such, you probably already have a hard time living without it).

Packages needed

This guide will use some packages out of Debian unstable. Those should be listed here.
For generating passwords, you'll need: 
aptitude install sharutils pwgen gnupg
For doing the crypto work you'll need: 
aptitude install cryptsetup
To have LVM available you'll need: 
aptitude install lvm2

2. Making the devices

Using keyfiles

If you haven't got a secure (in the paranoia meaning) machine to generate the keys on, you shouldn't be using keyfiles just yet. Follow the instructions on adding keys to the LUKS device, later. For now, use a simplistic passphrase for the LUKS device -- that passphrase will later be revoked so that a more secure passphrase will be the only entry-giving passphrase.

Using straight passphrases

First you need to partition the disk so there's a partion to use as ``<Your encrypted partition>''. Use cfdisk to create the largest possible partition out of the rest of the disk space on the harddisk that will be installed to: 
cfdisk /dev/hda # (Or whatever your boot device is named)
If you're running off the stock Debian kernel, you probably can't reload the partition tables while booted. To check, see if Linux has seen the change in partitoning, which is reported to the kernel log that may be viewed by executing: 
dmesg
If it hasn't, you'll need to reboot, here.
These commands will create the devices under /dev that will be needed for the decryption of your encrypted partion. 
cryptsetup --verify-passphrase --cipher aes-256-essiv:sha256 --key-size 256 luksFormat <Your encrypted partition>
# Enter chosen LUKS passphrase
cryptsetup luksOpen <Your encrypted partition> cryptroot
# Prompt for LUKS passphrase
At this point, you have an unformatted and transparently encrypted block device available at /dev/mapper/cryptroot. You could mkfs.ext3 on this very device, and have an encrypted filesystem. To mount it, you'd of course need to make the /dev/mapper/cryptroot available by providing the dm-crypt layer with the passphrase using the above cryptsetup luksOpen call. But, that's not the purpose of this howto, where we'll rather create another layer on top: LVM2. 
pvcreate /dev/mapper/cryptroot
vgcreate encryptedvg /dev/mapper/cryptroot
lvcreate -nencswap -L512 encryptedvg
lvcreate -nencvar -L1500 encryptedvg
lvcreate -nencroot -L30000 encryptedvg

3. Making the filesystems and installing an OS into them

mkfs.ext3 -L /var /dev/mapper/encryptedvg-encvar
mkfs.ext3 -L / /dev/mapper/encryptedvg-encroot
mkswap /dev/mapper/encryptedvg-encswap
mkdir /target /target/var
mount /dev/mapper/encryptedvg-encvar /target/var
mount /dev/mapper/encryptedvg-encroot /target
Now, there's a choice of how to install the system that's mounted in /target.

Copying the running system

You can easily copy the running system into the new install: 
for elm in /*; do egrep "^/(proc|sys|target|tmp)">/dev/null <<< "$elm" && continue; echo "$elm ..."; cp -Ra "$elm" /target; done
<Accept some errors here>
rm -Rf  /target/etc/mtab
mkdir /target/{proc,sys,tmp}
That's the easy solution, but only applies if your current operating system is worth copying.

Using debootstrap

The more fancy solution might be to use debootstrap to bootstrap a minimal Debian system into the /target directory. This however requires that you have the debootstrap application available. 
debootstrap sid /target http://ftp.debian.org/debian/

Common to all methods

What ever you choose, you'll still need to do this: 
editor /target/etc/fstab # Rewrite the relevant filesystem devices to reflect the /dev/mapper/encryptedvg-* devices

4. The initial ramdisk image

Linux provides an ``early userspace'', which is supposed to be a sparse filesystem that's uncompressed into RAM, and used as a temporary VFS root, ``/''. Inside this initramfs, init is called, which is a wrapper to circumvent the natural order of the kernel load. That is, if you want to have a NFS root file system, you want to make your init script up the networking, connect to the server and mount the NFS volumes -- what ever you configure it to.
In this case, it's desired to have the initramfs image decrypt the lvm volume, asking the user for the decryption passphrase. This task is already provided quite easily by Debian's initramfs-tools, which is lucky, since construction of initramfs'es has seemingly been a tedious process.

/etc/crypttab

The Debianish way of getting the cryptographic options for mounting / depends on /etc/crypttab. But since we're using LUKS (which stores the cryptographic options in the partition header), we'll mostly be using this file for show: 
echo "cryptroot <Your encrypted device> none none" >> /etc/crypttab

Straight passphrases

If you want to simply be prompted for the passphrase at boot, you're almost good to go. When you install a new kernel, the program `mkinitramfs-kpkg` generates a new ramdisk suitable for the installed kernel, places it in /boot and puts a line into the grub menu.lst. Alas, if the package ``initramfs-tools'' (which contains the executable `mkinitramfs-kpkg`) was available at kernel install time, an appropriate ramdisk should be available. Otherwise, you should run something like the below. (Considering how the howto steps thorough this, it's highly unlikely that your image is tip-top). 
update-initramfs -v -u -k $RELEVANT_KERNEL_VERSION
If that fails, do the slightly more forcefull version below.

Inspecting the ramdisk image

When you have a ramdisk image, you should consider doing something like the following oneliner, to see if the ramdisk image is OK. 
cd /tmp && rm -Rf w; mkdir w && cd w && cp /boot/initrd.img-$RELEVANT_KERNEL_VERSION i.cpio.gz && gunzip i.cpio.gz && cpio --extract --file=i.cpio && rm i.cpio
When this is done, you stand in /tmp/w, where you see what Linux sees at entry into the early userspace filesystem. There's no shell (so you can't chroot into it), but the main executable is `init`, which is in the root. What you want to do is to ensure that the correct settings are recorded in conf/conf.d/cryptroot (which is generated into the ramdisk image on its generation, using information from the /etc/crypttab of the running system) Also, you should check that `cryptsetup` has been copied into sbin for execution on startup.
Also, since you may be running through this less-than-smoothly, the interesting script to look into the behaviour of is found in scripts/local-top/cryptloop As you can see in this file, the prompt for the LUKS password (the $cryptcreate command) is run directly on the console, in this case, since there isn't any sbin/cryptgetpw in the ramdisk image.
If you find some error in the ramdisk image, you should correct the settings from which the image was created (rather than edit the image itself and re-pack it... The ugly way). When the options are corrected, you should re-generate the image, which the following oneliner will help doing: 
update-initramfs -d -v -k $RELEVANT_KERNEL_VERSION; rm -f /boot/initrd.img-$RELEVANT_KERNEL_VERSION ; update-initramfs -c -v -k $RELEVANT_KERNEL_VERSION
If you end up generating ramdisk images, I suggest you use grub as your bootloader and use its editing function to divert the standard initrd line to a working backup initrd in /boot. That has saved me numerous times.
Also, your unencrypted partition has uses after all. Should you ever lock yourself out, your rescue partition is right at hand, and it can probably boot anyway. I haven't tried it, but since the cryptroot script tries to figure out what's required of it at boot time, you should be able to pass the Linux parameter ``cryptopts='' using grub. This should lead to the cryptroot script concluding that it isn't needed (its $cryptopts variable is empty), and skip its operation. Of course this alternative boot would require according adjustment of the root=-parameter. Otherwise Linux will panic in its not finding init.

With keyfiles

To use keyfiles on removable media, you'll need to do some implementing yourself. The Debian interface is as follows:

I believe that that file has moved away from /sbin where it surely didn't belong

So, to use symmetrically gpg-encrypted keyfiles as input to cryptsetup, a script that more-or-less interactively generates an gpg-decrypted key on its standard output is needed. This script is to be run by BusyBox (whose sh differs from bash) in the early userspace.
There is however another problem in this respect. The Debian initramfs doesn't contain any gpg executable, so there will be a need for an ``initramfs-tools hook'' in either /etc/initramfs-tools/hooks/ or /usr/share/initramfs-tools/hooks/. Use the below command to easily download my script, which is as straightforward as it gets: 
wget -O/etc/initramfs-tools/hooks/requiregpg http://static.kroat.skrewz.dk/requiregpg && chmod +x /etc/initramfs-tools/hooks/requiregpg

Skrewz' cryptgetpw

I implemented such a script, which will become available on this site shortly. It uses the uuid of the encrypted partition to determine the keyfiles' location on the removable media, whether that be an USB Mass Storage Device or the cdrom drive. It contains some workarounds.

5. Adding/removing keys or keyfiles

An advantage of LUKS is the ability for multiple passphrases for a single device. If you followed the howto to this point and want to add a keyfile-using passphrase to your LUKS device, this is the time.
It's assumed that you are running the secure setup at this point. That, amongst others, means that your / mount and your swap are running off an encrypted system. (Especially the swap part is important). Of course, it's now your paranoia should really kick in, since the settings that you decide on now will determine a lot of the security in the system.

Generating good keys

For passwords that you aren't supposed to enter via the keyboard, you should use as much of the character set to generate passwords from, to maximize the passphrase-space (the set of all possible passphrases by a certain length). This way, you can dramatically increase the number of passphrases. See the calculations in this page
To generate some good human-rememberable passphrase, do: 
pwgen -ync 12
To output a key for the internals of a keyfile, do this. You shouldn't store this on unencrypted media, and this command is somewhat irrelevant. But it serves to give you an idea of the complexity of the keys. 
head -c45 /dev/random | uuencode -m - | head -n2 | tail -n1
Rather, you should pipe this through gpg already upon creation. This command will prompt you for a passphrase, which should be of the type mentioned above. Since twelve letters of this type are hard to remember, you could write it down on a note that you keep really close untill you're certain you remember the passphrase.
Only if you're absolutely certain nobody has skimmed the note, you can keep the passphrase and burn (!) the note. The passphrase is the weakest point of the whole setup, so take appropiate precautions.
Remember too, that it is absolutely the opposite of a priviledge to know others' passphrases -- the only guarantee that some information can't be fetched out of somebody's head is if it hasn't ever been there). This also is relevant in respect to seeing your own gpg-decrypted key. 
head -c45 /dev/random | uuencode -m - | head -n2 | tail -n1 | gpg --symmetric --armor > /mnt/keyfile.asc

A bit of maths to prove key complexity requirements:

A passphrase of length 7 with words from the English language: 
grep "^.......$" /usr/share/dict/web2 | wc -l
# 23734
A passphrase of length 7 with words from the English language which have been subjected to one of five variations (aprroximate, doesn't compensate for overlapping words): 
calc "$(grep "^.......$" /usr/share/dict/web2 | wc -l)*5"
# 118670
A passphrase of length 7 generated using random combinations of English letters: 
calc "26^7"
# 8031810176
A passphrase of length 7 generated using the 64 letters of base64 (a-z, A-Z, 0-9, two extra characters): 
calc "64^7"
# 4398046511104
The kind of passphrases this guide recommends for LUKS passphrases (45 bytes encoded in base64): 
calc "64^$(head -c45 /dev/random | uuencode -m - | head -n2 | tail -n1 | wc -c)"
# 150306725297525326584926758194517569752043683130132471725266622178061377607334940381676735896625196994043838464
The kind of passphrases this guide recommends for symmetric passphrases for gpg (very approximate, based on base64' characters plus about 20 special symbols that may still be found on an English keyboard; doesn't take into account the difference between `pwgen -sync` and `pwgen -ync`, which reduces the keyspace significantly): 
calc "(64+20)^12"
# 123410307017276135571456
Suppose a cracker can attempt verification with a thousand keys per second. That may well be a little low set, and the times mentioned could easily be optimistic.
In a brute-force attack your passphrase, obviously the English words and variations thereof would be the first tries. Therefore, it can be assured that in such a setup, your attacker has found your English-word-variation key within the first two minutes of starting the attack.
If you however had your passphrase generated randomly from english letters, the same attacker would have exhausted half the keyspace in 47 days (that's a cryptographic meassure of average time to match, which assumes that you'd -- on average -- need to check half the possibilities to find the match). That's an immense difference. Think about it when you make your passwords. Oh and by the way, if you add another letter, you can multiply the quoted times by 26.
Going even further, the howto's suggested passphrases are found in approximately 2 trilion years (1.96×10^12) in the same setup where a thousand keys could be tried a second. That makes room for being pessimistic:
In the course of your lifetime (which we assume will be 100 years = 3155695200 seconds), the hundred-thousand-times better setup (that can probe 100 million passphrases every second) will have tried 315569520000000000 passphrases, which constitutes 0.00026% of the possible passphrases. That percentage is also the chance that the attacker has found a match within these hundred years of searching.

Simply silly deductions on maths

Obviously the actual encryption key of length 256bit will be significantly tougher to brute-force attack. That's interesting, because this cracking is what an attacker will need to do on your encrypted partition, if your keyfile hasn't been revealed.
The possibility of finding a such key with one million Earth Simulators (present day fastest supercomputer) each testing a passphrase per flop (very optimistic, the world's economy would collapse trying to do this) in the 100 trillion years that one theory about the end of the Universe holds is well below 10^-35 %. In short: A brute force attack is undoable.

Modifying the passphrases

To view the active passphrases of a device: 
cryptsetup luksDump <Your encrypted partition>
To add a new passphrase using your old passphrase: 
cryptsetup luksAddKey <Your encrypted partition>
# Prompts for existing passphrase twice
# Echoes ``Keyslot n unlocked'' for some n
# Prompts for new passphrase on standard input
# Echoes ``Command successful''
As you may guess, this makes it hard to add keyfiles, that are gpg-decrypted into the cryptsetup executable. Assuming that you're running off the encrypted partition now,

Finishing comments

Kernel options

Actually, this shouldn't be necessary. The initramfs' included modules should provide the necessary kernel features. The only requirement to the kernel seems to be its ability to start the early userspace, which seemingly requires a newer 2.6'er.
Of course, this ability is to be held in mind when rolling own kernels. Also, at least modular support for dm_crypt, lvm perhaps more (like USB mass storage device support and the scsi disk layer that it uses).

Tips for secure and nice usage

Errors and disclaimer

The mathematics are all theoretical, but they are somewhat linked to the real world. However, I disclaim all responsibility for their correctness -- although I am pretty confident in them. However, the greatest breaks against these would lie in their implementing algorithtms. However, in this respect, note that The US National Security Agency considers 192bit AES good enough for ``TOP SECRET'', and this is 256bit. Also, the implementation is the assumably best-scrutinized implementation, since it's mainline in an popular open source family of operating systems.
If you have any suggestions, corrections or complaints, I'm reachable at skrewz@skrewz.dk.