[GPR14] The Exact PRF-Security of NMAC and HMAC
Authors: Peter Gaži, Krzysztof Pietrzak, Michal Rybár | Venue: CRYPTO 2014 | Source
Abstract
NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC.
NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto’96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto’06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction.
Our first contribution is a simpler and uniform proof: If f is an -secure PRF (against q queries) and a -non-adaptively secure PRF (against q queries), then NMAC is an -secure PRF against q queries of length at most l blocks each.
We then show that this bound is basically tight. For the most interesting case where we prove this by constructing an f for which an attack with advantage exists. This also violates the bound on the PRF-security of NMAC recently claimed by Koblitz and Menezes.
Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto’99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight bound for this step, improving over the trivial bound of . The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto’05]. We also analyze a variant of NI that does not include the message length in the last call to the compression function, proving a bound in this case.
BibTeX
@Inproceedings{C:GazPieRyb14,
author = {Peter Ga{\v{z}}i and Krzysztof Pietrzak and Michal Ryb{\'a}r},
title = {The Exact {PRF}-Security of {NMAC} and {HMAC}},
pages = {113--130},
editor = {Juan A. Garay and Rosario Gennaro},
booktitle = {Advances in Cryptology -- {CRYPTO}~2014, Part~I},
volume = {8616},
series = {Lecture Notes in Computer Science},
address = {Santa Barbara, CA, USA},
month = {aug~17--21},
publisher = {Springer Berlin Heidelberg, Germany},
year = {2014},
doi = {10.1007/978-3-662-44371-2_7},
}