Leave intermediates partially reduced in ML-KEM NTT This ports a074f282d026a0ebbed7c9efef5a0cf63f72338d's change to ML-DSA. Changes relative to the ML-DSA changes: - Barrett reduction needed to be adjusted from 24 to 32 bits so it can successfully reduce any uint32_t to 0..2*kPrime range. - NTT using partial reduction uses intermediates of up to 15*kPrime, which fits in uint16_t. - INTT using partial reduction uses intermediates of up to 128*kPrime, which required storing intermediates in an uint32_t array. This wasn't a problem in ML-DSA as it already stores vectors of uint32_t to begin with. Saves about 4.9% to 8.1% for TLS ML-KEM operations (most savings being in Encap and Decap, namely 11.0% to 14.7%) on aarch64 Apple M1 Pro: Did 27910 BM_SpeedMLKEM768KeyGenDecap/threads:1 operations (39989.3 ops/sec) [+4.9%] Did 48780 BM_SpeedMLKEM768ParseEncap/threads:1 operations (69751.4 ops/sec) [+7.6%] Did 19862 BM_SpeedMLKEM1024KeyGenDecap/threads:1 operations (28153.9 ops/sec) [+5.1%] Did 33890 BM_SpeedMLKEM1024ParseEncap/threads:1 operations (48063.6 ops/sec) [+8.1%] Did 46596 BM_SpeedMLKEM768KeyGenOnly/threads:1 operations (66675.0 ops/sec) [+2.9%] Did 45743 BM_SpeedMLKEM768PrivateKeyFromSeedOnly/threads:1 operations (65436.1 ops/sec) [+1.9%] Did 68136 BM_SpeedMLKEM768DecapOnly/threads:1 operations (96674.0 ops/sec) [+11.0%] Did 85036 BM_SpeedMLKEM768ParseOnly/threads:1 operations (120954.2 ops/sec) [+2.7%] Did 105067 BM_SpeedMLKEM768EncapOnly/threads:1 operations (150126.4 ops/sec) [+14.4%] Did 30992 BM_SpeedMLKEM1024KeyGenOnly/threads:1 operations (44467.0 ops/sec) [+3.2%] Did 30577 BM_SpeedMLKEM1024PrivateKeyFromSeedOnly/threads:1 operations (43805.5 ops/sec) [+2.9%] Did 50684 BM_SpeedMLKEM1024DecapOnly/threads:1 operations (73954.1 ops/sec) [+14.7%] Did 54923 BM_SpeedMLKEM1024ParseOnly/threads:1 operations (77869.7 ops/sec) [+2.6%] Did 82865 BM_SpeedMLKEM1024EncapOnly/threads:1 operations (118470.5 ops/sec) [+14.1%] Minor improvements (2.9% to 4.5% but only for parse/encap) on AMD EPYC 7B13: Did 12436 BM_SpeedMLKEM768KeyGenDecap/threads:1 operations (17751.4 ops/sec) [+0.0%] Did 22079 BM_SpeedMLKEM768ParseEncap/threads:1 operations (31509.8 ops/sec) [+2.9%] Did 8851 BM_SpeedMLKEM1024KeyGenDecap/threads:1 operations (12692.4 ops/sec) [-0.2%] Did 15821 BM_SpeedMLKEM1024ParseEncap/threads:1 operations (22667.0 ops/sec) [+4.5%] Did 23994 BM_SpeedMLKEM768KeyGenOnly/threads:1 operations (34374.9 ops/sec) [-1.9%] Did 23451 BM_SpeedMLKEM768PrivateKeyFromSeedOnly/threads:1 operations (33470.7 ops/sec) [-1.7%] Did 24538 BM_SpeedMLKEM768DecapOnly/threads:1 operations (35050.9 ops/sec) [+1.9%] Did 50112 BM_SpeedMLKEM768ParseOnly/threads:1 operations (71421.1 ops/sec) [+1.1%] Did 36402 BM_SpeedMLKEM768EncapOnly/threads:1 operations (52087.7 ops/sec) [+4.9%] Did 16656 BM_SpeedMLKEM1024KeyGenOnly/threads:1 operations (23778.1 ops/sec) [-0.7%] Did 16274 BM_SpeedMLKEM1024PrivateKeyFromSeedOnly/threads:1 operations (23304.1 ops/sec) [-0.5%] Did 18824 BM_SpeedMLKEM1024DecapOnly/threads:1 operations (26908.8 ops/sec) [+3.0%] Did 33258 BM_SpeedMLKEM1024ParseOnly/threads:1 operations (47471.2 ops/sec) [+1.0%] Did 28276 BM_SpeedMLKEM1024EncapOnly/threads:1 operations (40380.6 ops/sec) [+7.4%] Bug: 503700354 Change-Id: Idd4b6e8986253288e09e40b8ffbf3adf6a6a6964 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/101967 Auto-Submit: Rudolf Polzer <rpolzer@google.com> Reviewed-by: David Benjamin <davidben@google.com> Commit-Queue: David Benjamin <davidben@google.com> Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>
BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.
Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.
Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.
BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.
Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.
Project links:
To file a security issue, use the Chromium process and mention in the report this is for BoringSSL. You can ignore the parts of the process that are specific to Chromium/Chrome.
There are other files in this directory which might be helpful: