If you’ve never heard of NIST SP 800-108 before, or NIST Special Publications in general, here’s a quick primer:

Special Publications are a type of publication issued by NIST. Specifically, the SP 800-series reports on the Information Technology Laboratory’s research, guidelines, and outreach efforts in computer security, and its collaborative activities with industry, government, and academic organizations. These documents often support FIPS (Federal Information Protection Standards).

Via NIST.gov

One of the NIST 800-series documents concerned with Key Derivation using Pseudorandom Functions is NIST SP 800-108, first published in 2009.

In October 2021, NIST published a draft update to NIST SP 800-108 and opened a comment period until January 2022. This update mostly included Keccak-based Message Authentication Codes (KMAC) in addition to the incumbent standardized designs (HMAC and CMAC).

Upon reviewing a proposal for NIST SP 800-108 revision 1 after its comment period opened, Amazon’s cryptographers discovered a novel security issue with the standard.

I was a co-author of the public comment that disclosed this issue, along with Matthew Campagna, Panos Kampanakis, and Adam Petcher, but take no credit for its discovery.

Consequently, Section 6.7 was added to the final revision 1 of the standard to address Key Control Security.

This post examines the attack against the initial SP 800-108 design when AES-CMAC is used as the PRF in KDF Counter mode.

This meme is the TL;DR of this blog post

Preliminaries

(If you’re in a hurry, feel free to skip to the attack.)

NIST SP 800-108 specifies a “KDF in Counter Mode” that can be used with several PRFs, including AES-CMAC. It’s worth noting that this family of KDFs can be defined to use any arbitrary PRF, but only the PRFs approved by NIST for this use are recommended.

AES-CMAC is a one-key CBC-MAC construction. Some cryptographers, such as Matt Green, are famously not fond of CBC-MAC.

KDF Security and PRF Security

Yes, I will take any excuse to turn cryptography knowledge into wholesome memes.

KDF stands for “Key Derivation Function”.

PRF stands for “Pseudo-Random Function”.

The security notion for KDF Security is stronger than PRF Security.

PRFs require a uniformly-distributed secret key, while KDFs can tolerate a key that is not uniformly random.

This matters if you’re, say, trying to derive symmetric encryption keys from a Diffie-Hellman shared secret of some sort, where the output of your DH() function has some algebraic structure.

Realistically, the difference between the two security notions matters a lot less in scenarios where you’re deriving sub-keys from a primary uniformly random cryptographic secret.

However, it does make your proofs nicer to achieve KDF security instead of merely PRF security.

Key Control Security

Let’s pretend, for simplicity, we have a generic KDF() function that offers KDF Security. We don’t need to know how it works just yet.

Because KDFs are thought of as PRFs, but stronger, it seems perfectly reasonable that you could use KDF() in a setup where multiple inputs are provided, each from a different party, and the output would always be uniformly random.

Further, even if all other parties’ inputs are known, it should remain computationally infeasible for one of the parties to influence the output of KDF() to produce a specific value; e.g. a key with all bits zeroed.

The assumption that this result is computationally infeasible when working with KDF() is referred to as “Key Control Security”.

Loss of Key Control Security in NIST SP 800-108

You already know where this is going…

I’m going to explain the attack by way of example.

If you want a more formal treatment, I believe Appendix B of NIST SP 800-108 rev 1 has what you’re looking for.

Imagine that you’re designing an online two-party private messaging app. To ensure forward secrecy, you implement a forward-secure KDF ratchet, loosely inspired by Signal’s design.

For your KDF, you choose AES-CMAC in Counter Mode, because you’re designing for hardware that has accelerated AES instructions and want to avoid the overhead of hash functions.

(Aside: I guess this would also imply you’re most likely selecting AES-CCM for your actual message encryption.)

With each message, the sender commits some random bytes by encrypting them with their message. The recipient, after verifying the authentication tag and decrypting the message, possess knowledge of the same random bytes.

Both parties then use the random bytes and the current symmetric key to ratchet forward to a new 128-bit symmetric key.

The million dollar question is: Is this ratcheting protocol secure?

In the case of KDF in Counter Mode with AES-CMAC, if you have more than 16 bytes of input material, the answer is simply: No.

How The Attack Works

A two-block implementation of this KDF is normally computed as follows:

3. Return

Don’t get intimidated by the notation. This is just AES encryption and XOR.

The messages and are defined in the KDF specification. In the scenario we sketched above, we assume the attacker can choose these arbitrarily.

To coerce a recipient to use an arbitrary 128-bit value (i.e., ) all an attacker needs to do is:

1. Calculate
2. Let some value
   • Here, is the target value.
3. Force

Notice that is the result of encrypting , and our attacker’s goal in step 3 can be achieved solely by manipulating (which exists independent of )?

That’s the vulnerability.

The public comments and Appendix B on the NIST document describe the actual steps of computing to force a chosen , which involve manipulating the structure of to achieve this result.

Feel free to check out both documents if you’re interested in the finer details.

What Can An Attacker Actually Do With This?

If an attacker controls both and …

Or if an attacker knows some and can control …

…then they can force the final KDF output to equal whatever 128-bit value they want you to use.

The most straightforward application of the loss of key control security is to introduce a backdoor into an application.

If the Underhanded Crypto Contest were still running this year, NIST SP 800-108 using AES-CMAC in Counter Mode would be an excellent basis for a contestant.

Does Anyone Actually Use NIST SP 800-108 This Way?

I’m not aware of any specific products or services that use this KDF in this way. I will update this section if someone finds any.

Is This A Deliberate Backdoor in a NIST Standard?

No.

I understand that, in the wake of Dual_EC_DRBG, there is a lot of distrust for NIST’s work on standardized cryptography.

However, I have no specific knowledge to indicate this was placed deliberately in the standard.

It is inaccurate to describe the loss of key control security in this context as a backdoor. Instead, it’s an unexpected property of the algorithms that can be used to create a clever backdoor. These are wildly different propositions.

At least, that was the case until it was disclosed to NIST in January 2022. 🙂

(I’m including an answer to this question, preemptively, in case someone overreacts when I publish this blog post. I hope it proves unnecessary, but I figured some caution was warranted.)

Mitigation Options

If you care about Key Control Security and use NIST SP 800-108, you should use HMAC or KMAC instead of CMAC. Only CMAC is impacted.

Revision 1 of NIST SP800-108 also outlines another mitigation that involves changing the inputs to include an additional (but reusable) PRF output for every block.

This tweak does change makes the KDF behave more like our intuition for PRFs, but in my opinion it’s better to avoid using CMAC entirely for KDFs.

Why Wasn’t This Widely Publicized?

As interesting and surprising as the loss of Key Control Security in a NIST standard is to cryptography nerds, it’s exactly not like Heartbleed or Log4shell.

That said, regardless of your personal feelings on NIST, if you’re interesting in not having findings like this slip through the cracks in the future, it’s generally worthwhile to pay attention to what NIST is up to.

https://scottarc.blog/2024/06/04/attacking-nist-sp-800-108/

#cybersecurity #framework #KDF #KDFSecurity #KeyDerivationFunctions #NIST #NISTSP800108 #PRFSecurity #security #standards #symmetricCryptography