Crate hpke_kem

Expand description

Key Encapsulation Mechanism (KEM)

💡 This is a hacspec representation of the HPKE RFC. The text is mostly verbatim from the RFC with changes where required. It demonstrates the possibilities of hacspec for specifications.

GenerateKeyPair(): Randomized algorithm to generate a key pair (skX, pkX).
DeriveKeyPair(ikm): Deterministic algorithm to derive a key pair (skX, pkX) from the byte string ikm, where ikm SHOULD have at least Nsk bytes of entropy.
SerializePublicKey(pkX): Produce a byte string of length Npk encoding the public key pkX.
DeserializePublicKey(pkXm): Parse a byte string of length Npk to recover a public key. This function can raise a DeserializeError error upon pkXm deserialization failure.
Encap(pkR): Randomized algorithm to generate an ephemeral, fixed-length symmetric key (the KEM shared secret) and a fixed-length encapsulation of that key that can be decapsulated by the holder of the private key corresponding to pkR. This function can raise an EncapError on encapsulation failure.
Decap(enc, skR): Deterministic algorithm using the private key skR to recover the ephemeral symmetric key (the KEM shared secret) from its encapsulated representation enc. This function can raise a DecapError on decapsulation failure.
AuthEncap(pkR, skS) (optional): Same as Encap(), and the outputs encode an assurance that the KEM shared secret was generated by the holder of the private key skS.
AuthDecap(enc, skR, pkS) (optional): Same as Decap(), and the recipient is assured that the KEM shared secret was generated by the holder of the private key skS.
Nsecret: The length in bytes of a KEM shared secret produced by this KEM.
Nenc: The length in bytes of an encapsulated key produced by this KEM.
Npk: The length in bytes of an encoded public key for this KEM.
Nsk: The length in bytes of an encoded private key for this KEM.

Beyond the above, a KEM MAY also expose the following functions, whose behavior is detailed below:

SerializePrivateKey(skX): Produce a byte string of length Nsk encoding the private key skX.
DeserializePrivateKey(skXm): Parse a byte string of length Nsk to recover a private key. This function can raise a DeserializeError error upon skXm deserialization failure.

SerializePublicKey and DeserializePublicKey

For P-256, P-384 and P-521, the SerializePublicKey() function of the KEM performs the uncompressed Elliptic-Curve-Point-to-Octet-String conversion according to SECG. DeserializePublicKey() performs the uncompressed Octet-String-to-Elliptic-Curve-Point conversion.

For X25519 and X448, the SerializePublicKey() and DeserializePublicKey() functions are the identity function, since these curves already use fixed-length byte strings for public keys.

Some deserialized public keys MUST be validated before they can be used. See Validation for specifics.

SerializePrivateKey and DeserializePrivateKey

As per SECG, P-256, P-384, and P-521 private keys are field elements in the scalar field of the curve being used. For this section, and for DeriveKeyPair(), it is assumed that implementers of ECDH over these curves use an integer representation of private keys that is compatible with the OS2IP() function.

For P-256, P-384 and P-521, the SerializePrivateKey() function of the KEM performs the Field-Element-to-Octet-String conversion according to SECG. If the private key is an integer outside the range [0, order-1], where order is the order of the curve being used, the private key MUST be reduced to its representative in [0, order-1] before being serialized. DeserializePrivateKey() performs the Octet-String-to-Field-Element conversion according to SECG.

For X25519 and X448, private keys are identical to their byte string representation, so little processing has to be done. The SerializePrivateKey() function MUST clamp its output and DeserializePrivateKey() MUST clamp its input, where clamping refers to the bitwise operations performed on k in the decodeScalar25519() and decodeScalar448() functions defined in section 5 of RFC7748.

To catch invalid keys early on, implementers of DHKEMs SHOULD check that deserialized private keys are not equivalent to 0 (mod order), where order is the order of the DH group. Note that this property is trivially true for X25519 and X448 groups, since clamped values can never be 0 (mod order).

DeriveKeyPair

See DeriveKeyPair() for details.

DH-Based KEM

Suppose we are given a KDF, and a Diffie-Hellman group providing the following operations:

DH(skX, pkY): Perform a non-interactive Diffie-Hellman exchange using the private key skX and public key pkY to produce a Diffie-Hellman shared secret of length Ndh. This function can raise a ValidationError as described in validation.
Ndh: The length in bytes of a Diffie-Hellman shared secret produced by DH().
Nsk: The length in bytes of a Diffie-Hellman private key.

Then we can construct a KEM that implements the KEM interface called DHKEM(Group, KDF) in the following way, where Group denotes the Diffie-Hellman group and KDF the KDF. The function parameters pkR and pkS are deserialized public keys, and enc is a serialized public key. Since encapsulated keys are Diffie-Hellman public keys in this KEM algorithm, we use SerializePublicKey() and DeserializePublicKey() to encode and decode them, respectively. Npk equals Nenc. GenerateKeyPair() produces a key pair for the Diffie-Hellman group in use.

The suite_id value used within LabeledExtract and LabeledExpand is defined as follows, where kem_id is defined in KEM:

suite_id = concat("KEM", I2OSP(kem_id, 2))

The KDF used in DHKEM can be equal to or different from the KDF used in the remainder of HPKE, depending on the chosen variant. Implementations MUST make sure to use the constants (Nh) and function calls (LabeledExtract, LabeledExpand) of the appropriate KDF when implementing DHKEM. See kdf for a comment on the choice of a KDF for the remainder of HPKE, and the rationale of the labels.

For the variants of DHKEM defined in this document, the size Nsecret of the KEM shared secret is equal to the output length of the hash function underlying the KDF. For P-256, P-384 and P-521, the size Ndh of the Diffie-Hellman shared secret is equal to 32, 48, and 66, respectively, corresponding to the x-coordinate of the resulting elliptic curve point IEEE1363. For X25519 and X448, the size Ndh of is equal to 32 and 56, respectively (see RFC7748, Section 5).

It is important to note that the AuthEncap() and AuthDecap() functions of the DHKEM variants defined in this document are vulnerable to key-compromise impersonation (KCI). This means the assurance that the KEM shared secret was generated by the holder of the private key skS does not hold if the recipient private key skR is compromised.

Senders and recipients MUST validate KEM inputs and outputs as described in KEM.

Validation of Inputs and Outputs

The following public keys are subject to validation if the group requires public key validation: the sender MUST validate the recipient’s public key pkR; the recipient MUST validate the ephemeral public key pkE; in authenticated modes, the recipient MUST validate the sender’s static public key pkS. Validation failure yields a ValidationError.

For P-256, P-384 and P-521, senders and recipients MUST perform partial public-key validation on all public key inputs, as defined in section 5.6.2.3.4 of NIST SP 800-56A. This includes checking that the coordinates are in the correct range, that the point is on the curve, and that the point is not the point at infinity. Additionally, senders and recipients MUST ensure the Diffie-Hellman shared secret is not the point at infinity.

For X25519 and X448, public keys and Diffie-Hellman outputs MUST be validated as described in RFC7748. In particular, recipients MUST check whether the Diffie-Hellman shared secret is the all-zero value and abort if so.

Future KEMs

KEM Security lists security requirements on a KEM used within HPKE.

The AuthEncap() and AuthDecap() functions are OPTIONAL. If a KEM algorithm does not provide them, only the Base and PSK modes of HPKE are supported. Future specifications which define new KEMs MUST indicate whether or not Auth and AuthPSK modes are supported.

A KEM algorithm may support different encoding algorithms, with different output lengths, for KEM public keys. Such KEM algorithms MUST specify only one encoding algorithm whose output length is Npk.

Security Requirements on a KEM used within HPKE

A KEM used within HPKE MUST allow HPKE to satisfy its desired security properties described in its security properties section.

In particular, the KEM shared secret MUST be a uniformly random byte string of length Nsecret. This means, for instance, that it would not be sufficient if the KEM shared secret is only uniformly random as an element of some set prior to its encoding as byte string.

Encap/Decap Interface

As mentioned in [sec-considerations], CS01 provides some indications that if the KEM’s Encap()/Decap() interface (which is used in the Base and PSK modes), is IND-CCA2-secure, HPKE is able to satisfy its desired security properties. An appropriate definition of IND-CCA2-security for KEMs can be found in CS01 and BHK09.

AuthEncap/AuthDecap Interface

The analysis of HPKE’s Auth mode single-shot encryption API in ABHKLR20 provides composition theorems that guarantee that HPKE’s Auth mode achieves its desired security properties if the KEM’s AuthEncap()/AuthDecap() interface satisfies multi-user Outsider-CCA, Outsider-Auth, and Insider-CCA security as defined in the same paper.

Intuitively, Outsider-CCA security formalizes confidentiality, and Outsider-Auth security formalizes authentication of the KEM shared secret in case none of the sender or recipient private keys are compromised. Insider-CCA security formalizes confidentiality of the KEM shared secret in case the sender private key is known or chosen by the adversary. (If the recipient private key is known or chosen by the adversary, confidentiality is trivially broken, because then the adversary knows all secrets on the recipient’s side).

An Insider-Auth security notion would formalize authentication of the KEM shared secret in case the recipient private key is known or chosen by the adversary. (If the sender private key is known or chosen by the adversary, it can create KEM ciphertexts in the name of the sender). Because of the generic attack on an analogous Insider-Auth security notion of HPKE, a definition of Insider-Auth security for KEMs used within HPKE is not useful.

KEM Key Reuse

An ikm input to DeriveKeyPair() MUST NOT be reused elsewhere, in particular not with DeriveKeyPair() of a different KEM.

The randomness used in Encap() and AuthEncap() to generate the KEM shared secret or its encapsulation MUST NOT be reused elsewhere.

As a sender or recipient KEM key pair works with all modes, it can be used with multiple modes in parallel. HPKE is constructed to be secure in such settings due to domain separation using the suite_id variable. However, there is no formal proof of security at the time of writing for using multiple modes in parallel; HPKEAnalysis and ABHKLR20 only analyze isolated modes.

Enums

KEM

Key Encapsulation Mechanisms (KEMs)

Functions

AuthDecap

AuthEncap

DH

Perform a non-interactive Diffie-Hellman exchange using the private key skX and public key pkY to produce a Diffie-Hellman shared secret of length Ndh. This function can raise a ValidationError as described in validation.

Decap

DeriveKeyPair

DeriveKeyPairX

For X25519 and X448, the DeriveKeyPair() function applies a KDF to the input:

DeserializePublicKey

Parse a byte string of length Npk to recover a public key. This function can raise a DeserializeError error upon pkXm deserialization failure.

Encap

GenerateKeyPair

Randomized algorithm to generate a key pair (skX, pkX).

Ndh

The length in bytes of a Diffie-Hellman shared secret produced by DH().

Nenc