Add External-Mu support to ML-DSA

[bartonjs]

Background

FIPS 204 defines two pairs of signature generation and verification:

• ML-DSA.Sign(sk, M, ctx)
  • .NET: MLDsa.SignData(data: M, context: ctx);
• HashML-DSA.Sign(sk, M, ctx, PH)
  • .NET: MLDsa.SignPreHash(hash: PH(M), hashAlgorithmOid: PH.OID, context: ctx);

The two signatures are not mutually comprehensible. With the industry preferring the first ("pure") approach, but HSMs and the like dreading needing to send gigabytes, a comment in the spec made for a happy alternative:

FIPS 204, Section 6.2 (ML-DSA Signing (internal)), Algorithm 7 (ML-DSA.Sign_internal(sk, M', rnd))

...
6: 𝜇 ← H(BytesToBits(𝑡𝑟)||𝑀 ′, 64) ▷ message representative that may optionally be computed in a different cryptographic module

One supposes that the intention is that libraries like Windows CNG NCrypt can compute the mu value using software, then hand it over to the HSM to finish the hardware signature. Even as HSMs are celebrating this, the primitive cryptographic libraries realized this solved the problem for them that their API design required M to be in contiguous memory... which is not pleasant if one is signing something like a 4.5GB DVD ISO.

Underlying providers are therefore exposing Sign-Mu operations to be commensurate with RSA/DSA/EC-DSA SignHash. As this is about signing a mu value that came from outside the signature operation, it is colloquially referred to as "external" mu.

API Proposal

Part 1, Sign/Verify

Both the data and the context values are used in the calculation of mu, and neither appear again later in the signature algorithm. Therefore SignData(data, context) => SignExternalMu(mu).

namespace System.Security.Cryptography
{
    public abstract partial class MLDsa
    {
        public byte[] SignExternalMu(byte[] mu);
        public byte[] SignExternalMu(ReadOnlySpan<byte> mu);
        public void SignExternalMu(ReadOnlySpan<byte> mu, Span<byte> destination);
        protected abstract void SignExternalMuCore(ReadOnlySpan<byte> mu, Span<byte> destination);
    
        public bool VerifyExternalMu(byte[] mu, byte[] signature);
        public bool VerifyExternalMu(ReadOnlySpan<byte> mu, ReadOnlySpan<byte> signature);
        protected abstract bool VerifyExternalMuCore(ReadOnlySpan<byte> mu, ReadOnlySpan<byte> signature);
    }
    public partial class MLDsaAlgorithm
    {
        public int MuSizeInBytes { get; }
    }
}

Part 2, Computing Mu

• OpenSSL 3.5 exposes the hook for signing mu, but does not expose a direct way to calculate it.
• OpenSSL Main also does not expose a direct way to calculate mu, but instead is adding a way to accumulate data into a signature like how one accumulates into a hash.
• Windows does not currently have support for external mu, but based on discussions I expect them to end up like OSSL 3.5.

While mu is used for both ML-DSA.Sign and HashML-DSA.Sign, the API here is only concerned with "pure" mu, as the hash variant already has ways of accomplishing a streaming hash.

The MLDsaMuHash design is based on Shake256 and IncrementalHash.

namespace System.Security.Cryptography
{
    public abstract partial class MLDsa
    {
        /* OpenExternalMuHash, GetMuHasher, MUUUUUUU (like a cow says), MuBabyMu, TheCowSaysMu, ... */ 
        public MLDsaMuHash OpenExternalMuHash();
        public MLDsaMuHash OpenExternalMuHash(byte[]? context);
        public MLDsaMuHash OpenExternalMuHash(ReadOnlySpan<byte> context);
        protected virtual MLDsaMuHash OpenExternalMuHashCore(ReadOnlySpan<byte> context);
    }
    [ExperimentalAttribute("SYSLIB5006", UrlFormat="https://aka.ms/dotnet-warnings/{0}")]
    public abstract class MLDsaMuHash : IDisposable
    {
        protected MLDsaMuHash(MLDsa key);
    
        public int HashLengthInBytes { get; }
    
        protected MLDsa Key { get; }
    
        public void AppendData(byte[] data);
        public void AppendData(Stream stream);
        public void AppendData(ReadOnlySpan<byte> data);
        public Task AppendDataAsync(Stream stream, CancellationToken cancellationToken = default);
        protected abstract void AppendDataCore(ReadOnlySpan<byte> data);
    
        public MLDsaMuHash Clone();
        protected abstract MLDsaMuHash CloneCore();
    
        public void Dispose();
        protected virtual void Dispose(bool disposing);
    
        public byte[] GetCurrentHash();
        public void GetCurrentHash(Span<byte> destination);
        protected abstract void GetCurrentHashCore(Span<byte> destination);
    
        public byte[] GetHashAndReset();
        public void GetHashAndReset(Span<byte> destination);
        protected abstract void GetHashAndResetCore(Span<byte> destination);
    
        public void Reset();
        protected virtual void ResetCore();
    
        public byte[] SignAndReset();
        public void SignAndReset(Span<byte> destination);
    
        public bool VerifyAndReset(byte[] signature);
        public bool VerifyAndReset(ReadOnlySpan<byte> signature);
    }
}

Alternative Names

• MLDsaMuHash -> MLDsaMuBuilder
  • Then probably rename most of the methods.
• OpenExternalMuHash -> CreateExternalMuBuilder
  • Adding an instance "Create" method, and assumes a rename of Hash->Builder.

Alternative Designs

Reducing Capture

The MLDsaMuHash type captures the original MLDsa key object (whether it be public or private) to later invoke _key.SignExternalMu or _key.VerifyExternalMu from the Sign/Verify(AndReset) method groups.

Instead, we could remove those convenience methods and base the type on just MLDsaAlgorithm (though data from the public key is still needed at object creation time).

Matching OpenSSL

Instead of making it easy to compute the mu value, we could change the hash-builder to a signature-builder and only allow accumulating data into an ultimate call to sign or verify.

Split mu-calculation and signature accumulation into different types.

Either MLDsaSignatureBuilder : MLDsaMuBuilder or MLDsaSignatureBuilder(MLDsaMuBuilder).

Either way, it seems like we then need both OpenExternalMu and OpenSignatureBuilder to be present on MLDsa, and use virtuals to power them.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-security, @bartonjs, @vcsjones
See info in area-owners.md if you want to be subscribed.

[PranavSenthilnathan]

This is missing in the current edit of the proposal (suggest adding it to Part 1):

public abstract partial class MLDsaAlgorithm
{
    public int MuSizeInBytes { get; }
}

[bartonjs]

Good catch. Edited it in. And made tomorrow-me happy by putting namespace decls in 😄.

[vcsjones]

This is a prerecorded message. @vcsjones is at the beach and will not be in API Review. 🏖️

There are three angles to look at this:

1. Easy-of-use / avoid pitfalls
2. Functionality
3. Compliant implementation

The real reason why external Mu exists is because pure signing is not friendly for signing large messages. HashML-DSA exists, but there are some undesirable things about it, but everyone realized external Mu could make large messages work with Pure signing.

If I were implementing this API solely focusing on number one, I would suggest something like that OpenSSL is building: an incremental signer but the concept of Mu is hidden from developers.

That’s great to avoid misuse, but it doesn’t address other needs: Mu being calculated in another module and sent to another system.

Consider a use case like Azure Key Vault. Azure Key Vault’s client SDK might calculate Mu on the client and send that to some HSM that signs Mu. Azure Key Vault would not be able to entirely build this entirely in terms of an “incremental signer”, at least from what the Core methods look like. Clearly there is some need for “I want to get a Mu” and “Hey I have a Mu”.

On the other hand, calculating Mu in managed code is likely not going to be FIPS compliant implementation. It seems very reasonable that the Mu calculation could be covered by FIPS. So if platforms evolve in such a way that don’t have a “here’s mu” and “I have mu” then they will have a hard time staying FIPS-y.

This seems to be the case with OpenSSL: If developers want an external Mu implementation that keeps everything FIPS-y then it seems they would need to go the route of some “incremental signer” API.

That makes this API proposal somewhat interesting in the face of a FIPS-locked down OpenSSL build. GetCurrentHash, GetHashAndReset, etc would need to throw. This means SignAndReset would not really be convenience APIs - they would be the way to use external mu with OpenSSL.

Right now we are thinking of this as MLDsaMuHash - but I am not convinced this is right. It’s not really a just a dumb wrapper over SHAKE. That’s how it’s implemented right now, but it might be implemented very differently on other platforms!

Okay, so what am I suggesting.

• SignAndReset should have a SignAndResetCore. The “managed” implementation can just calculate Mu and send it off to MLDsa, but other implementations might not be able to use GetHashAndResetCore. Because they won’t be able to get the hash. They only have an incremental signer.
• Repeat the above for Verify.
• We have both MuSizeInBytes and HashLengthInBytes - I am not sure we need both.
• In broad strokes, I am trying to refrain from thinking of Mu as a hash. That’s what it is, sure, but mentally I have been trying to frame it as “mu” in the same way that a KDF is often just a hash under the covers, but its a purpose built construction. So I am not 100% sold on all of the “Hash” phrasing.

[bartonjs]

calculating Mu in managed code is likely not going to be FIPS compliant implementation

As with all things built on top of primitives, it's unclear (at least to me, and seems to be sporadic amongst auditors) whether "We did this in terms of FIPS SHAKE256" is kosher, or un-kosher.

(But, yes, I do share the concern that it'll be un-kosher)

[bartonjs]

Ignoring "so how do I get mu if I need to?" If we just wanted to do what OSSL 3.6 is doing, it'd be

namespace System.Security.Cryptography
{
    public abstract partial class MLDsa
    {
        public StreamingSignatureContext CreateSignatureContext();
        public StreamingSignatureContext CreateSignatureContext(byte[] context);
        public StreamingSignatureContext CreateSignatureContext(ReadOnlySpan<byte> context);
        protected abstract StreamingSignatureContext CreateSignatureContextCore(ReadOnlySpan<byte> context);
    }
    public abstract class StreamingSignatureContext : IDisposable
    {
        public void Dispose();
        protected virtual void Dispose(bool disposing);

        public void AppendData(byte[] data);
        public void AppendData(Stream stream);
        public void AppendData(ReadOnlySpan<byte> data);
        public Task AppendDataAsync(Stream stream, CancellationToken cancellationToken = default);
        protected abstract void AppendDataCore(ReadOnlySpan<byte> data);

        public byte[] SignAndClose();
        public void SignAndClose(Span<byte> destination);
        protected abstract void SignAndCloseCore(Span<byte> destination);
    
        public bool VerifyAndClose(byte[] signature);
        public bool VerifyAndClose(ReadOnlySpan<byte> signature);
        protected abstract bool VerifyAndClose(ReadOnlySpan<byte> signature);
    }
}

I made the context type not include MLDsa, because it doesn't currently expose back any ML-DSA data. And it could be Streaming, Incremental, whatever. (Though it would want some more love for "so, uh, how big is the signature, then?", e.g. doesn't work for X.509 EC-DSA)

And on that I have "AndClose", because I don't know these things to be rehydratable.

[bartonjs]

Video

• SignExternalMu(mu) -> Mu(externalMu)
• For the part 2 segment, we should defer until we have better, more clearly understood, scenarios.

namespace System.Security.Cryptography
{
    public abstract partial class MLDsa
    {
        public byte[] SignMu(byte[] externalMu);
        public byte[] SignMu(ReadOnlySpan<byte> externalMu);
        public void SignMu(ReadOnlySpan<byte> externalMu, Span<byte> destination);
        protected abstract void SignMuCore(ReadOnlySpan<byte> externalMu, Span<byte> destination);
    
        public bool VerifyMu(byte[] externalMu, byte[] signature);
        public bool VerifyMu(ReadOnlySpan<byte> externalMu, ReadOnlySpan<byte> signature);
        protected abstract bool VerifyMuCore(ReadOnlySpan<byte> externalMu, ReadOnlySpan<byte> signature);
    }
    public partial class MLDsaAlgorithm
    {
        public int MuSizeInBytes { get; }
    }
}