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

[Eric Biggers <ebiggers@kernel.org>]

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.  This makes the reduction more symmetric so
that the range of supported unreduced products is roughly symmetric.
I'll update the comments to clarify this.

> > +	for (int m = 0, len = 128; len >= 1; len /= 2) {
> 
> Can you put "int m = 0" outside of the for-statement?  I know putting it
> inside saves a line or two, but 'm' is not the loop counter - which it seems
> like it should be by virtue of being listed first.
> 
> > +	for (int m = 256, len = 1; len < 256; len *= 2) {
> 
> Ditto.

Sure.

> 
> > +static const u8 *decode_t1_elem(struct mldsa_ring_elem *out,
> > +				const u8 *t1_encoded)
> 
> I think this is (more or less) pkDecode()?  Can you put something like:
> 
>   * Decode the vector 't1' from the public key.
>   * Reference: FIPS 204 Algorithm 23, sigDecode.
> 
> in the comment before it?

Sure.

> > +/*
> > + * Use @seed to generate a ring element @c with coefficients in {-1, 0, 1},
> > + * exactly @tau of them nonzero.  Reference: FIPS 204 Algorithm 29, SampleInBall
> > + */
> > +static void sample_in_ball(struct mldsa_ring_elem *c, const u8 *seed,
> > +			   size_t seed_len, int tau, struct shake_ctx *shake)
> 
> Should "seed" actually be labelled "rho"?  I know a seed is what it is, but
> the algo description has a different label - and the caller passes it ctilde,
> not rho:-/.

FIPS 204 Algorithm 29 SampleInBall uses the variable rho for the seed,
while also calling it a "seed" in the descriptive text.  However,
elsewhere rho refers specifically to the public key's random seed.  I
think just calling it "seed" makes sense here.

> > +	u8 (*h)[N]; /* The signer's hint vector, length k */
> > +	h = (u8 (*)[N])&ws->z[l];
> 
> C is weird sometimes.

We could make it a 'u8 *', but then we'd have to use array indices like
h[i*k + j] rather than h[i][j].  May be worth it anyway, to avoid the
slightly-unusual syntax.

> > +		/* 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.)

> 
> > +		/* w1Encode(w'_1) */
> > +		w1_pos = 0;
> > ...
> 
> Given you put the decode functions into helpers, don't you want to do that
> with this?

Sure, I'll move the w1Encode part into a helper function.

> > +	if (memcmp(ws->ctildeprime, ctilde, params->ctilde_len) != 0)
> > +		return -EBADMSG;
> 
> Actually, this should return -EKEYREJECTED, not -EBADMSG.

Who/what decided that?  A lot of the crypto code uses -EBADMSG already.
crypto_aead uses it, for example.

> I guess you don't need to use crypto_memneq() as timing doesn't matter.

Correct.

> The maths look okay, I think.  You can add:
> 
> 	Reviewed-by: David Howells <dhowells@redhat.com>

Thanks,

- Eric