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

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$?

-
You might want to check out related-key attacks on AES. This is basically the same idea from a different point of view. But as a general answer: It depends on the actual scheme. – tylo Apr 14 '14 at 14:09
Is it the same thing? As I am not encrypting a different plaintext with the same key. If for example we were discussing a SHA-512 encryption, with a 512 bit random plaintext? What is the precise name for this type of attack? So I can look it up – Zack Newsham Apr 14 '14 at 14:37
Related key attack is the correct term, yes. The wiki link will tell you more. But SHA is not an encryption algorithm, don't throw hashing and symmetric encryption in the same bin. They have different properties and security models. – tylo Apr 14 '14 at 14:48
I was under the impression that any encryption algorithm could be turned into a secure hashing algorithm by swapping the inputs (key->plaintext, plaintext->key). I assumed this was the case in the opposite direction. – Zack Newsham Apr 14 '14 at 14:50
also, the keys are in no way related - I should probably have mentioned that we can assume they are truly random keys. – Zack Newsham Apr 14 '14 at 14:51

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.

-
Thanks for the expansive answer. In regards to CBC-mode, if the plaintext was always a single block, would CBC-mode make any difference? – Zack Newsham Apr 14 '14 at 16:58
@ZackNewsham: as far as we know, multiple encryptions to different keys is not harmful in CBC-mode, even if the plaintext consisted of a single block, and even if the IV was constant between all encryptions (there are other reasons to randomize IVs; it just happens to be OK in this scenario). – poncho Apr 14 '14 at 18:31

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.

-
It seems like you are suggesting that because an encryption is secure against CPA (for example) when the attacker offers one pair of messages, then it must be secure when the attacker offers the same pair of messages multiple times, is that correct? Because I would think that if an attacker submits two messages each time, one of which changes and one of which does not. And the encryption key always changes with each request, it would be easier for the attacker to identify the re-occurring message. – Zack Newsham Apr 14 '14 at 17:03
If some public or private key scheme is CPA secure, then for all PPT adversaries the advantage is at most 1/2 + negl(n). Using the Hybrid Argument you can prove different things. For instance you could say that the adversary outputs message vectors m_1, m_2. The scheme would still be secure, meaning that the negligible function might be different, but still negligible. You could also show that the scheme would remain secure if the adversary outputs two messages and the challenge ciphertext is a vector, where each position is encrypted with a different randomly chosen key. – simkin Apr 14 '14 at 20:51