# The Exact Security of PMAC

### 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 *l* (in *n*-bit blocks), and of total length σ ≤ *ql*, the original paper proves an upper bound on the distinguishing advantage of * Ο*(σ^{2}/2^{n}), while the currently best bound is * Ο* (*qσ*/2^{n}).In this work we show that this bound is tight by giving an attack with advantage Ω (*q*^{2}*l*/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 τ_{i} := γ_{i}·*L*, where *L* is a (secret) random value, and γ*i* is the *i*-th codeword of the Gray code. Our attack applies more generally to any sequence of γ_{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 τ_{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 τ_{i} 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.

*IACR Transactions on Symmetric Cryptology*,

*2016*(2), 145-161. https://doi.org/10.13154/tosc.v2016.i2.145-161

Copyright (c) 2017 Peter Gaži, Krzysztof Pietrzak, Michal Rybár

This work is licensed under a Creative Commons Attribution 4.0 International License.