Paper 2020/1595

Attack Beyond-Birthday-Bound MACs in Quantum Setting

Tingting Guo and Peng Wang and Lei Hu and Dingfeng Ye

Abstract

The security in the quantum setting of a series of message authentication codes (MACs) with provable beyond-birthday-bound (BBB) security is analyzed in this paper, including SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and some variants (2K-ECBC_Plus, GCM-SIV2, 1k-PMAC_Plus, 2K-PMAC_Plus, PMAC_TBC3k and 2kf9). All these MACs have a security proof up to $2^{2n/3}$ (even $2^{3n/4}$) queries assuming the block size of the underlying (tweakable) block cipher is $n$ bits. Given that the adversary can make quantum queries, we consider secret state recovery and partial key recovery attacks against these MACs. Both attacks lead to successful forgeries. For the first one, we apply Grover-meet-Simon algorithm to recover some secret states of SUM-ECBC, PolyMAC, PMAC_Plus, 3kf9 and so on. Our research shows this forgery attack costs at most $O(2^{n/2}n)$ quantum queries using at most $O(n^{2})$ qubits. For the second one, we apply Grover's algorithm to recover partial keys of PMAC_Plus, 3kf9, PMAC_TBC3k and so on. Our research shows this forgery attack costs $O(2^{m/2})$ quantum queries and $O(m+n^2)$ qubits assuming the size of one key is $m$ bits. As far as we know, these are the first quantum attacks against BBB MACs. Our results show that in the quantum setting their securities go back to birthday bounds.