what's wrong with HMAC?
Bart Preneel
bart.preneel at esat.kuleuven.be
Tue May 2 18:14:39 EDT 2006
On Tue, 2 May 2006, William Allen Simpson wrote:
> I had a preliminary paper showing that the nested N-MAC/H-MAC design was
> actually *weaker* than envelope style IP-MAC, [...]
But then again, Paul van Oorschot and myself found a key recovery attack
on envelope MAC that presents a certificational weakness of envelope MAC
as described in RFC 1828 (our Eurocrypt'96 paper). Once a collision is
found, one has both forgeries and key recovery, which is not the case for HMAC.
I must say that I don't understand this claim:
> The basic problem is that the nested method truncates the internal
> chaining variables, while the envelope method preserves them and
> truncates only upon final output.
...but of course I would like to see your preliminary paper (even after 10
years).
What we know now is that keying MDx-type compression functions through the IV/H_i
input is more secure than through the message input; this has no immediate
implication on the discussion of HMAC/envelope MAC however. I still maintain
that I would prefer to key the compression function in both inputs (a la MDx-MAC)
- maybe the common sense approach that is better than HMAC and envelope MAC.
Finally, I want to strongly defend theoretical analysis to improve the
understanding of a scheme; but it is important to understand the model and
assumptions of the reduction proof, the implications and limitations of the
analysis and not to overclaim.
--Bart
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven
Dept. Electrical Engineering-ESAT / COSIC
Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, BELGIUM
-------------------------------------------------------------------------------
On Tue, 2 May 2006, William Allen Simpson wrote:
> Hal Finney wrote:
> > Travis H. writes:
> >> Ross Anderson once said cryptically,
> >>> HMAC has a long story attched to it - the triumph of the
> >>> theory community over common sense
> >> He wouldn't expand on that any more... does anyone have an idea of
> >> what he is referring to?
> >
> > I might speculate, based on what you write here, that he believed that
> > the simpler, ad hoc constructions often used in the days preceding
> > HMAC were good enough in practice, and that the theoretical proofs of
> > security for HMAC were given too much weight. The original HMAC paper
> > is at http://www-cse.ucsd.edu/~mihir/papers/kmd5.pdf and the authors
> > show in section 6 various attacks on ad hoc constructions, but some of
> > them are admittedly impractical.
> >
> Actually, that paper really describes "version-2" (or even version-N) of
> HMAC, as the original design paper had some serious flaws.
>
> And the other constructions were not so much /ad hoc/ (they had been
> proposed by various established security folks with varying amounts of
> accompanying math) as *incompletely analyzed*. A part of the problem is
> that independent analysis wasn't forthcoming until long after
> implementation. The problem wasn't considered enough of a "hot topic" at
> the time.
>
> Another part of the problem was that the publication lag of RFCs was (is)
> so ridiculously long. The envelope method published in RFC 1828 was a
> variant of the original developed as part of the IPv6 design circa 1993:
> key, fill, datagram, key, fill
>
> but had been replaced circa 1995 by IP-MAC (in Photuris):
> key, fill, datagram, fill, key, fill
>
> yet was not officially published (due to politics) for MD5 until:
> * RFC 2522, "Photuris: Session-Key Management Protocol", March 1999.
>
> and SHA1 even later (took so long it was published as "Historic"):
> * RFC 2841, "IP Authentication using Keyed SHA1 with Interleaved Padding
> (IP-MAC)", November 2000.
>
> Filling (padding to the natural block boundary of the algorithm) was/is
> accomplished by the usual M-D strengthening technique.
>
> I had a preliminary paper showing that the nested N-MAC/H-MAC design was
> actually *weaker* than envelope style IP-MAC, but at the request of some
> colleagues saved it for a book they were putting together. Sadly, that
> book was never published.
>
> The basic problem is that the nested method truncates the internal
> chaining variables, while the envelope method preserves them and
> truncates only upon final output.
>
> Of course, AFAICT, the trailing key makes the various recent attacks
> on MD5 and SHA1 entirely inapplicable.
> --
> William Allen Simpson
> Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
>
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven tel. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC fax. +32 16 32 19 69
Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, BELGIUM
bart.preneel at esat.kuleuven.be
http://www.esat.kuleuven.be/~preneel
-------------------------------------------------------------------------------
On Tue, 2 May 2006, William Allen Simpson wrote:
> Hal Finney wrote:
> > Travis H. writes:
> >> Ross Anderson once said cryptically,
> >>> HMAC has a long story attched to it - the triumph of the
> >>> theory community over common sense
> >> He wouldn't expand on that any more... does anyone have an idea of
> >> what he is referring to?
> >
> > I might speculate, based on what you write here, that he believed that
> > the simpler, ad hoc constructions often used in the days preceding
> > HMAC were good enough in practice, and that the theoretical proofs of
> > security for HMAC were given too much weight. The original HMAC paper
> > is at http://www-cse.ucsd.edu/~mihir/papers/kmd5.pdf and the authors
> > show in section 6 various attacks on ad hoc constructions, but some of
> > them are admittedly impractical.
> >
> Actually, that paper really describes "version-2" (or even version-N) of
> HMAC, as the original design paper had some serious flaws.
>
> And the other constructions were not so much /ad hoc/ (they had been
> proposed by various established security folks with varying amounts of
> accompanying math) as *incompletely analyzed*. A part of the problem is
> that independent analysis wasn't forthcoming until long after
> implementation. The problem wasn't considered enough of a "hot topic" at
> the time.
>
> Another part of the problem was that the publication lag of RFCs was (is)
> so ridiculously long. The envelope method published in RFC 1828 was a
> variant of the original developed as part of the IPv6 design circa 1993:
> key, fill, datagram, key, fill
>
> but had been replaced circa 1995 by IP-MAC (in Photuris):
> key, fill, datagram, fill, key, fill
>
> yet was not officially published (due to politics) for MD5 until:
> * RFC 2522, "Photuris: Session-Key Management Protocol", March 1999.
>
> and SHA1 even later (took so long it was published as "Historic"):
> * RFC 2841, "IP Authentication using Keyed SHA1 with Interleaved Padding
> (IP-MAC)", November 2000.
>
> Filling (padding to the natural block boundary of the algorithm) was/is
> accomplished by the usual M-D strengthening technique.
>
> I had a preliminary paper showing that the nested N-MAC/H-MAC design was
> actually *weaker* than envelope style IP-MAC, but at the request of some
> colleagues saved it for a book they were putting together. Sadly, that
> book was never published.
>
> The basic problem is that the nested method truncates the internal
> chaining variables, while the envelope method preserves them and
> truncates only upon final output.
>
> Of course, AFAICT, the trailing key makes the various recent attacks
> on MD5 and SHA1 entirely inapplicable.
> --
> William Allen Simpson
> Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
>
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list