Paper 2017/653

Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions

Fanbao Liu and 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Universal forgerybirthday attackCBC-MACPMACCAESARquantum model.
Contact author(s)
lfbjantie @ 163 com
History
2017-08-03: revised
2017-07-05: received
See all versions
Short URL
https://ia.cr/2017/653
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/653,
      author = {Fanbao Liu and Fengmei Liu},
      title = {Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/653},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/653}},
      url = {https://eprint.iacr.org/2017/653}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.