(With severe apologies to Miles Davis.)

Post-Quantum Cryptography is coming. But in their haste to make headway on algorithm adoption, standards organizations (NIST, IETF) are making a dumb mistake that will almost certainly bite implementations in the future.

Sophie Schmieg wrote about this topic at length and Filippo Valsorda suggested we should all agree to only use Seeds for post-quantum KEMs. You can read their words and come to the same conclusion as what I’ve written here, but I thought this was important enough to write about–if, for no other reason, to make some cryptographer shitposts make more sense to everyone else. (Nobody likes to feel excluded from inside jokes, after all!)

OwO, What’s This?

It’s not at all necessary to understand advanced topics in cryptography to appreciate the current dilemma. In fact, the underlying algorithm really doesn’t matter at the moment. So let’s set aside the technical topics for a moment. We can get back to them in a later section.

Instead, imagine you have some algorithm that does nightmare magic math that cares what color pen you use. We’ll call it Whistle for now, since my fursona is also called a whistling dog sometimes.

Because of the nightmare magic math, you might decide to implement Whistle to accept a large, expanded secret key. At first glance, this isn’t a crazy decision: A pure mathematics description of our algorithm calls for such a monstrosity. These keys are kilobytes in size.

But that can be both inconvenient and unwieldy. So you might want to allow shorter keys to be stored, and then use those to derive the larger, expanded keys.

In cryptography terms, we call the shorter keys used to derive the other secret parameters in a complex algorithm a “seed”.

Ultimately, regardless of what Whistle does, or even in, the fact that you have two ways to implement it, with different kinds of inputs, means they are actually two different algorithms.

func WhistleWithSeed(seed [32]byte, ciphertext []byte) ([]byte, error) {
    expandedKey := ExpandKey(seed)
    return WhistleInternal(expandedKey, ciphertext)
}

func WhistleWithExpanded(expandedKey, ciphertext []byte) ([]byte, error) {
    // Hope this is done in constant-time:
    valid, err := ValidateKey(expandedKey)
    if err != nil {
        return nil, err
    }
    if !valid {
        return nil, errors.New("invalid key")
    }
    return WhistleInternal(expandedKey, ciphertext)
}

Unfortunately, standards organizations decided that these two algorithms are actually the same algorithm.

Whether this is because they never read The Art of Computer Programming by Donald Knuth (and therefore never learned what the definition for an algorithm is), or they’re stretching the definition for the sake of convenience, is difficult to say.

And, sure, there are some convenient reasons to ignore this definition:

• The same underlying algorithm (WhistleInternal in the pseudocode above) gets called either way.
• Whether you chose to store seeds or expanded keys, you’re going to get the same public key out of the other end of key generation.
• Similarly, the actual operation of WhistleInternal (the underlying subroutine) will produce the same set of {correct, incorrect} results for the same inputs.

But the downside is that software that expects one input (a seed or an expanded key), when given the other type of input, may misbehave in a way that attackers find useful.

The Keys You Don’t Play

Imagine you’re transfering a private key from one system (that uses a cryptography library which expects expanded keys) to another (that expects seeds).

Note: You generally don’t do such a thing. Private keys should never leave the device they’re generated on for most applications. However, there are corner cases where you need to do this.

The encoding rules for storing private keys to disk are generally defined in PKCS8 (and use heavily in ASN.1). Each algorithm is supposed to have its own OID (object identifier), which is never reused for different algorithms.

In order to shoehorn two different algorithms as the same algorithm, you generally have to encode these keys using something like ASN.1’s CHOICE. Unfortunately, NULL is always a valid CHOICE.

As Sophie noted in How not to format a private key:

It is easy to imagine one part of a system writing one field, and the other part of the system reading the other. In particular, since the seed is unrecoverable after the fact, a system that only has the semi-expanded key available might, instead of writing NULL in the seed field, write “NULL”, which the other system then prefers over the semi-expanded key that contains the actual key material, both compromising the system (as “NULL” is very brute-forcable) and potentially losing the actual private key forever.

And that’s the danger inherent in these standards organizations’ insistence on supporting both seeds and semi-expanded private keys.

What Should We Do?

As Filippo suggests, we should all agree to only use seeds.

He specifically said that about ML-KEM, but I think we should apply it to all post-quantum algorithms (i.e., ML-DSA as well, at the very least).

The semi-expanded key format should only be tolerable as a runtime artifact of expanding the key from a seed, and the seed is the only thing that anyone should ever write to disk.

Standards organizations will continue insist on supporting use cases where people store and pass around semi-expanded private keys, rather than seeds, and cite the performance hit of deriving the semi-expanded key from a seed as a reason to tolerate such behavior.

But standards organizations cannot force the rest of us to support these features in our actual software implementations of the standards. So let’s opt to never do that, where reasonably practical.

Sophie suggested that seeds and semi-expanded keys should be two different OIDS (in PKCS8 parlance). That’s a good compromise for systems that, for whatever stupid reason, can’t commit to only permitting seeds as the private key format for post-quantum cryptography.

If you’re writing software the expects a seed and you get a semi-expanded private key, that should return an error to the user. Even if the seed is included somewhere, don’t ever be helpful by failing open. Coerce the behavior you want to see in the world.

If you’re, instead, writing software that expects a semi-expanded private key? Regardless of what the user provides you, you’re doing it wrong and should rethink your life decisions.