The exact security of PMAC

P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.

Download
OA 597.34 KB

Journal Article | Published | English
Department
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/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.
Publishing Year
Date Published
2017-02-03
Journal Title
IACR Transactions on Symmetric Cryptology
Volume
2016
Issue
2
Page
145-161
eISSN
IST-REx-ID

Cite this

Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161
Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC. IACR Transactions on Symmetric Cryptology, 2016(2), 145–161. https://doi.org/10.13154/TOSC.V2016.I2.145-161
Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology 2016, no. 2 (2017): 145–61. https://doi.org/10.13154/TOSC.V2016.I2.145-161.
P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2, pp. 145–161, 2017.
Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161.
Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-04-04T13:53:58Z


Material in IST:
Dissertation containing IST record

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar