Multi-boot with full hard drive encryption and pre-boot authentication
Before you read all this, remember that this technique is at least 5 years old -- it's probably much easier by now (see the other answers). (But it sure was fun to figure this all out.)
I did this a few years ago with Fedora 10 and Windows Vista to demonstrate how all the intricacies fit together. It was a bit involved (mostly because Windows Vista doesn't "play well with others" and doesn't like being installed second), but in the end I found a method that suited me. Your case is more complex because you have 3 existing OS'es and you want to add another onto your drive.
Because I've never attempted this on the magnitude of 4 operating systems, I'll leave most of it up to you (the actual re-partitioning and such) and will try to take the general security principles from my experience and apply them to your situation. Also note that in my case, I started from scratch on a drive I had erased. This was more an experiment than an expert exposé... so take a few things with a grain of "salt" (no pun intended) and don't hold me responsible. :)
Remember, these are just my notes. You will have to adjust them for your situation. So here we go:
Problems overcome by the method described here
My notebook’s hard disk could only contain 4 primary partitions.
Primary partitions are the only ones that OSes can be installed to (Windows, anyway).
Primary partitions are the only partitions the system can boot from
Each extended partition counts as a primary partition.
6 or 7 partitions may be needed.
TrueCrypt can’t encrypt an entire drive that has multiple partitions, OSes, and various file systems when it only runs on one
TrueCrypt doesn’t play well with Grub or any non-Windows boot loader.
Windows likes to be installed first and only on a partition flagged as “bootable” (or, if no partitions are flagged “bootable” at all)
Benefits in the end
After the initial boot loader prompt, mounting various encrypted partitions could be automated with scripts. (<3 Truecrypt)
Files can be shared between encrypted operating systems (with password).
Each and every partition is encrypted, even swap file.
How the boot loaders work together
We install and use Windows’ default boot loader to the MBR. This is what the computer will boot to first.
We install GRUB (Fedora’s boot loader), but not to the MBR. This will merely be available for us to boot to later.
We install TrueCrypt which takes over the Windows boot loader. TrueCrypt’s boot loader goes into the MBR. On boot, the user will authenticate with TrueCrypt then be taken to the Windows boot loader where the option Vista or Linux (actually GRUB) becomes available.
In the end, my boot process looked like this:
Diagram of full-disk encrypted dual-boot process (yellow boxes are encrypted partitions; padlocks are another layer of security)
Possible adjustments for your situation
I didn't use Truecrypt on the Linux side except to mount the Windows partitions. I'm not sure how to mount native Linux-encrypted partitions from Windows, so my setup was rather one-way. You might consider using Truecrypt to encrypt at least your Linux
/homedirectory and let native Linux encryption protect the/swappartition, for example. This might allow Truecrypt on the Windows side to mount your Linux files.Re-partition your hard drive in-place, or add another drive for Red Hat. The folks over at SuperUser probably know more about this.
Figure out how you're going to partition your hard drive ahead of time... you don't need as many partitions as I used.
Requirements
A computer with at least one hard disk you are willing to wipe clean (Back up your data first, of course...)
Installation discs of the OSes you wish to install
Gparted LiveCD or LiveUSB
TrueCrypt
EasyBCD to modify the Windows boot loader (There's a free version...)
Instructions
Back up your data. You are going to wipe the hard disk totally clean and reformat it very soon.
Reformat the entire drive. To do this, I use Gparted LiveCD. If you don’t want to use Gparted, Fedora 10’s installer comes with a partition editor. But, it’s a bit trickier. You’ll have to partially complete the Fedora setup in order to get to it, apply the changes to the disk, then exit setup because Fedora shouldn’t be installed first. (Windows Vista’s partition editor is NOT powerful enough. You cannot use it for this.) I strongly encourage the use of a Gparted LiveCD or LiveUSB.
I thought about how to split up my drive and after a while, I came up with this:
Partition layout for dual booting Fedora 10 and Windows Vista with TrueCrypt
I wish I had sized them differently in hindsight, but you can do it however you want. Each padlock indicates an encrypted partition. The yellow padlocks with “TC” are encrypted with TrueCrypt in Windows. The blue ones are encrypted by Fedora. As you can see, each and every partition - except, of course, the /boot partition - is encrypted. Partitions labeled in red are for Windows. Black is for Linux.
Okay, so this is a setup that works for me. Basically, you’ll want these things:
A primary boot partition to put Grub (the boot loader Fedora can install for you) - I recommend about 50 to 100 megabytes. Do not flag this as “bootable” when partitioning - Windows will complain.
An extended partition to hold all the “data” or “miscellaneous” partitions. This will hold your Fedora /home directory (basically the “My Documents” folder of Linux), Windows backup partition (optional), and your Linux swap file (highly recommended). The swap file should be at least as large as your RAM’s capacity.
A primary partition for Windows Vista to be installed to.
A primary partition for Fedora 10 to be installed to.
Partition your drive as such and be sure to format with the appropriate file systems. You can use the table above as reference.
Write down the sizes of your partitions (in order) and their filesystem. You'll need this during the OS installs.
Start installing Windows Vista. You’ll be forced to do a custom installation. Choose the primary NTFS partition you reserved for the Windows install. Don’t forget to load hard disk drivers - especially on laptops. If your Windows install hangs around 70%, then you need to install the SATA drivers for your laptop. Once drivers are loaded and you select the right partition, install Windows.
After Windows installs, boot into it normally and finish setup. Don’t spend too much time customizing things yet. Once it is running, shut down and insert the Fedora 10 DVD. Boot to that and install Fedora. However, take note of the following:
Be sure you choose to do a custom layout for your partitioning. Fedora will want to wipe things and create its preferred partition layout by default. Don’t let it do this. Make sure you go straight to the part where you can view and modify your current partition information.
Don’t format the NTFS partitions. Windows is on one of them.
Be sure to set the mount point for the small partition (100 MB?) to be /boot. -Check “Format as” and select “ext3.” You cannot encrypt this partition.
Set the mount point for the partition for your /home directory to… you guessed it: /home. Check “Format as ” and select “ext3″ then choose the “Encrypt” option.
Set the mount point for the partition for your swap file as /swap. Linux will have to format it and you should, of course, select “Encrypt.”
Set the mount point for the partition for your main Fedora install to be “/”. Check “Format as” and select “ext3″ then choose the “Encrypt” option.
Before continuing, ensure that neither of the NTFS partitions have a check mark next to them. If they do, they will be formatted and you’ll have to start over. Continue. Fedora will warn you it will delete all the data on the modified partitions. That’s okay. You may have to set your passwords now as well. Go ahead and do that.
Soon it will ask you about the boot loader. Tread carefully here. Do not write the GRUB boot loader to the MBR. When it says “Install the boot loader on/dev/sda1″ (the “sda1″ may be different) - keep the box checked but click “Change Device” and choose “first sector of boot partition” instead.
After that step, you should be home free. Finish up the install and reboot the computer. It will boot straight into Windows.
Once Windows loads, download and install EasyBCD. You’ll want it to easily modify the Windows boot loader. Add an entry to the boot loader: click “Add/Remove Entries” - choose the “Linux” tab, select “GRUB” from the dropdown, and name it something intelligent. Choose the partition that contains GRUB, not Fedora. Leave the checkbox unchecked.
Add the entry then try rebooting. You should now be able to boot into either Fedora or Windows! Boot into Windows again and encrypt it, as follows:
Install TrueCrypt and create a new volume. Choose “Encrypt the system partition or entire system drive.” From this point, you’ll have to choose the proper options. Read them carefully! I don’t remember the exact sequence, but you need to specify “Multi-boot” at some point. At the end it will ask whether Windows has its boot loader in the MBR or if a different boot loader is used (like GRUB). Remember: we're using the Windows’ boot loader (we want Truecrypt to "overtake" it).
Once you’ve finished the volume creation wizard, you’ll be asked to “Test” the system. It will restart for you. It should boot into the TrueCrypt boot loader where you’ll type your password. After that, it should load the Windows boot loader where you can boot into either Linux or Windows.
From here, finish encrypting the Windows system partition, then remember to encrypt any other NTFS partitions you made for Windows.
When you’re done, try booting into Linux. It should go to the GRUB boot menu where you can select Fedora or change your mind and go back to Windows. As Fedora boots, you’ll be asked for your password as it mounts the encrypted partitions.
Tl; dr (Too long; didn't read)
It took me a few tries to get it right with two OSes, and employed the use of software like EasyBCD, Truecrypt, and Gparted, but I was successful in the end... for 2 OSes. Good luck with 4. The key is to plan effectively. Size and format your partitions properly, then install operating systems in the correct order. (Usually Windows goes first.)
PS. Hm, For a simpler solution, though not quite what you asked for: have you considered running 3 of the 4 operating systems in virtual machines? You can encrypt the host machine, thus protecting the other 3 at the same time. (And if you're worried about losing the VHD files, remember you can fully encrypt the guest OSes, too.)
Necro'd for update:
This has become far easier now; the newest version of TrueCrypt is Linux aware, and allows dual booting schemes involving multiple partitions and GRUB.
Full instructions here.