Remove ec_compute_wNAF's failure cases.
Replace them with asserts and better justify why each of the internal
cases are not reachable. Also change the loop to count up to bits+1 so
it is obvious there is no memory error. (The previous loop shape made
more sense when ec_compute_wNAF would return a variable length
schedule.)
Change-Id: I9c7df6abac4290b7a3e545e3d4aa1462108e239e
Reviewed-on: https://boringssl-review.googlesource.com/27705
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/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 891591f..a70c869 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -282,15 +282,15 @@
const EC_POINT *p, const EC_SCALAR *p_scalar, BN_CTX *ctx);
// ec_compute_wNAF writes the modified width-(w+1) Non-Adjacent Form (wNAF) of
-// |scalar| to |out| and returns one on success or zero on internal error. |out|
-// must have room for |bits| + 1 elements, each of which will be either zero or
-// odd with an absolute value less than 2^w satisfying
+// |scalar| to |out|. |out| must have room for |bits| + 1 elements, each of
+// which will be either zero or odd with an absolute value less than 2^w
+// satisfying
// scalar = \sum_j out[j]*2^j
// where at most one of any w+1 consecutive digits is non-zero
// with the exception that the most significant digit may be only
// w-1 zeros away from that next non-zero digit.
-int ec_compute_wNAF(const EC_GROUP *group, int8_t *out, const EC_SCALAR *scalar,
- size_t bits, int w);
+void ec_compute_wNAF(const EC_GROUP *group, int8_t *out,
+ const EC_SCALAR *scalar, size_t bits, int w);
int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const EC_SCALAR *g_scalar,
const EC_POINT *p, const EC_SCALAR *p_scalar, BN_CTX *ctx);
diff --git a/crypto/fipsmodule/ec/wnaf.c b/crypto/fipsmodule/ec/wnaf.c
index 0209d98..e6f0cf9 100644
--- a/crypto/fipsmodule/ec/wnaf.c
+++ b/crypto/fipsmodule/ec/wnaf.c
@@ -67,6 +67,7 @@
#include <openssl/ec.h>
+#include <assert.h>
#include <string.h>
#include <openssl/bn.h>
@@ -85,82 +86,66 @@
// http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
// http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
-int ec_compute_wNAF(const EC_GROUP *group, int8_t *out, const EC_SCALAR *scalar,
- size_t bits, int w) {
+void ec_compute_wNAF(const EC_GROUP *group, int8_t *out,
+ const EC_SCALAR *scalar, size_t bits, int w) {
// 'int8_t' can represent integers with absolute values less than 2^7.
- if (w <= 0 || w > 7 || bits == 0) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
- }
- int bit = 1 << w; // at most 128
- int next_bit = bit << 1; // at most 256
+ assert(0 < w && w <= 7);
+ assert(bits != 0);
+ int bit = 1 << w; // 2^w, at most 128
+ int next_bit = bit << 1; // 2^(w+1), at most 256
int mask = next_bit - 1; // at most 255
int window_val = scalar->words[0] & mask;
- size_t j = 0;
- // If j+w+1 >= bits, window_val will not increase.
- while (window_val != 0 || j + w + 1 < bits) {
+ for (size_t j = 0; j < bits + 1; j++) {
+ assert(0 <= window_val && window_val <= next_bit);
int digit = 0;
-
- // 0 <= window_val <= 2^(w+1)
-
if (window_val & 1) {
- // 0 < window_val < 2^(w+1)
-
+ assert(0 < window_val && window_val < next_bit);
if (window_val & bit) {
- digit = window_val - next_bit; // -2^w < digit < 0
+ digit = window_val - next_bit;
+ // We know -next_bit < digit < 0 and window_val - digit = next_bit.
-#if 1 // modified wNAF
+ // modified wNAF
if (j + w + 1 >= bits) {
// special case for generating modified wNAFs:
// no new bits will be added into window_val,
// so using a positive digit here will decrease
// the total length of the representation
- digit = window_val & (mask >> 1); // 0 < digit < 2^w
+ digit = window_val & (mask >> 1);
+ // We know 0 < digit < bit and window_val - digit = bit.
}
-#endif
} else {
- digit = window_val; // 0 < digit < 2^w
- }
-
- if (digit <= -bit || digit >= bit || !(digit & 1)) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
+ digit = window_val;
+ // We know 0 < digit < bit and window_val - digit = 0.
}
window_val -= digit;
- // Now window_val is 0 or 2^(w+1) in standard wNAF generation;
- // for modified window NAFs, it may also be 2^w.
- if (window_val != 0 && window_val != next_bit && window_val != bit) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
- }
+ // Now window_val is 0 or 2^(w+1) in standard wNAF generation.
+ // For modified window NAFs, it may also be 2^w.
+ //
+ // See the comments above for the derivation of each of these bounds.
+ assert(window_val == 0 || window_val == next_bit || window_val == bit);
+ assert(-bit < digit && digit < bit);
+
+ // window_val was odd, so digit is also odd.
+ assert(digit & 1);
}
- out[j++] = digit;
+ out[j] = digit;
+ // Incorporate the next bit. Previously, |window_val| <= |next_bit|, so if
+ // we shift and add at most one copy of |bit|, this will continue to hold
+ // afterwards.
window_val >>= 1;
window_val +=
- bit * bn_is_bit_set_words(scalar->words, group->order.width, j + w);
-
- if (window_val > next_bit) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
- }
+ bit * bn_is_bit_set_words(scalar->words, group->order.width, j + w + 1);
+ assert(window_val <= next_bit);
}
- // Fill the rest of the wNAF with zeros.
- if (j > bits + 1) {
- OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
- return 0;
- }
- for (size_t i = j; i < bits + 1; i++) {
- out[i] = 0;
- }
-
- return 1;
+ // bits + 1 entries should be sufficient to consume all bits.
+ assert(window_val == 0);
}
// TODO: table should be optimised for the wNAF-based implementation,
@@ -274,8 +259,8 @@
}
g_precomp = precomp_storage + total_precomp;
total_precomp += precomp_len;
- if (!ec_compute_wNAF(group, g_wNAF, g_scalar, bits, wsize) ||
- !compute_precomp(group, g_precomp, g, precomp_len, ctx)) {
+ ec_compute_wNAF(group, g_wNAF, g_scalar, bits, wsize);
+ if (!compute_precomp(group, g_precomp, g, precomp_len, ctx)) {
goto err;
}
}
@@ -283,8 +268,8 @@
if (p_scalar != NULL) {
p_precomp = precomp_storage + total_precomp;
total_precomp += precomp_len;
- if (!ec_compute_wNAF(group, p_wNAF, p_scalar, bits, wsize) ||
- !compute_precomp(group, p_precomp, p, precomp_len, ctx)) {
+ ec_compute_wNAF(group, p_wNAF, p_scalar, bits, wsize);
+ if (!compute_precomp(group, p_precomp, p, precomp_len, ctx)) {
goto err;
}
}
diff --git a/third_party/fiat/p256.c b/third_party/fiat/p256.c
index 53ae9ed..5920963 100644
--- a/third_party/fiat/p256.c
+++ b/third_party/fiat/p256.c
@@ -1738,9 +1738,7 @@
// Set up the coefficients for |p_scalar|.
int8_t p_wNAF[257];
- if (!ec_compute_wNAF(group, p_wNAF, p_scalar, 256, P256_WSIZE_PUBLIC)) {
- return 0;
- }
+ ec_compute_wNAF(group, p_wNAF, p_scalar, 256, P256_WSIZE_PUBLIC);
// Set |ret| to the point at infinity.
int skip = 1; // Save some point operations.
