Paper 2018/159
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})$.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in EUROCRYPT 2018
 Keywords
 Modes of operationCTRGCMPoly1305Cryptanalysis
 Contact author(s)
 gaetan leurent @ inria fr
 History
 20180213: revised
 20180211: received
 See all versions
 Short URL
 https://ia.cr/2018/159
 License

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}, url = {https://eprint.iacr.org/2018/159} }