Disadvantages of AES-CTR?

Question

On paper, it sounds *very* good to me:

• secure
• fast (in my tests it's somewhat slower than ECB (but without most of the weaknesses, more on that below) but faster than every other alternative I tested, which were ECB, CTR, CBC, OFB, CFB written in order of performance (link to benchmark code) )
• simple to understand
• does not require padding (which I guess significantly reduces the chance of implementing padding in an insecure manner)
• support parallelization (for both encryption and decryption)
• support random access

.. the only disadvantage I can think of, is that because it does not require padding, implementations in practice will probably reveal the exact message length, as compared to revealing circa-message-lengths (e.g. padded schemes may reveal something like the message is within 15 bytes of this length, while non-padded schemes may reveal the message is *exactly* this long), and if that's a concern, it's not like it can't be mitigated by just adding padding anyway.

I guess I'm missing something, so...

What are the disadvantages?

Answer 1

Disadvantages:

• Message length: In Cryptography, usually, the message length is not considered secret. There are approaches that you can add random values to the end or beginning or both if this is really an information leak for you. The random approach depends on your actual data case. It is also possible that a pre-determined fixed size can be used as the e-mail can be limited to 512 characters. In the end, at least the upper bound is revealed in all of the cases.

• The (IV, key) pair reuse is a real problem that can eliminate the confidentiality with the crib-dragging technique. This doesn't reveal the encryption key.

• Lack of authentication Like all unauthenticated encryption modes, the bare CTR mode lacks integrity and authentication. A single bit of flipping can have catastrophic results due to the malleability of the CTR mode.

  The AES-GCM mode that uses the CTR mode of operation provides you all-in-once, however, it has the same (IV, key) pair reuse problem. There is a Synthetic Initialization Vector (SIV) mode as nonce-misuse resistance ( paper, rfc8452 ) that eliminates this. SIV mode can still leak that the same message is sent under the same key, so an observer can distinguish this.

• Long message distinguisher: The CTR mode is designed with a Pseudo-Random-Function (PRF). When using AES in CTR mode, we use it with Pseudo Random Permutation (PRP); $$E_k\colon \{0,1\}^n \to \{0,1\}^n.$$ Whit PRP as long as the message blocks are not repeated the sequence $E_k(0), E_k(1), \dots, E_k(\ell - 1)$ with $\ell < 2^n$ is not repeated. If the message with length $\ell$-block has no repeated block this is no problem. If we approach the message as uniform random block then we expect a collision $\ell \approx \sqrt{2^n} = 2^{n/2}$ by the birthday paradox/attack.

  When used with AES-128 for long messages check for the repeat. The repeat enables the attacker to distinguish this from uniform random with non-negligible probability.

  In short, a duplicate ciphertext in any position leaks that the messages are different.

• Message size per key: although NIST say 64 nonce and 64 bit counter, one should stop using a key well before $2^{64}$ block. This is due to using a PRP (AES) instead of PRF in CTR mode.

---

Other advantages:

1. No need for the decryption: CTR mode doesn't require decryption of the block cipher, it always uses them for encryption. This is very helpful in constraint environments. Simplifies the software and hardware code, too.

2. No need PRP: Doesn't need a block cipher (PRP) at all. A hash function can be used like in the ChaCha series.

3. Prepocessing: the keystream generated by the CTR mode can be prepared before. This can help to use buffers.

4. CTR mode has CPA security.

---

A little history of CTR

CTR mode was introduced by Whitfield Diffie and Martin Hellman in 1979

• Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

• A concrete Security of Treatment of Symmetric Encryption, Bellare et. al, 97 provides the security bounds.

• See also; Comments to NIST concerning AES Modes of Operations: CTR-Mode Encryption, by Lipmaa et al. for other details of advantages and disadvantages.

Answer 2

Schneier and Ferguson initially recommended CTR mode, but switched to recommending CBC mode due to potential difficulties in ensuring that the counter was never re-used with a key.

Answer 3

While your question seems to be focusing on the CTR side of things, its worth an answer to discuss the AES side of things as well. There are at least two situations where other block ciphers may be more appropriate.

---

Secure Computation:

There are two main "difficulties" of AES with respect to secure computation (meaning multi-party computation and NIZKs mainly, but also likely fully-homomorphic encryption).

1. AES is computed over a field of characteristic 2. If an MPC/FHE system uses characteristic $p$ arithmetic, the having a cipher in characteristic 2 requires conversions between different representations (say, of an element in $\mathbb{Z}/p\mathbb{Z}$, or the base-2 decomposition of such an element) which are more costly than in standard computation.

2. Generically, multiplications are much more costly (relatively) than additions in the context of secure computation. This means that one can have a different "cost model" to build ciphers for, where one is more interested in reducing the number of multiplications in the cipher generically.

A cipher to look at for this topic is MiMC (although there was recently a partial attack against this cipher in a "$\mathbb{F}_{2^k}$ version" of it. It also has "$\mathbb{F}_p$" versions, which are not hit by the attack).

---

Embedded Systems:

On standard machines, the hardware implementation of AES (via the AES-NI instruction) gives something like a ~40x speedup over optimized software implementations of AES. This makes it difficult to be competitive with AES when comparing AES-NI to software implementations of other ciphers. But when you don't have AES-NI, other ciphers can be more competitive. This post by Matthew Green discusses using alternative to AES (his recommendation when writing this ~8 years ago was not do this, for the record) discusses certain ciphers like Salsa20 offering a 2x - 3x speedup over AES in software. Note that Salsa20 is technically a stream cipher compared to AES being a block cipher, but this is just to motivate being able to "beat" AES on speed when you don't have access to AES-NI.

A better source for faster ciphers in constrained computing environments is the ongoing NIST Lightweight Cryptography Standardization. I have not been following this closely, but there is currently much research interest in finding a new cipher to standardize for (essentially) use in embedded systems. They are currently planning to post their round 3 finalists this upcoming December, so it would not surprise me if within the next few years there was a "new cipher" which replaces the use of AES in embedded systems.

Answer 4

CTR is indeed a very nice block cipher mode of operation. Its main drawbacks are that:

1. it does not protect message integrity (and in fact allows an attacker to easily flip arbitrary bits in an encrypted message without having to decrypt it), and
2. it may leak plaintext if a counter block is ever reused; in particular, CTR mode encryption requires a unique nonce input that absolutely must not be reused for two different messages encrypted with the same key.

Fortunately, both of these problems may be solved by using CTR mode as a component in a higher-level construction:

• The first problem can be solved by using an authenticated encryption mode, many of which (such as EAX and GCM) are based on a combination of CTR mode with a message authentication code.
• The second problem can be solved by using a "nonce misuse resistant" encryption mode that derives the initial counter value based on (among other things) the plaintext message being encrypted. Such modes include SIV and GCM-SIV, both of which are also based on CTR mode and also provide message authentication as described above.

Of course, the addition of message authentication requires some extra processing that makes these modes slower than raw CTR (although a good implementation of GCM can still be very fast). In particular, to obtain the full security these modes guarantee, the receiver must authenticate the entire message before passing on any of the decrypted plaintext. For the misuse resistant modes, the same also applies when encrypting, since the entire message must be processed to derive the initial counter value before it can be encrypted.

Still that's generally a small price to pay for increased security. If you can use a nonce misuse resistant mode like SIV or GCM-SIV, I'd highly recommend you do so. If not, at least use a nonce-based AE mode like GCM.