Forgery Attacks on Several Beyond-Birthday-Bound Secure MACs
(2023) 29th International Conferenceon the Theory and Application of Cryptology and Information Security — Location: Guangzhou, China (4.December.2023)
Files
ForgeryAttacksonSeveralBeyond-Birthday-BoundSecureMACs.pdf
Open Access - Adobe PDF
- 675.1 KB
Details
- Authors
- Abstract
- At CRYPTO’18, Datta et al. proposed nPolyMAC and proved the security up to 22𝑛/3 authentication queries and 2𝑛 verification queries. At EUROCRYPT’19, Dutta et al. proposed CWC+ and showed the se- curity up to 22𝑛/3 queries. At FSE’19, Datta et al. proposed PolyMAC and its key-reduced variant 2k-PolyMAC, and showed the security up to 22𝑛/3 queries. This security bound was then improved by Kim et al. (EUROCRYPT’20) and Datta et al (FSE’23) respectively to 23𝑛/4 and in the multi-user setting. At FSE’20, Chakraborti et al. proposed PDM*MAC and 1k-PDM*MAC, and showed the security up to 22𝑛/3 queries. Recently, Chen et al. proposed nEHtM+ 𝑝 and showed the se- curity up to 22𝑛/3 queries. In this paper, we show forgery attacks on nPolyMAC, CWC+, PolyMAC, 2k-PolyMAC, PDM*MAC, 1k-PDM*MAC and nEHtM+ 𝑝 . Our attacks exploit some vulnerability in the underlying polynomial hash function Poly, and (i) require only one authentication query and one verification query; (ii) are nonce-respecting; (iii) succeed with probability 1. Thus, our attacks disprove the provable high security claims of these schemes. We then revisit their security analyses and iden- tify what went wrong. Finally, we propose two solutions that can restore the beyond-birthday-bound security.
- Affiliations
Citations
Shen, Y., Standaert, F.-X., & Lei Wang. (2023). Forgery Attacks on Several Beyond-Birthday-Bound Secure MACs. Advances in Cryptology - {ASIACRYPT} 2023. Published. 29th International Conferenceon the Theory and Application of Cryptology and Information Security, Guangzhou, China. https://doi.org/10.1007/978-981-99-8727-6_6