TY - JOUR AU - Gaži, Peter AU - Pietrzak, Krzysztof AU - Rybár, Michal PY - 2017/02/03 Y2 - 2024/03/28 TI - The Exact Security of PMAC JF - IACR Transactions on Symmetric Cryptology JA - ToSC VL - 2016 IS - 2 SE - Articles DO - 10.13154/tosc.v2016.i2.145-161 UR - https://tosc.iacr.org/index.php/ToSC/article/view/569 SP - 145-161 AB - <p>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 <em>n</em>-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making <em>q</em> queries, each of length at most <em>l</em> (in <em>n</em>-bit blocks), and of total length σ ≤ <em>ql</em>, the original paper proves an upper bound on the distinguishing advantage of <em> Ο</em>(σ<sup>2</sup>/2<sup><em>n</em></sup>), while the currently best bound is <em> Ο</em> (<em>qσ</em>/2<sup><em>n</em></sup>).In this work we show that this bound is tight by giving an attack with advantage Ω (<em>q</em><sup>2</sup><em>l</em>/2<sup><em>n</em></sup>). In the PMAC construction one initially XORs a mask to every message block, where the mask for the <em>i</em>th block is computed as τ<sub><em>i</em></sub> := γ<sub><em>i</em></sub>·<em>L</em>, where <em>L</em> is a (secret) random value, and γ<em>i</em> is the <em>i</em>-th codeword of the Gray code. Our attack applies more generally to any sequence of γ<sub><em>i</em></sub>’s which contains a large coset of a subgroup of <em>GF</em>(2<sup><em>n</em></sup>). We then investigate if the security of PMAC can be further improved by using τ<sub><em>i</em></sub>’s that are <em>k</em>-wise independent, for <em>k</em> &gt; 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 <em>O</em>(<em>q&lt;</em><sup>2</sup>/2<sup><em>n</em></sup>), if the τ<sub><em>i</em></sub> 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.</p> ER -