3
$\begingroup$

I'm trying to analyze the strength of a block cipher with CBC mode or with ECB mode on the scenario of an exhaustive search attack with knowledge of pairs of plaintext – ciphertext (known plaintext attack).

I understand that, for a block cipher that receives a key of $k$ bits and processes blocks of $n$ bits ($n>k$), on ECB mode, Oscar would find false keys and because of that he would need to check more than one pair (i.e. two or three for DES).

But how would this attack work in a block cipher that uses CBC mode? I suppose Oscar still needs to deal with false keys, but now a encryption operation over block $i$ needs the knowledge of block $i-1$ and possibly the knowledge of $IV$. This is confusing to me.

Improve this question
$\endgroup$
4
  • $\begingroup$ what is Oscar ? $\endgroup$
    – sashank
    May 2, 2014 at 5:06
  • $\begingroup$ Sorry. Oscar is the attacker. As Alice and Bob are the people trying to communicate. $\endgroup$
    – Pedro Alves
    May 2, 2014 at 13:48
  • $\begingroup$ How would Oscar find false keys ? $\endgroup$
    – sashank
    May 2, 2014 at 15:47
  • $\begingroup$ Oscar would use exhaustive search. $\endgroup$
    – Pedro Alves
    May 3, 2014 at 19:57

1 Answer 1

Reset to default
1
$\begingroup$

I understand that, for a block cipher that receives a key of k bits and processes blocks of n bits (n>k), on ECB mode, Oscar would find false keys and because of that he would need to check more than one pair (i.e. two or three for DES).

That doesn't sound right; if you are assuming that the attacker (Oscar) has a plaintext block $P$ and a ciphertext block $C$, and searches for all keys $K$ to find one that satisfies $C = E_K(P)$, well, if the size of the key space $k$ is smaller than the block size $n$, then one would expect that there would be at most one key $K$ that satifies this relationship. That is, if we assume that $E$ acts independently with different keys, then $E_K(P)$ is effectively a set of independent variables based on the various values of $K$; since $K$ can take on $2^k$ different values, $E_K(P)$ can take on up to $2^n$ different values. We're looking for a value $K$ for which $E_K(P)$ is a particular value (C); we know that there is one value $K$ (the correct one) for which this is true; the probability that there is a second (false) key for which this is true is at most $(2^k-1)/2^n$, which is fairly small if $k$ is larger than $n$.

However, on to your real question:

But how would this attack work in a block cipher that uses CBC mode?

Pretty much the exact same way as it does in ECB; CBC mode is defined as:

$C_i = E_K( P_i \oplus C_{i-1} )$

(where $C_{-1}$ is taken to be the IV)

When the attacker has a known plaintext (that is, he has a plaintext message and its corresponding ciphertext), then the attacker knows the values $C_i$, $P_i$, and $C_{i-1}$, and he can look for a key $K$ that satisfies the value relation exactly as he would with ECB mode. In addition, if he happens to find two keys $K^1$, $K^2$ that encrypts that block in the exact same way, then he can handle it just like in ECB mode, he steps to another block and does a test encryption (or decryption; whichever is most convienent) on that as well.

I suppose Oscar still needs to deal with false keys, but now a encryption operation over block i needs the knowledge of block i−1 and possibly the knowledge of IV.

We always assume that the attacker sees the entire ciphertext; hence he sees ciphertext block $i-1$. It's possible that he doesn't know the IV (we typically send the IV with the message, however that's not a requirement); if he doesn't, all the attacker does is not use the first block for his brute force attack.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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