Paper 2018/793

Universal Forgery and Multiple Forgeries of MergeMAC and Generalized Constructions

Tetsu Iwata, Virginie Lallemand, Gregor Leander, and Yu Sasaki

Abstract

This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim $64$-bit security and imply a risk of accepting beyond-birthday-bound queries. This paper first shows that it is inevitable to limit the number of queries up to the birthday bound, because a generic universal forgery against CBC-like MAC can be adopted to MergeMAC. Afterwards another attack is presented that works with a very few number of queries, 3 queries and $2^{58.6}$ computations of $\mathcal{F}$, by applying a preimage attack against weak $\mathcal{F}$, which breaks the claimed security. The analysis is then generalized to a MergeMAC variant where $\mathcal{F}$ is replaced with a one-way function $\mathcal{H}$. Finally, multiple forgeries are discussed in which the attacker's goal is to improve the ratio of the number of queries to the number of forged tags. It is shown that the attacker obtains tags of $q^2$ messages only by making $2q-1$ queries in the sense of existential forgery, and this is tight when $q^2$ messages have a particular structure. For universal forgery, tags for $3q$ arbitrary chosen messages can be obtained by making $5q$ queries.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
MergeMACuniversal forgerymultiple forgeriespublic finalizationpreimagesplice-and-cutHellman's time-memory tradeoff
Contact author(s)
sasaki yu @ lab ntt co jp
History
2018-09-01: received
Short URL
https://ia.cr/2018/793
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/793,
      author = {Tetsu Iwata and Virginie Lallemand and Gregor Leander and Yu Sasaki},
      title = {Universal Forgery and Multiple Forgeries of MergeMAC and Generalized Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/793},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/793}},
      url = {https://eprint.iacr.org/2018/793}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.