Encrypted offsite backups - where to store the encryption key?

In addition to regular onsite backups (kept in a fire resistant safe), we also send tapes offsite once a month, encrypted with AES. So if our site is one day vaporised by an alien heat ray, we should at least have one recent backup to recover from.

Except that the 128-bit encryption key is only stored onsite. So in the case of a true disaster, we would actually be left with one encrypted backup, and no way to decrypt it.

Question: What is the best policy for storing the encryption key offsite?

Whatever method we choose needs to pass a security audit, so "keep a copy at home" is not adequate, and "keep it with the offsite tapes" obviously defeats the purpose of encrypting them in the first place! A couple of options we are considering include:

• A safety deposit box in a bank
• Stored in the cloud or on a geographically separate network in password-protected form (e.g. using software like Keepass or Password Safe)

Of course, the second option poses another question: how do we keep that password safe.

This is going to be awfully subjective. I think we'd need to know more about your industry and any specific regulatory requirements to give good advice. What might suffice for a small business in an unregulated industry probably won't work for a large business in a regulated industry.

Keeping the key in the safe deposit box may be sufficient, given that the bank is supposed to authenticate the parties who have access to the box (typically with photo ID against a list of authorized parties). There is also a physical key necessary to open the box. When you combine these attributes with the box being stored in a physically secure location it looks more like a good place to store the key to me. Personally, I worry more about tapes getting lost / stolen moving to or from the safe deposit box, not being stolen from the safe deposit box itself. Alternatively you could get a safe deposit box at another bank with different authorized parties named simply to store the key material.

You might look to having corporate counsel store the key, assuming you don't have in house attorneys.

To get geeky and technical, there are various algorithms that allow you to break a secret key into a number of pieces such that the cooperation of some required number of parties is necessary to reconstruct the secret (known as threshold schemes). I'm not immediately aware of any practical implementations of any of these schemes, but I'm betting there are some out there if you search hard enough. You could distribute key material to multiple parties such that some fraction of them, upon getting together, could reconstruct the key. Compromise of any individual piece of the key (or any fewer number of pieces than the threshold requires) would not result in compromise of the key.

Edit:

A quick search turned up sharesecret, a GPL'd threshold scheme implementation.

One rather obvious solution is to keep a copy of the key in a different off-site location. e.g. A bank deposit box or a another, completely independent, off-site storage company.

Depending on how rigid your requirements are you may find that leaving the key with the company directors, lawyers or accountants may be adequate.

A practical solution:

Generate a 4096 bit private ssh key on a USB drive. then Create a heavily encrypted file container using truecrypt, and use the ssh key as a 'keyfile' i.e. the encrypted drive is unlocked with the ssh keyfile. Mount the file container like a partition, and create a filesystem on it (i.e. mkfs.ext4.) Mount the partition, and write the password file you want to archive. Unmount everything, and send your usb key along with your archive tapes. The file container you've created, you can (fairly safely) put in an operations dropbox account, on a floppy disk (who would seriously look on it?) etc. Essentially, without the keyfile, it would be impossible to access the backup, and the keyfile stored offsite is useless without the encrypted partition you store...wherever.

This may sound like a complex solution, but perhaps it'll point you in the right direction. Alternatively, an encrypted flash drive may be sufficient.

https://www.ironkey.com/

http://www.pcworld.com/article/254816/the_best_encrypted_flash_drives.html

Whatever solution you go with, the most important thing is very clear, current instructions on what to do, say, if you were hit by a bus the same day alien zombies nuked your office. Something as simple as a "in case of disaster" packet that goes with your backups should be sufficient.