Paper 2017/069

The Exact Security of PMAC

Peter Gaži, Krzysztof Pietrzak, and 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.

Metadata
Available format(s)
PDF
Category
Secret-key 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
2017-01-31: received
Short URL
https://ia.cr/2017/069
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.