Subject: [Cfrg] erratum for hmac what do we think...

From: Stephen Farrell <[email-masked]>
Date: Thu, 2 Feb 2017 02:24:44 +0000

Hiya,

There's an erratum posted for hmac [1] where I'd be
interested in what folks here think.

I'm unsure if this is a real problem, esp given that
there are I guess a lot of implementations.

And even if it were a real problem, I'm not sure we'd
want that fix.

Opinions welcome...

Thanks,
S.

[1]
https://www.rfc-editor.org/errata_search.php?rfc=2104&eid=4809&rec_status=15&area_acronym=&errata_type=&wg_acronym=&submitter_name=&stream_name=&submit_date=&presentation=records

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 2 Feb 2017 16:21:43 +0300

Hi Stephen,

I would let cryptographers decide whether it is a real problem
(I'm not a cryptographer), but the proposed resolution 
will break existing standards and implementations.
For example, in IKEv2 there is a requirement that 
PRFs MUST accept keys of any length and HMAC is widely
used as PRF (e.g. PRF_HMAC_SHA1 is currently MTI).
And since nonces are used as a PRF key for SKEYSEED 
computation in IKEv2, the key may be quite long. 
So, regardless whether this is a real problem,
the proposed resolution looks bad.

Regards,
Valery Smyslov.

> https://www.rfc-
> editor.org/errata_search.php?rfc=2104&eid=4809&rec_status=15&area_acronym=&errata_type=&wg_ac
> ronym=&submitter_name=&stream_name=&submit_date=&presentation=records

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 2 Feb 2017 14:07:49 +0000

Dear CFRG,

It'd be great if some HMAC experts could take a look at this proposed
erratum and give a view on it.

I looked quickly myself. It's an undesirable property, but I don't think
it's disastrous (yes, I could invent scenarios where one could come
unstuck because of it). It reminds me somewhat of the well-known, and
again somewhat unfortunate, fact that HMAC keys of different lengths can
end up being padded to form colliding keys.

Cheers,

Kenny 

On 02/02/2017 02:24, "Cfrg on behalf of Stephen Farrell"
<[email-masked] on behalf of [email-masked]> wrote:

>https://www.rfc-editor.org/errata_search.php?rfc=2104&eid=4809&rec_status=
>15&area_acronym=&errata_type=&wg_acronym=&submitter_name=&stream_name=&sub
>mit_date=&presentation=records
>

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Thu, 2 Feb 2017 14:20:03 +0000

Kenny just made a great point that HMAC is not a PRF: it is trivial to find 2 keys which produce the same HMAC output.

Quynh.

________________________________
From: Cfrg <[email-masked]> on behalf of Paterson, Kenny <[email-masked]>
Sent: Thursday, February 2, 2017 9:07 AM
To: Stephen Farrell; [email-masked]
Subject: Re: [Cfrg] erratum for hmac what do we think...

Dear CFRG,

Cheers,

Kenny

>mit_date=&presentation=records

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Thu, 2 Feb 2017 14:22:32 +0000

One way to fix that is always hash the key.

Quynh.

________________________________
From: Cfrg <[email-masked]> on behalf of Dang, Quynh (Fed) <[email-masked]>
Sent: Thursday, February 2, 2017 9:20:03 AM
To: Paterson, Kenny; Stephen Farrell; [email-masked]
Subject: Re: [Cfrg] erratum for hmac what do we think...

Quynh.

Dear CFRG,

Cheers,

Kenny

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 2 Feb 2017 15:21:35 +0000

> I looked quickly myself. It's an undesirable property, but I don't think it's
> disastrous

If this is accurate (paging Hugo... :) then I think the best reply to this is a couple of sentences in the security considerations advising applications that are concerned to limit keys to B bytes instead of hashing.

---

From: Dan Brown <[email-masked]>
Date: Thu, 2 Feb 2017 15:26:39 +0000

http://ia.cr/2013/382

might be relevant, theoretically, but I'm no expert...

Sent from my BlackBerry 10 smartphone on the Rogers network.
  Original Message
From: Paterson, Kenny
Sent: Thursday, February 2, 2017 9:08 AM
To: Stephen Farrell; [email-masked]
Subject: Re: [Cfrg] erratum for hmac what do we think...

Dear CFRG,

Cheers,

Kenny

---

From: Xander Sherry <[email-masked]>
Date: Thu, 2 Feb 2017 10:52:48 -0500

Speaking not as an HMAC expert but as an application security guy, while I
agree that the ares where the design of HMAC could be improved, the
vulnerability described in the proposed errata is, in my opinion, less a
security issue with HMAC, and more a security issue with a badly designed
system.  I can immediately think of several ways to mitigate the threat,
not the least of which is simply not to build a system that stores
plaintext hashes of bare keys.

As we all well know, virtually any cryptographic design can (and will!) be
implemented badly in ways that introduce vulnerability, when the
implementer doesn't understand the system he or she is implementing, which
is exactly what the scenario in question seems to be.   Generally speaking,
I think HMAC is easier than most to implement reasonably securely, and even
where it is not, this particular case is not where it is likeliest to fail.
  Short colliding keys as Kenny mentioned are certainly a bigger issue, and
weak keys and non-constant-time comparison are other issues I see regularly
in real systems.

On a tangent, purely as personal opinion, errata is a great tool for fixing
mistakes and adding clarification.  It's a lousy way to propose a
fundamental breaking change to an RFC that's been published for 19 years
and is already baked into who-knows-how-many systems in its current
specification.

Best regards,

-Xander Sherry

---

From: Michael StJohns <[email-masked]>
Date: Thu, 2 Feb 2017 11:10:59 -0500

Inline.

> And even if it were a real problem, I'm not sure we'd

I think it's probably a bogus erratum.   Basically, there are a lot of 
ways to calculate check values for secret keys - hashing the key as 
suggested in this report - is not the one I would suggest for HMAC 
keys.  Instead, doing an HMAC over a known value - HMAC (K, 
'0000000000000000'b) to get a check value might be a better choice.

I think this report boils down to a "I came up with a way to use this 
mechanism in a way that may have security weaknesses".  If he'd said 
that IPSEC uses this and its bad, then I'd say the report was actionable 
- with respect to IPSEC.  As it stands, I'd reject the report.  
Alternately, I might say "Applications MUST not use keys longer than 8 
bytes, where the hash of the key (with the same hash as used in the 
HMAC) is also used as a public value (a key identifier or check value)".

And given that AFAICT RFC 2104 was really a feeder document for the 
NIST  FIPS 198-1 submission  (compare if you will the abstract of the 
RFC with the NIST document Introduction), I would suggest that any 
changes to HMAC be fed in to NIST rather than being accepted as updates 
to this informational document.

Mike

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 2 Feb 2017 11:22:25 -0500

​These cases of  related key setting​s are well known and can indeed be
seen as a weakness of HMAC. They are part of the engineering trade-offs you
have to do for accommodating a design to the real world (and requirements
from often chaotic IETF discussions). There were things we would have liked
to do differently such as avoiding the longer-than-block keys or having
different keys for the inner and outer hash applications, but that would
have made the design problematic in different ways. The particular issue of
not disallowing keys longer than a block came at least from an IKE
requirement. For example, people wanted to use unlimited passphrases, and
between having people truncate long keys or hash them first, the latter
seemed the more robust solution. (BTW, the right way to deal with these
issues using HMAC is to use HKDF.)

Anyway, over the years I heard some rare instances where this led to a
weakness (I have myself shown such cases) but either these were theoretical
settings or some forms of bad practice (e.g. making the hash of a secret
key public). The paper cited earlier by Dan Brown also notes that this
property makes HMAC with long keys non-indifferentiable from a random
oracle. Again, not the nicest property but hardly something to worry much
about in practice. Also, contrary to what Quin said, this property does not
contradict HMAC being a PRF (PRFs can have related key weaknesses).

After 20 years of widespread use, it seems to me that (again) the
engineering considerations (not breaking existing implementations) are more
significant than the potential problems of such related key issues.

Hugo

---

From: Taylor R Campbell <[email-masked]>
Date: Thu, 2 Feb 2017 21:56:31 +0000

> Date: Thu, 2 Feb 2017 02:24:44 +0000
> From: Stephen Farrell <[email-masked]>
> 

Fix hash function H with block size b.  The alleged problem is that
for a key k, if |k| > b and h = H(k), then HMAC-H_h = HMAC-H_k.

What protocol would ever use HMAC-H with related keys of different
lengths like this for the same purpose?  What protocol would ever use
HMAC-H with keys of different lengths at all for the same purpose?

Needless flexibility like that strikes me as more likely to indicate a
deeper problem -- e.g., one reason that might happen is that the
protocol foolishly uses a password verbatim as an HMAC key.

---

From: Ann <[email-masked]>
Date: Fri, 3 Feb 2017 11:23:42 +0100

Anyway, the actual text is prone to HMACcollisions:
Given |k|<b one can find easily another k' with HMAC-H_h = HMAC-H_k.
Why not accept this issue as an erratum of the RFC?

Not sure that the prosed correction is necessary. You gave some
considerations to reject it.
My 2 cents: you should write "MUST NOT" instead of "MUST not" ;-)

Regards,
/Ann.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 3 Feb 2017 10:24:06 +0000

Hugo Krawczyk <[email-masked]> writes:

>For example, people wanted to use unlimited passphrases, and between having
>people truncate long keys or hash them first, the latter seemed the more
>robust solution. (BTW, the right way to deal with these issues using HMAC is
>to use HKDF.)

Another solution to the fact that there are two external-format keys that map
to a single internal-format key (i.e. the > blocksize key and its hash) would
be to reserve the first bit of the internal-format key to denote hashed vs.
non-hashed.  OTOH then people would complain about losing one bit of strength,
or someone would propose an attack based on knowing that the first bit will
almost always be zero (for non-hashed), or something similar.  You can't win
:-).

Peter.

---

From: David Jacobson <[email-masked]>
Date: Fri, 3 Feb 2017 08:06:18 -0800

> almost always be zero (for non-hashed), or something similar.  You can't win
Okay, we're off on a tangent and into hypotheticals about what could be 
done, so I'll make two suggestions.  They could be used separately or 
together.

1.  The present scheme uses an OPAD of 3636...  .  Instead use 3636... 
when no hashing is done and, say, a9a9... when hashing is done.

2.  In addition to XORing the key with the OPAD, also XOR (at the right 
of the first block) with the length of the key in in bits (or bytes).

    --David Jacobson

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 3 Feb 2017 18:28:14 +0000

Thanks all,

My reading of that thread leads me to conclude there there's consensus
to not verify the erratum on the basis that the threat isn't that
significant and a backwards incompatible change as would be required is
not justified. However, if HMAC were to be updated in a manner that
didn't require backwards compatibility then one would likely consider
this. Hence I've marked this as "hold for document update"

Cheers,
S.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Fri, 3 Feb 2017 19:47:35 +0000

Hi Hugo,

Thank you for calling me a nice name "Quin"!

In the HMAC paper, the key length is the IV length (the length of the hash function output). But in the RFC specification of the HMAC, the key is "any" length.

I am sure you saw that b bits of  (key||00000....) created the situation that many keys produced the same output from the function HMAC for the same message input when the key's length was not a fixed value. If you wanted a variable key length, you would have had at least 2 options: (1) adding encoding for key length and put some restriction on key length so that the key and its length encoding did not get longer than the hash function input block (avoiding one hash function call to improve performance) or (2) always hashing the key to produce the exact length L for the key.

Quynh.

________________________________
From: Cfrg <[email-masked]> on behalf of Hugo Krawczyk <[email-masked]>
Sent: Thursday, February 2, 2017 11:22:25 AM
Cc: [email-masked]
Subject: Re: [Cfrg] erratum for hmac what do we think...

​These cases of  related key setting​s are well known and can indeed be seen as a weakness of HMAC. They are part of the engineering trade-offs you have to do for accommodating a design to the real world (and requirements from often chaotic IETF discussions). There were things we would have liked to do differently such as avoiding the longer-than-block keys or having different keys for the inner and outer hash applications, but that would have made the design problematic in different ways. The particular issue of not disallowing keys longer than a block came at least from an IKE requirement. For example, people wanted to use unlimited passphrases, and between having people truncate long keys or hash them first, the latter seemed the more robust solution. (BTW, the right way to deal with these issues using HMAC is to use HKDF.)

Anyway, over the years I heard some rare instances where this led to a weakness (I have myself shown such cases) but either these were theoretical settings or some forms of bad practice (e.g. making the hash of a secret key public). The paper cited earlier by Dan Brown also notes that this property makes HMAC with long keys non-indifferentiable from a random oracle. Again, not the nicest property but hardly something to worry much about in practice. Also, contrary to what Quin said, this property does not contradict HMAC being a PRF (PRFs can have related key weaknesses).

After 20 years of widespread use, it seems to me that (again) the engineering considerations (not breaking existing implementations) are more significant than the potential problems of such related key issues.

Hugo

---

From: Michael StJohns <[email-masked]>
Date: Fri, 3 Feb 2017 14:49:14 -0500

> this. Hence I've marked this as "hold for document update"

I'd like to reiterate that RFC 2104 (or substantially similar text) was 
a feeder/submission for the FIPS 198-1 standard.  Its also old enough 
that it doesn't have the boilerplate we've since added that would allow 
for any changes/errata.  In that mode, its similar to the original 
publications of PKCS1, 7 and 12 as informational RFCs and we required a 
grant of rights to be able to gain change control over them.

Instead of making changes here to a document that's been OBEd by first 
being published as a FIPS  (FIPS 198) and second by an update in 2008 
(FIPS 198-1), let me suggest that comments should be bundled up and 
addressed to that document instead.

It looks like FIPS 198 is up for review in 2018 and changes might be 
applied then.

Perhaps I'm wrong about this, but we - the IETF - do not own change 
control over every RFC.

Mike

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 3 Feb 2017 15:32:31 -0500

Sorry Quin ;-)

I knew I had to go look at the spelling but was rushing too much... Let's
see how you spell my last name from memory :-)

To the technical point: regardless of what could have been the best
resolution to variable length keys, neither of these considerations
invalidate HMAC as a PRF. Your statement "HMAC is not a PRF" is wrong (and
can add unjustified and unwanted confusion).

As I said, practice constraints us in different ways and produce
sub-optimal results. But in the case of HMAC, really, it is hard to argue
with 20 years of widespread and robust use. If this was a real issue, it
would have come in some significant practical situations but it hasn't. I
see no justification to change the standard after (exactly) 20 years.

Hugo

On Fri, Feb 3, 2017 at 2:47 PM, Dang, Quynh (Fed) <[email-masked]>
wrote:

> In the HMAC paper, the key length is the IV length (the length of the hash
> function output). But in the RFC specification of the HMAC, the key is
> "any" length.
>
>
> I am sure you saw that b bits of  (key||00000....) created the situation
> that many keys produced the same output from the function HMAC for the same
> message input when the key's length was not a fixed value. If you wanted a
> variable key length, you would have had at least 2 options: (1) adding
> encoding for key length and put some restriction on key length so that the
> key and its length encoding did not get longer than the hash function input
> block (avoiding one hash function call to improve performance) or (2)
> always hashing the key to produce the exact length L for the key.
>
>
> Quynh.
> ------------------------------
> *From:* Cfrg <[email-masked]> on behalf of Hugo Krawczyk <
> [email-masked]>
> *Sent:* Thursday, February 2, 2017 11:22:25 AM
> *Cc:* [email-masked]
> *Subject:* Re: [Cfrg] erratum for hmac what do we think...
>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 3 Feb 2017 20:41:17 +0000

> Perhaps I'm wrong about this, but we - the IETF - do not own change

I don't think we need worry about process nits like that tbh. The
distinction between a rejected erratum, a hold-for-document-update
erratum and an erratum that's been posted but ignored for 6 months
isn't really of interest:-)

I would worry a bit about it if we approved an erratum that broke
interop, which we could have done, but didn't do, in this case.

And if/when someone wants to revise hmac then I hope they do talk
with the IETF about that. Most, but not all, RFCs that use that do
support alg agility so there could be done potential breakage to
consider.

S.