Fix BN_mod_exp_consttime so it does not produce unreduced result by t8m · Pull Request #18510 · openssl/openssl

t8m · 2022-06-09T14:24:18Z

The BN_mod_exp_consttime can produce result == modulus instead of 0. This was reported by @guidovranken.

Original fix was developed by @davidben for BoringSSL.

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]>

Inspired by BoringSSL fix by David Benjamin.

t8m · 2022-06-09T14:24:51Z

See also https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315

davidben · 2022-06-09T14:45:50Z

        }

-        ret = bn_from_montgomery(tmp.d, tmp.d, NULL, np, n0, top);
-        tmp.top = top;


You probably want to keep this line (tmp.top = top). That was a mistake in my original patch. The line isn't actually necessary in BoringSSL, due to how we solved #6640, but dropping it was a little sloppy on my part. I'm not sure if, for you all, it's a matter of sloppiness or actual necessity, since you haven't solved #6640 but have some partial "fixed top" bits. (Would need to dig into that.)

This was the follow-up that I did in BoringSSL, but that bn_resize_words in that CL is part of some infrastructure we did for #6640. Probably easiest for you all to put tmp.top back in. (It's because the most of this code just uses tmp as a random array, with implicit bounds, and so nothing actually ensures tmp.top matches the array bounds.
https://boringssl.googlesource.com/boringssl/+/77dc23983f004056dbcd95ae96922be107365190%5E%21/#F0

davidben · 2022-06-09T14:52:15Z

+}
+
+static ossl_inline BN_ULONG bn_reduce_once_in_place(BN_ULONG *r,
+                                                    BN_ULONG carry,


carry is always zero in the places you all call this one. (We have a carry argument because we actually use this function all over the place. It's because 2*m might have one bit more than m and not fit in num. It shows up in Montgomery reduction, modular addition, and setting up the ECDSA digest. Dunno if you were intending to do the same.)

Well, not any time soon, but at some point we might want to if we decide to fix the BN const time handling.

davidben · 2022-06-09T14:56:24Z

    from_words52(res2, factor_size, rr2_red);

+    bn_reduce_once_in_place(res1, /*carry=*/0, m1, storage, factor_size);
+    bn_reduce_once_in_place(res2, /*carry=*/0, m2, storage, factor_size);


NB: BoringSSL doesn't have this code, so I don't actually know whether this is the correct fix for it or what it's doing. The reference to both "AMM" and "RSAZ" (which uses NRMM, not AMM) is a little odd. This may warrant extra review make sure this fix is necessary/sufficient.

Yeah, someone who fully understands the math should verify if this is needed. @amatyuko-intc perhaps?

These two lines is causing #18625.

davidben · 2022-06-09T14:57:42Z

    /* from Montgomery */
    rsaz_512_mul_by_one(result, temp, m, k0);

+    bn_reduce_once_in_place(result, /*carry=*/0, m, storage, 8);


BoringSSL doesn't have this code---we don't consider RSA-1024 worth optimizing for these days---so I don't know off-hand whether it is correct. But supposing it's the same algorithm as rsaz_1024 (RSA-2048), the fix looks right.

The 512 bit testcase was actually failing without it and passing with it. So IMO this is right.

Yeah, question is whether it is sufficient. This fix assumes the result is bounded by 2m, which depends on what the code is doing. (I read through papers and asm to develop the fix for the bits we cared about.) But, yeah, this fix is almost certainly right since I'm pretty sure they're doing the same thing at different sizes. Less sure about ossl_rsaz_mod_exp_avx512_x2, but I haven't looked at what it's doing.

…duction.

t8m · 2022-06-09T15:13:21Z

Thanks @davidben for the review

openssl-machine · 2022-06-16T02:00:19Z

This pull request is ready to merge

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from #18510)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from #18510)

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from #18510) (cherry picked from commit 0ae365e)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from #18510) (cherry picked from commit 6d702ce)

t8m · 2022-06-16T13:32:40Z

Merged to master and 3.0 branches. Thank you for the reviews.

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl/openssl#18510)

This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime would sometimes return m, the modulus, when it should have returned zero. Thanks to Guido Vranken for reporting it. It is only a partial fix because the same bug also exists in the "rsaz" codepath. The bug only affects zero outputs (with non-zero inputs), so we believe it has no security impact on our cryptographic functions. The fx is to delete lowercase bn_from_montgomery altogether, and have the mont5 path use the same BN_from_montgomery ending as the non-mont5 path. This only impacts the final step of the whole exponentiation and has no measurable perf impact. See the original BoringSSL commit https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315 for further analysis. Original-author: David Benjamin <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl#18510)

Inspired by BoringSSL fix by David Benjamin. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from openssl#18510)

t8m added 2 commits June 9, 2022 12:34

Add an extra reduction step to RSAZ mod_exp implementations

a1110cb

Inspired by BoringSSL fix by David Benjamin.

github-actions Bot added the severity: fips change The pull request changes FIPS provider sources label Jun 9, 2022

t8m mentioned this pull request Jun 9, 2022

Fix BN_mod_exp_consttime so it does not produce unreduced result [1.1.1] #18511

Closed

t8m removed the branch: 1.1.1 Applies to OpenSSL_1_1_1-stable branch (EOL) label Jun 9, 2022

davidben reviewed Jun 9, 2022

View reviewed changes

fixup! Always end BN_mod_exp_mont_consttime with normal Montgomery re…

bd86cd2

…duction.

fixup! Add an extra reduction step to RSAZ mod_exp implementations

0a852b4

mattcaswell approved these changes Jun 14, 2022

View reviewed changes

mattcaswell removed the approval: otc review pending label Jun 14, 2022

paulidale approved these changes Jun 15, 2022

View reviewed changes

paulidale added approval: done This pull request has the required number of approvals and removed approval: review pending This pull request needs review by a committer labels Jun 15, 2022

openssl-machine added approval: ready to merge The 24 hour grace period has passed, ready to merge and removed approval: done This pull request has the required number of approvals labels Jun 16, 2022

t8m closed this Jun 16, 2022

Uh oh!

Uh oh!

Conversation

t8m commented Jun 9, 2022

Uh oh!

t8m commented Jun 9, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

t8m commented Jun 9, 2022

Uh oh!

openssl-machine commented Jun 16, 2022

Uh oh!

t8m commented Jun 16, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants