Re: [PATCH 1/4] lib/crypto: Add ML-DSA verification support

[Eric Biggers <ebiggers@kernel.org>]

On Fri, Nov 21, 2025 at 12:41:41PM +0000, David Howells wrote:
> Eric Biggers <ebiggers@kernel.org> wrote:
> 
> > On Thu, Nov 20, 2025 at 01:55:18PM +0000, David Howells wrote:
> > > Eric Biggers <ebiggers@kernel.org> wrote:
> > > 
> > > > +	/* Compute d = (c mod 2^32) * (q^-1 mod 2^32). */
> > > > +	s32 d = (s32)c * QINV_MOD_R;
> > > 
> > > Hmmm...  is "(s32)c" actually "(c mod 2^32)"?  Should that be:
> > > 
> > > 	u32 d = (u32)c * QINV_MOD_R;
> > > 
> > > This is followed up by casting 'd' to "s64".  I don't think that should
> > > sign-extend it, but...
> > 
> > It selects the representative in the range [INT32_MIN, INT32_MAX],
> > rather than the representative in the range [0, UINT32_MAX].  The sign
> > extension is intentional.
> 
> I'm concerned about the basis on which it becomes positive or negative.  It
> looks like the sign bit ends up being chosen arbitrarily.

Right, it's unrelated to the sign of the s64 value, unless the s64 value
happens to fit in a s32.  And that's okay: the worst-case analysis,
which considers the largest possible absolute value that can be built
up, assumes the signs happen to match repeatedly.

By the way, lest you think I'd doing anything particularly novel here,
the Dilithium reference code also uses this same (very-nearly-symmetric)
Montgomery reduction formula including the sign extension, where it made
its way into leancrypto and your patchset too.  It also appears in FIPS
204 as Algorithm 49, MontgomeryReduce.  There are other ways to
implement this stuff, but they would be less efficient.

However, unfortunately neither source explains it properly, and they
actually provide incorrect information.  The comment in the reference
code says the the input can be in "-2^{31}Q <= a <= Q*2^31", which isn't
quite correct; the upper bound is actually exclusive.  In my code, I
correctly document the upper bound as being exclusive.

FIPS 204 documents the same incorrect interval, but then sort of gets
around it by only claiming that the output is less than 2q in absolute
value (rather than q) and also by not clarifying whether sign extension
is done.  They may have thought that sign extension shouldn't be done,
as you seem to have thought.  Either way, their explanation is
misleading.  The very-nearly-symmetric version that produces an output
less than q in absolute value is the logical version when working with
signed values, and it seems to be what the Dilithium authors intended.

Anyway, it's clear that my code comments still didn't explain it
properly either, so I'll work on that.

> > > > +		/* Reduce to [0, q), then tmp = w'_1 = UseHint(h, w'_Approx) */
> > > 
> > > Bracket mismatch.  "[0, q]"
> > 
> > It's intentional, since it denotes a mathematical range.  Elsewhere I
> > used the words "the range" explicitly, so I'll add that above too.  (Or
> > maybe reword it differently.)
> 
> I meant you have an opening square bracket and a closing round bracket in
> "[0, q)".

That means the lower end is inclusive and the upper end is exclusive.
We're taking mod q, so we do *not* want q to be included.

I could write it another way that wouldn't assume familiarity with open
interval notation, like [0, q - 1] or 0 <= val < q.

- Eric