How to lose your data with full disk encryption the easy way
In the last entry I wrote that some full disk encryption schemes could cause total data loss on occasions other than you forgetting your keys (or having the entire disk die). A commentator then suggested dealing with the key loss problem this way:
Many systems support multiple keys (e.g. dm-crypt). Just keep one sealed in a safe.
Unfortunately, this is a great way to increase your chance of total data loss (in one of the ways that I was thinking of). In fact any time that you see a disk encryption scheme that allows either multiple keys or changing the key you should be very, very wary. To see why, let's ask ourselves how a multi-key scheme can possibly work.
Barring exotic cryptography where you can somehow encrypt data once so that it can be decoded with several different keys (I don't think this is possible but I don't know enough to definitely rule it out), there are only two choices. Either the system stores multiple copies of the data, each decrypted by a separate key, or there is a level of key indirection going on; there is a single master key that decrypts the data and the user-level keys you use simply decrypt the master key. Since multiple encryptions consume space (and IO bandwidth) at a prodigious rate, you can guess which option most systems take.
(Using a master key also allows the system to use a very strong one, with many very random bits. This may be important since the master key is used to encrypt a lot of data.)
Any time you have a master key, one that you the user does not provide directly, the master key has to be stored somewhere. When a master key is stored, damage to just the parts of the disk where the master key lives means that you lose the master key, which results in the usual catastrophic data loss. Axiomatically the master key is not stored all over the disk, which means that damage to less than the full disk will lose the entire disk. How much damage is required depends on the specific master key storage scheme used by your specific disk encryption scheme, in particular how many replicated copies of the master key it keeps.
For obvious reasons, a resilient system should store multiple copies of the master key (and multiple copies of the master key for each individual user-level key, because you may only know a single user-level key). However, there is a rainbow book security tradeoff here; the more replicated copies you have, the harder it is to invalidate a user-level key. Also, only having one copy of the key is simpler for the programmers creating these systems and besides, assuming that reliable storage is someone else's problem is a popular move.
Now let's ask the obvious question: how many copies of the master key does dm-crypt keep? I'm afraid that the best answer I can determine, from the LUKS on disk format specification, is one copy. Possibly effectively less than one, in that it seems that there are two separate disk locations that both have to be intact in order to retrieve the master key for a particular user-level key. This means that you are one unfortunate disk sector error or misdirected write away from total data loss. I would not be surprised if this was typical of full disk encryption software in general, but dm-crypt is the only one I've looked at.
(Misdirected writes happen for various reasons, including kernel bugs.)
Why systems that allow you to change your key are equally problematic and dangerous is because the easiest way to implement this is also to use master key (whether or not the system admits this). With a master key, changing your key simply requires re-encrypting the master key with the new user key. Without a master key, you would need to re-encrypt (ie read and rewrite) the entire disk (and either insure that the re-encryption is not interrupted partway through or handle it somehow).