10
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ to be fair, if you re-use IV's, i think you have a problem no matter what mode you use ^^ $\endgroup$ – hanshenrik Oct 15 at 8:50
  • 2
    $\begingroup$ It allows for "online" encryption as well, missing in the OP's question and this answer. As for message length: you can add a random sized padding, but that doesn't fully hide all information about the size. Similarly, using AES in SIV mode doesn't hide nonce reuse for identical messages (i.e. it will protect most of the information about the message, but it still may leak some information about the plaintext: messages that are identical could be distinguished from other messages). $\endgroup$ – Maarten Bodewes Oct 15 at 15:04
  • 1
    $\begingroup$ It's certainly related, in case you want a random byte decrypted then you can do that directly without decrypting a whole block. But I guess you can have block sized random access e.g. when using ECB. I'm not sure how well these kind of properties are defined. $\endgroup$ – Maarten Bodewes Oct 15 at 16:43
  • 1
    $\begingroup$ While it is implicitly included in "lack of authentication", I'd specifically call out the malleability of CTR mode as a deal breaker these days. Unlike with other malleable modes, such as CBC, very precise changes can be made to the plaintext the receiver gets. "Catastrophic results" indeed. $\endgroup$ – user7761803 Oct 16 at 14:47
  • 1
    $\begingroup$ @user7761803 yes, malleable is the other term. Even in the CBC mode, the bit flipping attack can be executed precisely. If you play with the IV's bit that will only affect single bit. This can be seen in the image of this answer. I've considered making a bullet about that but decided to keep it in the lack of authentication as a broader bullet. $\endgroup$ – kelalaka Oct 16 at 15:05
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you add the link of the claim? $\endgroup$ – kelalaka Oct 15 at 16:12
  • 1
    $\begingroup$ @kelalaka "Cryptography Engineering" p.71 (Section 4.7 in Chapter 4, "Block Cipher Modes") ©2010 Wily Publishing $\endgroup$ – Xander Oct 15 at 16:51
  • 1
    $\begingroup$ And, it turned out that the Padding oracles was the key attack for the CBC mode. If you limit the counter to 32 bits as in the GCM, you will have more options to secure the CTR. IV = Random+ counter. If anything happens change the key and use AES-256. +1 for the information. $\endgroup$ – kelalaka Oct 15 at 16:52
  • $\begingroup$ CBC has its own issues with IV misuse, however. If you're worried about IV/nonce reuse, the real solution is to use an MRAE mode such as SIV. $\endgroup$ – Ilmari Karonen Oct 16 at 1:47
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.