Improved Single-Key Distinguisher on HMAC-MD5 and Key Recovery Attacks on Sandwich-MAC-MD5 and MD5-MAC

Yu SASAKI  Gaoli WANG  Lei WANG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.1   pp.26-38
Publication Date: 2015/01/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Based Cryptography
Keyword: 
HMAC,  Sandwich-MAC,  MD5-MAC,  MD5,  key recovery,  

Full Text: PDF(1.3MB)
>>Buy this Article


Summary: 
This paper presents key recovery attacks on Sandwich-MAC instantiating MD5, where Sandwich-MAC is an improved variant of HMAC and achieves the same provable security level and better performance especially for short messages. The increased interest in lightweight cryptography motivates us to analyze such a MAC scheme. Our attacks are based on a distinguishing-H attack on HMAC-MD5 proposed by Wang et al. We first improve its complexity from 297 to 289.04. With this improvement, we then propose key recovery attacks on Sandwich-MAC-MD5 by combining various techniques such as distinguishing-H for HMAC-MD5, IV Bridge for APOP, dBB-near-collisions for related-key NMAC-MD5, meet-in-the-middle attack etc. In particular, we generalize a previous key-recovery technique as a new tool exploiting a conditional key-dependent distribution. Surprisingly, a key which is even longer than the tag size can be recovered without the knowledge of the key size. Finally, our attack also improves the previous partial-key (K1) recovery on MD5-MAC, and extends it to recover both of K1 and K2.