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.