article
The exact security of PMAC
published
yes
Peter
Gazi
author 3E0BFE38-F248-11E8-B48F-1D18A9856A87
Krzysztof Z
Pietrzak
author 3E04A7AA-F248-11E8-B48F-1D18A9856A87
Michal
Rybar
author 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
KrPi
department
Teaching Old Crypto New Tricks
project
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/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith 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(2n). 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/2n), 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.
https://research-explorer.app.ist.ac.at/download/6196/6197/2017_IACR_Gazi.pdf
application/pdfno
'https://creativecommons.org/licenses/by/4.0/'
Ruhr University Bochum2017
eng
IACR Transactions on Symmetric Cryptology
2519-173X10.13154/TOSC.V2016.I2.145-161
20162145-161
https://research-explorer.app.ist.ac.at/record/838
Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>. 2017;2016(2):145-161. doi:<a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>
Gazi, Peter, et al. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:<a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>.
P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.
Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i> 2016, no. 2 (2017): 145–61. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>.
Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>, <i>2016</i>(2), 145–161. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>
Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161.
P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2, pp. 145–161, 2017.
61962019-04-04T13:48:23Z2019-11-14T08:43:51Z