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$
  • $\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$ – Squeamish Ossifrage Sep 26 at 19:12
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$
  • 1
    $\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 Sep 27 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 Sep 27 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$
0
$\begingroup$

First of all, in CTR mode, using the same IV under the same key is catastrophic. Once an attacker notices this, he can use crib-dragging like in OTP. Mitigation from using the same IV is easy;

  • using a counter-based IV generation
  • Or LFSR based, both as recommended by NIST, and the first is more common.

In your mode, one needs the plaintext ready for the encryption. However, in CTR mode, you can prepare the stream before the data arrive.

Now, assume that you have used the same key with different messages in your mode. If a block repeats in two messages in the same position, they will have the same encryption. This can enable some traffic analyzing. However, in CTR if IV is not repeated, there is no problem. Your mode, in some sense, enables IV repeats.

$\endgroup$
  • $\begingroup$ In some contexts, it may be hard to ensure that a counter gets updated in a way that is robust in the face of unexpected power loss. $\endgroup$ – supercat Sep 27 at 18:32
  • $\begingroup$ @supercat are you talking about the CTR mode's recommendations? $\endgroup$ – kelalaka Sep 27 at 18:36
  • $\begingroup$ Essentially, the problem with CTR mode is that must have a means of keeping track of what IVs one may have used that is 100% robust, even if one loses power, has system state reloaded from a backup, etc. Not necessarily an insurmountable obstacle, but one that may be problematic if e.g. an application has no means of ensuring when information actually gets written to a storage medium (as opposed to merely delivered to the controller). $\endgroup$ – supercat Sep 27 at 20:19
  • $\begingroup$ @supercat If you know the daily encryption with the CTR mode under the same key by kept statistics, while reloading from a backup you can jump to day*maximum in a day + x. The application can ask to compare after storing. $\endgroup$ – kelalaka Sep 27 at 21:04
  • $\begingroup$ That would require that the unit have a reliable clock. Not a problem, if there's a working and trustworthy clock, but working clocks aren't always available. $\endgroup$ – supercat Sep 27 at 21:10

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.