[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Cfrg] KDF==MAC? and: how about HKDF-Poly1305? Re: Answers to HKDF questions
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