For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Cryptanalyses on a Merkle-Damgård Based MAC — Almost Universal Forgery and Distinguishing-H Attacks
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Based Cryptography
LPMAC, distinguishing-H attack, almost universal forgery attack, multi-collision, diamond structure, prefix freeness,
Full Text: PDF(1MB)
>>Buy this Article
This paper presents two types of cryptanalysis on a Merkle-Damgård hash based MAC, which computes a MAC value of a message M by Hash(K||l||M) with a shared key K and the message length l. This construction is often called LPMAC. Firstly, we present a distinguishing-H attack against LPMAC instantiated with any narrow-pipe Merkle-Damgård hash function with O(2n/2) queries, which indicates the incorrectness of the widely believed assumption that LPMAC instantiated with a secure hash function should resist the distinguishing-H attack up to 2n queries. In fact, all of the previous distinguishing-H attacks considered dedicated attacks depending on the underlying hash algorithm, and most of the cases, reduced rounds were attacked with a complexity between 2n/2 and 2n. Because it works in generic, our attack updates these results, namely full rounds are attacked with O(2n/2) complexity. Secondly, we show that an even stronger attack, which is a powerful form of an almost universal forgery attack, can be performed on LPMAC. In this setting, attackers can modify the first several message-blocks of a given message and aim to recover an internal state and forge the MAC value. For any narrow-pipe Merkle-Damgård hash function, our attack can be performed with O(2n/2) queries. These results show that the length prepending scheme is not enough to achieve a secure MAC.