Add multi-part sign-message and verify-message operations (was 'Allow external mu to MLDSA sign/verify PSA APIs')

[waleed-elmelegy-arm]

In NIST MLDSA specs supplying external mu is allowed instead of computing it internally in the API.
Algorithm 8 ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′, 𝜎) . . . 7: 𝜇 ← (H(BytesToBits(𝑡𝑟)||𝑀 ′, 64)) ▷ message representative that may optionally be computed in a different cryptographic module

This is useful in base data the needs to be signed/verified is scattered so supplying it in one continuous memory location can be a problem on memory constrained devices

[athoelke]

Crypto API is intended as an application crypto API: I wouldn't expect an application to be computing and passing mu to ML-DSA.Verify_internal(), as this involves extraction of part of the public key material. In this API, we expect the key to not be generally accessible to the application. Of course, it is possible to export the public key, parse it, and extract the tr value and then perform the hash to compute mu. But that is not in the spirit of this API in general.

The streaming use case is why FIPS 204 provides HashML-DSA, to support applications that just need a hash-and-sign algorithm. Alternatively, it is possible to sign message meta data, including the message hash, with ML-DSA; this approach provides authenticity for additional message attributes, and is agile (can be used with any signature algorithm).

NIST did not intend with the comment to permit an application to use the internal function, and the FIPS certification does not cover that use case. FIPS certification is for an implementation of ML-DSA.Verify and HashML-DSA.Verify(). The comment permits the implementation of ML-DSA.Verify() to compute mu in one sub-module, and sign the result in another - for example, mu is computed on the host processor and the signing operation on a secure element or HSM, which can be effective for signing large documents with only a low-bandwidth bus to the HSM.

It is entirely possible for an implementation of the Crypto API to do exactly that.

If a case can be made that the PSA Crypto API is used inside a cryptographic implementation, between sub-modules (e.g. between a host-side library and a secure element/HSM), then we might need to add additional algorithms for ML-DSA-external-mu. This might also be appropriate for the Crypto Driver Interface.

[gilles-peskine-arm]

This is useful in base data the needs to be signed/verified is scattered so supplying it in one continuous memory location can be a problem on memory constrained devices

For this scenario, you don't need to calculate mu externally. Another possibility is a multi-part sign-message and verify-message interface:

psa_sign_setup(&op, key, alg);
psa_sign_update(&op, input1, input1_length);
psa_sign_update(&op, input2, input2_length);
…
psa_sign_finish(&op, signature, signature_size, &signature_length);

This would be a logical extension of the current API, which we've discussed before (including in the description of #96), and the only reason we haven't put it in the API is that nobody had asked for it. Since someone is asking, we should add it.

[athoelke]

Another possibility is a multi-part sign-message and verify-message interface:

Yes, of course, that would be a viable option for ML-DSA as the internal signature algorithm only requires a single pass of the message data.

For SLH-DSA, a multi-past interface would be able to verify signatures, but computing a SLH-DSA signature has to process the full message data twice.

[athoelke]

When designing interruptble APIs for message signature, we considered all the possible multi-part signature operations
In the discussion of API design for multi-part and interruptible signature operations.

An initial discussion in #98, resulted in the following proposed API for multi-part sign-message and verify-message:

psa_sign_message_operation_t
PSA_SIGN_MESSAGE_OPERATION_INIT
psa_sign_message_operation_init()
psa_sign_message_setup(op, key, alg)
psa_sign_message_update(op, [inbuf] msg)
psa_sign_message_finish(op, [outbuf] sig)
psa_sign_message_abort(op)

psa_verify_message_operation_t
...
psa_verify_message_abort(op)

However, subsequent development of the interruptible signature operations in #107 flagged up some issues with very long identifiers. The result was using psa_sign_iop_t and psa_verify_iop_t (etc) for the signing and verifying interruptible operations.

Although the non-interruptible operations are only for sign-message and verify-message, it feels more aligned with the interruptible design to just use psa_sign_operation_t and psa_verify_operation_t for this API. So the proposed API will be:

psa_sign_operation_t
PSA_SIGN_OPERATION_INIT
psa_sign_operation_init()
psa_sign_setup(op, key, alg)
psa_sign_update(op, [inbuf] msg)
psa_sign_finish(op, [outbuf] sig)
psa_sign_abort(op)

psa_verify_operation_t
PSA_VERIFY_OPERATION_INIT
psa_verify_operation_init()
psa_verify_setup(op, key, alg, [inbuf] sig)
psa_verify_update(op, [inbuf] msg)
psa_verify_finish(op)
psa_verify_abort(op)