crypto/mlkem: new package

[FiloSottile]

ML-KEM (FIPS 203, formerly Kyber) is a postquantum (#64537) key exchange method that was recently standardized and is being deployed across the industry. We already have an implementation in the Go tree as part of #67061.

I propose we expose a new package implementing ML-KEM-768 and ML-KEM-1024. Ideally we'd implement only ML-KEM-768, because it's what's being deployed in most settings and because playing the "security levels" game is an obsolete concept, but alas CNSA 2.0 requires ML-KEM-1024 across the board. We have seen no deployments of ML-KEM-512, so we are leaving that out at least for now. This happens to match what BoringSSL implemented. We also only support seeds as the decapsulation key format. This should match the direction the IETF is taking.

The proposed API uses separate types for -768 and -1024 to avoid making the -768 values unnecessarily large. I'm not a big fan of the numeric suffixes, and I'm especially unhappy that 1024 sorts before 768 in godoc, but couldn't find better names.

We are not proposing a KEM interface yet, but note that the methods should be general enough to allow one in the future.

const (
	SharedKeySize = 32
	SeedSize      = 64
)

const (
	CiphertextSize768       = 1088
	EncapsulationKeySize768 = 1184
)
    ML-KEM-768 parameters.

type DecapsulationKey768 struct {
	// Has unexported fields.
}
    A DecapsulationKey768 is the secret key used to decapsulate a shared key
    from a ciphertext. It includes various precomputed values.

func GenerateKey768() (*DecapsulationKey768, error)
    GenerateKey768 generates a new decapsulation key, drawing random bytes from
    crypto/rand. The decapsulation key must be kept secret.

func NewDecapsulationKey768(seed []byte) (*DecapsulationKey768, error)
    NewDecapsulationKey768 parses a decapsulation key from a 64-byte seed in the
    "d || z" form. The seed must be uniformly random.

func (dk *DecapsulationKey768) Bytes() []byte
    Bytes returns the decapsulation key as a 64-byte seed in the "d || z" form.

    The decapsulation key must be kept secret.

func (dk *DecapsulationKey768) Decapsulate(ciphertext []byte) (sharedKey []byte, err error)
    Decapsulate generates a shared key from a ciphertext and a decapsulation
    key. If the ciphertext is not valid, Decapsulate returns an error.

    The shared key must be kept secret.

func (dk *DecapsulationKey768) EncapsulationKey() *EncapsulationKey768
    EncapsulationKey returns the public encapsulation key necessary to produce
    ciphertexts.

type EncapsulationKey768 struct {
	// Has unexported fields.
}
    An EncapsulationKey768 is the public key used to produce ciphertexts to be
    decapsulated by the corresponding DecapsulationKey768.

func NewEncapsulationKey768(encapsulationKey []byte) (*EncapsulationKey768, error)
    NewEncapsulationKey768 parses an encapsulation key from its encoded form. If
    the encapsulation key is not valid, NewEncapsulationKey768 returns an error.

func (ek *EncapsulationKey768) Bytes() []byte
    Bytes returns the encapsulation key as a byte slice.

func (ek *EncapsulationKey768) Encapsulate() (ciphertext, sharedKey []byte)
    Encapsulate generates a shared key and an associated ciphertext from an
    encapsulation key, drawing random bytes from crypto/rand.

    The shared key must be kept secret.

const (
	CiphertextSize1024       = 1568
	EncapsulationKeySize1024 = 1568
)
    ML-KEM-1024 parameters.

type DecapsulationKey1024 struct {
	// Has unexported fields.
}

func GenerateKey1024() (*DecapsulationKey1024, error)
func NewDecapsulationKey1024(seed []byte) (*DecapsulationKey1024, error)
func (dk *DecapsulationKey1024) Bytes() []byte
func (dk *DecapsulationKey1024) Decapsulate(ciphertext []byte) (sharedKey []byte, err error)
func (dk *DecapsulationKey1024) EncapsulationKey() *EncapsulationKey1024

type EncapsulationKey1024 struct {
	// Has unexported fields.
}

func NewEncapsulationKey1024(encapsulationKey []byte) (*EncapsulationKey1024, error)
func (ek *EncapsulationKey1024) Bytes() []byte
func (ek *EncapsulationKey1024) Encapsulate() (ciphertext, sharedKey []byte)

[gabyhelp]

Related Issues and Documentation

• crypto/internal/mlkem768: update to final FIPS 203

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[mateusz834]

@FiloSottile Does GenerateKey768 need an error return? CL 621979

[FiloSottile]

@FiloSottile Does GenerateKey768 need an error return? CL 621979

Maybe not, but I have rarely regretted adding an error, and very often regretted not adding one.

I convinced myself not to return an error from Encapsulate() because it takes no inputs so any errors can be returned at NewEncapsulationKey time.

[aclements]

I'm especially unhappy that 1024 sorts before 768 in godoc, but couldn't find better names.

What about having two separate packages with the same API names in both? E.g., crypto/mlkem768 and crypto/mlkem1024?

func (dk *DecapsulationKey768) EncapsulationKey() *EncapsulationKey768

@rolandshoemaker mentioned that we may want to add an interface in the future to wrap these, but the fact that this method returns a concrete type would interfere with that. (Maybe we could use an interface type parameterized over the encapsulation key type, but it's not clear that such an interface would be any more useful than the concrete types.)

[aclements]

we may want to add an interface in the future to wrap these

Another option would be that these types don't directly implement any interface, but that they have some method that returns an interface version implemented by some unexported type.

[FiloSottile]

What about having two separate packages with the same API names in both? E.g., crypto/mlkem768 and crypto/mlkem1024?

Not enthusiastic about it, it makes it harder to reuse code across them, and they share quite a bit. Also the only precedent is x/crypto/blake2b and x/crypto/blake2s which differ by more than key size, but still always felt a bit confusing to me.

Another option would be that these types don't directly implement any interface, but that they have some method that returns an interface version implemented by some unexported type.

I like that! It might also be a solution for #69982 and #61477 (comment), where we were wondering how to make a concrete sha3 type easy to use with hmac and hkdf which take func() hash.Hash.

[mateusz834]

Another option would be that these types don't directly implement any interface, but that they have some method that returns an interface version implemented by some unexported type.

Returning an unexported type (inside an interface) is not always great, especially seeing the recent move out of these in crypto proposals (#69982, #61477 (comment))

[FiloSottile]

@mateusz834 what I think @aclements is suggesting is that once we have a crypto.KEM interface, we can add a (*DecapsulationKey768).KEM() crypto.KEM method which wraps an unexported type. I think that is almost the best of both worlds: whoever needs the interface can opt-in to it, but we can still add methods to the original implementation, which is the main value of concrete types. Any performance overhead (these days kinda negated by devirtualization) is also avoided in the default case. The one remaining downside is that the interface can't be type-asserted.

[mateusz834]

@FiloSottile I might be missing some part, but AFAICT this can be made differently and simpler.

func (dk *DecapsulationKey768) EncapsulationKey() *EncapsulationKey768
func (dk *DecapsulationKey768) KEM() crypto.KEM { return dk.EncapsulationKey() }
var _ crypto.KEM = &EncapsulationKey768{} // *EncapsulationKey768 implements crypto.KEM.

Same as crypto/ecdh https://pkg.go.dev/crypto/ecdh#PrivateKey.Public, https://pkg.go.dev/crypto/ecdh#PrivateKey.PublicKey

[aclements]

I like that! It might also be a solution for #69982

I'm not sure I see how this solves the issue with func NewXXX() *SHA3 vs func NewXXX() hash.Hash because these are functions, not types.

I might be missing some part, but AFAICT this can be made differently and simpler.

I guess it depends on what the interfaces need to capture. You're right that we could have one interface for DecapsulationKey* that doesn't cover the EncapsulationKey method, but includes some other more generic method that returns the EncapsulationKey* as a second interface. If that works, I agree that's probably simpler, even though it has some "duplication" in that method.

[FiloSottile]

Sounds like we have enough options to retrofit interfaces in the future, once we know better what we want to use them for.

I'm not sure I see how this solves the issue with func NewXXX() *SHA3 vs func NewXXX() hash.Hash because these are functions, not types.

Fair, there the analogous answer would be to just add func NewXXXHash() hash.Hash if we need to.

[aclements]

The proposed API uses separate types for -768 and -1024 to avoid making the -768 values unnecessarily large.

Another possible option: would it work to have EncapsulationKey and DecapsulationKey both be parameterized over some type T, where there's a T for 768 and a T for 1024? The public methods on EncapsulationKey and DecapsulationKey could dispatch to unexported methods on T if necessary. I'm not sure if this would be a problem for the (*DecapsulationKey).EncapsulationKey method.

[aclements]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.

[gopherbot]

Change https://go.dev/cl/621983 mentions this issue: crypto/internal/fips/mlkem: implement ML-KEM-1024

[rsc]

FWIW the generics seem like overkill to me. These are typically specialized anyway, so that they can have optimized implementations. It seems okay to me to have the different sizes.

[aclements]

Fair enough. We at least have a path forward for creating common interfaces for these if the need arises.

[aclements]

Based on the discussion above, this proposal seems like a likely accept.

The proposal is to add a crypto/mlkem package with the API given in #70122 (comment).

[gopherbot]

Change https://go.dev/cl/630240 mentions this issue: crypto/mlkem: init package

[aclements]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.

The proposal is to add a crypto/mlkem package with the API given in #70122 (comment).

[FiloSottile]

Done in CL 630240.

[tmthrgd]

The order of return values in Encapsulate() (ciphertext, sharedKey []byte) is flipped compared to what is specified in FIPS 203.

As specified, the expected order of return values is shared secret key and then ciphertext:

Algorithm 20 ML-KEM.Encaps(ek)
Uses the encapsulation key to generate a shared secret key and an associated ciphertext.
Checked input: encapsulation key ek ∈ 𝔹384𝑘+32 .
Output: shared secret key 𝐾 ∈ 𝔹32 .
Output: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢𝑘+𝑑𝑣).
1: 𝑚 ←$− 𝔹32					▷ 𝑚 is 32 random bytes (see Section 3.3)
2: if 𝑚 == NULL then
3: 	return ⊥				▷ return an error indication if random bit generation failed
4: end if
5: (𝐾, 𝑐) ← ML-KEM.Encaps_internal(ek, 𝑚)	▷ run internal encapsulation algorithm
6: return (𝐾, 𝑐)

It seems like the original pre-NIST Kyber spec (from round 3) did have the ciphertext first:

Algorithm 8 Kyber.CCAKEM.Enc(pk )
Input: Public key pk ∈ B 12·k·n/8+32
Output: Ciphertext c ∈ B du ·k·n/8+dv ·n/8
Output: Shared key K ∈ B ∗
1: m ← B 32
2: m ← H(m)
3: (K̄, r) := G(m||H(pk))
4: c := Kyber.CPAPKE.Enc(pk , m, r)
5: K := KDF(K̄||H(c))
6: return (c, K)

Because both return types are []byte (so you don't get the type system to help you tell them apart), this seems like a potentially dangerous footgun and unfortunate divergence from the published spec. I also imagine any potential crypto.KEM API is going to want secret first. I think the order should be swapped to match FIPS 203 before go1.24 is released.

For reference, RFC 9180 (HPKE) also specifies it's KEMs to return secret first.

(I'm not sure if this deserves a new issue or not).

[tmthrgd]

@FiloSottile @rsc @aclements Just want to make sure my comment above (#70122 (comment)) doesn't get missed. Leaving our return value ordering different from the actual spec feels like a real mistake to me.

[FiloSottile]

@tmthrgd hmm, now I wonder where I got this ordering from, since I did the implementation from the NIST ipd.

Anyway, comments on closed issues fall off the radar, can you open a new issue and we'll flag it release-blocker?