does re-encrypting the same value with multiple keys reduce security

Question

I found myself wondering today, how much security is lost if you take a plaintext - assume that its content, including any metadata is unknown to an attacker, for example it may be random data - and encrypt it with multiple keys (not chained) and give all resulting ciphertexts to an attacker, how much higher is the probability of an attacker discovering the plaintext, vs only having a single ciphertext.

An example:

Take plaintext $P_1$ and encrypt it with $K_1$, and send the resulting ciphertext $C_1$ to attacker $A_1$.

In addition: take the same plaintext $P_1$ and, and encrypt it with $K_1$, giving $C_1$. Then take $P_1$ and encrypt it with $K_2$ giving $C_2$, then $K_n$ giving $C_n$ and send all $n$ ciphertexts to attacker $A_2$.

How much more likely is attacker $A_2$ to discover the value of $P_1$, than $A_1$?

Answer 1

Does re-encrypting the same value with multiple keys reduce security?

The answer is "it depends"; there are some attack models and encryption methods where the security is reduced, there are other cases where there appears to be no security reduction.

Let us go through some models where we actually see a security reduction:

Plaintext guessing attack and deterministic encryption

In this attack model, the attacker has a guess to the plaintext $P_{guess}$ and wants to confirm whether $P_1 \stackrel{?}{=} P_{guess}$. What he can do is guess random keys $K_{guess}$ and compute $E_{K_{guess}}(P_{guess})$ and he if that appears in one of the ciphertexts he's been given. If he happens to guess a key $K_i$, then ciphertext $C_i$ will match, and he will get confirmation that his guess is likely to be correct - that's because we assume that the encryption is deterministic and so if the keys and the plaintext match, the ciphertext will as well. Obviously, using more keys means that there are more targets the attacker can stumble into.

Deterministic stream ciphers, and plaintext with known linear relations.

Here, we assume we don't know the plaintext, however we do know certain linear relations between the bits of the plaintext; for example, we may know that the parity of each byte is even. We also assume that the cipher works by generating a keystream (as a function of the key), and then exclusive-or the keystream with the plaintext to form the ciphertext.

So, what the attacker can do is examine each ciphertext; by assuming that the linear relationships hold in the original plaintext, he can evaluate the corresponding linear functions on the keystream; in the example, he can compute the parity of each byte of the keystream.

Then, he can pick random keys, and generate the corresponding keystream (here, we assume that this is determanistic). Then, he can compute the linear function of that keystream (in the example, the parity of each byte), and see if it matches one of the keystreams that correspond to the known ciphertexts.

Like the first example, having more targets makes it more likely that the attacker will guess the correct key.

(Also, if you think that the example of "parity of each byte is even" is contrived, a more realistic example is "the msbit of each byte is 0").

Deterministic RSA encryption

If the encrypt the exact same message (without padding, or using determanistic padding) to $n$ different keys, and $n \ge e$ (where $e$ is the common public exponent), then it's easy to recover the message. This is typically used as an example why you need to add randomness to your RSA encryption, even if you don't care about plaintext guessing attacks.

---

The above are three examples where encrypting with multiple keys can reduce security; in other cases (such as CBC-mode encryption), there is no obvious way to use multiple ciphertexts.

Now, the obvious thing about all three examples are that they are deterministic encryption; it would appear to be wise to add randomness if you are encrypting with multiple keys.

Answer 2

The "security" of an encryption scheme is commonly defined through a so called indistinguishability games, i.e. the attacker picks two messages of same length. You pick one of those two at random, encrypt it, and give it to the attacker. If the scheme is "secure", then the attacker's advantage of guessing which messages was encrypted should not be negligibly bigger than pure guessing, i.e. 1/2. This kind of security notion comes in different flavours like CPA, CCA1, and CCA2.

If a private or public key encryption scheme is secure against CPA, CCA1, or CCA2, then it will also be secure against the same games, where instead of giving two messages, the attacker gives you two message vectors and you encrypted one of them. This is proven with a standard technique called hybrid argument, which basically shows that if you can win a game with vectors of messages, then you can also win it where the attacker only outputs two messages. Very roughly speaking you create a reduction, where your attacker guesses a position in the vector and inputs the challenge from the two message game. The probability of guessing the "correct" position in the vector is non-negligible if your vector is of polynomial length. There are plenty of books (e.g. the one by Katz & Lindell) or online resources that explain this in depth, so I won't reiterate it here.

In short: If something is secure w.r.t. to for instance CPA, then it will also be secure if you obtain encrypted message vectors (or as you state where one message is encrypted under multiple different keys). The success-probability might change, but only by a very small (still negligible) amount, so nobody cares, since it's still secure w.r.t to the notion.