### 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})$.

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Modes of operationCTRGCMPoly1305Cryptanalysis
Contact author(s)
gaetan leurent @ inria fr
History
2018-02-13: revised
See all versions
Short URL
https://ia.cr/2018/159

CC BY

BibTeX

@misc{cryptoeprint:2018/159,
author = {Gaëtan Leurent and Ferdinand Sibleyras},
title = {The Missing Difference Problem, and its Applications to Counter Mode Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2018/159},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/159}},
url = {https://eprint.iacr.org/2018/159}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.