Welcome to the resource topic for 2017/653
Title:
Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions
Authors: Fanbao Liu, Fengmei Liu
Abstract:An universal forgery attack means that for any given message M, an adversary without the key can forge the corresponding Message Authentication Code (MAC) tag \tau, and the pair (M,\tau) can be verified with probability 1. For a idea MAC, the universal forgery attack should be infeasible to be implemented, whose complexity is believed to be min{(2^n, 2^k)} queries in the classic setting, where n is the tag length and k is the key length of the MAC, respectively. In this paper, we launch a general universal forgery attack to some blockcipher-based MACs and authenticated encryptions (AEs) using birthday attack, whose complexity is about O(2^{n/2}) queries in the classic setting. The attack shows that such MACs and AEs are totally insecure. However, this attack is not applicable in the quantum model, since no inclusion of period in the input messages is guaranteed. We also propose other generic universal forgery attacks using collision finding with structural input messages with complexity of O(2^{n/2}), by birthday paradox in the classic setting. Since our attacks are based on the collision finding with fixed but unknown differences (or period), such attacks can also be implemented with only O(n) queries using \textit{Simon’s} algorithm in the quantum model, which shows that such MACs and AEs are completely broken in the quantum model. Our attacks can be applied to CBC-MAC, XCBC, EMAC, OMAC, CMAC, PC-MAC, MT-MAC, PMAC, PMAC with parity, LightMAC and some of their variants. Moreover, such attacks are also applicable to the authenticated encryptions of the third round of the CAESAR candidates: CLOC, SILC, AEZ, COLM (including COPA and ELmD) and Deoxys.
ePrint: https://eprint.iacr.org/2017/653
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .