ML-KEM multi-variant refactor by vdukhovni · Pull Request #26172 · openssl/openssl

vdukhovni · 2024-12-12T23:57:52Z

This is a cleaned up version, without any variant-specific source files, and a saner ML_KEM_KEY structure that is the same object in the implementation code and in the provider. The separate ML-KEM context is gone, absorbed into the key.
Both new internally visible types (ML_KEM_KEY and ML_KEM_VINFO) are upper-case.

Some new ML-KEM specific tests are now in their own file, rather than further bloating evp_extra_test.c.

The new SSL groups are now tested not only against the OQS provider, but also internally with various combinations of no-ec, no-dh, etc.

Performance is improved by ~5-10%, while addressing the "clangover" side-channel (misoptimisation in some versions of clang with vectorisation disabled, -Os or -O3 -fno-vectorize).

The non-local (still internal) symbols in libcrypto are now:

ossl_ml_kem_decap
ossl_ml_kem_encap_rand
ossl_ml_kem_encap_seed
ossl_ml_kem_encode_private_key
ossl_ml_kem_encode_public_key
ossl_ml_kem_genkey_rand
ossl_ml_kem_genkey_seed
ossl_ml_kem_get_vinfo
ossl_ml_kem_key_dup
ossl_ml_kem_key_free
ossl_ml_kem_key_new
ossl_ml_kem_parse_private_key
ossl_ml_kem_parse_public_key
ossl_ml_kem_pubkey_cmp

Checklist

tests are added or updated

crypto/ml_kem/ml_kem.c

crypto/ml_kem/build.info

crypto/ml_kem/ml_kem.c

include/crypto/ml_kem.h

providers/implementations/keymgmt/ml_kem_kmgmt.c

slontis

Overall I think this is much cleaner than your first branch..

providers/implementations/keymgmt/ml_kem_kmgmt.c

providers/implementations/kem/ml_kem.c

crypto/ml_kem/ml_kem.c

providers/implementations/include/prov/ml_kem.h

With the soon-to-be-merged ML-KEM openssl#26172 as the merge base.

This introduces support for ML-KEM-512 and ML-KEM-1024 using the same underlying implementation parameterised by a few macros for the associated types and constants. KAT tests are added for ML-KEM 512 and 1024, to complement the previous tests for ML-KEM-768. MLKEM{512,768,1024} TLS "group" codepoints are updated to match the final IANA assigments and to make the additional KEMs known to the TLS layer. The pure-QC MLKEMs are not in the default list of supported groups, and need to be explicitly enabled by the application. Future work will introduce support for hybrids, and for more fine-grained policy of which keyshares a client should send by default, and when a server should request (HRR) a new mutually-supported group that was not sent. Tests for ML-KEM key exchange added to sslapitest to make sure that our TLS client MLKEM{512,768,1024} implementations interoperate with our TLS server, and that MLKEM* are not negotiated in TLS 1.2. Tests also added to excercise non-derandomised ML-KEM APIs, both directly (bypassing the provider layer), and through the generic EVP KEM API (exercising the provider). These make sure that RNG input is used correctly (KAT tests bypass the RNG by specifying seeds). The API interface to the provider takes an "const ML_KEM_VINFO" pointer, (obtained from ossl_ml_kem_get_vinfo()). This checks input and output buffer sizes before passing control to internal code that assumes correctly sized (for each variant) buffers. The original BoringSSL API was refactored to eliminate the opaque public/private key structure wrappers, since these structures are an internal detail between libcrypto and the provider, they are not part of the public (EVP) API. New "clangover" counter-measures added, refined with much appreciated input from David Benjamin (Chromium). The internal steps of "encrypt_cpa" were reordered to reduce the working-set size of the algorithm, now needs space for just two temporary "vectors" rather than three. The "decap" function now process the decrypted message in one call, rather than three separate calls to scalar_decode_1, scalar_decompress and scalar_add. Some loops were unrolled, improving performance of en/decapsulate (pre-expanded vectors and matrix) by around 5%. To handle, however unlikely, the SHA3 primitives not behaving like "pure" functions and failing, the implementation of `decap` was modifed: - To use the KDF to compute the Fujisaki-Okamoto (FO) failure secret first thing, and if that fails, bail out returning an error, a shared secret is still returned at random from the RNG, but it is OK for the caller to not use it. - If any of the subsequently used hash primitives fail, use the computed FO failure secret (OK, despite no longer constant-time) and return success (otherwise the RNG would replace the result). - We quite reasonably assume that chosen-ciphertext attacks (of the correct length) cannot cause hash functions to fail in a manner the depends on the private key content. Support for ML-KEM-512 required adding a centered binomial distribution helper function to deal with η_1 == 3 in just that variant. Some additional comments were added to highlight how the code relates to the ML-KEM specification in FIPS 203. Reviewed-by: Paul Dale <ppzgs1@gmail.com> Reviewed-by: Tim Hudson <tjh@openssl.org> Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Tomas Mraz <tomas@openssl.org> (Merged from #26172)

With the soon-to-be-merged ML-KEM openssl#26172 as the merge base.

vdukhovni · 2024-12-26T09:10:23Z

Amazing work!

You're welcome. How are you planning to use this? We'll soon also have some EC/ECX + ML-KEM hybrids. (My SMTP server already supports both MLKEM768 and X25519MLKEM768 as well as the usual expected ECDHE/FFDHE groups).

With the soon-to-be-merged ML-KEM openssl#26172 as the merge base.

With the soon-to-be-merged ML-KEM #26172 as the merge base. Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Tim Hudson <tjh@openssl.org> Reviewed-by: Tomas Mraz <tomas@openssl.org> Reviewed-by: Neil Horman <nhorman@openssl.org> (Merged from #26217)

This introduces support for ML-KEM-512 and ML-KEM-1024 using the same underlying implementation parameterised by a few macros for the associated types and constants. KAT tests are added for ML-KEM 512 and 1024, to complement the previous tests for ML-KEM-768. MLKEM{512,768,1024} TLS "group" codepoints are updated to match the final IANA assigments and to make the additional KEMs known to the TLS layer. The pure-QC MLKEMs are not in the default list of supported groups, and need to be explicitly enabled by the application. Future work will introduce support for hybrids, and for more fine-grained policy of which keyshares a client should send by default, and when a server should request (HRR) a new mutually-supported group that was not sent. Tests for ML-KEM key exchange added to sslapitest to make sure that our TLS client MLKEM{512,768,1024} implementations interoperate with our TLS server, and that MLKEM* are not negotiated in TLS 1.2. Tests also added to excercise non-derandomised ML-KEM APIs, both directly (bypassing the provider layer), and through the generic EVP KEM API (exercising the provider). These make sure that RNG input is used correctly (KAT tests bypass the RNG by specifying seeds). The API interface to the provider takes an "const ML_KEM_VINFO" pointer, (obtained from ossl_ml_kem_get_vinfo()). This checks input and output buffer sizes before passing control to internal code that assumes correctly sized (for each variant) buffers. The original BoringSSL API was refactored to eliminate the opaque public/private key structure wrappers, since these structures are an internal detail between libcrypto and the provider, they are not part of the public (EVP) API. New "clangover" counter-measures added, refined with much appreciated input from David Benjamin (Chromium). The internal steps of "encrypt_cpa" were reordered to reduce the working-set size of the algorithm, now needs space for just two temporary "vectors" rather than three. The "decap" function now process the decrypted message in one call, rather than three separate calls to scalar_decode_1, scalar_decompress and scalar_add. Some loops were unrolled, improving performance of en/decapsulate (pre-expanded vectors and matrix) by around 5%. To handle, however unlikely, the SHA3 primitives not behaving like "pure" functions and failing, the implementation of `decap` was modifed: - To use the KDF to compute the Fujisaki-Okamoto (FO) failure secret first thing, and if that fails, bail out returning an error, a shared secret is still returned at random from the RNG, but it is OK for the caller to not use it. - If any of the subsequently used hash primitives fail, use the computed FO failure secret (OK, despite no longer constant-time) and return success (otherwise the RNG would replace the result). - We quite reasonably assume that chosen-ciphertext attacks (of the correct length) cannot cause hash functions to fail in a manner the depends on the private key content. Support for ML-KEM-512 required adding a centered binomial distribution helper function to deal with η_1 == 3 in just that variant. Some additional comments were added to highlight how the code relates to the ML-KEM specification in FIPS 203. Reviewed-by: Paul Dale <ppzgs1@gmail.com> Reviewed-by: Tim Hudson <tjh@openssl.org> Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Tomas Mraz <tomas@openssl.org> (Merged from openssl#26172)

With the soon-to-be-merged ML-KEM openssl#26172 as the merge base. Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Tim Hudson <tjh@openssl.org> Reviewed-by: Tomas Mraz <tomas@openssl.org> Reviewed-by: Neil Horman <nhorman@openssl.org> (Merged from openssl#26217)