How do I implement Multikey encryption?

Question

I'm looking for an algorithm, by which I can encrypt a piece of data with n keys and that to decrypt I can use any of them.

I think I remember bitcoin using something similar for blocks, but now I cannot find something to use.

Answer 1

It's fairly easy:

1. Generate a master key with which to encrypt the data.
2. Generate a user key for each user that you want to be able to decrypt the data.
3. Encrypt the master key with each of the user keys and store all of the encrypted results.
4. When you want to decrypt, use the user's key to decrypt the encrypted master key record and use that to decrypt the data.

If you're using 128-bit keys with AES, you can simply use AES directly without a block mode (ECB if one is forced) to encrypt the master key with each user key, because the key fits perfectly into one block size. If you're using 256-bit keys, you should use a block mode such as CBC and store the IV alongside each record for decryption.

Keep in mind that such a scheme does not allow for access to be securely revoked from a user without completely re-encrypting the data, as a malicious user could keep a copy of the master key. Additionally, this will not scale very well for lots and lots of users (e.g. thousands), as your key set ends up being very large.

For encrypting the files themselves I recommend AES-CBC if tampering is not a concern. You can store the IV in the clear with the file data. If tampering is a concern then you should consider an AEAD mode which prevents meaningful tampering with the file data.

Answer 2

I mean, TrueCrypt does it by simply encrypting a short message containing a master key under N other keys; then any of those keys can potentially decrypt the master key which can decrypt the payload. If the master key is 128-bits then it is also the block size for a lot of block ciphers and you don't even need a mode of encryption, though you would probably want an authenticated-encryption mode just on general principles. (Even if you use an auth-encrypted mode for the payload, do you really not want to waste N * 128 bits up front in exchange for decrypting the potentially many-megabyte payload N times to see if your choice was correct? Nah, storage is cheap: so just do N auth-encryptions of the master key under different keys, then auth-encrypt the payload so that you know it wasn't messed up in transmission.)

If that doesn't work for you, then you have design constraints you've not communicated and we would need to know those. For example, if "then any of the parties can make a change to the payload in-flight, that's not what I wanted!" then we can fix that; in each encrypted master-key section, also store an HMAC of the encrypted payload under either your key or the master key.

Answer 3

This could be implemented as per the answer above or with Secret Sharing, such as Shamir's Secret Sharing. Wikipedia has a good article on it, but you want the 1 < t < n case - where t is the number of keys needed to unlock and n is the total number of keys. I'd do the t=2, n = 2 * number of "keys" you want, and count each "key" as two key portions from Shamir's scheme.

The reason each "key" you want is two key pieces is because the secret sharing schemes normally don't handle the t = 1 case (because normally if you want any of the people's keys to be able to decrypt, you just give everyone the same key).