Welcome to the resource topic for 2018/159
Title:
The Missing Difference Problem, and its Applications to Counter Mode Encryption
Authors: Gaëtan Leurent, 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}).
ePrint: https://eprint.iacr.org/2018/159
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .