Split BN_uadd into a bn_uadd_fixed.
This is to be used in constant-time RSA CRT.
Bug: 233
Change-Id: Ibade5792324dc6aba38cab6971d255d41fb5eb91
Reviewed-on: https://boringssl-review.googlesource.com/25286
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/add.c b/crypto/fipsmodule/bn/add.c
index cc74510..ece7867 100644
--- a/crypto/fipsmodule/bn/add.c
+++ b/crypto/fipsmodule/bn/add.c
@@ -100,61 +100,38 @@
return ret;
}
-int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
- int max, min, dif;
- BN_ULONG *ap, *bp, *rp, carry, t1, t2;
- const BIGNUM *tmp;
-
+int bn_uadd_fixed(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
+ // Widths are public, so we normalize to make |a| the larger one.
if (a->width < b->width) {
- tmp = a;
+ const BIGNUM *tmp = a;
a = b;
b = tmp;
}
- max = a->width;
- min = b->width;
- dif = max - min;
+ int max = a->width;
+ int min = b->width;
if (!bn_wexpand(r, max + 1)) {
return 0;
}
+ r->width = max + 1;
- r->width = max;
-
- ap = a->d;
- bp = b->d;
- rp = r->d;
-
- carry = bn_add_words(rp, ap, bp, min);
- rp += min;
- ap += min;
- bp += min;
-
- if (carry) {
- while (dif) {
- dif--;
- t1 = *(ap++);
- t2 = t1 + 1;
- *(rp++) = t2;
- if (t2) {
- carry = 0;
- break;
- }
- }
- if (carry) {
- // carry != 0 => dif == 0
- *rp = 1;
- r->width++;
- }
+ BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
+ for (int i = min; i < max; i++) {
+ // |r| and |a| may alias, so use a temporary.
+ BN_ULONG tmp = carry + a->d[i];
+ carry = tmp < a->d[i];
+ r->d[i] = tmp;
}
- if (dif && rp != ap) {
- while (dif--) {
- // copy remaining words if ap != rp
- *(rp++) = *(ap++);
- }
- }
+ r->d[max] = carry;
+ return 1;
+}
- r->neg = 0;
+int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
+ if (!bn_uadd_fixed(r, a, b)) {
+ return 0;
+ }
+ bn_set_minimal_width(r);
return 1;
}
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index b09388a..a8baf4c 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -367,6 +367,10 @@
// to increase without bound. The corresponding public API functions minimize
// their outputs to avoid regressing calculator consumers.
+// bn_uadd_fixed behaves like |BN_uadd|, but it pessimally sets
+// |r->width| = |a->width| + |b->width| + 1.
+int bn_uadd_fixed(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
+
// bn_mul_fixed behaves like |BN_mul|, but it rejects negative inputs and
// pessimally sets |r->width| to |a->width| + |b->width|, to avoid leaking
// information about |a| and |b|.