[Cfrg] KDF==MAC? and: how about HKDF-Poly1305? Re: Answers to HKDF questions
Zooko Wilcox-O'Hearn <zooko@zooko.com> Fri, 04 December 2009 23:20 UTC
Return-Path: <zooko@zooko.com>
X-Original-To: cfrg@core3.amsl.com
Delivered-To: cfrg@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id F18F53A690D for <cfrg@core3.amsl.com>; Fri, 4 Dec 2009 15:20:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.599
X-Spam-Level:
X-Spam-Status: No, score=-4.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, GB_I_LETTER=-2]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uERqLbEWshnB for <cfrg@core3.amsl.com>; Fri, 4 Dec 2009 15:20:29 -0800 (PST)
Received: from postman.allmydata.com (postman.allmydata.com [207.7.153.130]) by core3.amsl.com (Postfix) with ESMTP id E56CA3A6829 for <cfrg@irtf.org>; Fri, 4 Dec 2009 15:20:29 -0800 (PST)
Received: from localhost (localhost [127.0.0.1]) by postman.allmydata.com (Postfix) with ESMTP id 11965223466F; Fri, 4 Dec 2009 15:20:20 -0800 (PST)
X-Virus-Scanned: Ubuntu amavisd-new at allmydata.com
Received: from postman.allmydata.com ([127.0.0.1]) by localhost (postman.allmydata.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mZT+p4JAQOfb; Fri, 4 Dec 2009 15:20:07 -0800 (PST)
Received: from [172.21.221.239] (ucb-np1-123.colorado.edu [128.138.64.123]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by postman.allmydata.com (Postfix) with ESMTPSA id 79B8B223432D; Fri, 4 Dec 2009 15:20:07 -0800 (PST)
In-Reply-To: <1AA41B0A-F458-444A-BFC0-78A49FAB6F43@cisco.com>
References: <e89b43830910211838x2e1ca67cgaf48d02cd4008710@mail.gmail.com> <46DFA920-54BF-4567-90AF-6742C8FAA5F2@zooko.com> <e89b43830910221609y75514633m8064d5b19d8d54e4@mail.gmail.com> <823D9A4C-11AB-4CBE-A554-D8FF62AC6166@zooko.com> <1AA41B0A-F458-444A-BFC0-78A49FAB6F43@cisco.com>
Mime-Version: 1.0 (Apple Message framework v753.1)
Content-Type: text/plain; charset="US-ASCII"; delsp="yes"; format="flowed"
Message-Id: <D4BA0244-BDB0-4EE5-8018-E2E1A49578B9@zooko.com>
Content-Transfer-Encoding: 7bit
From: Zooko Wilcox-O'Hearn <zooko@zooko.com>
Date: Fri, 04 Dec 2009 16:20:01 -0700
To: David McGrew <mcgrew@cisco.com>
X-Mailer: Apple Mail (2.753.1)
Cc: cfrg@irtf.org
Subject: [Cfrg] KDF==MAC? and: how about HKDF-Poly1305? Re: Answers to HKDF questions
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 04 Dec 2009 23:20:32 -0000
On Monday, 2009-10-26, at 5:07 , David McGrew wrote: >> In the context of the extraction stage, he seemed to say that a >> Carter-Wegman MAC such as Poly1305 should be analyzed merely as a >> statistical extractor, not as a computational extractor. Is that >> what you meant to say, David? > > Yes, that's right. > >> I don't see why that would be so. > > Check out S2.1 of http://cs.haifa.ac.il/~ronen/online_papers/survey.ps Okay, I've looked at that section. It seems to be talking about Carter-Wegman universal hash functions, not about secure MACs built on such functions. According to my, admittedly limited, understanding, a Carter-Wegman hash function could never be a computational extractor because there is nothing secret from an attacker, so it is trivial for an attacker to distinguish the output of a Carter-Wegman hash function from a truly uniform random string. However, a Carter-Wegman-based MAC such as Poly1305 does have a secret that can be withheld from the attacker in exactly the same way that HMAC has -- the MAC key. Do I understand correctly, David -- were you thinking of a Carter- Wegman hash function rather than of a Carter-Wegman MAC? So as far as I understand, an HKDF which uses Poly1305 internally should enjoy the same analysis based on the PRF serving as a computational extractor as an HKDF which uses HMAC internally. What security property do we want of a KDF anyway? Let's denote a KDF as a function f which is chosen from a family of functions by a key "s", and which takes an input "x" and outputs a result "r": r = f_s(x) I think we want the function f to have the property Unpredictable Function [1]. This means if I give you access to an oracle that will compute f(x) for you, then you can't guess what it will give you for any x that you didn't query the oracle for. That is also exactly the definition of a secure MAC! So, is the KDF problem solved, and the answer is "use a MAC"? I suppose this is perhaps the inspiration behind HKDF. It appears to me that Poly1305 has a better security guarantee than HMAC has for this purpose, and that the ciphers that can currently be used by Poly1305 (such as AES, Serpent, or Salsa20) are more likely to be secure than the hash functions that can currently be used by HMAC (such as SHA-256 and SHA-512). The security guarantee of Poly1305 is simply that if the underlying cipher is indistinguishable from a PRP, then Poly1305-CIPHER is an Unpredictable Function [2]. The best security guarantee of HMAC is that if the underlying hash function is both a "Privacy-Preserving MAC" (which is a stronger property than a MAC) and a "computationally almost universal" hash function then HMAC has the Unpredictable Function property [3, section 4]. So already Poly1305 requires less of its underlying components than HMAC does. But in addition to that, the underlying components that we have available to use with Poly1305 look stronger than the ones that we have available to use with HMAC. Already there are demonstrations that HMAC instantiated with popular, real-world hash functions like MD5 and SHA-1 is not secure [4]. (By the way, I don't know how to reconcile the results of [4] with the results of [3]. I suppose this implies that SHA-1 is either not a Privacy-Preserving MAC or not a computationally almost universal hash function.) There is a widespread concert that SHA-256 might turn out to be weak, as its older siblings MD5 and SHA-1 have. (That's why I'm holding my breath waiting for SHA-3.) If I want to implement and deploy HKDF today (and I do!), and I use HMAC, and I don't want to rely on the long-term safety of SHA-256, then I have few remaining options. SHA-512 is prohibitively expensive on one of my primary target platforms -- 32-bit embedded ARM boxes [5]. On the other hand if I deploy HKDF today using Poly1305 instead of HMAC, then I can use AES, and even if I don't want to use AES then I have several good alternatives such as Serpent and Salsa20. It seems much less likely that AES, Serpent, or Salsa20 will turn out to be distinguishable from a PRP than that SHA-256 will turn out to be not a Privacy-Preserving MAC or not a computationally almost universal hash function. In addition to these security advantages, Poly1305-AES or Poly1305- Salsa20 enjoy a substantial performance advantage over HMAC-SHA-256. So if I were forced to stop researching and start implementing today, I think I might implement HKDF-Poly1305 instead of HKDF-HMAC. Regards, Zooko Wilcox-O'Hearn P.S. Aha, and now I find this letter that Prof. Bernstein wrote to this list in 2006 which makes the same points plus some other good points: http://www.ietf.org/mail-archive/web/cfrg/current/ msg01167.html . I think I read that letter at the time, but it is worth re-reading. [1] Moni Naor, Omer Reingold: "From unpredictability to indistinguishability: A simple construction of pseudo-random functions from MACs" http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10.1.1.121.6517 [2] Daniel J. Bernstein: "The Poly1305-AES message-authentication code" http://cr.yp.to/mac/poly1305-20050329.pdf [3] Mihir Bellare: "New Proofs for NMAC and HMAC: Security without Collision-Resistance (2006)" http://citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.60.7396 [4] Christian Rechberger, Vincent Rijmen: "New Results on NMAC/HMAC when Instantiated with Popular Hash Functions" http://www.jucs.org/ jucs_14_3/new_results_on_nmac/jucs_14_3_0347_0376_rechberger.pdf [5] http://bench.cr.yp.to/results-hash.html#arm-apollo
- Re: [Cfrg] Answers to HKDF questions Zooko Wilcox-O'Hearn
- [Cfrg] Answers to HKDF questions Hugo Krawczyk
- Re: [Cfrg] Answers to HKDF questions David McGrew
- Re: [Cfrg] Answers to HKDF questions Hugo Krawczyk
- Re: [Cfrg] Answers to HKDF questions Blumenthal, Uri
- Re: [Cfrg] Answers to HKDF questions Hugo Krawczyk
- Re: [Cfrg] Answers to HKDF questions Zooko Wilcox-O'Hearn
- Re: [Cfrg] Answers to HKDF questions David McGrew
- [Cfrg] KDF==MAC? and: how about HKDF-Poly1305? Re… Zooko Wilcox-O'Hearn
- Re: [Cfrg] KDF==MAC? and: how about HKDF-Poly1305… David McGrew
- [Cfrg] Fwd: KDF==MAC? and: how about HKDF-Poly130… Hugo Krawczyk