Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
what is Oscar ? –  sashank May 2 at 5:06
    
Sorry. Oscar is the attacker. As Alice and Bob are the people trying to communicate. –  Pedro Alves May 2 at 13:48
    
How would Oscar find false keys ? –  sashank May 2 at 15:47
    
Oscar would use exhaustive search. –  Pedro Alves May 3 at 19:57
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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