Issues:

Related PRs:

• Import-mldsa-native-NTT stress test on delocator #2903
• AES-GCM: Add function pointer trampolines to avoid delocator issue #2919
• Service Indicator: Add error call trampoline to avoid delocator issue #2920

Import mldsa-native

This imports mldsa-native (https://github.com/pq-code-package/mldsa-native) into AWS-LC.

This PR focuses on the minimal configuration of mldsa-native: No assembly and no FIPS-202 code are imported.

mldsa-native is a high-performance, high-assurance C90 implementation of ML-DSA developed under the Post-Quantum Cryptography Alliance (PQCA) and the Linux Foundation. It is a fork of the Dilithium reference implementation.

Import Mechanism

The mldsa-native source code is unmodified and imported using the importer script crypto/fipsmodule/ml_dsa/importer.sh; the details of the import are in META.yml.

A custom config is provided for mldsa-native which in particular includes a small 'compatibility layer' between AWS-LC/OpenSSL and mldsa-native -- see below.

Future imports (C-only)

Future updates of the C-only mldsa-native source tree should happen through a re-import of mldsa-native: That is, (a) delete crypto/fipsmodule/ml_dsa/mldsa and (b) re-run import.sh. This will re-import mldsa-native/main, though you can set the GITHUB_SHA and GITHUB_REPOSITORY environment variables to point to any other mldsa-native repository/fork.

Future imports (native code)

Once we have verified meaningful parts of the mldsa-native assembly backends, PRs will be filed to integrate those. The details for this integration are TBD and not necessary to finalize for this PR. The options are (a) extending import.sh to import larger parts of the mldsa-native upstream source tree, including native backends, (b) writing custom backends, backed by sources living in the s2n-bignum source tree. Both is possible and compatible with this PR.

Import Scope

mldsa-native has a C-only version as well as native 'backends' in AVX2 and Neon for high performance. This commit only imports the C-only version. Integration of native backends will be done separately.

mldsa-native offers its own FIPS-202 implementation, including fast versions of batched FIPS-202. However, this commit does not import those, but instead provides glue-code around AWS-LC's own FIPS-202 implementation. The path to leveraging the FIPS-202 performance improvements in mldsa-native would be to integrate them directly into crypto/fipsmodule/sha.

Impact on build

None. No build-files are modified. The multilevel build process remains unchanged.

Internal API changes

3 Removed functions:

  [D] 'function void ml_dsa_44_params_init(ml_dsa_params*)'    {ml_dsa_44_params_init}
  [D] 'function void ml_dsa_65_params_init(ml_dsa_params*)'    {ml_dsa_65_params_init}
  [D] 'function void ml_dsa_87_params_init(ml_dsa_params*)'    {ml_dsa_87_params_init}

Compatibility layer

The configuration file mldsa_native_config.h includes a compatibility layer between AWS-LC/OpenSSL and mldsa-native, covering:

• FIPS/PCT: If AWSLC_FIPS is set, MLD_CONFIG_KEYGEN_PCT is enabled to include a PCT.
• FIPS/PCT: If BORINGSSL_FIPS_BREAK_TESTS is set, MLD_CONFIG_KEYGEN_PCT_BREAKAGE_TEST is set and mld_break_pct defined via boringssl_fips_break_test("MLDSA_PWCT"), to include runtime-breakage of the PCT for testing purposes.
• CT: If BORINGSSL_CONSTANT_TIME_VALIDATION is set, then MLD_CONFIG_CT_TESTING_ENABLED is set to enable valgrind testing.
• Zeroization: MLD_CONFIG_CUSTOM_ZEROIZE is set and mld_zeroize mapped to OPENSSL_cleanse to use OpenSSL's zeroization function.
• Randombytes: MLD_CONFIG_CUSTOM_RANDOMBYTES is set and mld_randombytes mapped to RAND_bytes to use AWS-LC's randombytes function.

Side-channels

mldsa-native's CI uses a patched version of valgrind to check for various compilers and compile flags that there are no secret-dependent memory accesses, branches, or divisions. The relevant assertions have been kept but are unused unless MLD_CONFIG_CT_TESTING_ENABLED is set, which is the case if and only if BORINGSSL_CONSTANT_TIME_VALIDATION is set.

mldsa-native uses value barriers to block potentially harmful compiler reasoning and optimization. Where standard gcc/clang inline assembly is not available, mldsa-native falls back to a slower 'opt blocker' based on a volatile global -- both are described in ct.h.

Formal Verification

All C-code imported in this commit is formally verified using the C Bounded Model Checker (CBMC) to be free of various classes of undefined behaviour, including out-of-bounds memory accesses and arithmetic overflow; the latter is of particular interest for ML-DSA because of the use of lazy modular reduction for improved performance.

The heart of the CBMC proofs are function contract and loop annotations to the C-code. Function contracts are denoted __contract__(...) clauses and occur at the time of declaration, while loop contracts are denoted __loop__ and follow the for statement.

The function contract and loop statements are kept in the source, but removed by the preprocessor so long as the CBMC macro is undefined. Keeping them simplifies the import, and care has been taken to make them readable to the non-expert, and thereby serve as precise documentation of assumptions and guarantees upheld by the code.

FIPS Compliance

mldsa-native unconditionally includes stack zeroization. mldsa-native's default secure memset is replaced by OPENSSL_cleanse.

mldsa-native conditionally includes a PCT, guarded by MLD_CONFIG_KEYGEN_PCT. This is set in the config if and only if AWSLC_FIPS is set.

While not part of the FIPS standard, the pk_from_sk function includes validation of both t0 (low-order bits) and tr (hash of public key) using constant-time comparison functions (mld_ct_memcmp), providing strong assurance of key consistency.

Testing

We KAT ML-DSA with test vectors obtained from https://github.com/post-quantum-cryptography/KAT within PQDSAParameterTest.KAT. We select the KATs for the signing mode hedged, which derives the signing private random seed (rho) pseudorandomly from the signer's private key, the message to be signed, and a 256-bit string rnd which is generated at random. The pure variant of these KATs were used, as they provide test vector inputs for "pure" i.e., non-pre-hashed messages.

We also run the ACVP test vectors obtained from https://github.com/usnistgov/ACVP-Server within the three functions PerMLDSATest.ACVPKeyGen, PerMLDSATest.ACVPSigGen and PerMLDSATest.ACVPSigVer. These correspond to the tests found at ML-DSA-keyGen-FIPS204, ML-DSA-sigGen-FIPS204, and ML-DSA-sigVer-FIPS204.
To test ML-DSA pure, non-deterministic mode, we use tgId = 19, 21, 23 of sigGen and tgId = 7, 9, 11 of sigVer.
To test ML-DSA ExternalMu, non-deterministic mode, we use tgId = 20, 22, 24 of sigGen and tgId = 8, 10, 12 of sigVer.

Test Results:

• ML-DSA Tests: 100% passing (61/61 tests)

Formatting

Code in crypto/fipsmodule/ml_dsa/mldsa is directly imported from mldsa-native and comes with its own crypto/fipsmodule/ml_dsa/mldsa/.clang-format.

Prefix build

The prefix build should not be affected by the import, since no definitions of external linkage are imported (everything is tagged either static directly, or MLD_EXTERNAL_API or MLD_INTERNAL_API, both of which are set to static in the context of the import, too).

Performance

Performance should be comparable to the previous integration as both are based on C-only code with AWS-LC's FIPS-202 implementation. The fast mldsa-native backends are not yet imported.

Multilevel build

At the core, mldsa-native is currently a 'single-level' implementation of ML-DSA: A build of the main source tree provides an implementation of exactly one of ML-DSA-44/65/87, depending on the MLD_CONFIG_PARAMETER_SET parameter.

To build all security levels, level-specific sources are built 3 times, once per security level, and linked with a single build of the level-independent code. The single-compilation-unit approach pursued by AWS-LC makes this process fairly simple since one merely needs to include the single-compilation-unit file provided by mldsa-native three times, and configure it so that the level-independent code is included only once. The final include moreover #undef'ines all macros defined by mldsa-native, reducing the risk of name clashes with other parts of crypto/fipsmodule/bcm.c.

Note that this process is entirely internal to ml_dsa.c, and does not affect the AWS-LC build.

HashML-DSA: mldsa-native includes lots of HashML-DSA functionality that we dont need in aws-lc. Perhaps we should add config upstream to mldsa-native to choose which of pure/externalmu/hash modes are imported to reduce unused code.

Main differences from reference implementation

mldsa-native is a fork of the ML-DSA reference implementation (Dilithium).

The following gives an overview of the major changes:

• CBMC and debug annotations, and minor code restructurings or signature changes to facilitate the CBMC proofs. For example, functions are structured to make loop bounds and memory access patterns explicit for formal verification.
• Introduction of 4x-batched versions of some functions from the reference implementation. This is to leverage 4x-batched Keccak-f1600 implementations if present. The batching happens at the C level even if no native backend for FIPS 202 is present.
• FIPS 204 compliance: Introduced optional PCT (FIPS 204, Section 4.4, Pairwise Consistency) and zeroization of stack buffers as required by (FIPS 204, Section 3.6.3, Destruction of intermediate values).
• Introduction of native backend implementations for AVX2. Those are drop-in replacements for the corresponding C functions and dispatched at compile-time. (Not in this PR, but the C code prep is in place).
• Restructuring of files to separate level-specific from level-generic functionality. This is needed to enable a multi-level build of mldsa-native where level-generic code is shared between levels.
• More pervasive use of value barriers to harden constant-time primitives, even when Link-Time-Optimization (LTO) is enabled. The use of LTO can lead to insecure compilation in case of the reference implementation.

License

mldsa-native (everything under crypto/fipsmodule/ml_dsa/mldsa/**) is imported under the Apache 2.0 license and the ISC license. The LICENSE file remains unchanged.

Integration-specific code (everything with direct parent crypto/fipsmodule/ml_dsa/*) is made under the terms of the Apache 2.0 license and the ISC license.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license and the ISC license.