0
$\begingroup$

Can I encrypt data with multiple keys and decrypt with one? To be clear, I am not saying encrypt a file, decrypt it, then encrypt it again with a different key. I want to encrypt it, then encrypt it again, then again, maybe even again. I want to know whether I can use only one key to decrypt. The key can change though, it doesn't have to be the same key (in fact it shouldn't be).

I need a smart way to update the key to the new key, depending on how many times the data was encrypted. Also, the only way to get the new key is to have the old key... Is this possible? Is there an encryption algorithm that can be stacked multiple times and be decrypted by one key (and can I create that key)? Either this can already be done, or I am crazy--remember, I'm new to this...

Previously handled comments on StackOverflow:

"What's the point of encrypting multiple times? Properly encrypted data is indistinguishable from random noise."

I'm not trying to make it more secure by doing this...

"Do you want to perform E(k_n, msg) once with one of many possible keys then E(k_d,ciphertext) to get the ciphertext? Or do you want to perform E(k_1, E(k2, ... E(k_n,msg) ... ) ) as the encryption?

The latter, except I don't want to do encrypt with all keys all at once. I want E(k_1, msg) ... some time ... E(k_2, encrypted_msg) ... and so on, but I want to know if I can decrypt with one key after however many encryptions (and how to get that key).

"Consider: 'I really want a smart way to update the key to the new key'."

Yes. And, of course, the encrypted file will change during the process.

|improve this question
$\endgroup$
  • $\begingroup$ Demonstrably, choice of the key for the second encryption requires knowledge of the deciphering key for the first encryption. If it did not, one without the first key could encipher with a new second key, then decipher and get the original plaintext, contrary to the goal of the first encryption. Is that OK? $\endgroup$ – fgrieu Dec 18 '17 at 8:11
  • 3
    $\begingroup$ Probably there is no construction like the one you are imagining. But the real question is: What is your actual goal here? This question seems quite likely to be a XY problem. You are asking about your own solution to some problem we don't know instead of asking about the actual problem. $\endgroup$ – tylo Dec 18 '17 at 13:02
  • 1
    $\begingroup$ My comment to the original question on SO: "It would help if you provided what you are trying to accomplish." $\endgroup$ – zaph Dec 18 '17 at 13:13
  • $\begingroup$ fgrieu 11, I don't know how someone would get the new second key, but yes, I would like to require possession of the first key in order to get any other ith key. $\endgroup$ – slo_burner Dec 19 '17 at 3:35
  • $\begingroup$ I'm closing this question as it isn't clear what the system is supposed to do (i.e. it focuses on the how rather than the what). See tylo's comment. $\endgroup$ – Maarten Bodewes♦ May 23 '19 at 9:30
2
$\begingroup$

Maybe this schema will suit your needs, even though it is not exactly what you asked:

Encrypt your plaintext $M$ with a symmetric key $K$, producing $\{M\}_K$. Then encrypt $K$ with $K_1$. Store $\{K\}_{K_1}||\{M\}_K$ (with $||$ being the concatenation operator).

Then, when you want to update your encryption key with $K_2$: Decrypt $\{K\}_{K_1}$ and encrypt it with $K_2$ (you will need to know $K_1$ and $K_2$ for this step). Update the header of the stored file by overwriting it with the new value, obtaining $\{K\}_{K_2}||\{M\}_K$.

Repeat as many times as you wish, obtaining $\{K\}_{K_n}||\{M\}_K$. At each encryption step $n$, you will need the previous key $K_{n-1}$ and the key $K_n$. You never have to decrypt $\{M\}_K$.

|improve this answer
$\endgroup$
2
$\begingroup$

Here is a candidate system, based on an ordinary message cipher $\mathcal E_\kappa(p)$ and $\mathcal D_\kappa(c)$ so that $\mathcal D_\kappa(\mathcal E_\kappa(p)) = p$ and $\mathcal E_\kappa(p)$ is indistinguishable from uniform random noise to anyone who doesn't know $\kappa$.

Let $k_i$ be the $i^\mathit{th}$ encryption key, let ${E^i}_{k_i}(x)$ be the $i^\mathit{th}$ encryption function, let $k$ be the decryption key, and let $D_k(x)$ be the decryption function. We want to define $E^i$ and $D$ so that $$D_k({E^{n-1}}_{k_{n-1}}(\cdots({E^1}_{k_1}({E^0}_{k_0}(x)))\cdots) = x,$$ but otherwise we want all the intermediate ciphertexts, ${E^i}_{k_i}(\cdots({E^0}_{k_0}(x))\cdots)$, to be indistinguishable from uniform random noise to an adversary who does not know $k$ or the $k_i$.

To this end, define

\begin{align*} {E^0}_{k_0}(x) &= \mathcal E_{k_0}(x), \\ {E^i}_{k_i}(x) &= x, &&\text{for $i > 0$.} \end{align*}

Decryption is easy: the decryption key is simply $k_0$, and $D_k(x) = \mathcal D_k(x)$.

If this doesn't satisfy your needs, you will need to be more specific about what your needs are so that they meaningfully exclude this system. ‘Meaningfully exclude’ implies that you have to give some reason related to your application why this won't work, rather than just say you don't like it and the $E^i$ functions have to actually do something.

In particular, it will be helpful for you to identify who changes the key and why. Are you the sender and recipient, and are you changing your password because it got compromised and surgically removing all traces of the previous key derived from it and ciphertexts encrypted with it from all storage systems everywhere? Are there multiple parties involved, like members of an organization who have split administrative functions to avoid unilateral power to doctor records? What are you or they all trying to accomplish? What is the adversary you hypothesize able to do to manipulate the resources they are trying to accomplish it with? What do you want to make sure the adversary can't do?

|improve this answer
$\endgroup$
  • $\begingroup$ Squeamish Ossifrage, this is good so far, but I want any k_i to be calculated from only k_0, and each key is different. Maybe I'm not understanding, but I'm confused why something encrypted i times can be decrypted with k_0, the first key... $\endgroup$ – slo_burner Dec 19 '17 at 3:47
  • $\begingroup$ If you look closely, you'll see that the $E^i$ for $i > 0$ don't actually do anything: ${E^i}_{k_i}(x) = x$ for $i > 0$. $\endgroup$ – Squeamish Ossifrage Dec 19 '17 at 3:49
  • $\begingroup$ Oh, I see. That is kind of silly though! Each E_i should change x. $\endgroup$ – slo_burner Dec 19 '17 at 5:19
  • $\begingroup$ I guess I need to meaningfully exclude this. The point of what I am doing is to change the encryption periodically and be able to calculate each new key from the first. $\endgroup$ – slo_burner Dec 19 '17 at 5:21
  • $\begingroup$ Setting the encryption other than the initial one to the identity function it cheating in my non-moderator opinion. Although the use case isn't clear, I presume that this cannot be it. $\endgroup$ – Maarten Bodewes♦ May 23 '19 at 9:29
1
$\begingroup$

I'm not sure I understand the question correctly. Assuming you want multiple encryption and decryption keys: Could you not just make multiple ciphertexts that are each encrypted with a different key?

If the problem is that the ciphertext is large, and you don't want multiple large ciphertexts, then you could generate a new "envelope" key, encrypt the message with the envelope key, and then make multiple ciphertexts of the envelope key encrypted with different keys. The envelope-key ciphertexts can be bundled with the main ciphertext. Then with any of those keys, the user could decrypt the envelope key, and then decrypt the main message.

I believe this is what GPG actually does internally if you encrypt a file with multiple symmetric or asymmetric keys.

This also allows you to update the main-message decryption key: you can take the main ciphertext with the previous envelope-key ciphertexts stripped off, generate new keys, encrypt the envelope key with the new keys, and then bundle the main ciphertext with the new envelope-key ciphertexts.

|improve this answer
$\endgroup$
-2
$\begingroup$

You could do this with one-time pads. Simply XOR the new pad into both the ciphertext and the decryption key each time.

|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Note: this is equivalent to encrypting with one key $\endgroup$ – Ella Rose May 21 '19 at 16:04
  • $\begingroup$ @EllaRose I assume you mean equivalent to decrypting with the old key and then re-encrypting with the new one. It is indeed very similar, but OP specifically said he did not want that. $\endgroup$ – Fax May 22 '19 at 8:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.