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 Ci (in n-bit blocks), and of total length sigma <= ql, 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)l/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).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 P MAC 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 P MAC 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) 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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.13154/tosc.v2016.i2.145-161 | IACR TRANSACTIONS ON SYMMETRIC CRYPTOLOGY |
Keywords | DocType | Volume |
Message Authentication Codes, PMAC, Attack, Masks | Journal | 2016 |
Issue | Citations | PageRank |
2 | 4 | 0.39 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Gaži | 1 | 84 | 5.81 |
Krzysztof Pietrzak | 2 | 1513 | 72.60 |
Michal Rybár | 3 | 6 | 1.12 |