diff options
| author | nagendra modadugu <ngm@google.com> | 2016-07-14 05:33:57 -0700 |
|---|---|---|
| committer | chrome-bot <chrome-bot@chromium.org> | 2016-07-21 17:32:15 -0700 |
| commit | 76ab8e6f448a3fa3f216b1c54e8a0ca4ff282a08 (patch) | |
| tree | 6fa11ae7c8147ef0afe058400516b2f439f0dfd5 | |
| parent | 5de5f2fded79fa22aebc106866ed43c1d1a01ac9 (diff) | |
| download | chrome-ec-76ab8e6f448a3fa3f216b1c54e8a0ca4ff282a08.tar.gz | |
CR50: bn_modinv_vartime - don't reduce on carry condition
The modinv logic shouldn't reduce modulo MOD
on a carry condition. Instead, just use more
space to hold the carry bit.
Also use full size buffers for all variables.
BRANCH=none
BUG=chrome-os-partner:43025,chrome-os-partner:47524,chrome-os-partner:50115
TEST=unit tested
Signed-off-by: nagendra modadugu <ngm@google.com>
Reviewed-on: https://chromium-review.googlesource.com/360248
Reviewed-by: Marius Schilder <mschilder@chromium.org>
Tested-by: Marius Schilder <mschilder@chromium.org>
Reviewed-by: Vadim Bendebury <vbendeb@chromium.org>
(cherry picked from commit 3f4e131daef04db5c990bb4532bb67ee9e58c02b)
(cherry picked from commit 485b02a17ecdd3c52210fd90ff29b4f1b829a47a)
Change-Id: I8d4f78966bfe15f0739c9de23f5a12685a65aabb
Reviewed-on: https://chromium-review.googlesource.com/362113
Commit-Ready: Vadim Bendebury <vbendeb@chromium.org>
Tested-by: Vadim Bendebury <vbendeb@chromium.org>
| -rw-r--r-- | chip/g/dcrypto/bn.c | 37 |
1 files changed, 16 insertions, 21 deletions
diff --git a/chip/g/dcrypto/bn.c b/chip/g/dcrypto/bn.c index 26a8533839..7d108a0d44 100644 --- a/chip/g/dcrypto/bn.c +++ b/chip/g/dcrypto/bn.c @@ -449,11 +449,11 @@ int bn_modinv_vartime(struct LITE_BIGNUM *d, const struct LITE_BIGNUM *e, const struct LITE_BIGNUM *MOD) { /* Buffers for B, D, and U must be as large as e. */ - uint32_t A_buf[RSA_MAX_WORDS]; - uint32_t B_buf[RSA_MAX_WORDS / 2]; - uint32_t C_buf[RSA_MAX_WORDS]; - uint32_t D_buf[RSA_MAX_WORDS / 2]; - uint32_t U_buf[RSA_MAX_WORDS / 2]; + uint32_t A_buf[RSA_MAX_WORDS + 1]; + uint32_t B_buf[RSA_MAX_WORDS + 1]; + uint32_t C_buf[RSA_MAX_WORDS + 1]; + uint32_t D_buf[RSA_MAX_WORDS + 1]; + uint32_t U_buf[RSA_MAX_WORDS]; uint32_t V_buf[RSA_MAX_WORDS]; int a_neg = 0; int b_neg = 0; @@ -473,17 +473,16 @@ int bn_modinv_vartime(struct LITE_BIGNUM *d, const struct LITE_BIGNUM *e, if (bn_size(e) > sizeof(U_buf)) return 0; - bn_init(&A, A_buf, bn_size(MOD)); + bn_init(&A, A_buf, bn_size(MOD) + sizeof(uint32_t)); + bn_init(&B, B_buf, bn_size(MOD) + sizeof(uint32_t)); + bn_init(&C, C_buf, bn_size(MOD) + sizeof(uint32_t)); + bn_init(&D, D_buf, bn_size(MOD) + sizeof(uint32_t)); + bn_init(&U, U_buf, bn_size(MOD)); + bn_init(&V, V_buf, bn_size(MOD)); + BN_DIGIT(&A, 0) = 1; - bn_init(&B, B_buf, bn_size(MOD) / 2); - bn_init(&C, C_buf, bn_size(MOD)); - bn_init(&D, D_buf, bn_size(MOD) / 2); BN_DIGIT(&D, 0) = 1; - - bn_init(&U, U_buf, bn_size(e)); memcpy(U_buf, e->d, bn_size(e)); - - bn_init(&V, V_buf, bn_size(MOD)); memcpy(V_buf, MOD->d, bn_size(MOD)); /* Binary extended GCD, as per Handbook of Applied @@ -510,18 +509,14 @@ int bn_modinv_vartime(struct LITE_BIGNUM *d, const struct LITE_BIGNUM *e, } else { /* U, V both odd. */ if (bn_gte(&U, &V)) { assert(!bn_sub(&U, &V)); - if (bn_signed_sub(&A, &a_neg, &C, c_neg)) - bn_signed_add(&A, &a_neg, MOD, 0); - if (bn_signed_sub(&B, &b_neg, &D, d_neg)) - bn_signed_add(&B, &b_neg, MOD, 0); + bn_signed_sub(&A, &a_neg, &C, c_neg); + bn_signed_sub(&B, &b_neg, &D, d_neg); if (bn_is_zero(&U)) break; /* done. */ } else { assert(!bn_sub(&V, &U)); - if (bn_signed_sub(&C, &c_neg, &A, a_neg)) - bn_signed_add(&C, &c_neg, MOD, 0); - if (bn_signed_sub(&D, &d_neg, &B, b_neg)) - bn_signed_add(&D, &d_neg, MOD, 0); + bn_signed_sub(&C, &c_neg, &A, a_neg); + bn_signed_sub(&D, &d_neg, &B, b_neg); } } if ((i + 1) % 1000 == 0) |