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.
Yu SASAKI
NTT Corporation
Gaoli WANG
Donghua University
Lei WANG
Nanyang Technologocal University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yu SASAKI, Gaoli WANG, Lei WANG, "Improved Single-Key Distinguisher on HMAC-MD5 and Key Recovery Attacks on Sandwich-MAC-MD5 and MD5-MAC" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 1, pp. 26-38, January 2015, doi: 10.1587/transfun.E98.A.26.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.26/_p
Copy
@ARTICLE{e98-a_1_26,
author={Yu SASAKI, Gaoli WANG, Lei WANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Single-Key Distinguisher on HMAC-MD5 and Key Recovery Attacks on Sandwich-MAC-MD5 and MD5-MAC},
year={2015},
volume={E98-A},
number={1},
pages={26-38},
abstract={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.},
keywords={},
doi={10.1587/transfun.E98.A.26},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Improved Single-Key Distinguisher on HMAC-MD5 and Key Recovery Attacks on Sandwich-MAC-MD5 and MD5-MAC
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 26
EP - 38
AU - Yu SASAKI
AU - Gaoli WANG
AU - Lei WANG
PY - 2015
DO - 10.1587/transfun.E98.A.26
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2015
AB - 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.
ER -