Define API for Module-Lattice-Based Digital Signature (ML-DSA aka CRYSTALS-Dilithium)

[athoelke]

Updated 13-09-2024: The final version of the specification is now published https://csrc.nist.gov/pubs/fips/204/final.

NIST has now published a draft specification for a Digital Signature algorithm derived from CRYSTALS-Dilithium. The algorithm is designated ML-DSA, and will be published as FIPS 204. The draft (open for review until 22 Nov 2023) can be downloaded from https://csrc.nist.gov/pubs/fips/204/ipd.

NIST is planning to standardize three parameterized variants of ML-DSA: ML-DSA-44, ML-DSA-65, ML-DSA-87, which provide increasing levels of security for increasing computation and size of keys and signature values.

The signature algorithm is recommended to use fresh randomness, to mitigate side-channel attacks; but can also operate deterministically when the implementation does not have access to randomness, by substituting a zero value in place of the random value.

The Crypto API should define an API for using these algorithms.

[athoelke]

API Design

The ML-DSA algorithms fit well within the existing signature API: it uses a private/public key pair, the sign-message and verify-message algorithms do not require additional inputs.

As specified, the algorithms do not naturally fit a sign-the-hash model, as the 'message representative' processed by the algorithm is not a hash of the message H( M ), but a composite hash H( H( pk ) || M ), where pk is the public key, and H( x ) is the first 512 bits of SHAKE256( x ). See Algorithm 2 ML-DSA.Sign(sk, M) in the draft.

However, other Crypto API signature algorithms do support the use of psa_sign_hash() even when the input is not precisely a hash of the message, for example, PSA_ALG_RSA_PKCS1V15_SIGN_RAW.

We could consider specifying that ML-DSA can be used with psa_sign_hash(). However, to provide the expected security of the signature algorithm, the application would have to use the encoded public-key value and compute the composite hash value for input to the API. It is not possible for an implementation of psa_sign_hash() to validate that this has been done correctly.

If we do not want to support this use of psa_sign_hash() for ML-DSA, then we could instead consider defining a multi-part operation for message signature and verification, that supports incremental supply of the message data. ML-DSA algorithms only makes a single pass of the message, and so would fit the multi-part operation model.

[athoelke]

Last month, the approved versions of the new NIST PQ crypto standards was announced. That document includes a description of the comments and changes since the draft last summer.

The final specification for ML-DSA is at https://csrc.nist.gov/pubs/fips/204/final.

Most details of the scheme are unchanged, the main changes since the draft that affects the API design are:

• The pre-hash and pure variants of the scheme are now domain-separated via the input to the hash computation of the message representative. There are now separate External functions defined for prehash signature and verification.
• It is permitted to store the 32-byte seed, and regenerate the key-pair on demand, in place of storing the 3.8-7.3kB private + public key-pair (the public key cannot be computed from the private key, only from the initial seed). This could affect the decision on the default export format for the ML-DSA key-pair.

[athoelke]

Some API design thoughts are already being explored in the #210 PR discussion.