The FIPS Compliance of HKDF

HKDF is an HMAC-based key-derivation function specified in RFC 5869. It’s nice and we generally like using it. FIPS (Federal Information Processing Standards) is used generally as a moniker for the set of standards, recommendations, and guidance published by the U.S. National Institute of Standards and Technology, and more specifically for FIPS 140, the standard concerning the validation of cryptographic modules. There are a number of regulatory settings (such as FedRAMP) that require FIPS 140 compliance, and it often doesn’t let us have nice things. As of earlier this year, I decided to finally bite the bullet and pursue a FIPS 140-3 validation for the Go cryptography standard library, trying to retain as many nice things as possible, so I am diving into the finer details of what’s allowed and what’s not.

The FIPS compliance of HKDF is a somewhat confusing and controversial topic, partially because the normative reference is split over at least four separate documents, but in practice it’s approved for almost any purpose.

NIST SP 800-133 Rev. 2, Recommendation for Cryptographic Key Generation, discusses in Section 6.2 the derivation of symmetric keys, and presents two categories of key-derivation methods:

1. one-step KDFs, defined in SP 800-108 for general purpose use or in SP 800-56C for use on the shared secrets produced by key-agreement schemes;^[1]
2. two-step extraction-then-expansion key-derivation procedures, defined in Section 6.3 (extraction) and SP 800-108 (expansion) for general purpose use or again in SP 800-56C for use as part of key-agreement schemes.

Here the path bifurcates, depending on whether HKDF is being used as part of a key-agreement scheme. Key agreement is defined as

A (pair-wise) key-establishment procedure in which the resultant secret keying material is a function of information contributed by both participants so that neither party can predetermine the value of the secret keying material independently of the contributions of the other party; contrast with key transport.

… essentially Diffie-Hellman.^[2] (See also FIPS 140-3 Implementation Guidance D.F.)

HKDF as part of key-agreement

Let’s start with the key-agreement case, as it’s somewhat more straightforward.

NIST SP 800-56C Rev. 2, Recommendation for Key-Derivation Methods in Key-Establishment Schemes, presents a Two-Step Key Derivation in Section 5. As acknowledged at the bottom of Section 5.1, when instantiated with HMAC, an empty IV, and a Feedback Mode KDF for expansion, this is equivalent to HKDF.

RFC 5869 specifies a version of the above extraction-then-expansion key-derivation procedure using HMAC for both the extraction and expansion steps.

The salt can be negotiated, a fixed value, or all zeroes, like in HKDF. Using the output of one Extract step for multiple Expand operations is explicitly approved, as long as the same HMAC function is used in both.

The input key material can be concatenated with other values, a common practice with Diffie-Hellman contributions:

this Recommendation permits the use of a “hybrid” shared secret of the form Z ′ = Z || T, a concatenation consisting of a “standard” shared secret Z that was generated during the execution of a key-establishment scheme (as currently specified in [SP 800-56A] or [SP 800-56B]) followed by an auxiliary shared secret T that has been generated using some other method

HKDF as part of key-agreement can be CAVP-tested stand-alone as “KDA HKDF Sp800-56Cr2” per IG D.F.

Note that the one-step key derivation defined in SP 800-56C is a counter-based KDF (i.e. neither HKDF-Extract nor HKDF-Expand) so it doesn’t seem to be FIPS-compliant to skip either the extract or expand step as part of key-agreement.

HKDF as a general-purpose KDF

Until recently I was under the impression that HKDF was only allowed as part of key-agreement. That’s not the case!

HKDF-Expand as a SP 800-108 KDF

HKDF-Expand on its own turns out to be a mode of NIST SP 800-108 Rev. 1 Upd. 1, Recommendation for Key Derivation Using Pseudorandom Functions, which defines approved general-purpose KDFs (and is referenced by SP 800-133 above for one-step KDFs).

I initially thought that not to be the case, because the Feedback Mode KDF is defined in Section 4.2 as computing HMAC(K_in, K(i-1) || i || FixedInfo) while HKDF-Expand computes HMAC(K_in, K(i-1) || info || i). Note the order of counter i and info. Everything else in the SP 800-108 Feedback Mode KDF could be tweaked to land at HKDF, but I found nothing in the text that allowed swapping the order.

However, SP 800-56C claims explicitly that HKDF is a profile of its two-step key-derivation method, and describes the expansion step simply by reference to SP 800-108!

One of the general-purpose, PRF-based key-derivation functions defined in SP 800-108 shall be used for key expansion.

To confirm this, I went looking at the ACVP tests for SP 800-108, and indeed there’s a fixedDataOrder parameter which “describes where the counter appears in the fixed data” and that can be set to "after fixed data". The relevant ACVP test vectors^[3] pass when applied to HKDF-Expand, proving that it’s an approved version of SP 800-108.

Note that in order to use HKDF-Expand in the approved mode of operation for this purpose, the FIPS 140 cryptographic module will need to include the SP 800-108 Feedback KDF in its certificate.

HKDF-Extract per SP 800-133

Ok, so HKDF-Expand is a general purpose KDF, but what about HKDF-Extract?

SP 800-133 Rev. 2, published in 2020, added a new method to Section 6.3, Symmetric Keys Produced by Combining (Multiple) Keys and Other Data. The new Method 3, called “a key-extraction process” is simply HMAC(salt, K || … || D || …) aka HKDF-Extract!

While the other methods require multiple keys, or both a key and other data, Method 3 requires n (the number of keys) ≥ 1 and m (the other data) ≥ 0, so it’s explicitly allowed even with a single key as input. The salt can be a secret or non-secret value. Alternative orderings of keys and data are explicitly permitted.

This is confirmed by IG 2.4.B, which states “the underlying functions performed within the [n.d.a. HKDF-based] TLS 1.3 KDF map to NIST approved standards, namely: SP 800-133rev2 (Section 6.3 Option #3), SP 800-56Crev2, and SP 800-108”.

There is no CAVP testing or CAST requirement for SP 800-133 Section 6.3 but IG D.H requires Vendor Affirmation in the module certificate.

Vendor affirmation to SP 800-133 is required for all methods covered by Sections 4 and 6.3 of this standard; […] The Security Policy shall provide the details of each method. […] There is no specific CAST requirement if vendor affirmation is claimed for SP 800-133, other than the CASTs required for the underlying approved algorithms, per IG 10.3.A.

Additional Comment 4 even goes out of its way to bless Section 6.2(3).

The method of generating a key by a key-extraction process defined in item 3 of Section 6.3 of SP 800-133rev2 is new to the SP 800-133 series. This method is approved for use in the approved mode upon the publication of this Implementation Guidance.

There’s a wrinkle, though. The same IG says that at least one of the input keys must be generated from a DRBG, so it seems to me that you can’t feed the output of a KDF into HKDF-Extract as a key (unlike with SP 800-108 KDFs per Section 6 and IG D.M).

(a) At least one of the component keys K1, …, Kn is generated as shown in Section 4 of SP 800-133 with an independence requirement of Section 6.3 met, and (b) None of the component keys K1, …, Kn are generated from a password.

Summing up

If you’re doing key-agreement you can use HKDF per SP 800-56C Rev. 2. If you’re not you can use HKDF-Extract to combine a randomly-generated key with other keys and/or data per SP 800-133 Rev. 2 (Section 6.3 Option #3), and use HKDF-Expand as a general purpose KDF per SP 800-108.

I should note that this makes sense, because if you have a high-quality key (as opposed to a shared secret, in which case SP 800-56C applies) you can generally skip the Extract step and go straight to the SP 800-108 use. If you want to combine multiple keys, or keys and other data, you’ll want to do Extract, and that’s what SP 800-133 Section 6.3 covers.

Keep in mind that using approved algorithms is only half the battle, since FIPS 140 compliance also requires using a module that was validated for those algorithms. The planned Go FIPS module will test HKDF as both SP 800-56Crev2 and SP 800-133, and will Vendor Affirm SP 800-133rev2 support, making it usable everywhere possible.

If you’d like to sponsor the effort to validate the Go standard library (and produce these 1500 words articles), reach out! If you’d like to follow along as I descend into madness, follow me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @filippo@abyssdomain.expert.

The picture

Some of us don’t go to IKEA for the nordic furniture that comes with an assembling minigame, but for the extremely huggable stuffed BLÅHAJ sharks. There were rumors of them being discontinued a couple years ago, so I acquired a small strategic reserve. Here you can see them discussing their future deployments.

My maintenance work is funded by the awesome Geomys clients: Latacora, Interchain, Smallstep, Ava Labs, Teleport, SandboxAQ, Charm, and Tailscale. Through our retainer contracts they ensure the sustainability and reliability of our open source maintenance work and get a direct line to my expertise and that of the other Geomys maintainers. (Learn more in the Geomys announcement.)

Here are a few words from some of them!

Latacora — Latacora bootstraps security practices for startups. Instead of wasting your time trying to hire a security person who is good at everything from Android security to AWS IAM strategies to SOC2 and apparently has the time to answer all your security questionnaires plus never gets sick or takes a day off, you hire us. We provide a crack team of professionals prepped with processes and power tools, coupling individual security capabilities with strategic program management and tactical project management.

Teleport — For the past five years, attacks and compromises have been shifting from traditional malware and security breaches to identifying and compromising valid user accounts and credentials with social engineering, credential theft, or phishing. Teleport Identity Governance & Security is designed to eliminate weak access patterns through access monitoring, minimize attack surface with access requests, and purge unused permissions via mandatory access reviews.

Ava Labs — We at Ava Labs, maintainer of AvalancheGo (the most widely used client for interacting with the Avalanche Network), believe the sustainable maintenance and development of open source cryptographic protocols is critical to the broad adoption of blockchain technology. We are proud to support this necessary and impactful work through our ongoing sponsorship of Filippo and his team.

SandboxAQ — SandboxAQ’s AQtive Guard is a unified cryptographic management software platform that helps protect sensitive data and ensures compliance with authorities and customers. It provides a full range of capabilities to achieve cryptographic agility, acting as an essential cryptography inventory and data aggregation platform that applies current and future standardization organizations mandates. AQtive Guard automatically analyzes and reports on your cryptographic security posture and policy management, enabling your team to deploy and enforce new protocols, including quantum-resistant cryptography, without re-writing code or modifying your IT infrastructure.

Charm — If you’re a terminal lover, join the club. Charm builds tools and libraries for the command line. Everything from styling terminal apps with Lip Gloss to making your shell scripts interactive with Gum. Charm builds libraries in Go to enhance CLI applications while building with these libraries to deliver CLI and TUI-based apps.