# Statistical differences between ciphertexts generated by AES in ECB vs CBC mode?

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?

• "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... Commented Apr 19 at 17:01
• 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. Commented Apr 19 at 17:12
• I've updated my question so it's hopefully a bit clearer that I'm not making gratuitous assumptions about the plaintexts. Commented Apr 19 at 17:38
• 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.. Commented Apr 19 at 18:09
• @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? Commented Apr 19 at 18:50

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.
• 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. Commented Apr 20 at 16:05