Creating a hybrid post quantum key exchange scheme

• Authentication of the public keys used in the scheme is the responsibility of the host.
  • ML-KEM or CRYSTALS-Kyber keys do not participate in public key infrastructures (PKIs) at this time. The MLKEM-cert-A certificate for an ML-KEM or CRYSTALS-Kyber public key identified below is in recognition that certificate formats will be needed for the authentication part of a protocol.
  • For the ECC public keys, the CCA internal PKI may be used for authentication if the trust anchor has been installed to the cryptographic coprocessor.
• A full protocol should include a Key Check Value calculated over the shared key created by Bob so that Alice can verify creation of an agreed shared key.

The hybrid post quantum key exchange scheme involves two participants: Alice and Bob, and also involves two CCA services: CSNDPKE and CSNDEDH.

Step 1: Alice

1. Alice creates these keys:
   • MLKEM-priv-A, MLKEM-pub-A: ML-KEM or CRYSTALS-Kyber (1024) key pair
   • EC-priv-A, EC-pub-A: ECC key pair for key agreement
   • MLKEM-cert-A, EC-cert-A: authenticated forms of MLKEM-pub-A and EC-pub-A

   Remember: In CCA, keys are retained within a structure called a key token. A CCA key token contains the key value together with key attributes. It is protected by the CCA master key.

2. Alice sends to Bob: MLKEM-cert-A and EC-cert-A.

Step 2: Bob

1. Bob receives and validates MLKEM-cert-A and EC-cert-A.
2. After validation, Bob creates these keys:
   • AES-ciph-B: AES-CIPHER key in a CCA key token.

     Note: AES-ciph-B should be as strong as the shared key to be derived and should allow encryption and decryption since it is used on the same node.

   • EC-priv-B, EC-pub-B: ECC key pair for key agreement
   • EC-cert-B: authenticated form of EC-pub-B.
   • MLKEM-pub-A: CCA public key token, with public key pulled from MLKEM-cert-A.
3. Bob creates the shared key derivation input using CSNDPKE. Bob calls the CSNDPKE service with the RANDOM keyword, AES-ciph-B, MLKEM-pub-A, and the AES encryption initialization vector (IV).

   CSNDPKE performs the following:

   • generates a random 32B value: rand-32
   • AES-CBC encrypts rand-32 using key AES-ciph-B and the AES encryption IV, returning [AES-ciph-B(rand-32)] in the keyvalue parameter.
   • ML-KEM encrypts rand-32 with MLKEM-pub-A returning [MLKEM-pub-A(rand-32)] in the PKA_enciphered_keyvalue parameter.
4. Bob completes the shared key derivation, using CSNDEDH. Bob calls CSNDEDH with a derivation keyword, desired key length, [AES-ciph-B(rand-32)], AES-ciph-B, AES encryption IV, EC-priv-B, EC-cert-A, output skeleton token.

   CSNDEDH performs the following:

   • decrypts rand-32 using the key AES-ciph-B and the AES encryption IV,
   • uses EC-priv-B and EC-cert-A with ECDH to generate the Z value,
   • passes Z and rand-32 to the key derivation function indicated by the derivation keyword. rand-32 is the salt or OtherData. The shared key of the requested length is derived.
   • places the shared key in the provided output skeleton token, and encrypts the key value.
   • returns the final CCA shared key token.
5. Bob stores the shared key token.
6. Bob sends to Alice: EC-cert-B, [MLKEM-pub-A(rand-32)]

Step 3: Alice

1. Alice receives and validates EC-cert-B, [MLKEM-pub-A(rand-32)] .
2. Alice completes the shared key derivation, using CSNDEDH. Alice calls CSNDEDH with a derivation keyword, desired key length, [MLKEM-pub-A(rand-32)], MLKEM-priv-A, EC-priv-A, EC-cert-B, output skeleton token.

   CSNDEDH performs the following:

   • decrypts rand-32 using MLKEM-priv-A,
   • uses EC-priv-A and EC-cert-B with ECDH to generate the Z value,
   • passes Z and rand-32 to the key derivation function indicated by the derivation keyword,rand-32 is the salt or OtherData. The shared key of the requested length is derived.
   • places the shared key in the output skeleton token provided, encrypts the key value,
   • returns the final CCA shared key token.
3. Alice stores the shared key token.

The shared key is now established for both Alice and Bob.

The role of CSNDPKE

The role of CSNDPKE in this scheme is to create the rand-32 derivation input and return rand-32 in 2 forms:

1. encrypted by Bob's AES cipher key, AES-ciph-B
2. encrypted by Alice's CRYSTALS-Kyber or ML-KEM public key, Kyb-pub-A.

This is accomplished by calls to CSNDPKE as follows:

a) inputs:

• RANDOM rule-array keyword.
• AES-ciph-B: AES-cipher key token for Bob, which should be as strong as the derived shared-key.
• Kyb-pub-A or Encap-pub-A as PKA_key_identifier: CRYSTALS-Kyber or ML-KEM key for Alice.

b) outputs:

• keyvalue parameter: [AES-ciph-B(rand-32)]
• PKA_enciphered_keyvalue parameter: [Encap-pub-A(rand-32)]

The role of CSNDEDH

The role of CSNDEDH in this scheme is to complete the shared-key derivation for Alice or Bob and return the shared-key in a CCA key token.

For DERIV01 and DERIV02, there is an identical change to the key derivation in the CSNDEDH service: NIST SP 800-56C Rev 2 has defined Z’ = Z || T where T is a hybrid addition. The decrypted hybrid_ciphertext is concatenated to the end of the normal Z in the CSNDEDH concatenation string. This is accomplished by calls to CSNDEDH as follows:

Bob's call to CSNDEDH

a) inputs:

• derivation keyword
• desired key length
• [AES-ciph-B(rand-32)]: output from CSNDPKE, random 32 byte value encrypted by AES-ciph-B
• AES-ciph-B : AES-cipher key CCA token for Bob
• EC-priv-B: Bob's private ECC key
• EC-cert-A: Alice's public key
• AES or DES skeleton token

b) output:

• CCA shared-key token

Alice's call to CSNDEDH

a) inputs:

• derivation keyword
• desired key length
• [MLKEM-pub-A(rand-32)]: output from CSNDPKE, random 32 byte value encrypted by MLKEM-pub-A
• MLKEM-priv-A: ML-KEM or CRYSTALS-Kyber private key CCA token for Alice
• EC-priv-A: Alice's private ECC key
• EC-cert-B: Bob's public key
• AES or DES skeleton token

b) outputs:

• CCA shared-key token