# AWS-LC KEM design ## Key Encapsulation Mechanism (KEM) The purpose of a KEM is to establish a shared secret between two parties. There are three main functionalities defined for a KEM: key generation, encapsulation, decapsulation. The protocol works in three steps: ``` 1. Alice generates her key pair (public_key, secret_key). Sends public_key to Bob. 2. Bob generates a shared secret and encapsulates it using Alice's public key. This produces a ciphertext. Sends ciphertext to Alice. 3. Alice decapsulates the ciphertext with her key pair and obtains the shared secret. Alice's and Bob's shared secrets are the same if the protocol succeeded. ``` The KEM design in AWS-LC is generic and not specific to any particular KEM. The primary use-case for the API are the post-quantum cryptographic algorithms that were specified and evaluated in NIST's Post-Quantum Crypto Standardization Project ([link](https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization)). ## The public KEM API **Core functions.** To use a KEM, you have access to three core functions: key generation, encapsulation, decapsulation. Following the general design in AWS-LC, these three functions are offered in the form of standard AWS-LC EVP APIs: ``` // Generates a (public, private) key pair. EVP_PKEY_keygen(ctx, &pkey); // KEM Encapsulation - generates a shared secret and the corresponding ciphertext. EVP_PKEY_encapsulate(ctx, ciphertext, &ciphertext_len, shared_secret, &shared_secret_len); // KEM Decapsulation - decapsulates given ciphertext to recover the shared secret. EVP_PKEY_decapsulate(ctx, shared_secret, &shared_secret_len, ciphertext, ciphertext_len); ``` The `ctx` variable above is a pointer to a “context” object of type `EVP_PKEY_CTX`. The `pkey` variable listed as an argument of `EVP_PKEY_keygen` function is a pointer to an object of type `EVP_PKEY`. The `ciphertext` and `shared_secret` are byte arrays of length `ciphertext_len` and `shared_secret_len`, respectively. **The context.** How to create the context? Depending on the use case, this can be done in two ways: ``` 1. EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new_id(EVP_PKEY_KEM, NULL); EVP_PKEY_CTX_kem_set_params(ctx, NID_KYBER512_R3); ``` This creates a fresh context of type `EVP_PKEY_KEM` and sets the specific KEM parameters (Kyber512 in this example). The context is now ready for key generation (`EVP_PKEY_keygen`). However, the context created in this way doesn’t have an associated key (`EVP_PKEY`), so obviously, we can’t encapsulate/decapsulate with it. Therefore, this is useful for key generation only, i.e. before we have a key. The second way to create a context is with an already existing key (`EVP_PKEY`): ``` 2. EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new(pkey, NULL); ``` This creates a fresh context of type `EVP_PKEY_KEM`, sets the specific KEM parameters defined in the `pkey` object itself, and associates `pkey` to the context. The context is now ready to encapsulate/decapsulate because it contains the encapsulation/decapsulation key. The key is usually either generated by the caller via `EVP_PKEY_keygen`, or received from another party as a raw byte array of the public key, in which case an `EVP_PKEY` is created as shown below. **EVP_PKEY from/to raw data.** If you need to store/load the key-pair (`public_key, secret_key`) to/from memory or to transmit the public key as part of the protocol, you can retrieve the raw keys by calling the following methods: ``` 1. Create EVP_PKEY object from raw data: EVP_PKEY *EVP_PKEY_kem_new_raw_key(int nid, const uint8_t *in_public, size_t len_public, const uint8_t *in_secret, size_t len_secret); EVP_PKEY *EVP_PKEY_kem_new_raw_public_key(int nid, const uint8_t *in, size_t len); EVP_PKEY *EVP_PKEY_kem_new_raw_secret_key(int nid, const uint8_t *in, size_t len); ``` and ``` 2. Extract raw data from EVP_PKEY object: OPENSSL_EXPORT int EVP_PKEY_get_raw_private_key(const EVP_PKEY *pkey, uint8_t *out, size_t *out_len); OPENSSL_EXPORT int EVP_PKEY_get_raw_public_key(const EVP_PKEY *pkey, uint8_t *out, size_t *out_len); ``` **KEM parameters size.** KEM specific parameter sizes can be retrieved by calling the above APIs with `NULL` out pointers. For example, calling: ``` EVP_PKEY_encapsulate(ctx, NULL, &ciphertext_len, NULL, &shared_secret_len); ``` will store the size of the ciphertext and the shared secret (of the KEM specified in `ctx`) in `ciphertext_len` and `shared_secret_len`, respectively. ## Full example Simulation of one KEM protocol execution using Kyber512: ``` ALICE | BOB // START Alice and Bob have agreed which KEM to use (Kyber512 in this case) // Generate a (public, secret) key pair for the desired KEM. int generate_key_pair(/* OUT */ EVP_PKEY **key, /* IN */ int kem_nid) { EVP_PKEY_CTX *ctx = NULL; // Create the contex. ctx = EVP_PKEY_CTX_new_id(EVP_PKEY_KEM, NULL); if (!ctx || !EVP_PKEY_CTX_kem_set_params(ctx, kem_nid) || !EVP_PKEY_keygen_init(ctx) || !EVP_PKEY_keygen(ctx, key)) { EVP_PKEY_free(*key); EVP_PKEY_CTX_free(ctx); return FAIL; } // Note: a single context can be used to generate many keys. EVP_PKEY_CTX_free(ctx); return SUCCESS; } int get_raw_public_key(/* IN */ EVP_PKEY *key, /* OUT */ uint8_t **pub_key, /* OUT */ size_t *pub_key_len) { // We call the function with NULL as the |out| argument // to get the required buffer length. if (!EVP_PKEY_get_raw_public_key(key, NULL, pub_key_len)) { *pub_key_len = 0; return FAIL; } // Allocate memory for the output buffer. *pub_key = (uint8_t*) OPENSSL_malloc(*pub_key_len); if (pub_key == NULL) { *pub_key_len = 0; return FAIL; } // Get the raw public key in the output buffer. if (!EVP_PKEY_get_raw_public_key(key, *pub_key, pub_key_len)) { OPENSSL_free(*pub_key); *pub_key_len = 0; return FAIL; } return SUCCESS; } // With the two helper functions above you can: // // 1. Generate the key (Kyber512 key in our example), EVP_PKEY *key = NULL; if (generate_key_pair(&key, NID_KYBER512_R3) != SUCCESS) { return FAIL; } // 2. Extract the public key. uint8_t *pub_key; size_t pub_key_len; if (get_raw_public_key(key, &pub_key, &pub_key_len) != SUCCESS) { EVP_PKEY_free(key); return FAIL; } // 3. Send the public key to Bob. pub_key -------------------> Note: you can use the generated |key| directly int encapsulate(/* IN */ int kem_nid, in the decapsulation phase, as shown below, /* IN */ uint8_t *pub_key, or use the get_raw functions to store/transmit /* IN */ size_t pub_key_len, the key as needed. /* OUT */ uint8_t **ct, /* OUT */ size_t *ct_len, /* OUT */ uint8_t **ss, /* OUT */ size_t *ss_len) { int ret = FAIL; EVP_PKEY_CTX *ctx = NULL; EVP_PKEY *key = NULL; // Create PKEY from the received raw public key. key = EVP_PKEY_kem_new_raw_public_key(kem_nid, pub_key, pub_key_len); if (key == NULL) { goto end; } // Create the context. ctx = EVP_PKEY_CTX_new(key, NULL); if (ctx == NULL) { goto end; } // Get the required buffer lengths and allocate the buffers. if (!EVP_PKEY_encapsulate(ctx, NULL, ct_len, NULL, ss_len)) { goto end; } *ct = (uint8_t*) OPENSSL_malloc(*ct_len); *ss = (uint8_t*) OPENSSL_malloc(*ss_len); if (*ct == NULL || *ss == NULL) { goto end; } // Encapsulate. if (!EVP_PKEY_encapsulate(ctx, *ct, ct_len, *ss, ss_len)) { goto end; } ret = SUCCESS; end: if (ret != SUCCESS) { // Make sure the caller doesn't have to cleanup on failure. *ct_len = 0; *ss_len = 0; OPENSSL_free(*ss); OPENSSL_free(*ct); } EVP_PKEY_free(key); EVP_PKEY_CTX_free(ctx); return ret; } // With the helper function above and upon receiving // Alice's public key you can encapsulate to generate the // shared secret and the corresponding ciphertext: uint8_t *ct = NULL, *ss = NULL; // ciphertext and shared secret, size_t ct_len, ss_len; // and their lengths. int ret = encapsulate(NID_KYBER512_R3, pub_key, pub_key_len, &ct, &ct_len, &ss, &ss_len); // On |ret| being SUCCESS, |ss| is the generated shared secret you can use, // and |ct| is the ciphertext to be sent to Alice. ct <------------------- int decapsulate(/* IN */ EVP_PKEY *key, /* IN */ uint8_t *ct, /* IN */ size_t ct_len, /* OUT */ uint8_t **ss, /* OUT */ size_t *ss_len) { int ret = FAIL; // Create the context. EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new(key, NULL); if (ctx == NULL) { goto end; } // Get the required buffer length and allocate the buffer. if (!EVP_PKEY_decapsulate(ctx, NULL, ss_len, ct, ct_len)) { goto end; } *ss = (uint8_t*) OPENSSL_malloc(*ss_len); if (*ss == NULL) { return FAIL; } // Decapsulate. if (!EVP_PKEY_decapsulate(ctx, *ss, ss_len, ct, ct_len)) { goto end; } ret = SUCCESS; end: if (ret != SUCCESS) { // Make sure the caller doesn't have to cleanup on failure. *ss_len = 0; OPENSSL_free(*ss); } EVP_PKEY_CTX_free(ctx); return ret; } // With the helper function above and upon receiving // Bob's ciphertext you can decapsulate to get the // shared secret: uint8_t *ss = NULL; // shared secret, size_t ss_len; // and its length. int ret = decapsulate(key, ct, ct_len, &ss, &ss_len); EVP_PKEY_free(key); // free if |key| not needed any more. // On |ret| being SUCCESS, |ss| is the generated shared secret you can use. // END Alice's shared secret is equal to Bob's shared secret if the protocol succeeded. ```