views:

1495

answers:

6

What are the fundamentals to accomplish data encryption with exactly two keys (which could be password-based), but needing only one (either one) of the two keys to decrypt the data?

For example, data is encrypted with a user's password and his company's password, and then he or his company can decrypt the data. Neither of them know the other password. Only one copy of the encrypted data is stored.

I don't mean public/private key. Probably via symmetric key cryptography and maybe it involves something like XORing the keys together to use them for encrypting.

Update: I would also like to find a solution that does not involve storing the keys at all.

+3  A: 

Generally speaking, what you do is encrypt the data with a randomly generated key, and then append versions of that random key that have been encrypted with every known key. So anybody with a valid key can discover the 'real' key that was used to encrypt the data.

Brad Wilson
+11  A: 

The way this is customarily done is to generate a single symmetric key to encrypt the data. Then you encrypt the symmetric key with each recipient's key or password to that they can decrypt it on their own. S/MIME (actually the Cryptographic Message Syntax on which S/MIME is based) uses this technique.

This way, you only have to store one copy of the encrypted message, but multiple copies of its key.

erickson
Are there any security issues with this method? If I'm sending several files (each file with a different symmetric key) to the same list of recipients (call them A, and B). Can person A look at what the symmetric key (source text) and the encrypted form for person B is and determine person B's key if enough messages are sent?
Asa Ayers
Asa, it will depend on the algorithm used to encrypt the content (message) encryption key. Some algorithms could be vulnerable. I typically use RSA to encrypt the content encryption key, and there, the right padding mode can defend against plaintext attacks. I use OAEP whenever possible.
erickson
A: 

I think I thought of a solution that would work:

D = data to encrypt
h1 = hash(userpassword)
h2 = hash(companyPassword)
k = h1 concat h2

E = function to encrypt
//C is the encrypted data
C = E_h1(h2) concat E_h2(h1) concat E_k(D)

Then either person can decrypt the hash of the other person, and then combine them to decrypt the rest of the data.

Perhaps there is a better solution than this though?

Brian R. Bondy
+1  A: 

@Brian,

That solution will work, although it becomes unwieldy when there are more than 2 keys.

Brad Wilson
A: 

Thanks erickson and Brad Wilson, those seem like great methods because you can easily change either password without re-encrypting all data. My suggested solution didn't have that property.

Brian R. Bondy
A: 

In the more general case, a secret (in this application, a decryption key for the data) can be split into shares such that some threshold number of these shares is required to recover the secret. This is known as secret sharing or with n shares and a threshold of t, a (t,n)-threshold scheme.

One way this can be done is by creating a polynomial of order t-1, setting the secret as the first coefficient, and choosing the rest of the coefficients at random. Then, n random points on this curve are selected and become the shares.

Andrew
For his use case, secret sharing would be degenerate, as t = 1, and the "curve" would be the horizontal line passing through the secret. Also, note that its not important to pick the share points randomly. In practice, the shares are often issued in sequence: 1, 2, 3...
erickson