Subject: [CFRG] Extract-and-expand with KMAC

From: John Mattsson <[email-masked]>
Date: Sun, 15 Nov 2020 13:47:42 +0000

Hi,

HMAC is needed to mitigate the length extension weakness of SHA-2. SHAKE does not have this weakness and NIST has therefore standardized the simple and efficient KMAC mode.

LAKE WG is discussing using KMAC in a extract-and-expand fashion similar to HKDF. However, there are several options when mapping the HKDF Extract and Expand interfaces to KMAC(K, X, L, S).

Would the following be reasonable for KMAC128, or would CFRG suggest something else?

PRK = Extract(salt, IKM) = KMAC128(salt, IKM, 256, “”)
OKM = Expand(PRK, L, info)  = KMAC128(PRK, “”, L, info)

Or should maybe the Extract and Expand intefaces be updated with more parameters?

Cheers John

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 15 Nov 2020 18:35:35 +0200

On Sun, Nov 15, 2020 at 01:47:42PM +0000, John Mattsson wrote:
>  Hi,
> 
> HMAC is needed to mitigate the length extension weakness of SHA-2.
> SHAKE does not have this weakness and NIST has therefore
> standardized the simple and efficient KMAC mode.

What I do not like about KMAC is that the spec is somewhat difficult to
understand (even if it is not quite as bad as FIPS202), and seemingly
lacks any usable test vectors (where usable means everything is
multiple of octet; I have not found unofficial ones either).

(KMAC is closely related to cSHAKE, and I did find some unofficial(?)
test vectors for cSHAKE. Those test vectors were very useful when
writing implementation of cSHAKE.)

> LAKE WG is discussing using KMAC in a extract-and-expand fashion
> similar to HKDF. However, there are several options when mapping the
> KDF Extract and Expand interfaces to KMAC(K, X, L, S).
> 

The S parameter is contextualization and processed before K, so one
should not stick arbitrary and/or possibly attacker-controlled things
in S.

If one just did raw substitution inside HKDF and eliminated the
redundant counter octet (since first block is always enough), one would
obtain:

PRK = Extract(salt, IKM) = KMAC128(salt, IKM, 256, "")
OKM = Expand(PRK, L, info) = KMAC128(PRK, info, L, "")

One might want to contextualize those two, to obtain something like:

PRK = Extract(salt, IKM) = KMAC128(salt, IKM, 256, "KDF extraction")
OKM = Expand(PRK, L, info) = KMAC128(PRK, info, L, "KDF expansion")

No further contextualization is possible without going beyond present
KDF interface.

For 256-bit level, just replace KMAC128 by KMAC256, and 256 with 512.

This also has the property that if multiple expansions are computed
from the same PRK, one can precompute the first two Keccak-F
invocations and share those among the different expansions of the PRK.
 
> Or should maybe the Extract and Expand intefaces be updated with more
parameters?

Wouldn't that cause serious API issues? Adding parameters to
interfaces can cause serious issues, especially when the parameters
are sometimes available and sometimes not.

-Ilari

---

From: John Mattsson <[email-masked]>
Date: Sun, 15 Nov 2020 16:56:44 +0000

Thanks Ilari!

-----Original Message-----
From: <[email-masked]> on behalf of Ilari Liusvaara <[email-masked]>
Date: Sunday, 15 November 2020 at 17:35
To: John Mattsson <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Extract-and-expand with KMAC

-Ilari

---

From: Jonathan Hammell <[email-masked]>
Date: Mon, 16 Nov 2020 02:21:28 -0500

> writing implementation of cSHAKE.)

There are a couple (unofficial?) test vectors for KMAC in Figure 12 of
https://usnistgov.github.io/ACVP/draft-celi-acvp-xof.txt .

Jonathan

---

From: Ruggero SUSELLA <[email-masked]>
Date: Mon, 16 Nov 2020 10:01:39 +0000

There are, just a couple of, official cshake and kmac test vectors here https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values
Under "secure hashing".

Ruggero

-----Original Message-----
From: CFRG <[email-masked]> On Behalf Of Jonathan Hammell
Sent: Monday, November 16, 2020 8:21 AM
To: Ilari Liusvaara <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Extract-and-expand with KMAC

On Sun, Nov 15, 2020 at 11:36 AM Ilari Liusvaara <[email-masked]> wrote:
> What I do not like about KMAC is that the spec is somewhat difficult 
> to understand (even if it is not quite as bad as FIPS202), and 
> seemingly lacks any usable test vectors (where usable means everything 
> is multiple of octet; I have not found unofficial ones either).
>

There are a couple (unofficial?) test vectors for KMAC in Figure 12 of https://usnistgov.github.io/ACVP/draft-celi-acvp-xof.txt .

Jonathan

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

---

From: Gilles VAN ASSCHE <[email-masked]>
Date: Wed, 18 Nov 2020 09:39:31 +0000

Dear all,

> OKM = Expand(PRK, L, info) = KMAC128(PRK, info, L, "")

Is there a particular need to expose the intermediate value PRK in this application?

Otherwise, wouldn't it be simpler and more efficient to compute
    SHAKE128(salt ; IKM ; info)
where ";" stands for some reversible concatenation (i.e., from which the individual strings can be recovered)?

One could see the absorbing phase of SHAKE128 as the extraction step and, starting from the state at this stage being a PRK, the squeezing phase as the expansion step.

This solution is not incompatible with the case where an intermediate value PRK is required: (salt ; IKM) is padded to take a whole number of blocks, and PRK is the state value after absorbing it.

Kind regards,
Gilles

---

From: [email-masked]
Date: Wed, 18 Nov 2020 09:53:30 -0800

Gilles VAN ASSCHE <[email-masked]> wrote:
> This solution is not incompatible with the case where an intermediate
> value PRK is required: (salt ; IKM) is padded to take a whole number
> of blocks, and PRK is the state value after absorbing it.

I'll admit I am stating the obvious, but: while this proposal works
technically, it requires access to implementation internals that
may not always be available.

(In particular: the SHAKE API, to my knowledge, does not include the
ability to save and reload state. I'm aware that some implementations
*do* provide this functionality, but strictly speaking it violates
the contract. This could lead to implementation issues down the road.)

Best,

-=rsw

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Wed, 18 Nov 2020 18:19:58 +0000

Hi R,

I am not aware of a protocol where the output from an extract step: PRK is saved and the expansion step gets executed later to generate keys.

Both steps get completed to produce key(s) and one of these keys can be used as a key derivation key to derive more keys later if there is a need like that.

When you use KMAC, one of the output keys can be used as a key derivation key to derive keys.

The point of KMAC or SHAKE as a KDF is that it covers the extraction and expansion functionalities in its sponge's construction already.

Regards,
Quynh.
________________________________
From: CFRG <[email-masked]> on behalf of [email-masked] <[email-masked]>
Sent: Wednesday, November 18, 2020 12:53 PM
To: Gilles VAN ASSCHE <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Extract-and-expand with KMAC

Best,

-=rsw

_______________________________________________
CFRG mailing list
[email-masked]
https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=04%7C01%7Cquynh.dang%40nist.gov%7C7fd1eb001fff4cd915f408d88beb2dd6%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637413189515656868%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=4lRQ1TXrcTOetxwjoMaZCA8sp78WgrfUgJitNAImC3s%3D&amp;reserved=0

---

From: "[email-masked]" <[email-masked]>
Date: Wed, 18 Nov 2020 11:05:50 -0800

Hi Quynh,

"Dang, Quynh H. (Fed)" <[email-masked]> wrote:
> I am not aware of a protocol where the output from an extract step:
> PRK is saved and the expansion step gets executed later to generate
> keys.

Totally agreed! in most cases, we don't worry much about PRK. Note,
however, that the message I was responding to explicitly *did* worry
about it:

Gilles VAN ASSCHE <[email-masked]> wrote:
> value PRK is required:

If indeed the intermediate value is required, as discussed here, then
my concerns about non--black-box use of the primitives are relevant.
Otherwise, as you say, no worries at all---and we have good reason
to believe that constructions like SHA-3 are great for such cases.

Best,

-=rsw

---

From: Gilles VAN ASSCHE <[email-masked]>
Date: Thu, 19 Nov 2020 11:05:23 +0000

Hi,

> Totally agreed! in most cases, we don't worry much about PRK. Note, however, that the message I was responding to explicitly *did* worry about it:

> If indeed the intermediate value is required, as discussed here, then my concerns about non--black-box use of the primitives are relevant.
> Otherwise, as you say, no worries at all---and we have good reason to believe that constructions like SHA-3 are great for such cases.

Indeed, my primary message was that the intermediate value PRK is probably (=without knowledge of the application) not needed, and therefore evaluating SHAKE128(salt ; IKM ; info) works as is. So I guess we agree on this point.

I understand your concerns about the non-black-box use of SHAKE. However, it seems to me they would be addressed with an implementation that supports Init-Update-Final-like (IUF) function calls. The PRK would then materialize as the state (e.g., the struct passed to these functions) after Update(salt ; IKM). Note that I am not advocating this mechanism, but just using it to argue that
- the PRK exists so philosophically SHAKE is also somehow doing extract+expand and
- it is not unreasonable to expose the PRK with an IUF implementation, should the need of a delayed expansion occurs.

Kind regards,
Gilles