Paper 2017/069
The Exact Security of PMAC
Peter Gaži, Krzysztof Pietrzak, and Michal Rybár
Abstract
PMAC is a simple and parallel blockcipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over nbit strings, PMAC constitutes a provably secure variable inputlength (pseudo)random function. For adversaries making q queries, each of length at most $\ell$ (in nbit 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 ith block is computed as $\tau_i := \gamma_i \cdot L$, where $L$ is a (secret) random value, and $\gamma_i$ is the ith 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 1wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2wise independent distribution, and then prove that the security increases to $O(q^2/2^n)$, if the $\tau_i$'s are 4wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3wise independence is already sufficient to get this level of security is left as an open problem.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in FSE 2017
 Keywords
 message authentication codes
 Contact author(s)
 michal rybar @ ist ac at
 History
 20170131: received
 Short URL
 https://ia.cr/2017/069
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/069, author = {Peter Gaži and Krzysztof Pietrzak and Michal Rybár}, title = {The Exact Security of {PMAC}}, howpublished = {Cryptology ePrint Archive, Paper 2017/069}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/069}}, url = {https://eprint.iacr.org/2017/069} }