1
$\begingroup$

Given two ciphertexts encrypting the same (natural language) plaintext, where we know that one of the ciphertexts was encrypted with AES-CBC (and unknown IV) and one was encrypted with AES in EBC mode, and given that neither of the two ciphertexts has any duplicated blocks, are there any statistical tests that could generally (and reliably) detect which of the ciphertexts was generated by ECB and which one with CBC?

It's trivial to tell which one was generated by ECB if the plaintext has duplicated blocks, but in this case, since we don't see duplicated blocks in the ciphertexts we know that the plaintext doesn't have duplicates. I initially assumed it might be possible to still tell the difference between the two modes, and tried to implement a detector, trying out several of the NIST statistical test suite, taking as input English texts of about 2000 characters, but none of the tests appeared to make it possible to implement this (reliably, with > 50% chance of being correct for any plaintext without duplicate blocks).

My understanding now is that the answer to my first question is: No, impossible.

Reasoning: Given one plaintext block, the ciphertext block in either ECB or CBC mode will appear to be a block of random bits (or practically indistinguishable from random bits) (Correct?) It doesn't matter which mode is used. When a good, random IV is used in CBC mode, this will not increase the randomness of the encrypted output block. This would imply that all ciphertext blocks together also are equally random (or near-random) in ECB mode as in CBC mode. Is my understanding correct, or am I missing something?

$\endgroup$
6
  • $\begingroup$ "t's trivial to tell which one was generated by ECB if the plaintext has duplicated blocks, but the assumption here is that we don't have duplicates."; why do you think that is a valid assumption? Natural languages often has repeated phrases (of at least 16 characters); if the same phrase occurs at a multiple of 16 characters apart, you have a good chance at a repeated block... $\endgroup$
    – poncho
    Commented Apr 19 at 17:01
  • 1
    $\begingroup$ Of course, natural language texts often have repetitions, and you can easily get repeated blocks, but this question is a theoretical question where it's given that there are no repeated blocks in the two ciphertexts. $\endgroup$
    – mudskipper
    Commented Apr 19 at 17:12
  • $\begingroup$ I've updated my question so it's hopefully a bit clearer that I'm not making gratuitous assumptions about the plaintexts. $\endgroup$
    – mudskipper
    Commented Apr 19 at 17:38
  • 1
    $\begingroup$ If the plaintext is all different, then you will have different ciphertext, however, in CBC mode there can be a repeat since the input is x-ored with the previous output. Now if we assume the output is random and the plaintext is random ( uniqueness another issue) we will have collusion. Another way to look at this is the PRF-PRP switching lemma.. $\endgroup$
    – kelalaka
    Commented Apr 19 at 18:09
  • $\begingroup$ @kelaka - Thank you for the reference to PRF-PRP (wasn't aware of that). I'm not sure if I understand your reply though. Are you saying that my basic understanding (the "reasoning" in my question above) is correct? $\endgroup$
    – mudskipper
    Commented Apr 19 at 18:50

1 Answer 1

3
$\begingroup$

I believe if you impose the restriction that there are no duplicate blocks, then the answer should be: no, you can't distinguish between them. If you were able to do so then I believe that would lead to an attack on the underlying block cipher.

On the other hand, natural language has low entropy. A trivial example, based on AES or any other cipher with 128-bit block size: if you're using 7-bit ASCII to represent your natural language, the only $2^{112}$ out of all possible $2^{128}$ messages are actually valid in ECB mode, whereas with CBC, in principle all $2^{128}$ messages are possible. Even if all $2^{112}$ messages in ECB mode were uniformly distributed, then a collision would happen with probability roughly $2^{-56}$, vs. $2^{-64}$ for CBC mode.

But in reality the distribution of ECB-encrypted messages will be far from uniform, as the actual entropy of natural language text is lower than 7 bits. I believe there is an estimate of around 1 bit per letter of English text, which would translate into an entropy of just 16 bits per block. Of course this assumes a sophisticated compression model and does not translate directly to encoding symbols in 16-byte blocks, often splitting words in the middle. Even so suppose a reasonable 3 bits/letter. That's 48 bits per block so a collision has a probability of about $2^{-24}$. If you're dealing with fairly large messages (some megabytes), then a collision is not out of the question, whereas such a collision is exceedingly unlikely in CBC mode unless your messages are billions of terabytes in size.

$\endgroup$
7
  • 2
    $\begingroup$ The first paragraph is not correct. ECB ciphertext will be unique, however, in CBC we will have collisions $\endgroup$
    – kelalaka
    Commented Apr 19 at 20:52
  • $\begingroup$ @kelalaka - I believe you meant that the second paragraph is not correct? So, the ECB ciphertexts will not have collisions (since the output space is larger than the input space)? $\endgroup$
    – mudskipper
    Commented Apr 20 at 15:45
  • 2
    $\begingroup$ First. Under a key, a block cipher is a permutation, so if all inputs are different then there is no repeat in ECB ( it repeats iff an input repeats). This is not true for CBC since the chaining randomizes the input. So, we may assume that the input of the blockcipher is random in CBC ( plaintext x-or previous ciphertext). Therefore, with the usual collision in the first $2^{64}$ input with the probability %50 we expect to see repeat. Unfortunately, many people forgot the definition of the collision; It is probabilistic like the %50 after roughly $\sqrt{inputSize}$ is seen or processed. $\endgroup$
    – kelalaka
    Commented Apr 20 at 16:05
  • $\begingroup$ Ok, so if understand you correctly, you are saying: A sequence of CBC blocks can be seen as a random selection of the 2<sup>128</sup> possible blocks (due to the chaining) so you can expect a duplicate after seeing roughly 2<sup>64</sup> blocks (birthday paradox). While for EBC you will not see any collisions (since it's given that the input doesn't have any). Is that correct? If so, perhaps I was too hasty/ignorant in accepting this answer? :) $\endgroup$
    – mudskipper
    Commented Apr 21 at 22:48
  • 1
    $\begingroup$ @mudskipper under this very unnatural assumption of no duplicates on low-entropy messages, then indeed my first paragraph is wrong -- although it will take ~2^64 blocks until collisions for CBC mode crop up. The core of the argument (the other two paragraphs) is that it is unreasonable to expect no duplicates for natural language messages, and as a matter of fact, they should crop up at the order of magnitude of a few megabytes, which may or may not be plausible in your scenario -- but billions of terabytes for a CBC collision is, I assume, definitely not plausible. $\endgroup$
    – swineone
    Commented Apr 22 at 2:58

Your Answer

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

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