ML-DSA signing failure rate
82 views
Skip to first unread message
Becker, Hanno
11:25 AM (11 hours ago) 11:25 AM
to pqc-...@list.nist.gov
Hi,
In [FIPS 204, Section 4, Table 1, ML-DSA parameter sets] and [FIPS 204, Appendix C], the expected repetitions in the rejection sampling loop of ML-DSA-{44,65,87} are documented as 4.25, 5.1 and 3.85, respectively.
Empirical measurements suggest that the true values are closer to 4.36, 5.14, and 3.91, respectively.
This mildly affects the minimum number of signing attempts to achieve a signing failure rate of < 2^{-256}, currently documented as 814.
It appears that the figures from FIPS 204 are about the failure rate for check [FIPS 204, Algorithm 7, ML-DSA.Sign_internal, L23], whereas the overall failure rate is increased by the follow-up check on L28. This nuance has been lost between the Dilithium 3
spec and FIPS 204.
All the best,
Hanno
Markku-Juhani O. Saarinen
12:06 PM (10 hours ago) 12:06 PM
to Becker, Hanno, pqc-...@list.nist.gov
Hi All,
I discussed this with Hanno beforehand -- and I agree. And the FIPS 204 Table 1 the repeat rate mismatch does not seem to appear in the latest errata sheet I found ( https://csrc.nist.gov/files/pubs/fips/204/final/docs/fips-204-potential-updates.xlsx ).
How did this happen? Here's some observations: Those numbers { 4.25, 5.1, 3.85 } can also be found in the Dilithium 3.1 spec ( https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) -- see Table 2. There, importantly, there is a reference to Equation 5, which exactly reproduces them. Uf you look at its derivation and surrounding text, Equation 5 is only claimed to be an approximate "probability that Step 21 passes"; so it doesn't even claim to account for the hint (omega) rejection on Step 24 of Dilithium 3.1 spec.
By accounting for all sources of rejection/repeat (derivation omitted here, but it still involves some distributional assumptions), I arrive at repeat rates {4.358, 5.137, 3.905}. These match Hanno's experiments with the given precision. The unaccounted-for omega hint rejection (Line 28 of Algorithm 7 in FIPS 204) causes most of the gap with reality; the rest is approximation error in Equation 5.
ps. While both (Alg 7, FIPS 204) Line 23 checks contribute substantially to the rejection probability, and this hint rejection (Line 28) contributes (order of magnitude) ~1%, the fourth condition (Also on Line 28), ‖ct₀‖∞ ≥ γ₂, practically never fires for ML-DSA-65 and ML-DSA-87. For ML-DSA-44, the probability of this type of rejection is something like 7*10^-9.
I discussed this with Hanno beforehand -- and I agree. And the FIPS 204 Table 1 the repeat rate mismatch does not seem to appear in the latest errata sheet I found ( https://csrc.nist.gov/files/pubs/fips/204/final/docs/fips-204-potential-updates.xlsx ).
How did this happen? Here's some observations: Those numbers { 4.25, 5.1, 3.85 } can also be found in the Dilithium 3.1 spec ( https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) -- see Table 2. There, importantly, there is a reference to Equation 5, which exactly reproduces them. Uf you look at its derivation and surrounding text, Equation 5 is only claimed to be an approximate "probability that Step 21 passes"; so it doesn't even claim to account for the hint (omega) rejection on Step 24 of Dilithium 3.1 spec.
By accounting for all sources of rejection/repeat (derivation omitted here, but it still involves some distributional assumptions), I arrive at repeat rates {4.358, 5.137, 3.905}. These match Hanno's experiments with the given precision. The unaccounted-for omega hint rejection (Line 28 of Algorithm 7 in FIPS 204) causes most of the gap with reality; the rest is approximation error in Equation 5.
ps. While both (Alg 7, FIPS 204) Line 23 checks contribute substantially to the rejection probability, and this hint rejection (Line 28) contributes (order of magnitude) ~1%, the fourth condition (Also on Line 28), ‖ct₀‖∞ ≥ γ₂, practically never fires for ML-DSA-65 and ML-DSA-87. For ML-DSA-44, the probability of this type of rejection is something like 7*10^-9.
Mike Hamburg & Co. already observed this in March 2024. He did a gazillion measurements: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/G8Zf0hC-uu0/m/eUK_Apm4AQAJ
Cheers,
-markku
--
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 visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/LO4P123MB512139063B4B44166E7AE3B9E6FA2%40LO4P123MB5121.GBRP123.PROD.OUTLOOK.COM.
Sophie Schmieg
12:29 PM (10 hours ago) 12:29 PM
to Markku-Juhani O. Saarinen, Becker, Hanno, pqc-...@list.nist.gov
As an explanation on the likely cause for this oversight, these two rejection reasons are cryptographically very different. The rejection in line 23 is necessary for ML-DSA to be a secure algorithm, as not rejecting here would leak information about the private key. The line 28 rejection on the other hand is done out of convenience, to enable the public key compression, but is not strictly necessary for a secure algorithm (you merely can't encode the resulting signatures). So I presume what happened was that the number for the security analysis somehow got reused for the number of actual rejections, even though that number also has to account for the compression related failures.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qnxWVkuiZBDh_R_aZZRdNgD1MZOAtdiTjeG53a0JX22pQ%40mail.gmail.com.
D. J. Bernstein
4:58 PM (5 hours ago) 4:58 PM
to pqc-...@list.nist.gov
Rule #2 in NASA's "Rules for developing safety critical code" says the
following: "All loops must have a fixed upper-bound. It must be
trivially possible for a checking tool to _prove_ statically that a
preset upper-bound on the number of iterations of a loop cannot be
exceeded." The same rule appears in other coding requirements and
testing tools---see, e.g., MISRA C requiring "well-formed" loops where a
loop counter is tested against a preset limit.
I've commented before on how poorly designed these rules are (see, e.g.,
https://web-backend.simula.no/sites/default/files/publications/Simula.SE.331.pdf)
and on ways around the rules: invoke waiver procedures; use at most
123456789123456789ULL iterations. But the reality is that some
implementors will truncate the ML-DSA signing loop at some much smaller
limit, _even if_ they see that NIST recommends against doing so.
Some of the implementors will end up with a wrong limit---for example,
they'll mistakenly copy a number from the wrong place (as NIST seems to
have done here), or they'll base the number on some inadequate tests, or
they'll simply have the number spoiled by a typo.
This process can produce many different failure probabilities---for
example, maybe it ends up with failure probability ~1/1000 for a key
used billions of times. Sometimes an implementation will have a test
that catches this, but let's think about all the other implementations.
Maybe some programmers will raise an exception for the application, but
the simplest way of inserting a limit into the loop will end up issuing
a signature that should have been rejected.
Presumably some feasible number of those signatures will give away the
secret key, since such rejection is advertised as the primary defense
against https://link.springer.com/article/10.1007/s00145-008-9031-0
etc., although maybe there's some reason that such attacks don't work in
the case of ML-DSA.
Have there been any papers studying these attacks in the case of ML-DSA?
FIPS 204 doesn't provide any citations when it says that release of an
invalid ML-DSA signature "would leak information about the private key".
Analogy: The CRYSTALS team announced in January 2018 that both of the
Dilithium implementations had a bug that "can easily be exploited to
recover the secret key"; but they provided no justification for this
claim of easy secret-key recovery. https://cr.yp.to/papers.html#mldsa
now reports a demo of efficient recovery of a _portion_ of the secret
key given an analogous ML-DSA bug; the demo also uses that portion to
efficiently forge signatures; but the forgery part involves looking at
ML-DSA details. Presumably something similar would also apply to the
original version of Dilithium, but this still wouldn't justify the
January 2018 key-recovery claim. We've seen other claims of Dilithium
leaks for which the response was that those leaks don't matter. It's
_plausible_ that FIPS 204 is correct in claiming that invalid signatures
leak information and, more to the point, leading the reader to think
that this is a problem for ML-DSA, but FIPS 204 doesn't say "presumably"
and doesn't cite the supposed basis for what it does claim.
On the flip side, I also didn't notice any statement in FIPS 204 along
the lines of "Here's a theorem showing that rejection _doesn't_ leak
information". Have there been any cryptanalysis papers looking at what
exactly rejection reveals for ML-DSA?
I also have two simple yes/no questions specifically for NIST. Someone
who says he "was NIST's lattice cryptographer" wrote in
https://web.archive.org/web/20260630121205/mailarchive.ietf.org/arch/msg/tls/nVeE4qhVAnLCOfGZcNloENNF34Q/
that "ML-KEM was fully vetted" during "the NIST PQC process". I'd think
many readers will understand this to be a statement of NIST's position,
and from context as also applying to ML-DSA. Does NIST in fact claim
that ML-KEM was fully vetted during the NIST PQC process? Does NIST
claim that ML-DSA was fully vetted during the NIST PQC process?
---D. J. Bernstein
following: "All loops must have a fixed upper-bound. It must be
trivially possible for a checking tool to _prove_ statically that a
preset upper-bound on the number of iterations of a loop cannot be
exceeded." The same rule appears in other coding requirements and
testing tools---see, e.g., MISRA C requiring "well-formed" loops where a
loop counter is tested against a preset limit.
I've commented before on how poorly designed these rules are (see, e.g.,
https://web-backend.simula.no/sites/default/files/publications/Simula.SE.331.pdf)
and on ways around the rules: invoke waiver procedures; use at most
123456789123456789ULL iterations. But the reality is that some
implementors will truncate the ML-DSA signing loop at some much smaller
limit, _even if_ they see that NIST recommends against doing so.
Some of the implementors will end up with a wrong limit---for example,
they'll mistakenly copy a number from the wrong place (as NIST seems to
have done here), or they'll base the number on some inadequate tests, or
they'll simply have the number spoiled by a typo.
This process can produce many different failure probabilities---for
example, maybe it ends up with failure probability ~1/1000 for a key
used billions of times. Sometimes an implementation will have a test
that catches this, but let's think about all the other implementations.
Maybe some programmers will raise an exception for the application, but
the simplest way of inserting a limit into the loop will end up issuing
a signature that should have been rejected.
Presumably some feasible number of those signatures will give away the
secret key, since such rejection is advertised as the primary defense
against https://link.springer.com/article/10.1007/s00145-008-9031-0
etc., although maybe there's some reason that such attacks don't work in
the case of ML-DSA.
Have there been any papers studying these attacks in the case of ML-DSA?
FIPS 204 doesn't provide any citations when it says that release of an
invalid ML-DSA signature "would leak information about the private key".
Analogy: The CRYSTALS team announced in January 2018 that both of the
Dilithium implementations had a bug that "can easily be exploited to
recover the secret key"; but they provided no justification for this
claim of easy secret-key recovery. https://cr.yp.to/papers.html#mldsa
now reports a demo of efficient recovery of a _portion_ of the secret
key given an analogous ML-DSA bug; the demo also uses that portion to
efficiently forge signatures; but the forgery part involves looking at
ML-DSA details. Presumably something similar would also apply to the
original version of Dilithium, but this still wouldn't justify the
January 2018 key-recovery claim. We've seen other claims of Dilithium
leaks for which the response was that those leaks don't matter. It's
_plausible_ that FIPS 204 is correct in claiming that invalid signatures
leak information and, more to the point, leading the reader to think
that this is a problem for ML-DSA, but FIPS 204 doesn't say "presumably"
and doesn't cite the supposed basis for what it does claim.
On the flip side, I also didn't notice any statement in FIPS 204 along
the lines of "Here's a theorem showing that rejection _doesn't_ leak
information". Have there been any cryptanalysis papers looking at what
exactly rejection reveals for ML-DSA?
I also have two simple yes/no questions specifically for NIST. Someone
who says he "was NIST's lattice cryptographer" wrote in
https://web.archive.org/web/20260630121205/mailarchive.ietf.org/arch/msg/tls/nVeE4qhVAnLCOfGZcNloENNF34Q/
that "ML-KEM was fully vetted" during "the NIST PQC process". I'd think
many readers will understand this to be a statement of NIST's position,
and from context as also applying to ML-DSA. Does NIST in fact claim
that ML-KEM was fully vetted during the NIST PQC process? Does NIST
claim that ML-DSA was fully vetted during the NIST PQC process?
---D. J. Bernstein
Kris Kwiatkowski
7:49 PM (3 hours ago) 7:49 PM
to pqc-...@list.nist.gov
Hi all,
I've run an empirical test with PQShield's PQCryptoLib and can
confirm Hanno's measurements. Average number of executions of
the rejection sampling loop:
ML-DSA-44: 4.35566
ML-DSA-65: 5.13904
ML-DSA-87: 3.90502
These are very close to Hanno's figures (4.36, 5.14, 3.91) and
consistent with the explanation that the FIPS 204 values only
account for the check on L23 of Algorithm 7, while the follow-up
check on L28 increases the overall rejection rate.
All the best,
Kris
Reply all
Reply to author
Forward
0 new messages