[Resource Topic] 2018/793: Universal Forgery and Multiple Forgeries of MergeMAC and Generalized Constructions

Welcome to the resource topic for 2018/793

Universal Forgery and Multiple Forgeries of MergeMAC and Generalized Constructions

Authors: Tetsu Iwata, Virginie Lallemand, Gregor Leander, Yu Sasaki


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.

ePrint: https://eprint.iacr.org/2018/793

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 .