| commit | 338f44af3c92ef665bf740a8127a2d69c872b52a | [log] [tgz] |
|---|---|---|
| author | David Benjamin <davidben@google.com> | Sat Oct 11 14:47:59 2025 -0400 |
| committer | Boringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> | Mon Oct 13 16:44:38 2025 -0700 |
| tree | b9dcac50c52aa268a414058ec6b00081decd921b | |
| parent | 2067eac9e25332fa983c3d5f1bd1b00fa4f467fc [diff] |
Fix a bug when BN_mod_sqrt is called on very annoying primes https://boringssl-review.googlesource.com/c/boringssl/+/70813 introduced a bug in the error-handling at the BN_usub call. (It was missing a `!`.) The bug is triggered when computing BN_mod_sqrt over a prime p such that: - p is 1 mod 8 - The least quadratic non-residue is 22 or higher Then BN_mod_sqrt might fail with some probability (dependent on how far below p is from a power of two). The trivial fix is to add the `!` back but, while I'm here, switch to BN_rand_range_ex as suggested by Theo Buehler. This has no impact on any cryptography. Modular square roots are used to decode compressed coordinates. There, the only annoying prime is P-224. P-224 which is merely *annoying* (1 mod 8) and not *very annoying* (last quadratic non-residue is big). It can only impact callers who were calling into us to compute some math function for some reason. (Were one to construct an arbitrary elliptic curve that hit this, the failure mode would just be that we might reject a public key that we should have accepted.) What's happening here is that modular square roots easy when p is 3 mod 4 or 5 mod 8, but they're very hard when 1 mod 8. If 1 mod 8, we must use Tonelli/Shanks. Part of Tonelli/Shanks requires that we find some quadratic non-residue y. BN_mod_sqrt tries y = 2 up to y = 21 before giving up and trying random values. The bug was in that random value case. Thanks to Alex Gaynor for reporting an input that tripped this! It seems that input was picked as the first prime with a high enough least quadratic non-residue. I added some tests also with another modulus, 0x2e3a719, which I believe was the 1 mod 8 prime under 100,000,000 with the largest least quadratic non-residue. Also it happened that 0x7deb1 was just under a power of two, so 0x2e3a719 trips the bug more reliably. (It's unfortunate that this is public API and that rust-openssl binds it. This function is only in libcrypto for EC compressed coordinates, but it's not the right function for it anyway. EC code tries to avoid heap-allocated BIGNUMs and should be specialized. Were it not for P-224, we would only need the 3 mod 4 case. With P-224, we can at least know ahead of time that y = 11 and not bother looking for a quadratic non-residue. Ah well.) Change-Id: I6fe97ffe239a03557ed7ff5417bed23f318e8ff4 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/82788 Reviewed-by: Lily Chen <chlily@google.com> Auto-Submit: David Benjamin <davidben@google.com> Commit-Queue: Lily Chen <chlily@google.com>
BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.
Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.
Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.
BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.
Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.
Project links:
To file a security issue, use the Chromium process and mention in the report this is for BoringSSL. You can ignore the parts of the process that are specific to Chromium/Chrome.
There are other files in this directory which might be helpful: