Add support for CMAC based KDF algorithms

[adeaarm]

Current revision of the spec does not have support for CMAC based KDFs as described by NIST in SP 800-108 in the list of KDF algorithms, but it support only HMAC based algorithms. This is important for use cases where CMAC used as the PRF in the KDF is fully accelerated by the underlying hardware platform. PRF can be used in different modes, ideally add support for all of them to extend flexibility for platform integrators.

[MarcusJGStreets]

There are issues around CMAC, raised within SP 800-108 with mitigations. So we would need to ensure that the API enforced those.

When using CMAC as the PRF in counter mode, a party with knowledge of the key KIN, who
also can freely select portions of the string Label || 0x00 || Context || [L] 2 (as described in
Appendix B), may be able to control the values of one or more of the K(i). One way to guard
against the possibility of this sort of key control would be by replacing the fixed input data
Label || 0x00 || Context || [L] 2
with
Label || 0x00 || Context || [L] 2 || K (0),
where
K(0) = PRF(KIN, Label || 0x00 || Context || [L] 2).

When using CMAC as the PRF in feedback mode, a party with knowledge of the key KIN, who
can also freely select portions of the string Label || 0x00 || Context || [L] 2 and/or portions of the
IV, may be able to control the values of one or more of the K(i), as was the case for counter
mode. One way to guard against the possibility of this sort of key control would be by requiring
that
IV = PRF (KIN, Label || 0x00 || Context || [L]2 )
and requiring the inclusion of a counter in the feedback mode (i.e., [i]2 is not optional).

When using CMAC as the PRF in double-pipeline mode, a party with knowledge of the key KIN
may be able to control the values of one or more of the K(i). One way to guard against the
possibility of this sort of key control would be by requiring the inclusion of a counter in double-
pipeline mode (i.e., [i] 2 is not optional).

[athoelke]

SP 800-108 provides general construction methods for building KDFs, but does not define any specific KDF construction, that is adequate for implementing an interoperable KDF. We want to only define algorithm identifiers for precise algorithm specifications, that ensure compatibility of results across implementations.

HKDF and the HMAC-based TLS KDFs are defined because their behavior is fully specified.

If you have specific CMAC-based KDFs, ideally with an example use case, then adding an algorithm identifier and describing the KDF will be straightforward. Clearly, CMAC-based KDFs that follow secure-construction guidelines are preferable to ones that do not.

[gilles-peskine-arm]

SP 800-108 unfortunately defines very general families that leave a lot of choices in terms of how you format the data to be processed.

• There are three different scheme.
• Each scheme takes multiple parameters.
• The discussion in §5 specifies that the pseudocode given in the next subsections does not fully define the functions: implementations are also allowed to change the order of the concatenation [i] || Label || 0x00 || Context || [L].

There is a draft NIST specification for a JSON syntax that describes the capabilities of an SP 800-108 implementation. Read and despair.

SP 800-108 KDF in counter mode is a generalization of ANSI X9.62 KDF1, which uses SHA-1 as the PRF. Limiting the API to the structure of KDF1, but with HMAC/KMAC/CMAC rather than SHA-1 as the primitive, might be viable.

PKCS#11 allows a lot of variation, and even there I'm not sure if it covers all the functions that are compliant to SP 800-108. The result is too complicated for PSA.

OpenSSL 3.1 doesn't have KDFs other than the ones used by TLS. Neither does BouncyCastle, as far as I can find.

Cryptodome only offers counter mode, with one specific encoding which is not specified in the documentation.

Just to add to the fun, SP 800-56C §4 specifies a “one-step key derivation function” which follows the same principle as SP 800-108's KDF in counter mode, but formats the data in an incompatible way! Whereas SP 800-108 passes the secret input as a key for a key-indexed PRF, SP 800-56C passes the secret input as part of some data which is concatenated into an input to a single PRF. SP 800-56C allows a lot of variation over the FixedInfo part (i.e. encoding various non-secret parameters). SP 800-56A §5.8.2.1 gives additional rules regarding the formation of FixedInfo in various use cases, but these rules are about non-secret inputs, so for our API design, we can let the application construct it. Note that SP 800-56C does not support CMAC (it needs a keyed hash, not just a MAC, because it uses a non-secret key; SP 800-56C over CMAC would be broken).

So I think we should specify the following NIST-approved KDF families:

• A subset of SP 800-108 in counter mode, based on HMAC, KMAC or CMAC. This subset should be as close as possible to KDF1 and to Cryptodome's SP800_108_Counter.

  • Note that the CMAC variant is limited to a secret input of size exactly 16, 24 or 32 bytes since it's directly used as an AES key. This makes the CMAC variant possibly vulnerable to related-key attacks in some scenarios.

• SP 800-56C in all generality, with hash, HMAC and KMAC variants.

[adeaarm]

Just wanted to confirm that having point 1 (A subset of SP800-109 in counter mode, especially in the CMAC variant) would fulfill most of the requirements that we see from partners around CMAC based KDF. I think this should be due to the fact that it's common to have accelerators where the CMAC functionality can be accelerated entirely (and possibly hardened in HW against side channels).

[athoelke]

Do partners know what the applications are, and can tell us precisely what KDF they need? - or are they expecting that if we specify some CMAC-based KDF, and they implement it, that it will get used by applications because it is accelerated?

[athoelke]

• A subset of SP 800-108 in counter mode, based on HMAC, KMAC or CMAC. This subset should be as close as possible to KDF1 and to Cryptodome's SP800_108_Counter.

It will be challenging* to achieve alignment with both KDF1 structure (i.e. replace the hash with a *MAC as the PRF) and Cryptodome SP800_108_Counter() (assuming it literally follows §4.1 in SP 800-108).

[* As in technically impossible]

If the HMAC/CMAC/KMAC operation is denoted as $\text{PRF}(s, x)$, without output length $prflen$ (in bits), then the number of output blocks required is $n=\lceil L/prflen \rceil$ if $L$ is the number of bits of output requested. I have used $[x]_n$ to denote an encoding of the integer $x$ as an $n$-byte string. Then the blocks of output for KDF1 are:

$$K_i = \text{PRF}(K_{IN}, [i]_4), \quad i=0..n-1$$

Whereas SP 800-108 §4.1 Counter mode outputs the following blocks:

$$K_i = \text{PRF}(K_{IN},[i]_4\text{ || }Label\text{ || }0x00\text{ || }Context\text{ || }[L]_8), \quad i=1..n$$

[I have adopted a 4-byte encoding of $i$ and an 8-byte encoding of L in this demonstration - it is not documented what CryptoDome does].

Even with empty $Label$ and $Context$ values, these are incompatible due to the zero-based and one-based indexing, and the additional fixed data in the PRF input.

The SP 800-108 construction is preferable as it provides placeholders for shared $Context$ information (identity/protocol etc.) that help to indicate protocol errors, and key separation via $Label$ for key schedules that do multiple derivations.

However, the inclusion of $L$ in the PRF input is problematic for the PSA Crypto key derivation API, as we do not have a one-shot key derivation function, and the application can continue to extract additional output. We could take one of the following approaches:

• Recognize that this is optional in the NIST paper, and just drop $[L]$ from the PRF input
• Used the fixed value $[0]_8$ instead of $[L]_8$
• If the application calls psa_key_derivation_set_capacity(len), then use $[\mathtt{len*8}]_8$ in the PRF input, otherwise $[0]_8$

The last of these might permit interoperability with CryptoDome (assuming there is agreement on the PRF input structure), by setting the capacity before extracting any output.

[adeaarm]

Do partners know what the applications are, and can tell us precisely what KDF they need? - or are they expecting that if we specify some CMAC-based KDF, and they implement it, that it will get used by applications because it is accelerated?

A couple of examples are available here and here

I believe in both cases, given that the underlying acceleration technology is similar, the driving requirement is the capability of having it fully accelerated in HW (that HW could be hardened against side channels), rather than some peculiarity of the chosen algorithms, i.e. it's a platform integration constraint. For this reason I believe that the expectation is to have some algorithm based on CMAC for KDF, standardized in the spec. And once it is standardized, it will be used because it is accelerated on such platforms and for such use cases, at the same time keeping compliance to the PSA Crypto standard.

[athoelke]

For this reason I believe that the expectation is to have the some algorithm based on CMAC for KDF, standardized in the spec. And once it is standardized, it will be used because it is accelerated on such platforms and for such use cases, at the same time keeping compliance to the PSA Crypto standard.

It will be important to understand how much of the algorithm is accelerated (or 'difficult to change'). If it just the PRF (CMAC-AES) then what happens with the KDF structure around that is a matter of software/firmware/driver coding. If the structure of the KDF itself is baked into those implementations, then it might be valuable to see if the PSA specification can match those existing implementations.

[athoelke]

However, the inclusion of L in the PRF input is problematic for the PSA Crypto key derivation API, as we do not have a one-shot key derivation function, and the application can continue to extract additional output. We could take one of the following approaches:
...

Alternatively, or in addition, as the input to the PRF after the counter index is fixed for the whole KDF, we could permit the application to supply that entire string (using a different input step value) instead of providing separate $Label$ and $Context$ values.

This places more burden on the programmer to format this string (particularly if they want to match SP 800-108 recommendations), but supports a higher level of interoperability. This might not work with accelerated implementations that have encoded more of the PRF input structure into their design (see previous comment).

[adeaarm]

For this reason I believe that the expectation is to have the some algorithm based on CMAC for KDF, standardized in the spec. And once it is standardized, it will be used because it is accelerated on such platforms and for such use cases, at the same time keeping compliance to the PSA Crypto standard.

It will be important to understand how much of the algorithm is accelerated (or 'difficult to change'). If it just the PRF (CMAC-AES) then what happens with the KDF structure around that is a matter of software/firmware/driver coding. If the structure of the KDF itself is baked into those implementations, then it might be valuable to see if the PSA specification can match those existing implementations.

Talking for these particular implementations, it's the AES-CMAC block being accelerated (i.e. the PRF only), not the construction around it. And the AES HW block in particular is hardened against side channels. I believe such configuration would be common especially in IoT or low power in general targeted accelerators where implementing in HW the whole construction would increase the complexity.

[gilles-peskine-arm]

To clarify and expand on something that I wrote earlier: the KDF from SP 800-108 have a subtle limitation when used with CMAC. They require a secret input KIN of length exactly 16, 24 or 32 bytes. If KIN is not secret (which includes the case where it's a low-entropy, guessable secret), an adversary can construct label or context strings that produce partially known output. This often defeats the security of the protocol that relies on the KDF. In a nutshell, having a fixed-length secret is crucial.

This is specifically a problem with CMAC. With key derivation functions based on a hash or HMAC or KMAC, the differences between the inputs don't really matter: you can use a public input as the “secret” and a private input as the “label”, and that doesn't actually change the practical security properties. So there's a high risk that users will take a protocol that's designed for the most common hash-based KDF, and will not realize that by using CMAC as the building block instead of hash/HMAC the protocol is no longer secure.

SP 800-108r1 warns about this in §4.1 (bottom of page 7):

When using CMAC as the PRF in counter mode, a party with knowledge of the key KIN, who also can freely select portions of the string Label || 0x00 || Context || [L]2 (as described in Appendix B), may be able to control the values of one or more of the K(i). One way to guard against the possibility of this sort of key control would be by replacing the fixed input data
Label || 0x00 || Context || [L]2
with
Label || 0x00 || Context || [L]2 || K (0),
where
K(0) = PRF(KIN, Label || 0x00 || Context || [L]2).

We can specify this construction instead of the default SP 800-108 one. But if we do that, we lose interoperability with common implementations. For example, I don't think you can build that on top of the PKCS#11 CKM_SP800_108_COUNTER_KDF. And if we don't have good interoperability anway, we might as well specify a different CMAC-based construction that can be implemented more efficiently. The SP 800-108 key derivation functions re-process the whole fixed label+context for each output block, which is costly both in processor time and RAM. If we have to build our own, we might as well select a more efficient construction.

[athoelke]

To clarify and expand on something that I wrote earlier: the KDF from SP 800-108 have a subtle limitation when used with CMAC. They require a secret input KIN of length exactly 16, 24 or 32 bytes. If KIN is not secret (which includes the case where it's a low-entropy, guessable secret), an adversary can construct label or context strings that produce partially known output. This often defeats the security of the protocol that relies on the KDF. In a nutshell, having a fixed-length secret is crucial.

For a CMAC-based KDF we can mandate that the PSA_KEY_DERIVATION_INPUT_SECRET step must be a block-cipher key [that is compatible with CMAC] provided using psa_key_derivation_input_key(). This would naturally block a trivial application change from switching from an HMAC-based KDF to a CMAC-based KDF. [In passing, I note that although HKDF-EXPAND uses the secret input as the HMAC key, we failed to specify that the secret key input to this algorithm should have type PSA_KEY_TYPE_HMAC when introducing this algorithm.]

[athoelke]

We can specify this construction instead of the default SP 800-108 one. But if we do that, we lose interoperability with common implementations. For example, I don't think you can build that on top of the PKCS#11 CKM_SP800_108_COUNTER_KDF. And if we don't have good interoperability anway, we might as well specify a different CMAC-based construction that can be implemented more efficiently.

I wondered about leaving this mitigation step to the application, for when the key is known to an attacker: if we specified that the application can specify the entire 'Info' data instead of Label and Context. However, the application would need to use $K_{IN}$ for a CMAC computation, as well as the KDF, which isn't supported by our single-permitted-algorithm policies. If we think hardening the CMAC case by default is better, then I agree that the algorithm definition doesn't need to directly align with what we do for SP800-108-HMAC.

The SP 800-108 key derivation functions re-process the whole fixed label+context for each output block, which is costly both in processor time and RAM. If we have to build our own, we might as well select a more efficient construction.

All of the modes in SP 800-108 process the fixed info once for each output block. HKDF-Expand does the same (but uses a feedback-with-counter style of construction). I'm not sure we should start designing our own CMAC-based KDF, especially if the CMAC computation is borne by hardware.

However, we could simplify the input structure, but include the general design and known-key mitigation from SP 800-108. A suggestion:

Inputs:

• $K_{IN}$: a CMAC key
• $Info$: a possibly-empty application-selected string
• $L$: length of output required

Process:

• $K_0=\mathrm{PRF}(K_{IN},Info)$
• $K_i=\mathrm{PRF}(K_{IN},K_{i-1}\text{ || }[i]_4\text{ || }Info), \quad i=1, ..., n$

Output:

• The first $L$ bytes of $K_1\text{ || }K_2\text{ || }...\text{ || }K_n$

Instead of feedback-mode, could just use $K_0$ in all of the following calls to the PRF, as recommended in the mitigation for CMAC in SP 800-108 counter mode.

[Vge0rge]

Do partners know what the applications are, and can tell us precisely what KDF they need? - or are they expecting that if we specify some CMAC-based KDF, and they implement it, that it will get used by applications because it is accelerated?

I work for Nordic Semiconductor and I just want to back what @adeaarm said already. The most important thing for us it to have the CMAC AES based PRF defined in the PSA APIs. AES CMAC is hardware accelerated and we use it for key derivation.

Having said that and following the very interesting discussion here I think that following a NIST recommendation (even if it leaves some things unclear) is for me an easier decision than implementing our CMAC PRF variant. Enforcing the NIST mitigation inside the APIs is not a problem.

@athoelke Just to make sure that I follow you correctly here. Is your suggestion to allow the users to do a single call to the key derivation APIs where the input whatever structure they want? So they will have to prepare a buffer which (if they want to follow the NIST recommendation) will be:

Label || 0x00 || Context || [L]2

and the driver will have to prefix the counter and suffix the K0?

[athoelke]

Is your suggestion to allow the users to do a single call to the key derivation APIs where the input whatever structure they want? So they will have to prepare a buffer which (if they want to follow the NIST recommendation) will be:

Label || 0x00 || Context || [L]2

and the driver will have to prefix the counter and suffix the K0?

Basically, yes. As the Crypto API permits incremental output of bytes and/or keys, the key derivation operation does not necessarily know how much output it should produce. In contrast, SP 800-108 constructions show the inclusion of [L] in the PRF input, to diversify the output depending on how much derived material is needed.

My suggestion is that instead of an application providing separate Label, Context, and L parameters to the operation, it just supplies a single Info parameter. If the application wants this to match a specific SP 800-108-based design, it needs to structure this Info buffer appropriately.

But as Gilles highlighted, if we adopt the SP 800-108r1 recommendation for CMAC, and add the $K_0$ suffix to the PRF input, then the KDF we specify will not be interoperable with CryptoDome or with PKCS#11 implementations. So perhaps interoperability with other crypto libraries should not be a priority for this function.