[Bug]: sc448_reduce and sc448_muladd only weakly reduce the scalars

[aCinal]

Contact Details

[email protected]

Version

5.7.4

Description

All implementations of sc448_reduce and sc448_muladd in wolfcrypt/src/ge_448.c (three of each) fail to fully reduce the scalar before returning, i.e., bring it into the canonical range [0, L) where L is the group order. Instead, only weak reduction is performed which brings the scalar into the [0, 2L) range. This can lead to WolfSSL producing invalid Ed448 signatures, as canonicity of the response scalar (returned directly from sc448_muladd) is checked during signature verification (see, e.g., ed448_verify_msg_final_with_sha in wolfcrypt/src/ed448.c).

A missing step at the end of both sc448_reduce and sc448_muladd is checking for canonicity of the result and, if not canonical, subtracting L from it. Importantly, this conditional subtraction must be performed in constant-time so as to not leak information about the input values via a side channel (the response, for example, is computed from the secret key and the secret ephemeral value).

This is most easily reproduced with L itself as input. sc448_reduce leaves it unchanged, even though L = 0 (mod L). For sc448_muladd, try computing, e.g., 1 * L + 0 or 2 * L + L.

Reproduction steps

/* Fails for all three implementations of sc448_reduce */
byte input[] = {
    0xf3, 0x44, 0x58, 0xab, 0x92, 0xc2, 0x78, 0x23,
    0x55, 0x8f, 0xc5, 0x8d, 0x72, 0xc2, 0x6c, 0x21,
    0x90, 0x36, 0xd6, 0xae, 0x49, 0xdb, 0x4e, 0xc4,
    0xe9, 0x23, 0xca, 0x7c, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00
};
sc448_reduce(input);
byte expected[57] = {};
assert(0 == memcmp(input, expected, 57));

/* Fails for all three implementations of sc448_muladd */
byte order[] = {
    0xf3, 0x44, 0x58, 0xab, 0x92, 0xc2, 0x78, 0x23,
    0x55, 0x8f, 0xc5, 0x8d, 0x72, 0xc2, 0x6c, 0x21,
    0x90, 0x36, 0xd6, 0xae, 0x49, 0xdb, 0x4e, 0xc4,
    0xe9, 0x23, 0xca, 0x7c, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f,
    0x00
};
byte two[57] = {
    2
};
byte zero[57] = {};
byte result[57];

sc448_muladd(result, two, order, zero);
byte expected[57] = {};
assert(0 == memcmp(result, expected, 57));

Relevant log output

No response

[dgarske]

@SparkiDev will you please review this report? Thank you

[dgarske]

Hi @aCinal ,

Thank you again for the report. I wanted to let you know we are looking into this.

Thanks,
David Garske, wolfSSL

[dgarske]

Hi @aCinal ,

Can you tell us about your project and use of ED448? I'm curious what is driving your choice for using ED448. If you'd like to keep the response confidential please email support at wolfssl dot com.

Thanks,
David Garske, wolfSSL

[philljj]

Hi @aCinal,

Thank you for the report and the reproduction steps; I was able to reproduce this. We will work on this.

Best,
Jordan

[SparkiDev]

Hi @aCinal

I've put up a pull request that I believe fixes this issue: #8276

Could you please check the implementations?

Thanks,
Sean

[aCinal]

Looks good to me. Maybe it is worth documenting in the code (comments) that sc448_reduce only performs weak reduction. This is fine as long as sc448_muladd as well as scalar multiplication routines (ge448_double_scalarmult_vartime and ge448_scalarmult_base) can handle their inputs in non-canonical form (i.e., possibly up to twice the group order exclusive). Then, internally, WolfSSL could still use weakly-reduced scalars and only reduce the response when finalizing the signature, which is exactly your approach in the PR.

Regards,
Adrian

[SparkiDev]

Hi Adrian,

Thanks for confirming the fix!

I've update the comments on the implementation of sc448_reduce and added a comment in the header file.
The code will now go up for review.

Sean