Why is ECB+CTR not a thing?

Question

AES-CTR is nice for its parallelizability and simplicity but if you duplicate an IV you reveal plaintext.

Chaining modes like CFB and CBC don't have that problem per se but they are not parallelizable. (CBC-type modes have padding issues too but that's a separate problem.)

Naive ECB mode is not secure because it reveals structure in the plaintext as shown clearly here.

However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

The advantage over CTR as I see it is that duplicating a nonce/IV (or having no nonce/IV) would not allow actual plaintext recovery. It may reveal duplication, but that's it. In the no-IV case duplicate messages would have duplicate ciphertext, but that again only reveals message duplication but does not compromise secrecy.

Obviously you'd need some kind of padding but again that's a separate issue.

Why is this kind of mode not a thing? Would a mode like that have some problem I don't see or is it simply deemed unnecessary?

Answer 1

However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

This is trivially insecure. Counter-Example: Consider the nonce $0^n$ and the plaintext $0^{2n-1}\|1$. This mode will encrypt the first block to be $E(0^n)$ and the second block to be $E((0^{n-1}\|1)\oplus(0^{n-1}\|1))=E(0^n)$ and so the two blocks will match revealing that they were all zero and all-zero appended with 1. This easily breaks IND$-CPA and RoR-CPA security (the latter being equivalent to more standard CPA security).

Why is this kind of mode not a thing?

This sort of mode is a thing actually. Just not in the naive formulation as described in the question. Namely if you have a almost-XOR-universal hash function $H_K$ keyed with some key $K$ and a block cipher $E$, then $H_K(T)\oplus E(M\oplus H_K(T))$ is a secure tweakable block cipher¹. Now you can put a counter in the tweak $T$ and change it for each block so swap attacks no longer work as do the pattern attacks you know from ECB. In fact tweakable block cipher (modes) are so useful, they see widespread use as XTS (which is based upon LRW which is the above construction and used by essentially all disk encryption software in a variant of this mode) and are the basis for the famously fast OCB modes.

---

^{1: Technically this constructs a strong tweakable pseudo-random permutation. For a non-strong TPRP it actually suffices to compute $E(M\oplus H_K(T))$ and the simplest $H_K(T)$ is actually $K\cdot T$ over $F_{2^{128}}$ which when used with a counting $T$ is very close to the question's construction it's just the additional secret value that makes the difference.}

Answer 2

However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

Not really; it hides precisely duplicated plaintext blocks, but it would still reveal related plaintext blocks.

Consider a two-block plaintext that consists of $(7, 6)$. Suppose we encrypt it with a counter $nonce = 4$; what this mode would do is generate a two-block ciphertext block $\operatorname{AES}_k( 7 \oplus 4 ), \operatorname{AES}_k( 6 \oplus 5) = \operatorname{AES}_k( 3 ), \operatorname{AES}_k( 3) $. When the attacker sees this, he can immediately deduce that the xor of the first two plaintext blocks is the value 1.

Not only does this mean that we don't meet CPA security, but also it might leak on plaintexts that might reasonably occur.

Now, a similar idea that I have seen suggested (source: Richard Schroeppel) is the same general idea, but you keep the initial counter value secret (e.g. it is $\operatorname{AES}_k(iv)$), and to update the counter for each block, you don't do a simple increment, but instead you do a multiply by 2 in $\operatorname{GF}(2^{128})$ (that is, you have a 128 bit LFSR based on a prime polynomial, and you step it once for each block). This can be shown to be CPA secure; however it never caught on...