ML-DSA and decoding of malformed private keys

[Guillaume Endignoux]

Dear forum,

Some discussion came up while implementing test vectors for ML-DSA: https://github.com/C2SP/wycheproof/pull/112

In particular, algorithm 19 (skDecode) is somewhat ill-defined: on the one hand the mathematical description accepts as input any byte array of the private key length (the domain is `B^skLength`), on the other hand, the lines 812-814 mention that:

> there exist malformed inputs than can cause skDecode to return values that are not in the correct range. Hence skDecode should only be run on input that comes from trusted sources.

and the mathematical description has comments such as:

> This may lie outside [-eta, eta], if input is malformed

This is unfortunate, and it would be clearer if the specification could clarify that either (1) inputs must (rather than should) be well-wormed (i.e. the input domain would be a subset of `B^skLength` rather than the full `B^skLength`), or that (2) the skDecode function must return an error if a value is outside of the [-eta, eta] range.

Realistically, the second option (error check) looks more pragmatic to me, and its overhead should be low (aside from making sure it's constant time).

It may of course seem odd to validate a private key, given that if it was tampered with there is no security guaranty anymore. My concern is that ambiguity in a specification leads to different implementations having different behaviors due to their respective interpretation of the specs, and that might in turn lead to incompatibilities (or worse, vulnerabilities). Additionally, a signature algorithm is a fundamental building block, so this might matter in a more complex protocol (I don't have an example though).

A bolder alternative could be to have the private key be serialized as its seed, as was discussed for ML-KEM. One drawback is that the key generation procedure needs to be re-run before signing a message (but then the expanded key can be kept as an object in memory to sign more messge - it just cannot be serialized/deserialized).

This would however have multiple benefits:

- A serialized private key is smaller (32 bytes).

- All private keys are valid.

- The secret values s1, s2 are not only in the [-eta, eta] range, but also follow the intended distribution. There is less risk to import a private key which was (for whatever reason) generated with the wrong distribution*.

Guillaume

*To be more precise, someone might brute-force values of the seed to skew the distribution, but cannot for example just set all coefficients of s1 and s2 to zero.

[Bas Westerbaan]

For the reasons you've laid out, I agree that a single 32-byte seed is the best format for a portable ML-DSA signing key, and I would be in favour of adopting it as the primary signing key format, as long as it does not preclude implementations that never export signing key after keygen, from using the current format internally.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/67b9d205-c98c-4f96-903b-d6ab064a2b76n%40list.nist.gov.

[Blumenthal, Uri - 0553 - MITLL]

I concur, and support this proposal.

 

-- 

V/R,

Uri

 

 

From: 'Bas Westerbaan' via pqc-forum <pqc-...@list.nist.gov>
Date: Tuesday, May 28, 2024 at 08:45
To: Guillaume Endignoux <guill...@google.com>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXT] Re: [pqc-forum] ML-DSA and decoding of malformed private keys

For the reasons you've laid out, I agree that a single 32-byte seed is the best format for a portable ML-DSA signing key, and I would be in favour of adopting it as the primary signing key format, as long as it does not preclude implementations

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender This message came from outside the Laboratory.

ZjQcmQRYFpfptBannerEnd

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoWgiFWtHuAa142-TJabY-DE5AN7VUAjmmGzpaXHZBTW9w%40mail.gmail.com.

[Mike Ounsworth]

I also am in favour of the 32-byte seed as the primary portable ML-DSA private key format.

 

But I think it is also worth defining a serialization format for the full key because as mentioned by Guillaume, applications that sign often will want to hold on to the expanded private key for performance reasons. Giving a serialization for this avoids interop problems, and gives us a place to put a security consideration note about error checking the private key.

 

---

Mike Ounsworth

 

From: 'Bas Westerbaan' via pqc-forum <pqc-...@list.nist.gov>

Sent: Tuesday, May 28, 2024 7:44 AM
To: Guillaume Endignoux <guill...@google.com>
Cc: pqc-forum <pqc-...@list.nist.gov>

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoWgiFWtHuAa142-TJabY-DE5AN7VUAjmmGzpaXHZBTW9w%40mail.gmail.com.

[Paul Hoffman]

On May 28, 2024, at 06:45, 'Mike Ounsworth' via pqc-forum <pqc-...@list.nist.gov> wrote:
> -->I also am in favour of the 32-byte seed as the primary portable ML-DSA private key format.

> But I think it is also worth defining a serialization format for the full key because as mentioned by Guillaume, applications that sign often will want to hold on to the expanded private key for performance reasons. Giving a serialization for this avoids interop problems, and gives us a place to put a security consideration note about error checking the private key.

If NIST is not willing to create the serialization format (possibly due to trying to get the current work out in a timely fashion), this seems like an easy thing to do in the IETF.

--Paul Hoffman

[Guillaume Endignoux]

A perhaps (very) minor drawback of collapsing the private key to its original seed is in terms of generating edge-case test vectors.

Indeed, the method I described in pqc-forum/c/OzMYMWPnMYY to generate tests that exercise the "ct0 max vs. gamma2" condition for ML-DSA-44 wouldn't be possible, as my proposed test cases use hand-crafted secret vectors s1 and s2 (without knowing a seed).

That said:

- A brute-force method to generate test cases based on the seed is feasible as shown by Mike Hamburg and Qinglai Xiao in pqc-forum/c/G8Zf0hC-uu0 (it's only around 100x slower).

- Test cases only need to be generated once.

- These tests are only relevant for ML-DSA-44 (with other parameters the check is always true as discussed in pqc-forum/c/eLaw4fgjaMg as well).

So while I do think test vectors that exercise as many pitfalls and edge cases as possible are essential, here this doesn't prevent choosing portable serialization formats that are as simple and unambiguous as possible (i.e. portable private key = a seed).

[Sophie Schmieg]

I would not worry too much about generating test cases, unless you have a property that is both unlikely enough to be very expensive to brute force, but not expensive enough that it cannot reasonably be brute forced by anyone. In other words, as long as the edge does not have a probability above 1/2^128 but below something like 1/2^50, we can always generate test vectors. Lower probabilities are possible if we make it a cryptocurrency proof of work, I guess 🙃. There are other reasons to not want code paths this unlikely in your algorithm anyways, as not every implementation will be run against every test vector.

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/f4ec74a3-9806-4cdd-959b-4da23e6e9c13n%40list.nist.gov.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Mike Ounsworth]

Guillaume raises a good point though that some research will require constructing test cases around hand-crafted keypairs for which we do not know the seed, and that implementations that only support seed-based private keys will have difficulty running these test cases.

 

It seems to me that the answer is for the test frameworks of robust implementations to be able to accept fully inflated private keys, even if the implementation’s normal mode of operation only accepts seeds.

 

---

Mike Ounsworth

 

From: Sophie Schmieg <ssch...@google.com>
Sent: Friday, May 31, 2024 7:01 AM
To: Guillaume Endignoux <guill...@google.com>
Cc: pqc-forum <pqc-...@list.nist.gov>; Paul Hoffman <paul.h...@icann.org>; Mike Ounsworth <Mike.Ou...@entrust.com>
Subject: [EXTERNAL] Re: [pqc-forum] ML-DSA and decoding of malformed private keys

 

I would not worry too much about generating test cases, unless you have a property that is both unlikely enough to be very expensive to brute force, but not expensive enough that it cannot reasonably be brute forced by anyone. In other words,

[Bas Westerbaan]

It seems to me that the answer is for the test frameworks of robust implementations to be able to accept fully inflated private keys, even if the implementation’s normal mode of operation only accepts seeds.

Indeed. Even better: just have test vectors for the internal functions such in this case ExpandA.