7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Maybe start by asking: What is the security goal that this would serve, what other alternatives already serve that security goal, and does it perform better than the alternatives? $\endgroup$ Commented Sep 26, 2019 at 19:12

2 Answers 2

10
$\begingroup$

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 cipher1. 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.

$\endgroup$
2
  • 2
    $\begingroup$ "the two blocks will match revealing that they were all zero and all-zero appended with 1" -- couldn't they be xxx0 and xxx1 for any bitstrings xxx? There's "just" the difference revealed. $\endgroup$
    – ilkkachu
    Commented Sep 27, 2019 at 13:41
  • $\begingroup$ Yes, this attack would also work as you suggested as long as the counter is currently at an even value for xxx0. Note that revealing the fact that these ciphertext blocks are related is already enough to break even the most basic modern cryptographic security notions. $\endgroup$
    – SEJPM
    Commented Sep 27, 2019 at 14:52
5
$\begingroup$

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...

$\endgroup$

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.