Is the following scheme secure for different cipher

Let's say I have

• two keys K1 and K2.
• two messages M1 and M2 of the same length.
• Cipher (E,D)
• 3 ciphertexts: C11, C12,C22 where Cij = E(Ki, Mj)

In situation where attacker knows K2 and all the ciphertexts (which also gives him M2), can I choose a cipher to guarantee that attacker won't be able to compute neither the K1 key, nor first message.

I see three possible options:

1. Attacker won't be able to compute anything no matter what cipher was chosen [if cipher itself is "secure"].
2. Attacker will be able to compute either K1 or M1 for some ciphers.
3. Attacker will be able to compute either K1 or M1 for all ciphers.

Which one is correct?

P.S.: Saying "all ciphers" I mean "all more or less secure ciphers".

P.S. 2: I suspect that it is not the first option because at least for stream cipher attacker can easily compute the pseudorandom sequence for K1 if he knows M2 and C12. Then he will be able to decode C11 using this sequence. Is it true for other ciphers?

-
Please feel free to set correct tags for the question – Snowbear Mar 16 '12 at 19:56

1 Answer

Actually, it's option 1: the attacker won't be able to compute anything, as long as a secure cipher is used.

The reason for this is that one of the requirements of a security cipher is resistance to known plaintext; that is, a message encrypted by the cipher with a key is secure even if the attacker can get the text of another message (and corresponding ciphertext) encrypted with the same key.

Your attack reveals M2 to the attacker and so the attacker has the pair C12 and M2 (a known plaintext pair) along with the ciphertext C11; this is exactly a known plaintext scenario; because a cipher is not considered secure unless it is invulnerable to a known plaintext attack, the attacker learns nothing about M1.

Note that your stream cipher example is not a counterexample to this, because this usage of a stream cipher is not particularly secure. For example, even without any known plaintext, the encrypted messages C11 and C12 allows an attacker to compute the value of M1 exclusive or'ed with M2; depending on the language that M1 and M2 are in, this is often enough to deduce the values of M1 and M2 (and so this example isn't even secure against a ciphertext only attack.

Because of this, we never use a stream cipher in that manner; you should either use a distinct key for each message, use successive portions of the key stream to encrypt successive messages, or use a stream cipher that take a nonce (which modifies the stream cipher output).

-