Paper 2006/043
New Proofs for NMAC and HMAC: Security Without Collision-Resistance
Mihir Bellare
Abstract
HMAC was proved by Bellare, Canetti and Krawczyk [2] to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made.
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in CRYPTO 2006
- Keywords
- message authenticationHMACPRFsecurity proof
- Contact author(s)
- mihir @ eng ucsd edu
- History
- 2014-04-10: last of 10 revisions
- 2006-02-06: received
- See all versions
- Short URL
- https://ia.cr/2006/043
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/043,
author = {Mihir Bellare},
title = {New Proofs for {NMAC} and {HMAC}: Security Without Collision-Resistance},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/043},
year = {2006},
url = {https://eprint.iacr.org/2006/043}
}
