Paper 2020/1595
Attacks on Beyond-Birthday-Bound MACs in the Quantum Setting
Tingting Guo and Peng Wang and Lei Hu and Dingfeng Ye
Abstract
We systematically study the security of twelve Beyond-Birthday-Bound Message Authentication Codes (BBB MACs) in the Q2 model where attackers have quantum-query access to MACs. Assuming the block size of the underlying (tweakable) block cipher is $n$ bits, the security proofs show that they are secure at least up to $\mathcal{O}(2^ {2n/3}) $ queries in the classical setting. The best classical attacks need $\mathcal{O}(2^ {3n/4}) $ queries. We consider secret state recovery against SUM-ECBC-like and PMAC_Plus-like MACs and key recovery against PMAC_Plus-like MACs. Both attacks lead to successful forgeries. The first attack costs $\mathcal{O}(2^{n/2}n)$ quantum queries by applying Grover-meet-Simon algorithm. The second attack costs $\mathcal{O}(2^{m/2})$ quantum queries by applying Grover's algorithm, assuming the key size of (tweakable) block cipher is $m$ bits. As far as we know, these are the first quantum attacks against BBB MACs. It is remarkable that our attacks are suitable even for some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, and mPMAC+-p2.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Minor revision. PQCrypto 2021
- Keywords
- Beyond-Birthday-BoundMessage Authentication CodesQuantum Attacks
- Contact author(s)
- w rocking @ gmail com,guotingting @ iie ac cn,hulei @ iie ac cn,yedingfeng @ iie ac cn
- History
- 2021-05-18: last of 8 revisions
- 2020-12-24: received
- See all versions
- Short URL
- https://ia.cr/2020/1595
- License
-
CC BY