Security: BoringSSL bn_mod_add_consttime invalid result
Reported by
guidovra...@gmail.com,
Jul 20
|
|||||
Issue description
VULNERABILITY DETAILS
bn_mod_add_consttime() in BoringSSL computes an invalid value for certain input.
It is unclear whether this is actually a security issue, because it involves a negative number.
Nonetheless, code depending on it, such as code that calls BN_mod_add_quick(), is prone to bugs.
VERSION
Chrome Version: Not applicable
Operating System: Not applicable
BoringSSL: latest Git checkout
REPRODUCTION CASE
Compile the following with BoringSSL (libcrypto.a)
#include <openssl/bn.h>
int main(void)
{
BIGNUM *A = BN_new();
BIGNUM *B = BN_new();
BIGNUM *C = BN_new();
BIGNUM *D = BN_new();
BN_CTX* ctx = BN_CTX_new();
BN_dec2bn(&A, "-555033333333333333333333333333333303333333335555533555555555555555555555555555555555555555555555555");
BN_dec2bn(&B, "2555555555555555555555555055503333333333333333333333333333335555555555555555555555555555555555555555");
BN_dec2bn(&C, "2555555555555555555555555555555555555555555555555555555555555555555555555555555555365550333555333333");
BN_dec2bn(&D, "7333333330000000000000000000000000000500000000000000000000000000333333333333333333333333333333333333");
int ret = bn_mod_add_consttime(A, B, C, D, ctx);
printf("ret is %d\n", ret);
printf("result is %s\n", BN_bn2dec(A));
}
,
Jul 20
bn_mod_add_consttime is documented to only work with non-negative numbers. Did you find that this is called with negative values anywhere? (Perhaps this is worth an assert in BN_mod_add_quick to catch any mistakes? This is really David's area these days.)
,
Jul 20
Indeed. bn_mod_add_consttime and BN_mod_add_quick assume the input is fully reduced: // BN_mod_add_quick acts like |BN_mod_add| but requires that |a| and |b| be // non-negative and less than |m|. // bn_mod_add_consttime acts like |BN_mod_add_quick| but takes a |BN_CTX|. OpenSSL likewise has a comment on BN_mod_add_quick: /* * BN_mod_add variant that may be used if both a and b are non-negative and * less than m */ I see I forgot to add the same sentence to bn_mod_add_words but that was the intent. This function is kind of useless otherwise. The whole point is that modular addition of two fully-reduced inputs needs a conditional subtraction, which is easy to make constant-time. If the inputs are negative, the fixup step is in the wrong direction. A fully general implementation must even resort to division, which is hard to do efficiently in constant-time. (Note BN_div is *not* constant-time, even the BN_FLG_CONSTTIME path.) In general, constant-time algorithms very rarely tolerate unbounded general integers. An assert SGTM, though yeah I'd like to know if there is a particular caller you're thinking of. If code within BoringSSL does it, that's certainly a bug. Note nothing in BoringSSL calls BN_mod_add_quick at all these days, though other ones are certainly called. Such asserts may be good for OpenSSL too, though I'll note their ECDSA code actually very slightly violates these bounds because they don't do this step: https://boringssl.googlesource.com/boringssl/+/master/crypto/fipsmodule/ecdsa/ecdsa.c#91 It's not strictly necessary as the natural implementation of ECDSA tolerates it, but it does violate the usual preconditions.
,
Jul 20
I replied a couple of times by e-mail to this thread but apparently the messages didn't come through. I found this with my bignum fuzzer, which makes sure that the 3 input BN's adhere to the constraints (eg. no negatives) before calling BN_mod_add_quick: https://github.com/guidovranken/bignum-fuzzer/blob/master/modules/openssl/operations.c#L136 The actual bug is that if the *result* BN is negative (which is 'A' in my PoC), this influences the computation! It should not matter what the value of the result BN is. PS. I will setup BoringSSL bignum fuzzing on oss-fuzz shortly. Which e-mail addresses should be CC'ed to? Thanks Guido
,
Jul 20
Ooohhh, I see. Sorry, I misunderstood. Yes, I agree that's a bug. We should be clearing that bit. Thanks! Looking through callers within BoringSSL and the one project that calls them outside, I believe this case never comes up. (Negative numbers don't really turn up in cryptography; a better-designed BIGNUM would not even have the bit at all, but we're stuck with the existing OpenSSL BIGNUM API.) > PS. I will setup BoringSSL bignum fuzzing on oss-fuzz shortly. Which e-mail addresses should be CC'ed to? That sounds great. Thanks! There should already be a BoringSSL project on oss-fuzz. You can just take the CC list from there.
,
Jul 20
No problem :). Thank you. You may close the report.
,
Jul 20
Well, not until I've fixed it! :-P https://boringssl-review.googlesource.com/c/boringssl/+/29944
,
Jul 20
,
Jul 20
The following revision refers to this bug: https://boringssl.googlesource.com/boringssl/+/20b6a4e2a18e6a2c961ae0cd9945b69ad42dc64e commit 20b6a4e2a18e6a2c961ae0cd9945b69ad42dc64e Author: David Benjamin <davidben@google.com> Date: Fri Jul 20 23:45:06 2018 Clear r->neg in bn_mod_{add,sub}_consttime. Otherwise, if the output BIGNUM was previously negative, we'd incorrectly give a negative result. Thanks to Guide Vranken for reporting this issue! Fortunately, this does not appear to come up in any existing caller. This isn't all that surprising as negative numbers never really come up in cryptography. Were it not for OpenSSL historically designing a calculator API, we'd just delete the bit altogether. :-( Bug: chromium:865924 Change-Id: I28fdc986dfaba3e38435b14ebf07453d537cc60a Reviewed-on: https://boringssl-review.googlesource.com/29944 Commit-Queue: David Benjamin <davidben@google.com> Commit-Queue: Adam Langley <agl@google.com> Reviewed-by: Adam Langley <agl@google.com> CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> [modify] https://crrev.com/20b6a4e2a18e6a2c961ae0cd9945b69ad42dc64e/crypto/fipsmodule/bn/bn_test.cc [modify] https://crrev.com/20b6a4e2a18e6a2c961ae0cd9945b69ad42dc64e/crypto/fipsmodule/bn/div.c
,
Jul 20
|
|||||
►
Sign in to add a comment |
|||||
Comment 1 by cthomp@chromium.org
, Jul 20Owner: agl@chromium.org