1
$\begingroup$

Theoretically – is CBC mode harder to bruteforce when compared with ECB when assuming:

  1. we ignore computational cost for the XOR operations, and
  2. the IV is made public?
$\endgroup$
5
  • 3
    $\begingroup$ Hint: Bruteforce enumerates the possible keys and checks each one (by procedures different in ECB and CBC); how many keys are expected to be tested in each case? What's the hardest step in each check? $\;$ Note: I think you want to assume known plaintext (and known ciphertext, but that one is always assumed in crypto); and perhaps something about the plaintext to allow ECB to be bruteforced. $\endgroup$
    – fgrieu
    Mar 4 '15 at 3:39
  • 1
    $\begingroup$ You could argue that if you ignore the XOR operations that CBC is ECB, but I don't think that was meant :) $\endgroup$
    – Maarten Bodewes
    Mar 4 '15 at 9:14
  • $\begingroup$ @maartenbodewes, I edited the question to avoid confusion Ah! genius i see u took the opportunity to give me the answer as well. $\endgroup$
    – laycat
    Mar 4 '15 at 13:00
  • $\begingroup$ @laycat No, in case this wasn't clear yet, the comment above isn't an answer - after the edit of the question anyway. $\endgroup$
    – Maarten Bodewes
    Mar 6 '15 at 12:16
  • $\begingroup$ @both answers are really good and detail, which one should I mark as the answer? $\endgroup$
    – laycat
    Mar 7 '15 at 13:08
3
$\begingroup$

As Maarten Bodewes already wrote in a comment, if you ignore the computational overhead of XOR, then there is essentially no difference in CBC and ECB for a bruteforce attack.

However, the question is actually mixing oranges and apples (and it is not obvious), because the security weakness of modes of operation has nothing to do with the underlying symmetric cipher - and a brute force attack has everything to do with the underlying cipher.

The problem is, that brute force attacks are a completely different scenario than what the different modes of operation try to achieve. In brute force you actually try out keys until you find the correct one. In cryptanalysis this is called a total break. The weakness of ECB compared to CBC is, that you can actually can achieve an easier goal of the attack: A distinguishing attack works on ECB and doesn't (with proper randomness, etc.) on CBC - under the assumption that the cipher is secure.

Btw, your 2. assumption is not needed. The IV is always assumed to be publicly known (and generated randomly for security arguments).

$\endgroup$
3
$\begingroup$

Yes there is a significant difference concerning brute-force.

  • ECB suffers from multi target attacks whenever you encrypt the same message block.

    This is always possible in a chosen-plaintext attack and often possible in practice with a known-plaintext attack.

  • With CBC the IV means that the plaintexts passed to the blockcipher are almost certainly unique (as long as the total message size stays below the birthday bound), so there is only one target.

With 128 bit and smaller keys this could lead to practical attacks. With 256 bit keys the security margin is so big that even multi-target attacks don't matter anymore.


But of course the main reason why we don't use ECB isn't the susceptibility to multi-target attacks, but that it leaks a lot of information even if the key is big enough.

$\endgroup$
2
  • 1
    $\begingroup$ You're talking about a scenario where the attacker can obtain many messages encrypted with different keys, and only needs to break one key, right? I agree, ECB is (slightly) weaker than CBC in that case, at least as long as the IVs for CBC are properly chosen (i.e. unpredictable by the attacker). $\endgroup$ Mar 4 '15 at 21:17
  • 2
    $\begingroup$ @IlmariKaronen Yes, I'm taking about an attacker learning the same message encrypted with different keys and is happy if they break some of them. Trevor Perrin's noise protocol is a particularly severe example, since it uses a different key for each message, but obtaining one key allows you to compute all following keys. $\endgroup$ Mar 4 '15 at 21:20

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.