What are the risks of using CTR mode with 64 bit blocks?

Question

On DJB's blog he writes:

I was one of about 40 people sitting in a meeting where the speaker, NSA's Louis Wingers (one of the Simon and Speck authors), falsely claimed that counter mode is safe for 64-bit blocks, since counter mode doesn't have block collisions. NSA's continuing promotion of these dangerous ciphers includes perfect sentences to quote in the introductions of "provable security" papers studying small block sizes.

I can think of the following problems with 64 bit CTR mode (either used with HMAC or without the need for message authentication)

• The keystream can be distinguished from random if the length is close to (or greater than) $2^{32}$ blocks. No two blocks will have equal values assuming no counter overflow. The birthday effect means repeat block values are expected after around this many blocks.
• There is a potential plaintext information leak. For ciphertext $C$ and plaintext $P$ (for any length), only if $P_i \neq P_j$ may $C_i = C_j$ where $i \neq j$. This is true for CTR mode with any block size but is more of a problem for 64 bit blocks than for 128 bit blocks because the birthday limit for 64 bit blocks is smaller.
• Random IV collisions are too common because the maximum length of the IV is less than 64 bits.

Are there other problems for CTR mode associated with 64 bit block sizes? (Perhaps associated with different message authentication algorithms.) If not, then what is Bernstein referring to? The problems I identified seem like they would be minor if keys can be regenerated to avoid encryption of too many blocks with the same key.

_{I hope my list is not exhaustive just so I don't need to post an answer to my own question. Besides mathematical problems I suspect there are a lot of human problems. Those alone I think are serious enough to justify completely discouraging 64 bit block sizes. Plus I believe the IV problem is especially serious.}

Answer 1

I believe that he was referring to the misconception that the birthday problem that arises in encryption is only when you use the same counter twice. If a random IV is used, then such a counter repeats at $2^{32}$ blocks with high probability (and if you want a $2^{-32}$ safety margin then you can only encrypt $2^{16}$ blocks). However, if distinct counters are guaranteed to be used, then you never get a collision on the input to the block cipher and so you can encrypt more. I assume that the NSA claim was with reference to this version of counter mode where distinct counters are guaranteed (something that's easy to do if you have state).

Anyway, this is a misconception for the exact reason that you point out. The problem is that people think that this leaks only a very little bit of information, unlike in CBC mode where a collision in the ciphertext immediately reveals the XOR of two plaintext blocks. Recently, at EUROCRYPT 2018, a paper was presented showing how to obtain actual plaintext in a number of realistic scenarios when counter mode is used beyond the birthday bound, even with unique counters. The paper is called The Missing Difference Problem, and its Applications to Counter Mode Encryption. I recommend reading it.

Answer 2

This answer summarizes what's achieved against CTR mode in the paper pointed by Yehuda Lindell's answer: Gaëtan Leurent and Ferdinand Sibleyras's The Missing Difference Problem, and its Applications to Counter Mode Encryption (in proceedings of Eurocrypt 2018).

The setting is CTR mode with an $n$-bit block cipher applied to a plaintext consisting of $2m$ blocks, with $m$ known (say the firsts) and the others consisting of the same unknown block $S$ repeated $m$ times. $m$ is assumed somewhat above $2^{n/2}$.

Write $a_i$ for the $2m$ blocks of keystream. The $a_i$ differ from uniformly random in that $0\le i<j<2m\implies a_i\ne a_j$. We know $a_i$ for $0\le i<m$, and the question's first bullet remarks that they being distinct gives a distinguisher.

Write $b_j$ for the $m$ known blocks of ciphertext corresponding the unknown $S$. $m\le j<2m\implies b_j=a_j\oplus S$. These $b_j$ are distinct, and that gives a distinguisher, but no information about $S$.

Observe that in this setting $$0\le i<m\le j<2m\implies a_i\oplus a_j\ne 0\implies a_i\oplus b_j\ne S$$ where the $a_i$ and $b_j$ are known. This relation defines $m^2$ loosely dependent pseudo-random values $a_i\oplus b_j$ among $2^n$ that $S$ can not take. It is likely to leave only a single $S$ possible for $m$ only polynomialy above $2^{n/2}$ (by a variation of the coupon collector problem).

The article gives algorithms finding $S$ that are significantly more efficient than the obvious $\tilde{\mathcal O}(2^n)$ and previous improvements. With $m=2^{n/2}\sqrt{n/2}$, time and memory complexity is only $\tilde{\mathcal O}(2^{2n/3})$; and that reduces to $\tilde{\mathcal O}(2^{n/2})$ when a constant number of bits of $S$ are unknown. Note: $g(x)=\tilde{\mathcal O}(2^x)$ means $|g(x)|<x^k\,2^x$ for some constant $k$ and $x$ above some bound.

For $n=64$ block size and regardless of key size, we are talking 400 GiB of ciphertext and very plausible amount of work, for something that actually recovers some plaintext.