Subject: Re: [Cfrg] Aside Re: [CFRG] erratum for hmac ...

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Wed, 8 Feb 2017 13:31:22 +0000

Randal, Michael and many others,

Thank you for your suggestions.

Kenny,

Thank you for your discussion email.

We are thinking about what would be the best option for HMAC.  Some technical possibilities are below.

1) Don't change the HMAC spec.

Ask a HMAC key always to have a fixed length such as HMAC-SHA256 having 256-bit key. Which means that all protocols using HMAC-SHA256 use 256-bit keys.

If each protocol uses a different key length, then the issue would still exist across protocols. I don't know if this is a practical security problem, but it seems like a problem that should be avoided.

Should ask HMAC keys to be processed/produced by a hash function or another PRF always.

This option does not break interoperability of  the current HMAC implementations.

2) Change the HMAC Spec.

a) Always hash the key regardless of its length, then perform step 3 in FIPS 198.
b) Use a hash-based KDF (not HKDF) to produce B bits from the key, then go to step 4 in the FIPS. (bad for performance).
c) Require key < B, then do multi-rate padding 10* to make the key B bits, then go to step 4 in the FIPS. (good for performance).

We recommend the use of KMAC in SP 800-185. KMAC's security is solid and proven, and it has great performance. Code to implement KMAC can be reused to implement many other Keccak-derived symmetric-key crypto functions.

Regards,
Quynh.
________________________________
From: Randal Atkinson <[email-masked]>
Sent: Tuesday, February 7, 2017 12:34 PM
To: Dang, Quynh (Fed)
Cc: Randal Atkinson
Subject: Aside Re: [CFRG] erratum for hmac ...

One option available to NIST would be for NIST to open comments
on updating FIPS 198-1, even if opening comments on that now/soon
would be earlier than NIST ordinarily would do so.

Given how long it takes to move from an approved FIPS revision
to widespread US Government deployment, if data exists from
Kenny P and/or others that merits an update, then starting sooner
would not be a bad thing for the USG.

Cheers,

Ran Atkinson

--------------------------------
Randal Atkinson, PhD
Cheltenham Research for NRL 5520
[email-masked]

---

From: David Jacobson <[email-masked]>
Date: Thu, 9 Feb 2017 21:27:24 -0800

See interleaved comment.

On 2/8/17 5:31 AM, Dang, Quynh (Fed) wrote:
> Ask a HMAC key always to have a fixed length such as HMAC-SHA256 
> having 256-bit key. Which means that all protocols using HMAC-SHA256 
> use 256-bit keys.
>
> If each protocol uses a different key length, then the issue 
> would still exist across protocols. I don't know if this is a 
> practical security problem, but it seems like a problem that should be 
> avoided.
>

I don't see the need or even desirability for this, assuming you ask 
each protocol to use a fixed (for that protocol) key length.  (That was 
the line above.)

For an attacker to find two messages with the same HMAC, not knowing the 
key, he would have to find a collision in the first stage, not knowing 
the first block.  And if you add an extra hash, you are only making it 
easier.  He has to get a collision in the pre-hash, where he knows 
everything.

    --David Jacobson
> b) Use a hash-based KDF (not HKDF) to produce B bits from the key, 
> then go to step 4 in the FIPS. (bad for performance).
> c) Require key < B, then do multi-rate padding 10* to make the key B 
> bits, then go to step 4 in the FIPS. (good for performance).
>
> We recommend the use of KMAC in SP 800-185. KMAC's security is solid 
> and proven, and it has great performance. Code to implement KMAC can 
> be reused to implement many other Keccak-derived symmetric-key crypto 
> functions.
>
> Regards,
> Quynh.
> ------------------------------------------------------------------------
> *From:* Randal Atkinson <[email-masked]>
> *Sent:* Tuesday, February 7, 2017 12:34 PM
> *To:* Dang, Quynh (Fed)
> *Cc:* Randal Atkinson
> *Subject:* Aside Re: [CFRG] erratum for hmac ...
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: David Jacobson <[email-masked]>
Date: Thu, 9 Feb 2017 21:38:31 -0800

Oops.  I made a mistake.  It is the key that is being hashed not the 
message.

But I still don't see where it helps.  An attacker does not choose the key.

Now there was this discussion about related keys they could generate the 
same output.  But if we fix the key to some protocol-specific value, 
then there is no easy way to get related keys that give the same 
output.  You would need to find a sort of double-collision where the 
hash internal state after the first block is the same for keyA ^ IPAD 
and keyB ^ IPAD and the internal state after the first block is the same 
for keyA ^ OPAD and keyB ^ OPAD.  This seems much harder than just 
finding a collision.

    --David

On 2/9/17 9:27 PM, David Jacobson wrote:
>> practical security problem, but it seems like a problem that should 
>> be avoided.
>>
> For an attacker to find two messages with the same HMAC, not knowing 
> the key, he would have to find a collision in the first stage, not 
> knowing the first block.  And if you add an extra hash, you are only 
> making it easier.  He has to get a collision in the pre-hash, where he 
> knows everything.
>
>    --David Jacobson
>>

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 10 Feb 2017 06:23:09 +0000

> Date: Thu, 9 Feb 2017 21:38:31 -0800
> From: David Jacobson <[email-masked]>
> 

Consider an authenticated encrypted content-addressed storage scheme
similar to Tahoe-LAFS.  Our goal is to store files in some server's
key/value store.  We hope to conceal the content of the files from the
server and detect any attempts at forgery by the server, excluding
replays of old files.

To store a file m, compute k = SHA512(m).  Let k0 be the first 256
bits of k.  Use k0 as an AES256-CTR encryption key and k as an
HMAC-SHA256 key with encrypt-then-MAC to obtain ciphertext c0,
authenticator a, and tagged ciphetext c, where:

   c0 = AES256-CTR(h, m)
   a = HMAC-SHA256(k, c0)
   c = c0 || a.

Then use SHA256(k) as the key to store the value c in the server's
key/value store.

Problem:  By revealing SHA256(k) to the server, we have allowed the
server to forge stored ciphertexts, because HMAC-SHA256(k, c0) =
HMAC-SHA256(SHA256(k), c0), the latter of which the server can now
compute for any c0.

This protocol is obviously quirky.  It is close to, but not quite,
Tahoe-LAFS's protocol; Tahoe-LAFS goes to some trouble to enforce
domain separation between its various uses of SHA256.  But it is not
far from a plausible protocol that someone might invent, and the only
practical problem I foresee with it is the HMAC key collision:

- Sharing key material between AES256-CTR and HMAC-SHA256 makes my
skin crawl, but -- particularly since the key is prehashed for
HMAC-SHA256! -- I can't imagine an attack arising from this.

- On the other hand, I can easily imagine someone trying to use a
512-bit key with AES256-CTR and HMAC-SHA256 and, on finding that the
nearest crypto library rejects it for AES256-CTR but accepts it for
HMAC-SHA256, simply truncating the AES256-CTR key.

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 10 Feb 2017 06:55:30 +0000

> Date: Fri, 10 Feb 2017 06:23:09 +0000
> From: Taylor R Campbell <[email-masked]>
> 
> To store a file m, compute k = SHA512(m).  [...]
> 
> HMAC-SHA256(SHA256(k), c0), [...]

Oops -- this particular scenario doesn't work because if |k| <= 512,
the block size of SHA256, then HMAC-SHA256 uses k verbatim with no
prehash.  We would need to have chosen a >512-bit k, which makes this
whole scenario even less likely: typical block sizes are >=512 bits
(e.g., MD5, SHA1, SHA2, SHA3, BLAKE2), and typical output sizes are
<=512 bits.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Fri, 10 Feb 2017 13:23:29 +0000

See my discussion below.

From: David Jacobson <[email-masked]<mailto:[email-masked]>>
Date: Friday, February 10, 2017 at 12:27 AM
To: 'Quynh' <[email-masked]<mailto:[email-masked]>>, Randal Atkinson <[email-masked]<mailto:[email-masked]>>, Michael StJohns <[email-masked]<mailto:[email-masked]>>, "Paterson, Kenny" <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Aside Re: [CFRG] erratum for hmac ...

See interleaved comment.

Kenny,

I don't see the need or even desirability for this, assuming you ask each protocol to use a fixed (for that protocol) key length.  (That was the line above.)

For an attacker to find two messages with the same HMAC, not knowing the key, he would have to find a collision in the first stage, not knowing the first block.  And if you add an extra hash, you are only making it easier.  He has to get a collision in the pre-hash, where he knows everything.

Of course, the hash function must be a collision-resistant one.

The reason for hashing the key or the key is produced by a good hash function or a PRF is to make the key become more of a "random key" as you know HMAC is a PRF as keys are selected randomly, not selectively.

Quynh.

   --David Jacobson

2) Change the HMAC Spec.

Regards,
Quynh.
________________________________
From: Randal Atkinson <[email-masked]><mailto:[email-masked]>
Sent: Tuesday, February 7, 2017 12:34 PM
To: Dang, Quynh (Fed)
Cc: Randal Atkinson
Subject: Aside Re: [CFRG] erratum for hmac ...

Cheers,

Ran Atkinson

--------------------------------
Randal Atkinson, PhD
Cheltenham Research for NRL 5520
[email-masked]<mailto:[email-masked]>

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

---

From: David Jacobson <[email-masked]>
Date: Fri, 10 Feb 2017 07:50:05 -0800

In engineering, we like to be able to think of things as black boxes 
with specifications.  If you follow the rules in the specification, it 
works properly.

The problem here is that HMAC fails to do this.  If you use HMAC with a 
key larger that the input block size (allowed), and you reveal the hash 
of the key (a la original /etc/password), you can lose security.

My suggestion would be to add wording to the specification that says ( 
a) that use of keys larger than the input block size is discouraged, and 
(b) if the keys larger than the input block size are used, the H(K) is 
also sensitive and must be protected with the same diligence as the key 
would be protected.

     --David Jacobson

On 2/10/17 5:23 AM, Dang, Quynh (Fed) wrote:
> To: 'Quynh' <[email-masked] <mailto:[email-masked]>>, Randal 
> Atkinson <[email-masked] 
> <mailto:[email-masked]>>, Michael StJohns 
> <[email-masked] <mailto:[email-masked]>>, "Paterson, 
> Kenny" <[email-masked] <mailto:[email-masked]>>
> Cc: "[email-masked] <mailto:[email-masked]>" <[email-masked] 
> <mailto:[email-masked]>>
>>     having 256-bit key. Which means that all protocols using
>>     HMAC-SHA256 use 256-bit keys.
>>
>>     practical security problem, but it seems like a problem that
>>     should be avoided.
>>
>     I don't see the need or even desirability for this, assuming you
>     ask each protocol to use a fixed (for that protocol) key length. 
>     (That was the line above.)
>
>     For an attacker to find two messages with the same HMAC, not
>     knowing the key, he would have to find a collision in the first
>     stage, not knowing the first block.  And if you add an extra hash,
>     you are only making it easier.  He has to get a collision in the
>     pre-hash, where he knows everything.
>
>
> The reason for hashing the key or the key is produced by a good hash 
> function or a PRF is to make the key become more of a "random key" as 
> you know HMAC is a PRF as keys are selected randomly, not selectively.
>
> Quynh.
>
>
>
>
>
>        --David Jacobson
>>
>>     b) Use a hash-based KDF (not HKDF) to produce B bits from the
>>     key, then go to step 4 in the FIPS. (bad for performance).
>>     c) Require key < B, then do multi-rate padding 10* to make the
>>     key B bits, then go to step 4 in the FIPS. (good for performance).
>>
>>     We recommend the use of KMAC in SP 800-185. KMAC's security is
>>     solid and proven, and it has great performance. Code to implement
>>     KMAC can be reused to implement many other
>>     Keccak-derived symmetric-key crypto functions.
>>
>>     Regards,
>>     Quynh.
>>     [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Fri, 10 Feb 2017 18:44:50 +0000

Date: Friday, February 10, 2017 at 10:50 AM

In engineering, we like to be able to think of things as black boxes with specifications.  If you follow the rules in the specification, it works properly.

The problem here is that HMAC fails to do this.  If you use HMAC with a key larger that the input block size (allowed), and you reveal the hash of the key (a la original /etc/password), you can lose security.

In our guildlines, we require to keep K0 as secret key.

My suggestion would be to add wording to the specification that says ( a) that use of keys larger than the input block size is discouraged, and (b) if the keys larger than the input block size are used, the H(K) is also sensitive and must be protected with the same diligence as the key would be protected.

    --David Jacobson

Thank you,
Quynh.

See interleaved comment.

Kenny,

Quynh.

   --David Jacobson

2) Change the HMAC Spec.

Regards,
Quynh.

Cheers,

Ran Atkinson