**The Missing Difference Problem, and its Applications to Counter Mode Encryption**

*Gaëtan Leurent and Ferdinand Sibleyras*

**Abstract: **The counter mode (CTR) is a simple, efficient and widely used encryption
mode using a block cipher. It comes with a security proof that
guarantees no attacks up to the birthday bound (i.e. as long as the
number of encrypted blocks $\sigma$ satisfies $\sigma \ll 2^{n/2}$), and
a matching attack that can distinguish plaintext/ciphertext pairs from
random using about $2^{n/2}$ blocks of data.

The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity $\tilde{\mathcal{O}}(2^{n/2})$. This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message.

To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required.

As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity $\tilde{\mathcal{O}}(2^{2n/3})$.

**Category / Keywords: **secret-key cryptography / Modes of operation, CTR, GCM, Poly1305, Cryptanalysis

**Original Publication**** (in the same form): **IACR-EUROCRYPT-2018

**Date: **received 8 Feb 2018, last revised 13 Feb 2018

**Contact author: **gaetan leurent at inria fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20180213:154257 (All versions of this report)

**Short URL: **ia.cr/2018/159

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]