Move some exponentation functions out of the FIPS module BN_exp is never used in cryptography. We never call BN_mod_exp from the library and instead call the specific implementations directly. We never call BN_mod_exp_mont_word. Looks like this was originally added for optimized small generator operations in Diffie-Hellman, but we dropped the optimizations. We consider (non-EC) Diffie-Hellman to be a legacy algorithm. BN_mod_exp2_mont is used in DSA, but we dropped the optimizations (non-EC) DSA is also a legacy algorithm and DSA is not in the FIPS module. Change-Id: I1cf2975a834f1da12f4e7623339739de151a3e1e Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/77447 Commit-Queue: Bob Beck <bbe@google.com> Reviewed-by: Bob Beck <bbe@google.com> Auto-Submit: David Benjamin <davidben@google.com>
diff --git a/build.json b/build.json index b9e8f71..d480382 100644 --- a/build.json +++ b/build.json
@@ -204,6 +204,7 @@ "crypto/blake2/blake2.cc", "crypto/bn/bn_asn1.cc", "crypto/bn/convert.cc", + "crypto/bn/exponentiation.cc", "crypto/buf/buf.cc", "crypto/bytestring/asn1_compat.cc", "crypto/bytestring/ber.cc",
diff --git a/crypto/bn/exponentiation.cc b/crypto/bn/exponentiation.cc new file mode 100644 index 0000000..9942986 --- /dev/null +++ b/crypto/bn/exponentiation.cc
@@ -0,0 +1,190 @@ +// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <openssl/bn.h> + +#include <assert.h> + +#include <openssl/err.h> + +#include "../fipsmodule/bn/internal.h" + + +int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { + int i, bits, ret = 0; + BIGNUM *v, *rr; + + BN_CTX_start(ctx); + if (r == a || r == p) { + rr = BN_CTX_get(ctx); + } else { + rr = r; + } + + v = BN_CTX_get(ctx); + if (rr == NULL || v == NULL) { + goto err; + } + + if (BN_copy(v, a) == NULL) { + goto err; + } + bits = BN_num_bits(p); + + if (BN_is_odd(p)) { + if (BN_copy(rr, a) == NULL) { + goto err; + } + } else { + if (!BN_one(rr)) { + goto err; + } + } + + for (i = 1; i < bits; i++) { + if (!BN_sqr(v, v, ctx)) { + goto err; + } + if (BN_is_bit_set(p, i)) { + if (!BN_mul(rr, rr, v, ctx)) { + goto err; + } + } + } + + if (r != rr && !BN_copy(r, rr)) { + goto err; + } + ret = 1; + +err: + BN_CTX_end(ctx); + return ret; +} + +static int mod_exp_even(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) { + // No cryptographic operations require modular exponentiation with an even + // modulus. We support it for backwards compatibility with any applications + // that may have relied on the operation, but optimize for simplicity over + // performance with straightforward square-and-multiply routine. + int bits = BN_num_bits(p); + if (bits == 0) { + return BN_one(r); + } + + // Make a copy of |a|, in case it aliases |r|. + bssl::BN_CTXScope scope(ctx); + BIGNUM *tmp = BN_CTX_get(ctx); + if (tmp == nullptr || !BN_copy(tmp, a)) { + return 0; + } + + assert(BN_is_bit_set(p, bits - 1)); + if (!BN_copy(r, tmp)) { + return 0; + } + + for (int i = bits - 2; i >= 0; i--) { + if (!BN_mod_sqr(r, r, m, ctx) || + (BN_is_bit_set(p, i) && !BN_mod_mul(r, r, tmp, m, ctx))) { + return 0; + } + } + + return 1; +} + +int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, + BN_CTX *ctx) { + if (m->neg) { + OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); + return 0; + } + if (a->neg || BN_ucmp(a, m) >= 0) { + if (!BN_nnmod(r, a, m, ctx)) { + return 0; + } + a = r; + } + + if (BN_is_odd(m)) { + return BN_mod_exp_mont(r, a, p, m, ctx, NULL); + } + + return mod_exp_even(r, a, p, m, ctx); +} + +int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, + const BN_MONT_CTX *mont) { + BIGNUM a_bignum; + BN_init(&a_bignum); + + int ret = 0; + + // BN_mod_exp_mont requires reduced inputs. + if (bn_minimal_width(m) == 1) { + a %= m->d[0]; + } + + if (!BN_set_word(&a_bignum, a)) { + OPENSSL_PUT_ERROR(BN, ERR_R_INTERNAL_ERROR); + goto err; + } + + ret = BN_mod_exp_mont(rr, &a_bignum, p, m, ctx, mont); + +err: + BN_free(&a_bignum); + + return ret; +} + +int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, + const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, + BN_CTX *ctx, const BN_MONT_CTX *mont) { + BIGNUM tmp; + BN_init(&tmp); + + int ret = 0; + BN_MONT_CTX *new_mont = NULL; + + // Allocate a montgomery context if it was not supplied by the caller. + if (mont == NULL) { + new_mont = BN_MONT_CTX_new_for_modulus(m, ctx); + if (new_mont == NULL) { + goto err; + } + mont = new_mont; + } + + // BN_mod_mul_montgomery removes one Montgomery factor, so passing one + // Montgomery-encoded and one non-Montgomery-encoded value gives a + // non-Montgomery-encoded result. + if (!BN_mod_exp_mont(rr, a1, p1, m, ctx, mont) || + !BN_mod_exp_mont(&tmp, a2, p2, m, ctx, mont) || + !BN_to_montgomery(rr, rr, mont, ctx) || + !BN_mod_mul_montgomery(rr, rr, &tmp, mont, ctx)) { + goto err; + } + + ret = 1; + +err: + BN_MONT_CTX_free(new_mont); + BN_free(&tmp); + + return ret; +}
diff --git a/crypto/fipsmodule/bn/exponentiation.cc.inc b/crypto/fipsmodule/bn/exponentiation.cc.inc index 53081c4..bcf88e5 100644 --- a/crypto/fipsmodule/bn/exponentiation.cc.inc +++ b/crypto/fipsmodule/bn/exponentiation.cc.inc
@@ -70,58 +70,6 @@ #endif // defined(OPENSSL_BN_ASM_MONT5) -int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { - int i, bits, ret = 0; - BIGNUM *v, *rr; - - BN_CTX_start(ctx); - if (r == a || r == p) { - rr = BN_CTX_get(ctx); - } else { - rr = r; - } - - v = BN_CTX_get(ctx); - if (rr == NULL || v == NULL) { - goto err; - } - - if (BN_copy(v, a) == NULL) { - goto err; - } - bits = BN_num_bits(p); - - if (BN_is_odd(p)) { - if (BN_copy(rr, a) == NULL) { - goto err; - } - } else { - if (!BN_one(rr)) { - goto err; - } - } - - for (i = 1; i < bits; i++) { - if (!BN_sqr(v, v, ctx)) { - goto err; - } - if (BN_is_bit_set(p, i)) { - if (!BN_mul(rr, rr, v, ctx)) { - goto err; - } - } - } - - if (r != rr && !BN_copy(r, rr)) { - goto err; - } - ret = 1; - -err: - BN_CTX_end(ctx); - return ret; -} - // BN_window_bits_for_exponent_size returns sliding window size for mod_exp with // a |b| bit exponent. // @@ -175,59 +123,6 @@ // |BN_BITS2| * |BN_SMALL_MAX_WORDS|. #define TABLE_SIZE_SMALL (1 << (TABLE_BITS_SMALL - 1)) -static int mod_exp_even(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx) { - // No cryptographic operations require modular exponentiation with an even - // modulus. We support it for backwards compatibility with any applications - // that may have relied on the operation, but optimize for simplicity over - // performance with straightforward square-and-multiply routine. - int bits = BN_num_bits(p); - if (bits == 0) { - return BN_one(r); - } - - // Make a copy of |a|, in case it aliases |r|. - bssl::BN_CTXScope scope(ctx); - BIGNUM *tmp = BN_CTX_get(ctx); - if (tmp == nullptr || !BN_copy(tmp, a)) { - return 0; - } - - assert(BN_is_bit_set(p, bits - 1)); - if (!BN_copy(r, tmp)) { - return 0; - } - - for (int i = bits - 2; i >= 0; i--) { - if (!BN_mod_sqr(r, r, m, ctx) || - (BN_is_bit_set(p, i) && !BN_mod_mul(r, r, tmp, m, ctx))) { - return 0; - } - } - - return 1; -} - -int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, - BN_CTX *ctx) { - if (m->neg) { - OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); - return 0; - } - if (a->neg || BN_ucmp(a, m) >= 0) { - if (!BN_nnmod(r, a, m, ctx)) { - return 0; - } - a = r; - } - - if (BN_is_odd(m)) { - return BN_mod_exp_mont(r, a, p, m, ctx, NULL); - } - - return mod_exp_even(r, a, p, m, ctx); -} - int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx, const BN_MONT_CTX *mont) { if (!BN_is_odd(m)) { @@ -853,68 +748,3 @@ OPENSSL_free(powerbuf_free); return ret; } - -int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, - const BIGNUM *m, BN_CTX *ctx, - const BN_MONT_CTX *mont) { - BIGNUM a_bignum; - BN_init(&a_bignum); - - int ret = 0; - - // BN_mod_exp_mont requires reduced inputs. - if (bn_minimal_width(m) == 1) { - a %= m->d[0]; - } - - if (!BN_set_word(&a_bignum, a)) { - OPENSSL_PUT_ERROR(BN, ERR_R_INTERNAL_ERROR); - goto err; - } - - ret = BN_mod_exp_mont(rr, &a_bignum, p, m, ctx, mont); - -err: - BN_free(&a_bignum); - - return ret; -} - -#define TABLE_SIZE 32 - -int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, - const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, - BN_CTX *ctx, const BN_MONT_CTX *mont) { - BIGNUM tmp; - BN_init(&tmp); - - int ret = 0; - BN_MONT_CTX *new_mont = NULL; - - // Allocate a montgomery context if it was not supplied by the caller. - if (mont == NULL) { - new_mont = BN_MONT_CTX_new_for_modulus(m, ctx); - if (new_mont == NULL) { - goto err; - } - mont = new_mont; - } - - // BN_mod_mul_montgomery removes one Montgomery factor, so passing one - // Montgomery-encoded and one non-Montgomery-encoded value gives a - // non-Montgomery-encoded result. - if (!BN_mod_exp_mont(rr, a1, p1, m, ctx, mont) || - !BN_mod_exp_mont(&tmp, a2, p2, m, ctx, mont) || - !BN_to_montgomery(rr, rr, mont, ctx) || - !BN_mod_mul_montgomery(rr, rr, &tmp, mont, ctx)) { - goto err; - } - - ret = 1; - -err: - BN_MONT_CTX_free(new_mont); - BN_free(&tmp); - - return ret; -}
diff --git a/gen/sources.bzl b/gen/sources.bzl index c5c1fa9..faef20e 100644 --- a/gen/sources.bzl +++ b/gen/sources.bzl
@@ -303,6 +303,7 @@ "crypto/blake2/blake2.cc", "crypto/bn/bn_asn1.cc", "crypto/bn/convert.cc", + "crypto/bn/exponentiation.cc", "crypto/buf/buf.cc", "crypto/bytestring/asn1_compat.cc", "crypto/bytestring/ber.cc",
diff --git a/gen/sources.cmake b/gen/sources.cmake index 8d7b69e..b193769 100644 --- a/gen/sources.cmake +++ b/gen/sources.cmake
@@ -317,6 +317,7 @@ crypto/blake2/blake2.cc crypto/bn/bn_asn1.cc crypto/bn/convert.cc + crypto/bn/exponentiation.cc crypto/buf/buf.cc crypto/bytestring/asn1_compat.cc crypto/bytestring/ber.cc
diff --git a/gen/sources.gni b/gen/sources.gni index ea49630..b5324ff 100644 --- a/gen/sources.gni +++ b/gen/sources.gni
@@ -303,6 +303,7 @@ "crypto/blake2/blake2.cc", "crypto/bn/bn_asn1.cc", "crypto/bn/convert.cc", + "crypto/bn/exponentiation.cc", "crypto/buf/buf.cc", "crypto/bytestring/asn1_compat.cc", "crypto/bytestring/ber.cc",
diff --git a/gen/sources.json b/gen/sources.json index 47c6c55..183ac5c 100644 --- a/gen/sources.json +++ b/gen/sources.json
@@ -287,6 +287,7 @@ "crypto/blake2/blake2.cc", "crypto/bn/bn_asn1.cc", "crypto/bn/convert.cc", + "crypto/bn/exponentiation.cc", "crypto/buf/buf.cc", "crypto/bytestring/asn1_compat.cc", "crypto/bytestring/ber.cc",
diff --git a/gen/sources.mk b/gen/sources.mk index 7e6187a..266d960 100644 --- a/gen/sources.mk +++ b/gen/sources.mk
@@ -297,6 +297,7 @@ crypto/blake2/blake2.cc \ crypto/bn/bn_asn1.cc \ crypto/bn/convert.cc \ + crypto/bn/exponentiation.cc \ crypto/buf/buf.cc \ crypto/bytestring/asn1_compat.cc \ crypto/bytestring/ber.cc \