0
$\begingroup$

I had a quiz last week in computer security course. There was a confusing question that I am still looking for a good and clear answer.

First, I know that counter mode with a good block cipher is widely accepted and most likely unbreakable as long as the counter (IV) is not being reused.

The question was about using counter mode with a strong block cipher, say AES. The IVs are independently generated. Suppose we encrypt two messages M1 and M2 where M2 is zeros, a sequence of zero bits, and get ciphertexts C1 and C2. Assume C1, M2, C2 are known by an attacker, would it be possible to decrypt, reveal M1?

Since in counter mode C = M ⊕ E(K,(nonce,IV))

for M2, the C2 = E(K,(nonce,IV)) , since M2 is zeros and xoring with zeros does not do anything.

I know that C1 ⊕ C2 = M1 ⊕ M2 but not sure if it is useful here.

My answer was the attacker will not be able to know (M1) because of the strength of the block cipher and the encryption process depends on the key, nonce, and IV which won't be broken if the attacker knows pair of plaintext and it corresponding ciphertext.

I am confused because what I have learned the strength of the counter mode depends on a good block cipher and non-reused IV, but what will happen if the input was zeros, and E(K,(nonce,IV)) was exposed to attacker?

I did not feel I was right, and still confused about it.

Hopefully I can get a clear answer with appreciation.

$\endgroup$
  • $\begingroup$ I'm at loss as to why you have both nounce and IV. $\;$ Hint: when applying whatever general formula involving variables without index ($C$, $M$, $K$, $IV$), to variables with index ($C_j$, $M_j$,..), it is crucial to think carefully for each variable if it should get an index or not. $\endgroup$ – fgrieu Feb 5 '15 at 9:20
2
$\begingroup$

This all depends on the IVs. If they are independently generated, the IVs will not only be different (so $IV_1 \neq IV_2$), but also their sequences will not overlap with overwhelming probability. In that case, then everything should be fine, so $C_2 = E(K,(nonce,IV_2))$, and $C_1 = M_1 \oplus E(K,(nonce,IV_1))$.

However, if they are reused (so $IV_1 = IV_2$), then $C_2 = E(K,(nonce,IV_2)) = E(K,(nonce,IV_1))$, so $C_1 = M_1 \oplus E(K,(nonce,IV_1)) = M_1 \oplus C_2$, and therefore $M_1 = C_1 \oplus C_2$.

$\endgroup$
  • $\begingroup$ clear.So M1 will not be compromised in case IVs are not reused,am I right? I think C2=E(K,(nonce,IV2)) can be used somehow to recover M1, not sure! $\endgroup$ – Naif Alghamdi Feb 4 '15 at 10:51
  • 2
    $\begingroup$ It is necessary, but not quite sufficient, that $IV_1\ne IV_2$. For example, $IV_2=IV_1+1$ reveals $M_1$ except for its first 128 bits (assuming $M_1$ and $M_2$ are at least 128-bit). What's wanted is that the counter ranges used in the two encryptions do not overlap. Here we are told that "The IVs are independently generated", thus this situation holds with high odds, for reasonably sized messages. $\endgroup$ – fgrieu Feb 5 '15 at 9:15
  • $\begingroup$ @fgrieu True. I updated the answer accordingly :) $\endgroup$ – cygnusv Feb 5 '15 at 10:54
0
$\begingroup$

Assuming CTR mode is used properly (in particular, neither $IV_1$ nor $IV_2$ is a prefix of the other, which if they're the same length just means they're different), knowing $(M_2,C_2)$ does not help an attacker find $M_1$. Vulnerability to such an attack would imply vulnerability to a chosen plaintext attack; instead, CTR has the IND-CPA property, which says that an attacker who can get you to encrypt a bunch of messages of his choice, who then sends you two plaintexts and receives the encryption of one of them, can't tell which one it was you encrypted.

But more generally, resistance to your scenario is a property that is commonly required for a proposed encryption scheme to be considered secure: we generally assume an attacker might be able to recover some plaintexts, and so require our scheme to be secure even if that's the case.

There are a few things to keep in mind:

  • There is literally no difference from a security standpoint between $M_2$ being all zeroes or $M_2$ being any other string. An attacker couldn't care less about $M_2$; what they'd use it for is to get the keystream, which is the sequence of $E(IV_2||0\dots01,K), E(IV_2||0\ldots02,K),\ldots$. All they need for this is to know $M_2$; they don't need it to be zeroes. So if CTR mode broke in this case, it would never protect ciphertext if an attacker recovers a single other thing encrypted with the same key but different IV.
  • The CTR IV is only half of what's encrypted to make the keystream. It's concatenated to a block counter, which starts at 1 and increments by 1 each block. The security of CTR does not, strictly speaking, rely on $IV$ being unique -- rather, the combination of IV and the block counter must be unique across all blocks encrypted with a particular key (to put it a different way, encrypting $A||B$ with a single IV is no worse than encrypting $A$ with one IV and $B$ with a different one). In this case, two messages with different IVs is no worse than sending $0\dots0||A$ encrypted with one IV. But that's just like sending POST /mail/submit.py HTTP/1.0 ...data... - in both cases, the attacker knows some of the keystream, so we require them to not be able to figure out the rest of it. CTR mode is designed to be usable for that POST request, which incidentally requires it to be secure in your case.

While some encryption schemes break under your conditions, the fact that they break under your conditions is, in and of itself, a major flaw in them that justifies never using them to encrypt a message except under extremely strict circumstances that keeps those specific flaws from being relevant. It would not be considered safe for general use, unlike CTR mode (plus authentication, CTR by itself is not good for other reasons, but at this point you should always have authentication anyways).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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