[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