DOC PREVIEW
New Proofs for NMAC and HMAC

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A preliminary version of this paper appears in Advances in Cryptology – CRYPTO ’06, LectureNotes in Computer Science Vol. 4117 , C. Dwork ed., Springer-Verlag, 2006. This is the full version.New Proofs for NMAC and HMAC:Security without Collision-ResistanceMihir Bellare∗June 2006AbstractHMAC was proved in [3] to be a PRF assuming that (1) the underlying compression functionis a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacksshow that assumption (2) is false for MD5 and SHA-1, removing the proof-based support forHMAC in these cases. This paper proves that HMAC is a PRF under the sole assumptionthat the compression function is a PRF. This recovers a proof based guarantee since no knownattacks compromise the pseudorandomness of the compression function, and it also helps explainthe resistance-to-attack that HMAC has shown even when implemented with hash functionswhose (weak) collision resistance is compromised. We also show that an even weaker-than-PRFcondition on the compression function, namely that it is a privacy-preserving MAC, suffices toestablish HMAC is a secure MAC as long as the hash function meets the very weak requirementof being computationally almost universal, where again the value lies in the fact that knownattacks do not invalidate the assumptions made.Keywords: Message authentication, hash functions, Pseudorandom Functions, Carter-Wegman.∗Dept. of Computer Science & Engineering 0404, University of California San Diego, 9500 Gilman Drive, LaJolla, CA 92093-0404, USA. Email: [email protected]. URL: http://www-cse.ucsd.edu/users/mihir. Supportedin part by NSF grant CNS-0524765, an IBM Faculty Partnership Development Award, and a gift from INTELCorporation.1Contents1 Introduction 32 Definitions 53 Security of NMAC 73.1 The results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 Tightness of bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.4 Proof of Lemma 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.5 Proof of Theorem 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 MAC-security of NMAC under weaker assumptions 194.1 Privacy preserving MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.3 Proof of Lemma 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Security of HMAC 245.1 Security of GHMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Single-keyed HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3 Lifting the results of Section 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27References 27A Attacking weak collision-resistance 29B The reduction-from-pf-PRF proof 2921 IntroductionHMAC [3] is a popular cryptographic-hash-function-based MAC. The basic construct is actuallyNMAC, of which HMAC can be viewed as a derivative.The constructions. Succinctly:NMAC(KoutkKin, M) = H∗(Kout, H∗(Kin, M))HMAC(KoutkKin, M) = H(KoutkH(KinkM)) .Here H is a cryptographic hash function, eg. MD5 [28], SHA-1 [26], or RIPEMD-160 [17]. Leth: {0, 1}c× {0, 1}b→ {0, 1}cdenote the underlying compression function. (Here b = 512 whilec is 128 or 160.) Let h∗be the iterated compression function which on input K ∈ {0, 1}cand amessage x = x[1] . . . x[n] consisting of b-bit blocks, lets a[0] = K and a[i] = h(a[i − 1], x[i]) fori = 1, . . . , n, and finally returns a[n]. Then H∗(K, M) = h∗(K, M∗) and H(M) = H∗(IV, M),where M∗denotes M padded appropriately to a length that is a positive multiple of b and IV isa public c-bit initial vector that is fixed as part of the description of H. Both NMAC and HMACuse two keys, which in the case of NMAC are of length c bits each, and in the case of HMAC oflength b bits each and derived from a single b-bit key. HMAC is a non-intrusive version of NMACin the sense that it uses the cryptographic hash function only as a black box, making it easier toimplement.Usage. HMAC is standardized via an IETF RFC [22], a NIST FIPS [25] and ANSI X9.71 [1],and implemented in SSL, SSH, IPsec and TLS amongst other places. It is often used as a PRF(pseudorandom function [19]) rather than merely as a MAC. In particular this is the case when itis used for key-derivation, as in TLS [16] and IKE (the Internet Key Exchange protocol of IPsec)[20]. HMAC is also used as a PRF in a proposed standard for one-time passwords [24].What’s known. The results are for NMAC but can be lifted to HMAC. It is shown in [3] thatNMAC is a secure PRF if (1) the underlying compression function h is a secure PRF, and also(2) that the hash function H is weakly collision resistant (WCR). The latter, introduced in [3],is a relaxation of collision resistance (CR) that asks that it be computationally infeasible for anadversary, given an oracle for H∗(K, ·) under a hidden key K, to find a collision, meaning distinctinputs M1, M2such that H∗(K, M1) = H∗(K, M2).The problem. HMAC is usually implemented with MD5 or SHA-1. But, due to recent attacks[32, 31], these functions are not WCR. Thus the assumption on which the proof of [3] is based is nottrue. This does not reflect any actual weaknesses in the NMAC or HMAC constructs, on which noattacks …


New Proofs for NMAC and HMAC

Download New Proofs for NMAC and HMAC
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view New Proofs for NMAC and HMAC and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view New Proofs for NMAC and HMAC 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?