bn/asm/x86_64-mont5.pl: fix carry bug in bn_sqr8x_internal.
CVE-2017-3732
(Imported from upstream's 3f4bcf5bb664b47ed369a70b99fac4e0ad141bb3 and
3e7a496307ab1174c1f8f64eed4454c1c9cde1a8.)
Change-Id: I40255fdf4184e3b919758a72c3d3a7486d91ff65
Reviewed-on: https://boringssl-review.googlesource.com/13360
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/bn/asm/x86_64-mont5.pl b/crypto/bn/asm/x86_64-mont5.pl
index 61dd902..61fde2d 100755
--- a/crypto/bn/asm/x86_64-mont5.pl
+++ b/crypto/bn/asm/x86_64-mont5.pl
@@ -1852,6 +1852,7 @@
.align 32
.L8x_tail_done:
+ xor %rax,%rax
add (%rdx),%r8 # can this overflow?
adc \$0,%r9
adc \$0,%r10
@@ -1859,10 +1860,8 @@
adc \$0,%r12
adc \$0,%r13
adc \$0,%r14
- adc \$0,%r15 # can't overflow, because we
- # started with "overhung" part
- # of multiplication
- xor %rax,%rax
+ adc \$0,%r15
+ adc \$0,%rax
neg $carry
.L8x_no_tail:
@@ -3248,6 +3247,7 @@
.align 32
.Lsqrx8x_tail_done:
+ xor %rax,%rax
add 24+8(%rsp),%r8 # can this overflow?
adc \$0,%r9
adc \$0,%r10
@@ -3255,10 +3255,8 @@
adc \$0,%r12
adc \$0,%r13
adc \$0,%r14
- adc \$0,%r15 # can't overflow, because we
- # started with "overhung" part
- # of multiplication
- mov $carry,%rax # xor %rax,%rax
+ adc \$0,%r15
+ adc \$0,%rax
sub 16+8(%rsp),$carry # mov 16(%rsp),%cf
.Lsqrx8x_no_tail: # %cf is 0 if jumped here
@@ -3273,7 +3271,7 @@
adc 8*5($tptr),%r13
adc 8*6($tptr),%r14
adc 8*7($tptr),%r15
- adc %rax,%rax # top-most carry
+ adc \$0,%rax # top-most carry
mov 32+8(%rsp),%rbx # n0
mov 8*8($tptr,%rcx),%rdx # modulo-scheduled "%r8"
diff --git a/crypto/bn/bn_test.cc b/crypto/bn/bn_test.cc
index 8f93ad0..a152cdf 100644
--- a/crypto/bn/bn_test.cc
+++ b/crypto/bn/bn_test.cc
@@ -515,6 +515,54 @@
return true;
}
+static bool TestModSquare(FileTest *t, BN_CTX *ctx) {
+ bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A");
+ bssl::UniquePtr<BIGNUM> m = GetBIGNUM(t, "M");
+ bssl::UniquePtr<BIGNUM> mod_square = GetBIGNUM(t, "ModSquare");
+ if (!a || !m || !mod_square) {
+ return false;
+ }
+
+ bssl::UniquePtr<BIGNUM> a_copy(BN_new());
+ bssl::UniquePtr<BIGNUM> ret(BN_new());
+ if (!ret || !a_copy ||
+ !BN_mod_mul(ret.get(), a.get(), a.get(), m.get(), ctx) ||
+ !ExpectBIGNUMsEqual(t, "A * A (mod M)", mod_square.get(), ret.get()) ||
+ // Repeat the operation with |a_copy|.
+ !BN_copy(a_copy.get(), a.get()) ||
+ !BN_mod_mul(ret.get(), a.get(), a_copy.get(), m.get(), ctx) ||
+ !ExpectBIGNUMsEqual(t, "A * A_copy (mod M)", mod_square.get(),
+ ret.get())) {
+ return false;
+ }
+
+ if (BN_is_odd(m.get())) {
+ // Reduce |a| and test the Montgomery version.
+ bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new());
+ bssl::UniquePtr<BIGNUM> a_tmp(BN_new());
+ if (!mont || !a_tmp ||
+ !BN_MONT_CTX_set(mont.get(), m.get(), ctx) ||
+ !BN_nnmod(a_tmp.get(), a.get(), m.get(), ctx) ||
+ !BN_to_montgomery(a_tmp.get(), a_tmp.get(), mont.get(), ctx) ||
+ !BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_tmp.get(), mont.get(),
+ ctx) ||
+ !BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx) ||
+ !ExpectBIGNUMsEqual(t, "A * A (mod M) (Montgomery)",
+ mod_square.get(), ret.get()) ||
+ // Repeat the operation with |a_copy|.
+ !BN_copy(a_copy.get(), a_tmp.get()) ||
+ !BN_mod_mul_montgomery(ret.get(), a_tmp.get(), a_copy.get(), mont.get(),
+ ctx) ||
+ !BN_from_montgomery(ret.get(), ret.get(), mont.get(), ctx) ||
+ !ExpectBIGNUMsEqual(t, "A * A_copy (mod M) (Montgomery)",
+ mod_square.get(), ret.get())) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
static bool TestModExp(FileTest *t, BN_CTX *ctx) {
bssl::UniquePtr<BIGNUM> a = GetBIGNUM(t, "A");
bssl::UniquePtr<BIGNUM> e = GetBIGNUM(t, "E");
@@ -649,6 +697,7 @@
{"Product", TestProduct},
{"Quotient", TestQuotient},
{"ModMul", TestModMul},
+ {"ModSquare", TestModSquare},
{"ModExp", TestModExp},
{"Exp", TestExp},
{"ModSqrt", TestModSqrt},
diff --git a/crypto/bn/bn_tests.txt b/crypto/bn/bn_tests.txt
index 46c788f..c53eb23 100644
--- a/crypto/bn/bn_tests.txt
+++ b/crypto/bn/bn_tests.txt
@@ -9888,6 +9888,16 @@
M = d78af684e71db0c39cff4e64fb9db567132cb9c50cc98009feb820b26f2ded9b91b9b5e2b83ae0ae4eb4e0523ca726bfbe969b89fd754f674ce99118c3f2d1c5d81fdc7c54e02b60262b241d53c040e99e45826eca37a804668e690e1afc1ca42c9a15d84d4954425f0b7642fc0bd9d7b24e2618d2dcc9b729d944badacfddaf
+# ModSquare tests.
+#
+# These test vectors satisfy A * A = ModSquare (mod M) and 0 <= ModSquare < M.
+
+# Regression test for CVE-2017-3732.
+ModSquare = fffffffdfffffd01000009000002f6fffdf403000312000402f3fff5f602fe080a0005fdfafffa00010001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000002000002fefffff7fffffd07000109fdfffef3fffdfd06000405ff00fdfbfffe00010001
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000ffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffff00000000
+M = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000ffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffff
+
+
# ModExp tests.
#
# These test vectors satisfy A ^ E = ModExp (mod M) and 0 <= ModExp < M.
