There is, at the time of this writing, an ongoing debate in the Crypto Research Forum Group (CFRG) at the IETF about KEM combiners.

One of the participants, Deirdre Connolly, wrote a blog post titled How to Hold KEMs. The subtitle is refreshingly honest: “A living document on how to juggle these damned things.”

Deirdre also co-authored the paper describing a Hybrid KEM called X-Wing, which combines X25519 with ML-KEM-768 (which is the name for a standardized tweak of Kyber, which I happened to opine on a few years ago).

After sharing a link to Deirdre’s blog in a few places, several friendly folk expressed confusion about KEMs in general.

So very briefly, here’s an introduction to Key Encapsulation Mechanisms in general, to serve as a supplementary resource for any future discussion on KEMs.

You shouldn’t need to understand lattices or number theory, or even how to read a mathematics paper, to understand this stuff.

CMYKat

Building Intuition for KEMs

For the moment, let’s suspend most real-world security risks and focus on a simplified, ideal setting.

To begin with, you need some kind of Asymmetric Encryption.

Asymmetric Encryption means, “Encrypt some data with a Public Key, then Decrypt the ciphertext with a Secret Key.” You don’t need to know, or even care, about how it works at the moment.

Your mental model for asymmetric encryption and decryption should look like this:

interface AsymmetricEncryption { encrypt(publicKey: CryptoKey, plaintext: Uint8Array); decrypt(secretKey: CryptoKey, ciphertext: Uint8Array);}

As I’ve written previously, you never want to actually use asymmetric encryption directly.

Using asymmetric encryption safely means using it to exchange a key used for symmetric data encryption, like so:

// Alice sends an encrypted key to BobsymmetricKey = randomBytes(32)sendToBob = AsymmetricEncryption.encrypt( bobPublicKey, symmetricKey)// Bob decrypts the encrypted key from Alicedecrypted = AsymmetricEncryption.decrypt( bobSecretKey, sendToBob)assert(decrypted == symmetricKey) // true

You can then use symmetricKey to encrypt your actual messages and, unless something else goes wrong, only the other party can read them. Hooray!

And, ideally, this is where the story would end. Asymmetric encryption is cool. Don’t look at the scroll bar.

CMYKat

Unfortunately

The real world isn’t as nice as our previous imagination.

We just kind of hand-waved that asymmetric encryption is a thing that happens, without further examination. It turns out, you have to examine further in order to be secure.

The most common asymmetric encryption algorithm deployed on the Internet as of February 2024 is called RSA. It involves Number Theory. You can learn all about it from other articles if you’re curious. I’m only going to describe the essential facts here.

Keep in mind, the primary motivation for KEMs comes from post-quantum cryptography, not RSA.

CMYKat

From Textbook RSA to Real World RSA

RSA is what we call a “trapdoor permutation”: It’s easy to compute encryption (one way), but decrypting is only easy if you have the correct secret key (the other way).

RSA operates on large blocks, related to the size of the public key. For example: 2048-bit RSA public keys operate on 2048-bit messages.

Encrypting with RSA involves exponents. The base of these exponents is your message. The outcome of the exponent operation is reduced, using the modulus operator, by the public key.

(The correct terminology is actually slightly different, but we’re aiming for intuition, not technical precision. Your public key is both the large modulus and exponent used for encryption. Don’t worry about it for the moment.)

If you have a very short message, and a tiny exponent (say, 3), you don’t need the secret key to decrypt it. You can just take the cube-root of the ciphertext and recover the message!

That’s obviously not very good!

To prevent this very trivial weakness, cryptographers proposed standardized padding schemes to ensure that the output of the exponentiation is always larger than the public key. (We say, “it must wrap the modulus”.)

The most common padding mode is called PKCS#1 v1.5 padding. Almost everything that implements RSA uses this padding scheme. It’s also been publicly known to be insecure since 1998.

The other padding mode, which you should be using (if you even use RSA at all) is called OAEP. However, even OAEP isn’t fool proof: If you don’t implement it in constant-time, your application will be vulnerable to a slightly different attack.

This Padding Stinks; Can We Dispense Of It?

It turns out, yes, we can. Safely, too!

We need to change our relationship with our asymmetric encryption primitive.

Instead of encrypting the secret we actually want to use, let’s just encrypt some very large random value.

Then we can use the result with a Key Derivation Function (which you can think of, for the moment, like a hash function) to derive a symmetric encryption key.

class OversimplifiedKEM { function encaps(pk: CryptoKey) { let N = pk.getModulus() let r = randomNumber(1, N-1) let c = AsymmetricEncryption.encrypt(pk, r) return [c, kdf(r)] } function decaps(sk: CryptoKey, c: Uint8Array) { let r2 = AsymmetricEncryption.decrypt(sk, c) return kdf(r2) }}

In the pseudocode above, the actual asymmetric encryption primitive doesn’t involve any sort of padding mode. It’s textbook RSA, or equivalent.

KEMs are generally constructed somewhat like this, but they’re all different in their own special, nuanced ways. Some will look like what I sketched out, others will look subtly different.

Understanding that KEMs are a construction on top of asymmetric encryption is critical to understanding them.

It’s just a slight departure from asymmetric encryption as most developers intuit it.

Cool, we’re almost there.

CMYKat

The one thing to keep in mind: While this transition from Asymmetric Encryption (also known as “Public Key Encryption”) to a Key Encapsulation Mechanism is easy to follow, the story isn’t as simple as “it lets you skip padding”. That’s an RSA specific implementation detail for this specific path into KEMs.

The main thing you get out of KEMs is called IND-CCA security, even when the underlying Public Key Encryption mechanism doesn’t offer that property.

CMYKat

IND-CCA security is a formal notion that basically means “protection against an attacker that can alter ciphertexts and study the system’s response, and then learn something useful from that response”.

IND-CCA is short for “indistinguishability under chosen ciphertext attack”. There are several levels of IND-CCA security (1, 2, and 3). Most modern systems aim for IND-CCA2.

Most people reading this don’t have to know or even care what this means; it will not be on the final exam. But cryptographers and their adversaries do care about this.

What Are You Feeding That Thing?

Deirdre’s blog post touched on a bunch of formal security properties for KEMs, which have names like X-BIND-K-PK or X-BIND-CT-PK.

Most of this has to deal with, “What exactly gets hashed in the KEM construction at the KDF step?” (although some properties can hold even without being included; it gets complicated).

For example, from the pseudocode in the previous section, it’s more secure to not only hash r, but also c and pk, and any other relevant transcript data.

class BetterKEM { function encaps(pk: CryptoKey) { let N = pk.getModulus() let r = randomNumber(1, N-1) let c = AsymmetricEncryption.encrypt(pk, r) return [c, kdf(pk, c, r)] } function decaps(sk: CryptoKey, c: Uint8Array) { let pk = sk.getPublickey() let r2 = AsymmetricEncryption.decrypt(sk, c) return kdf(pk, c, r2) }}

In this example, BetterKem is greatly more secure than OversimplifiedKEM, for reasons that have nothing to do with the underlying asymmetric primitive. The thing it does better is commit more of its context into the KDF step, which means that there’s less pliability given to attackers while still targeting the same KDF output.

If you think about KDFs like you do hash functions (which they’re usually built with), changing any of the values in the transcript will trigger the avalanche effect: The resulting calculation, which is not directly transmitted, is practically indistinguishable from random bytes. This is annoying to try to attack–even with collision attack strategies (birthday collision, Pollard’s rho, etc.).

However, if your hash function is very slow (i.e., SHA3-256), you might be worried about the extra computation and energy expenditure, especially if you’re working with larger keys.

Specifically, the size of keys you get from ML-KEM or other lattice-based cryptography.

That’s where X-Wing is actually very clever: It combines X25519 and ML-KEM-768 in such a way that binds the output to both keys without requiring the additional bytes of ML-KEM-768 ciphertext or public key.

From the X-Wing paper.

However, it’s only secure to use it this way because of the specific properties of ML-KEM and X25519.

Some questions may come to mind:

1. Does this additional performance hit actually matter, though?
2. Would a general purpose KEM combiner be better than one that’s specially tailored to the primitives it uses?
3. Is it secure to simply concatenate the output of multiple asymmetric operations to feed into a single KDF, or should a more specialized KDF be defined for this purpose?

Well, that’s exactly what the CFRG is debating!

CMYKat

Closing Thoughts

KEMs aren’t nearly as arcane or unapproachable as you may suspect. You don’t really even need to know any of the mathematics to understand them, though it certainly does help.

I hope that others find this useful.

Header art by Harubaki and AJ.

https://soatok.blog/2024/02/26/kem-trails-understanding-key-encapsulation-mechanisms/

#asymmetricCryptography #cryptography #KDF #KEM #keyEncapsulationMechanism #postQuantumCryptography #RSA

Dhole Moments

2022-01-27 11:13:50

Did you know that, in the Furry Fandom, the most popular choice in species for one’s fursona is actually a hybrid?

Source: FurScience

Of course, we’re not talking about that kind of hybrid today. I just thought it was an amusing coincidence.

Art: Lynx vs Jackalope

Nor are we talking about what comes to mind for engineers accustomed to classical cryptography when you say Hybrid.

(Such engineers typically envision some combination of asymmetric key encapsulation with symmetric encryption; because too many people encrypt with RSA directly and the sane approach is often described as a Hybrid Cryptosystem in the literature.)

Rather, Hybrid Cryptography in today’s context refers to:

Cryptography systems that use a post-quantum cryptography algorithm, combined with one of the algorithms deployed today that aren’t resistant to quantum computers.

If you need to differentiate the two, PQ-Hybrid might be a better designation.

Why Hybrid Cryptosystems?

At some point in the future (years or decades from now), humanity may build a practical quantum computer. This will be a complete disaster for all of the cryptography deployed on the Internet today.

In response to this distant existential threat, cryptographers have been hard at work designing and attacking algorithms that remain secure even when quantum computers arrive. These algorithms are classified as post-quantum cryptography (mostly to distinguish it from techniques that uses quantum computers to facilitate cryptography rather than attack it, which is “quantum cryptography” and not really worth our time talking about). Post-quantum cryptography is often abbreviated as “PQ Crypto” or “PQC”.

However, a lot of the post-quantum cryptography designs are relatively new or comparatively less studied than their classical (pre-quantum) counterparts. Several of the Round 1 candidates to NIST’s post quantum cryptography project were broken immediately (PDF). Exploit code referenced in PDF duplicated below.:

#!/usr/bin/env python3import binascii, structdef recover_bit(ct, bit): assert bit < len(ct) // 4000 ts = [struct.unpack('BB', ct[i:i+2]) for i in range(4000*bit, 4000*(bit+1), 2)] xs, ys = [a for a, b in ts if b == 1], [a for a, b in ts if b == 2] return sum(xs) / len(xs) >= sum(ys) / len(ys)def decrypt(ct): res = sum(recover_bit(ct, b) << b for b in range(len(ct) // 4000)) return int.to_bytes(res, len(ct) // 4000 // 8, 'little')kat = 0for l in open('KAT_GuessAgain/GuessAgainEncryptKAT_2000.rsp'): if l.startswith('msg = '): # only used for verifying the recovered plaintext. msg = binascii.unhexlify(l[len('msg = '):].strip()) elif l.startswith('c = '): ct = binascii.unhexlify(l[len('c = '):].strip()) print('{}attacking known-answer test #{}'.format('\n' * (kat > 0), kat)) print('correct plaintext: {}'.format(binascii.hexlify(msg).decode())) plain = decrypt(ct) print('recovered plaintext: {} ({})'.format(binascii.hexlify(plain).decode(), plain == msg)) kat += 1

More pertinent to our discussions: Rainbow, which was one of the Round 3 Finalists for post-quantum digital signature algorithms, was discovered in 2020 to be much easier to attack than previously thought. Specifically, for the third round parameters, the attack cost was reduced by a factor of , , and .

That security reduction is just a tad bit more concerning than a Round 1 candidate being totally broken, since NIST had concluded by then that Rainbow was a good signature algorithm until that attack was discovered. Maybe there are similar attacks just waiting to be found?

Given that new cryptography is accompanied by less confidence than incumbent cryptography, hybrid designs are an excellent way to mitigate the risk of attack advancements in post-quantum cryptography:

If the security of your system requires breaking the cryptography used today AND breaking one of the new-fangled designs, you’ll always be at least as secure as the stronger algorithm.

Art: Lynx vs Jackalope

Why Is Hybrid Cryptography Controversial?

Despite the risks of greenfield cryptographic algorithms, the NSA has begun recommending a strictly-PQ approach to cryptography and have explicitly stated that they will not require hybrid designs.

Another pushback on hybrid cryptography comes from Uri Blumenthal of MIT’s Lincoln Labs on the IETF CFRG mailing list (the acronym CRQC expands to “Cryptographically-Relevant Quantum Computer”):

Here are the possibilities and their relation to the usefulness of the Hybrid approach.

1. CRQC arrived, Classic hold against classic attacks, PQ algorithms hold – Hybrid is useless.

2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail – Hybrid is useless.

3. CRQC arrived, Classic broken against classic attacks, PQ algorithms hold – Hybrid is useless.

4. CRQC arrived, Classic hold against classic attacks, PQ algorithms broken – Hybrid useless.

5. CRQC doesn’t arrive, Classic hold against classic attacks, PQ algorithms hold – Hybrid is useless.

6. CRQC doesn’t arrive, Classic hold against classic attacks, PQ algorithms broken – Hybrid helps.

7. CRQC doesn’t arrive, Classic broken against classic attacks, PQ algorithms hold – Hybrid is useless.

8. CRQC doesn’t arrive, Classic broken against classic attacks, PQ algorithms broken – Hybrid is useless.

Uri Blumenthal, IETF CFRG mailing list, December 2021 (link)

Why Hybrid Is Actually A Damn Good Idea

Art: Scruff Kerfluff

Uri’s risk analysis is, of course, flawed. And I’m not the first to disagree with him.

First, Uri’s framing sort of implies that each of the 8 possible outputs of these 3 boolean variables are relatively equally likely outcomes.

It’s very tempting to look at this and think, “Wow, that’s a lot of work for something that only helps in 12.5% of possible outcomes!” Uri didn’t explicitly state this assumption, and he might not even believe that, but it is a cognitive trap that emerges in the structure of his argument, so watch your step.

Second, for many candidate algorithms, we’re already in scenario 6 that Uri outlined! It’s not some hypothetical future, it’s the present state of affairs.

To wit: The advances in cryptanalysis on Rainbow don’t totally break it in a practical sense, but they do reduce the security by a devastating margin (which will require significantly larger parameter sets and performance penalties to remedy).

For many post-quantum algorithms, we’re still uncertain about which scenario is most relevant. But since PQ algorithms are being successfully attacked and a quantum computer still hasn’t arrived, and classical algorithms are still holding up fine, it’s very clear that “hybrid helps” is the world we most likely inhabit today, and likely will for many years (until the existence of quantum computers is finally settled).

Finally, even in other scenarios (which are more relevant for other post-quantum algorithms), hybrid doesn’t significantly hurt security. It does carry a minor cost to bandwidth and performance, and it does mean having a larger codebase to review when compared with jettisoning the algorithms we use today, but I’d argue that the existing code is relatively low risk compared to new code.

From what I’ve read, the NSA didn’t make as strong an argument as Uri; they said hybrid would not be required, but didn’t go so far as to attack it.

Hybrid cryptography is a long-term bet that will protect the most users from cryptanalytic advancements, contrasted with strictly-PQ and no-PQ approaches.

Why The Hybrid Controversy Remains Unsettled

Even if we can all agree that hybrid is the way to go, there’s still significant disagreement on exactly how to do it.

Hybrid KEMs

There are two schools of thought on hybrid Key Encapsulation Mechanisms (KEMs):

1. Wrap the post-quantum KEM in the encrypted channel created by the classical KEM.
2. Use both the post-quantum KEM and classical KEM as inputs to a secure KDF, then use a single encrypted channel secured by both.

The first option (layered) has the benefit of making migrations smoother. You can begin with classical cryptography (i.e. ECDHE for TLS ciphersuites), which is what most systems online support today. Then you can do your post-quantum cryptography inside the existing channel to create a post-quantum-secure channel. This also lends toward opportunistic upgrades (which might not be a good idea).

The second option (composite) has the benefit of making the security of your protocol all-or-nothing: You cannot attack the weak now and the strong part later. The session keys you’ll derive require attacking both algorithms in order to get access to the plaintext. Additionally, you only need a single layer. The complexity lies entirely within the handshake, instead of every packet.

Personally, I think composite is a better option for security than layered.

Hybrid Signatures

There are, additionally, two different schools of thought on hybrid digital signature algorithms. However, the difference is more subtle than with KEMs.

1. Require separate classical signatures and post-quantum signatures.
2. Specify a composite mode that combines the two together and treat it as a distinct algorithm.

To better illustrate what this looks like, I outlined what a composite hybrid digital signature algorithm could look like on the CFRG mailing list:

primary_seed := randombytes_buf(64) // store thised25519_seed := hash_sha512256(PREFIX_CLASSICAL || primary_seed)pq_seed := hash_sha512256(PREFIX_POSTQUANTUM || primary_seed)ed25519_keypair := crypto_sign_seed_keypair(ed25519_seed)pq_keypair := pqcrypto_sign_seed_keypair(pq_seed)

Your composite public key would be your Ed25519 public key, followed by your post-quantum public key. Since Ed25519 public keys are always 32 bytes, this is easy to implement securely.

Every composite signature would be an Ed25519 signature concatenated with the post-quantum signature. Since Ed25519 signatures are always 64 bytes, this leads to a predictable signature size relative to the post-quantum signature.

The main motivation for preferring a composite hybrid signature over a detached hybrid signature is to push the hybridization of cryptography lower in the stack so developers don’t have to think about these details. They just select HYBRIDSIG1 or HYBRIDSIG2 in their ciphersuite configuration, and cryptographers get to decide what that means.

TL;DR

Hybrid designs of post-quantum crypto are good, and I think composite hybrid designs make the most sense for both KEMs and signatures.

https://soatok.blog/2022/01/27/the-controversy-surrounding-hybrid-cryptography/

#asymmetricCryptography #classicalCryptography #cryptography #digitalSignatureAlgorithm #hybridCryptography #hybridDesigns #KEM #keyEncapsulationMechanism #NISTPostQuantumCryptographyProject #NISTPQC #postQuantumCryptography

NIST opened public comments on SP 800-108 Rev. 1 (the NIST recommendations for Key Derivation Functions) last month. The main thing that’s changed from the original document published in 2009 is the inclusion of the Keccak-based KMAC alongside the incumbent algorithms.

One of the recommendations of SP 800-108 is called “KDF in Counter Mode”. A related document, SP 800-56C, suggests using a specific algorithm called HKDF instead of the generic Counter Mode construction from SP 800-108–even though they both accomplish the same goal.

Isn’t standards compliance fun?

Interestingly, HKDF isn’t just an inconsistently NIST-recommended KDF, it’s also a common building block in a software developer’s toolkit which sees a lot of use in different protocols.

Unfortunately, the way HKDF is widely used is actually incorrect given its formal security definition. I’ll explain what I mean in a moment.

Art: Scruff

What is HKDF?

To first understand what HKDF is, you first need to know about HMAC.

HMAC is a standard message authentication code (MAC) algorithm built with cryptographic hash functions (that’s the H). HMAC is specified in RFC 2104 (yes, it’s that old).

HKDF is a key-derivation function that uses HMAC under-the-hood. HKDF is commonly used in encryption tools (Signal, age). HKDF is specified in RFC 5869.

HKDF is used to derive a uniformly-random secret key, typically for use with symmetric cryptography algorithms. In any situation where a key might need to be derived, you might see HKDF being used. (Although, there may be better algorithms.)

Art: LvJ

How Developers Understand and Use HKDF

If you’re a software developer working with cryptography, you’ve probably seen an API in the crypto module for your programming language that looks like this, or maybe this.

hash_hkdf( string $algo, string $key, int $length = 0, string $info = "", string $salt = ""): string

Software developers that work with cryptography will typically think of the HKDF parameters like so:

• $algo — which hash function to use
• $key — the input key, from which multiple keys can be derived
• $length — how many bytes to derive
• $info — some arbitrary string used to bind a derived key to an intended context
• $salt — some additional randomness (optional)

The most common use-case of HKDF is to implement key-splitting, where a single input key (the Initial Keying Material, or IKM) is used to derive two or more independent keys, so that you’re never using a single key for multiple algorithms.

See also: [url=https://github.com/defuse/php-encryption]defuse/php-encryption[/url], a popular PHP encryption library that does exactly what I just described.

At a super high level, the HKDF usage I’m describing looks like this:

class MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'encryption', $salt )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'message authentication', $salt )); return [$encryptKey, $authKey];}public function encryptString(string $plaintext, CryptographyKey $key): string{ $salt = random_bytes(32); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... encryption logic here ... return base64_encode($salt . $ciphertext . $mac);}public function decryptString(string $encrypted, CryptographyKey $key): string{ $decoded = base64_decode($encrypted); $salt = mb_substr($decoded, 0, 32, '8bit'); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... decryption logic here ... return $plaintext;}// ... other method here ...}

Unfortunately, anyone who ever does something like this just violated one of the core assumptions of the HKDF security definition and no longer gets to claim “KDF security” for their construction. Instead, your protocol merely gets to claim “PRF security”.

Art: Harubaki

KDF? PRF? OMGWTFBBQ?

Let’s take a step back and look at some basic concepts.

(If you want a more formal treatment, read this Stack Exchange answer.)

PRF: Pseudo-Random Functions

A pseudorandom function (PRF) is an efficient function that emulates a random oracle.

“What the hell’s a random oracle?” you ask? Well, Thomas Pornin has the best explanation for random oracles:

A random oracle is described by the following model:

• There is a black box. In the box lives a gnome, with a big book and some dice.
• We can input some data into the box (an arbitrary sequence of bits).
• Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
• If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message m. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really “random” oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Thomas Pornin

Alternatively, Wikipedia has a more formal definition available to the academic-inclined.

In practical terms, we can generate a strong PRF out of secure cryptographic hash functions by using a keyed construction; i.e. HMAC.

Thus, as long as your HMAC key is a secret, the output of HMAC can be generally treated as a PRF for all practical purposes. Your main security consideration (besides key management) is the collision risk if you truncate its output.

Art: LvJ

KDF: Key Derivation Functions

A key derivation function (KDF) is exactly what it says on the label: a cryptographic algorithm that derives one or more cryptographic keys from a secret input (which may be another cryptography key, a group element from a Diffie-Hellman key exchange, or a human-memorable password).

Note that passwords should be used with a Password-Based Key Derivation Function, such as scrypt or Argon2id, not HKDF.

Despite what you may read online, KDFs do not need to be built upon cryptographic hash functions, specifically; but in practice, they often are.

A notable counter-example to this hash function assumption: CMAC in Counter Mode (from NIST SP 800-108) uses AES-CMAC, which is a variable-length input variant of CBC-MAC. CBC-MAC uses a block cipher, not a hash function.

Regardless of the construction, KDFs use a PRF under the hood, and the output of a KDF is supposed to be a uniformly random bit string.

Art: LvJ

PRF vs KDF Security Definitions

The security definition for a KDF has more relaxed requirements than PRFs: PRFs require the secret key be uniformly random. KDFs do not have this requirement.

If you use a KDF with a non-uniformly random IKM, you probably need the KDF security definition.

If your IKM is already uniformly random (i.e. the “key separation” use case), you can get by with just a PRF security definition.

After all, the entire point of KDFs is to allow a congruent security level as you’d get from uniformly random secret keys, without also requiring them.

However, if you’re building a protocol with a security requirement satisfied by a KDF, but you actually implemented a PRF (i.e., not a KDF), this is a security vulnerability in your cryptographic design.

Art: LvJ

The HKDF Algorithm

HKDF is an HMAC-based KDF. Its algorithm consists of two distinct steps:

1. HKDF-Extract uses the Initial Keying Material (IKM) and Salt to produce a Pseudo-Random Key (PRK).
2. HKDF-Expand actually derives the keys using PRK, the info parameter, and a counter (from 0 to 255) for each hash function output needed to generate the desired output length.

If you’d like to see an implementation of this algorithm, defuse/php-encryption provides one (since it didn’t land in PHP until 7.1.0). Alternatively, there’s a Python implementation on Wikipedia that uses HMAC-SHA256.

This detail about the two steps will matter a lot in just a moment.

Art: Swizz

How HKDF Salts Are Misused

The HKDF paper, written by Hugo Krawczyk, contains the following definition (page 7).

The paper goes on to discuss the requirements for authenticating the salt over the communication channel, lest the attacker have the ability to influence it.

A subtle detail of this definition is that the security definition says that A salt value , not Multiple salt values.

Which means: You’re not supposed to use HKDF with a constant IKM, info label, etc. but vary the salt for multiple invocations. The salt must either be a fixed random value, or NULL.

The HKDF RFC makes this distinction even less clear when it argues for random salts.

We stress, however, that the use of salt adds significantly to the strength of HKDF, ensuring independence between different uses of the hash function, supporting “source-independent” extraction, and strengthening the analytical results that back the HKDF design.

Random salt differs fundamentally from the initial keying material in two ways: it is non-secret and can be re-used. As such, salt values are available to many applications. For example, a pseudorandom number generator (PRNG) that continuously produces outputs by applying HKDF to renewable pools of entropy (e.g., sampled system events) can fix a salt value and use it for multiple applications of HKDF without having to protect the secrecy of the salt. In a different application domain, a key agreement protocol deriving cryptographic keys from a Diffie-Hellman exchange can derive a salt value from public nonces exchanged and authenticated between communicating parties as part of the key agreement (this is the approach taken in [IKEv2]).

RFC 5869, section 3.1

Okay, sure. Random salts are better than a NULL salt. And while this section alludes to “[fixing] a salt value” to “use it for multiple applications of HKDF without having to protect the secrecy of the salt”, it never explicitly states this requirement. Thus, the poor implementor is left to figure this out on their own.

Thus, because it’s not using HKDF in accordance with its security definition, many implementations (such as the PHP encryption library we’ve been studying) do not get to claim that their construction has KDF security.

Instead, they only get to claim “Strong PRF” security, which you can get from just using HMAC.

Art: LvJ

What Purpose Do HKDF Salts Actually Serve?

Recall that the HKDF algorithm uses salts in the HDKF-Extract step. Salts in this context were intended for deriving keys from a Diffie-Hellman output, or a human-memorable password.

In the case of [Elliptic Curve] Diffie-Hellman outputs, the result of the key exchange algorithm is a random group element, but not necessarily uniformly random bit string. There’s some structure to the output of these functions. This is why you always, at minimum, apply a cryptographic hash function to the output of [EC]DH before using it as a symmetric key.

HKDF uses salts as a mechanism to improve the quality of randomness when working with group elements and passwords.

Extending the nonce for a symmetric-key AEAD mode is a good idea, but using HKDF’s salt parameter specifically to accomplish this is a misuse of its intended function, and produces a weaker argument for your protocol’s security than would otherwise be possible.

How Should You Introduce Randomness into HKDF?

Just shove it in the info parameter.

Art: LvJ

It may seem weird, and defy intuition, but the correct way to introduce randomness into HKDF as most developers interact with the algorithm is to skip the salt parameter entirely (either fixing it to a specific value for domain-separation or leaving it NULL), and instead concatenate data into the info parameter.

class BetterEncryptor extends MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'encryption', '' // intentionally empty )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'message authentication', '' // intentionally empty )); return [$encryptKey, $authKey];}}

Of course, you still have to watch out for canonicalization attacks if you’re feeding multi-part messages into the info tag.

Another advantage: This also lets you optimize your HKDF calls by caching the PRK from the HKDF-Extract step and reuse it for multiple invocations of HKDF-Expand with a distinct info. This allows you to reduce the number of hash function invocations from to (since each HMAC involves two hash function invocations).

Notably, this HKDF salt usage was one of the things that was changed in V3/V4 of PASETO.

Does This Distinction Really Matter?

If it matters, your cryptographer will tell you it matters–which probably means they have a security proof that assumes the KDF security definition for a very good reason, and you’re not allowed to violate that assumption.

Otherwise, probably not. Strong PRF security is still pretty damn good for most threat models.

Art: LvJ

Closing Thoughts

If your takeaway was, “Wow, I feel stupid,” don’t, because you’re in good company.

I’ve encountered several designs in my professional life that shoved the randomness into the info parameter, and it perplexed me because there was a perfectly good salt parameter right there. It turned out, I was wrong to believe that, for all of the subtle and previously poorly documented reasons discussed above. But now we both know, and we’re all better off for it.

So don’t feel dumb for not knowing. I didn’t either, until this was pointed out to me by a very patient colleague.

“Feeling like you were stupid” just means you learned.
(Art: LvJ)

Also, someone should really get NIST to be consistent about whether you should use HKDF or “KDF in Counter Mode with HMAC” as a PRF, because SP 800-108’s new revision doesn’t concede this point at all (presumably a relic from the 2009 draft).

This concession was made separately in 2011 with SP 800-56C revision 1 (presumably in response to criticism from the 2010 HKDF paper), and the present inconsistency is somewhat vexing.

(On that note, does anyone actually use the NIST 800-108 KDFs instead of HKDF? If so, why? Please don’t say you need CMAC…)

Bonus Content

These questions were asked after this blog post initially went public, and I thought they were worth adding. If you ask a good question, it may end up being edited in at the end, too.

Art: LvJ

Why Does HKDF use the Salt as the HMAC key in the Extract Step? (via r/crypto)

Broadly speaking, when applying a PRF to two “keys”, you get to decide which one you treat as the “key” in the underlying API.

HMAC’s API is HMACalg(key, message), but how HKDF uses it might as well be HMACalg(key1, key2).

The difference here seems almost arbitrary, but there’s a catch.

HKDF was designed for Diffie-Hellman outputs (before ECDH was the norm), which are generally able to be much larger than the block size of the underlying hash function. 2048-bit DH results fit in 256 bytes, which is 4 times the SHA256 block size.

If you have to make a decision, using the longer input (DH output) as the message is more intuitive for analysis than using it as the key, due to pre-hashing. I’ve discussed the counter-intuitive nature of HMAC’s pre-hashing behavior at length in this post, if you’re interested.

So with ECDH, it literally doesn’t matter which one was used (unless you have a weird mismatch in hash functions and ECC groups; i.e. NIST P-521 with SHA-224).

But before the era of ECDH, it was important to use the salt as the HMAC key in the extract step, since they were necessarily smaller than a DH group element.

Thus, HKDF chose HMACalg(salt, IKM) instead of HMACalg(IKM, salt) for the calculation of PRK in the HKDF-Extract step.

Neil Madden also adds that the reverse would create a chicken-egg situation, but I personally suspect that the pre-hashing would be more harmful to the security analysis than merely supplying a non-uniformly random bit string as an HMAC key in this specific context.

My reason for believing this is, when a salt isn’t supplied, it defaults to a string of 0x00 bytes as long as the output size of the underlying hash function. If the uniform randomness of the salt mattered that much, this wouldn’t be a tolerable condition.

https://soatok.blog/2021/11/17/understanding-hkdf/

#cryptographicHashFunction #cryptography #hashFunction #HMAC #KDF #keyDerivationFunction #securityDefinition #SecurityGuidance

Dhole Moments

2020-12-24 06:16:58

As we look upon the sunset of a remarkably tiresome year, I thought it would be appropriate to talk about cryptographic wear-out.

What is cryptographic wear-out?

It’s the threshold when you’ve used the same key to encrypt so much data that you should probably switch to a new key before you encrypt any more. Otherwise, you might let someone capable of observing all your encrypted data perform interesting attacks that compromise the security of the data you’ve encrypted.

My definitions always aim to be more understandable than pedantically correct.
(Art by Swizz)

The exact value of the threshold varies depending on how exactly you’re encrypting data (n.b. AEAD modes, block ciphers + cipher modes, etc. each have different wear-out thresholds due to their composition).

Let’s take a look at the wear-out limits of the more popular symmetric encryption methods, and calculate those limits ourselves.

Specific Ciphers and Modes

(Art by Khia. Poorly edited by the author.)

Cryptographic Limits for AES-GCM

I’ve written about AES-GCM before (and why I think it sucks).

AES-GCM is a construction that combines AES-CTR with an authenticator called GMAC, whose consumption of nonces looks something like this:

• Calculating H (used in GHASH for all messages encrypted under the same key, regardless of nonce):
  
  • Encrypt(00000000 00000000 00000000 00000000)

  
  

• Calculating J0 (the pre-counter block):
  
  • If the nonce is 96 bits long:
    
    • NNNNNNNN NNNNNNNN NNNNNNNN 00000001 where the N spaces represent the nonce hexits.

    
    

  • Otherwise:
    
    • s = 128 * ceil(len(nonce)/nonce) - len(nonce)
    • J0 = GHASH(H, nonce || zero(s+64) || int2bytes(len(nonce))

    
    

  
  

• Each block of data encrypted uses J0 + block counter (starting at 1) as a CTR nonce.
• J0 is additionally used as the nonce to calculate the final GMAC tag.

AES-GCM is one of the algorithms where it’s easy to separately calculate the safety limits per message (i.e. for a given nonce and key), as well as for all messages under a key.

AES-GCM Single Message Length Limits

In the simplest case (nonce is 96 bits), you end up with the following nonces consumed:

• For each key: 00000000 00000000 00000000 00000000
• For each (nonce, key) pair:
  
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000001 for J0
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000002 for encrypting the first 16 bytes of plaintext
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000003 for the next 16 bytes of plaintext…
  • …
  • NNNNNNNN NNNNNNNN NNNNNNNN FFFFFFFFF for the final 16 bytes of plaintext.

  
  

From here, it’s pretty easy to see that you can encrypt the blocks from 00000002 to FFFFFFFF without overflowing and creating a nonce reuse. This means that each (key, nonce) can be used to encrypt a single message up to blocks of the underlying ciphertext.

Since the block size of AES is 16 bytes, this means the maximum length of a single AES-GCM (key, nonce) pair is bytes (or 68,719,476,480 bytes). This is approximately 68 GB or 64 GiB.

Things get a bit tricker to analyze when the nonce is not 96 bits, since it’s hashed.

The disadvantage of this hashing behavior is that it’s possible for two different nonces to produce overlapping ranges of AES-CTR output, which makes the security analysis very difficult.

However, this hashed output is also hidden from network observers since they do not know the value of H. Without some method of reliably detecting when you have an overlapping range of hidden block counters, you can’t exploit this.

(If you want to live dangerously and motivate cryptanalysis research, mix 96-bit and non-96-bit nonces with the same key in a system that does something valuable.)

Multi-Message AES-GCM Key Wear-Out

Now that we’ve established the maximum length for a single message, how many messages you can safely encrypt under a given AES-GCM key depends entirely on how your nonce is selected.

If you have a reliable counter, which is guaranteed to never repeat, and start it at 0 you can theoretically encrypt messages safely. Hooray!

Hooray!
(Art by Swizz)

You probably don’t have a reliable counter, especially in real-world settings (distributed systems, multi-threaded applications, virtual machines that might be snapshotted and restored, etc.).

Confound you, technical limitations!
(Art by Swizz)

Additionally (thanks to 2adic for the expedient correction), you cannot safely encrypt more than blocks with AES because the keystream blocks–as the output of a block cipher–cannot repeat.

Most systems that cannot guarantee unique incrementing nonces simply generate nonces with a cryptographically secure random number generator. This is a good idea, but no matter how high quality your random number generator is, random functions will produce collisions with a discrete probability.

If you have possible values, you should expect a single collision(with 50% probability) after (or )samples. This is called the birthday bound.

However, 50% of a nonce reuse isn’t exactly a comfortable safety threshold for most systems (especially since nonce reuse will cause AES-GCM to become vulnerable to active attackers). 1 in 4 billion is a much more comfortable safety margin against nonce reuse via collisions than 1 in 2. Fortunately, you can calculate the discrete probability of a birthday collision pretty easily.

If you want to rekey after your collision probability exceeds (for a random nonce between 0 and ), you simply need to re-key after messages.

AES-GCM Safety Limits

• Maximum message length: bytes
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

Not bad, but we can do better.
(Art by Khia.)

Cryptographic Limits for ChaCha20-Poly1305

The IETF version of ChaCha20-Poly1305 uses 96-bit nonces and 32-bit internal counters. A similar analysis follows from AES-GCM’s, with a few notable exceptions.

For starters, the one-time Poly1305 key is derived from the first 32 bytes of the ChaCha20 keystream output (block 0) for a given (nonce, key) pair. There is no equivalent to AES-GCM’s H parameter which is static for each key. (The ChaCha20 encryption begins using block 1.)

Additionally, each block for ChaCha20 is 512 bits, unlike AES’s 128 bits. So the message limit here is a little more forgiving.

Since the block size is 512 bits (or 64 bytes), and only one block is consumed for Poly1305 key derivation, we can calculate a message length limit of , or 274,877,906,880 bytes–nearly 256 GiB for each (nonce, key) pair.

The same rules for handling 96-bit nonces applies as with AES-GCM, so we can carry that value forward.

ChaCha20-Poly1305 Safety Limits

• Maximum message length: bytes
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

A significant improvement, but still practically limited.
(Art by Khia.)

Cryptographic Limits for XChaCha20-Poly1305

XChaCha20-Poly1305 is a variant of XSalsa20-Poly1305 (as used in libsodium) and the IETF’s ChaCha20-Poly1305 construction. It features 192-bit nonces and 32-bit internal counters.

XChaCha20-Poly1305 is instantiated by using HChaCha20 of the key over the first 128 bits of the nonce to produce a subkey, which is used with the remaining nonce bits using the aforementioned ChaCha20-Poly1305.

This doesn’t change the maximum message length, but it does change the number of messages you can safely encrypt (since you’re actually using up to distinct keys).

Thus, even if you manage to repeat the final ChaCha20-Poly1305 nonce, as long as the total nonce differs, each encryptions will be performed with a distinct key (thanks to the HChaCha20 key derivation; see the XSalsa20 paper and IETF RFC draft for details).

UPDATE (2021-04-15): It turns out, my read of the libsodium implementation was erroneous due to endian-ness. The maximum message length for XChaCha20-Poly1305 is blocks, and for AEAD_XChaCha20_Poly1305 is blocks. Each block is 64 bytes, so that changes the maximum message length to about . This doesn’t change the extended-nonce details, just the underlying ChaCha usage.

XChaCha20-Poly1305 Safety Limits

• Maximum message length: bytes (earlier version of this document said )
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

I can see encrypt forever, man.
(Art by Khia.)

Cryptographic Limits for AES-CBC

It’s tempting to compare non-AEAD constructions and block cipher modes such as CBC (Cipher Block Chaining), but they’re totally different monsters.

• AEAD ciphers have a clean delineation between message length limit and the message quantity limit
• CBC and other cipher modes do not have this separation

Every time you encrypt a block with AES-CBC, you are depleting from a universal bucket that affects the birthday bound security of encrypting more messages under that key. (And unlike AES-GCM with long nonces, AES-CBC’s IV is public.)

This is in addition to the operational requirements of AES-CBC (plaintext padding, initialization vectors that never repeat and must be unpredictable, separate message authentication since CBC doesn’t provide integrity and is vulnerable to chosen-ciphertext atacks, etc.).

My canned response to most queries about AES-CBC.
(Art by Khia.)

For this reason, most cryptographers don’t even bother calculating the safety limit for AES-CBC in the same breath as discussing AES-GCM. And they’re right to do so!

If you find yourself using AES-CBC (or AES-CTR, for that matter), you’d best be performing a separate HMAC-SHA256 over the ciphertext (and verifying this HMAC with a secure comparison function before decrypting). Additionally, you should consider using an extended nonce construction to split one-time encryption and authentication keys.

(Art by Riley.)

However, for the sake of completeness, let’s figure out what our practical limits are.

CBC operates on entire blocks of plaintext, whether you need the entire block or not.

On encryption, the output of the previous block is mixed (using XOR) with the current block, then encrypted with the block cipher. For the first block, the IV is used in the place of a “previous” block. (Hence, its requirements to be non-repeating and unpredictable.)

This means you can informally model (IV xor PlaintextBlock) and (PBn xor PBn+1) as a pseudo-random function, before it’s encrypted with the block cipher.

If those words don’t mean anything to you, here’s the kicker: You can use the above discussion about birthday bounds to calculate the upper safety bounds for the total number of blocks encrypted under a single AES key (assuming IVs are generated from a secure random source).

If you’re okay with a 50% probability of a collision, you should re-key after blocks have been encrypted.

https://www.youtube.com/watch?v=v0IsYNDMV7A

If your safety margin is closer to the 1 in 4 billion (as with AES-GCM), you want to rekey after blocks.

However, blocks encrypted doesn’t map neatly to bytes encrypted.

If your plaintext is always an even multiple of 128 bits (or 16 bytes), this allows for up to bytes of plaintext. If you’re using PKCS#7 padding, keep in mind that this will include an entire padding block per message, so your safety margin will deplete a bit faster (depending on how many individual messages you encrypt, and therefore how many padding blocks you need).

On the other extreme (1-byte plaintexts), you’ll only be able to eek encrypted bytes before you should re-key.

Therefore, to stay within the safety margin of AES-CBC, you SHOULD re-key after blocks (including padding) have been encrypted.

Keep in mind: single-byte blocks is still approximately 281 TiB of data (including padding). On the upper end, 15-byte blocks (with 1-byte padding to stay within a block) clocks in at about or about 4.22 PiB of data.

That’s Blocks. What About Bytes?

The actual plaintext byte limit sans padding is a bit fuzzy and context-dependent.

The local extrema occurs if your plaintext is always 16 bytes (and thus requires an extra 16 bytes of padding). Any less, and the padding fits within one block. Any more, and the data😛adding ratio starts to dominate.

Therefore, the worst case scenario with padding is that you take the above safety limit for block counts, and cut it in half. Cutting a number in half means reducing the exponent by 1.

But this still doesn’t eliminate the variance. blocks could be anywhere from to bytes of real plaintext. When in situations like this, we have to assume the worst (n.b. take the most conservative value).

Therefore…

AES-CBC Safety Limits

• Maximum data safely encrypted under a single key with a random nonce: bytes (approximately 141 TiB)

Yet another reason to dislike non-AEAD ciphers.
(Art by Khia.)

Take-Away

Compared to AES-CBC, AES-GCM gives you approximately a million times as much usage out of the same key, for the same threat profile.

ChaCha20-Poly1305 and XChaCha20-Poly1305 provides even greater allowances of encrypting data under the same key. The latter is even safe to use to encrypt arbitrarily large volumes of data under a single key without having to worry about ever practically hitting the birthday bound.

I’m aware that this blog post could have simply been a comparison table and a few footnotes (or even an IETF RFC draft), but I thought it would be more fun to explain how these values are derived from the cipher constructions.

(Art by Khia.)

https://soatok.blog/2020/12/24/cryptographic-wear-out-for-symmetric-encryption/

#AES #AESCBC #AESGCM #birthdayAttack #birthdayBound #cryptography #safetyMargin #SecurityGuidance #symmetricCryptography #symmetricEncryption #wearOut