Welcome to the resource topic for 2017/069
Title:
The Exact Security of PMAC
Authors: Peter Gaži, Krzysztof Pietrzak, Michal Rybár
Abstract:PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most \ell (in n-bit blocks), and of total length \sigma \leq q\ell, the original paper proves an upper bound on the distinguishing advantage of O(\sigma^2/2^n), while the currently best bound is O(q\sigma/2^n). In this work we show that this bound is tight by giving an attack with advantage \Omega(q^2\ell/2^n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i-th block is computed as \tau_i := \gamma_i \cdot L, where L is a (secret) random value, and \gamma_i is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of $\gamma_{i}$’s which contains a large coset of a subgroup of GF(2^n). We then investigate, if the security of PMAC can be further improved by using $\tau_{i}$’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q^2/2^n), if the \tau_i's are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.
ePrint: https://eprint.iacr.org/2017/069
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 .