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

摘要

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. We first improve a distinguishing-H attack on HMAC-MD5 proposed by Wang et al. We then propose key recovery attacks on Sandwich-MAC-MD5 by combining various techniques such as distinguishing-H for HMAC-MD5, Ⅳ 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. Our attack also improves the partial-key (K_1) recovery on MD5-MAC, and extends it to recover both K_1 and K_2.