Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Beyond-Birthday-Bound, Message Authentication Codes, Quantum Attacks

Original Publication (with minor differences): PQCrypto 2021

Date: received 22 Dec 2020, last revised 18 May 2021

Contact author: w rocking at gmail com, guotingting at iie ac cn, hulei at iie ac cn, yedingfeng at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20210518:072645 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]