diff options
author | nagendra modadugu <ngm@google.com> | 2016-03-04 14:38:15 -0800 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2016-04-19 21:13:07 -0700 |
commit | c864a9785804a5e2e5cb2a7cbc4bb7fb993aa52a (patch) | |
tree | ae40fc6b41061eb348ae06d5ba97810f178ae1d9 | |
parent | 7e9245fde47860f0f1503c140d66a26a7860197f (diff) | |
download | chrome-ec-c864a9785804a5e2e5cb2a7cbc4bb7fb993aa52a.tar.gz |
CR50: add support for RSA key "testing"
Implement _cpri__TestKeyRSA, which computes
the modulus and private exponent given a
pair of primes, or computes the second prime
and private exponent given the modulus and
one prime.
The _cpri__TestKeyRSA call is used to determine
whether the components of an RSA key match each other.
BRANCH=none
BUG=chrome-os-partner:43025,chrome-os-partner:47524
TEST=tests in test/tpm/tpmtest.py pass
Change-Id: I2c68d844f4bab207588cbda5c962b09078519a1a
Signed-off-by: nagendra modadugu <ngm@google.com>
Reviewed-on: https://chromium-review.googlesource.com/330466
Commit-Ready: Nagendra Modadugu <ngm@google.com>
Tested-by: Nagendra Modadugu <ngm@google.com>
Reviewed-by: Marius Schilder <mschilder@chromium.org>
-rw-r--r-- | board/cr50/tpm2/rsa.c | 163 | ||||
-rw-r--r-- | board/cr50/tpm2/stubs.c | 14 | ||||
-rw-r--r-- | chip/g/dcrypto/bn.c | 249 | ||||
-rw-r--r-- | chip/g/dcrypto/dcrypto.h | 9 | ||||
-rw-r--r-- | chip/g/dcrypto/internal.h | 5 | ||||
-rw-r--r-- | chip/g/dcrypto/rsa.c | 35 | ||||
-rw-r--r-- | test/tpm_test/rsa_test.py | 29 |
7 files changed, 484 insertions, 20 deletions
diff --git a/board/cr50/tpm2/rsa.c b/board/cr50/tpm2/rsa.c index 2e7ccd8208..e48e4fb352 100644 --- a/board/cr50/tpm2/rsa.c +++ b/board/cr50/tpm2/rsa.c @@ -206,6 +206,51 @@ CRYPT_RESULT _cpri__ValidateSignatureRSA( return CRYPT_FAIL; } +CRYPT_RESULT _cpri__TestKeyRSA(TPM2B *d_buf, uint32_t e, + TPM2B *N_buf, TPM2B *p_buf, TPM2B *q_buf) +{ + struct BIGNUM N; + struct BIGNUM p; + struct BIGNUM q; + struct BIGNUM d; + int result; + + if (!p_buf) + return CRYPT_PARAMETER; + if (q_buf && p_buf->size != q_buf->size) + return CRYPT_PARAMETER; + if (N_buf->size != p_buf->size * 2) + return CRYPT_PARAMETER; /* Insufficient output buffer space. */ + if (N_buf->size > RSA_MAX_BYTES) + return CRYPT_PARAMETER; /* Unsupported key size. */ + + DCRYPTO_bn_wrap(&N, N_buf->buffer, N_buf->size); + DCRYPTO_bn_wrap(&p, p_buf->buffer, p_buf->size); + reverse_tpm2b(N_buf); + reverse_tpm2b(p_buf); + if (q_buf) { + DCRYPTO_bn_wrap(&q, q_buf->buffer, q_buf->size); + reverse_tpm2b(q_buf); + } + /* d_buf->size may be uninitialized. */ + DCRYPTO_bn_wrap(&d, d_buf->buffer, N_buf->size); + + result = DCRYPTO_rsa_key_compute(&N, &d, &p, q_buf ? &q : NULL, e); + + reverse_tpm2b(N_buf); + reverse_tpm2b(p_buf); + if (q_buf) + reverse_tpm2b(q_buf); + + if (result) { + d_buf->size = N_buf->size; + reverse_tpm2b(d_buf); + return CRYPT_SUCCESS; + } else { + return CRYPT_FAIL; + } +} + #ifdef CRYPTO_TEST_SETUP #include "extension.h" @@ -215,7 +260,8 @@ enum { TEST_RSA_DECRYPT = 1, TEST_RSA_SIGN = 2, TEST_RSA_VERIFY = 3, - TEST_RSA_KEYGEN = 4 + TEST_RSA_KEYGEN = 4, + TEST_RSA_KEYTEST = 5 }; static const TPM2B_PUBLIC_KEY_RSA RSA_768_N = { @@ -254,6 +300,30 @@ static const TPM2B_PUBLIC_KEY_RSA RSA_768_D = { } }; +static const TPM2B_PUBLIC_KEY_RSA RSA_768_P = { + .t = {48, { + 0xd6, 0x09, 0x64, 0xc8, 0xf3, 0x5c, 0x02, 0xc7, + 0xc6, 0x47, 0x4e, 0x7f, 0x43, 0x9d, 0x31, 0x46, + 0x7a, 0x33, 0x85, 0xa0, 0xa4, 0x16, 0xea, 0x22, + 0x7b, 0xcd, 0x64, 0x9b, 0x50, 0xec, 0xa7, 0x2f, + 0x7e, 0xcf, 0xeb, 0x69, 0x29, 0x34, 0x8e, 0xb7, + 0xb5, 0xb3, 0xba, 0x7f, 0x9b, 0x01, 0x7d, 0x69 + } + } +}; + +static const TPM2B_PUBLIC_KEY_RSA RSA_768_Q = { + .t = {48, { + 0xd3, 0x88, 0x92, 0x2d, 0xd5, 0xc6, 0x29, 0xf4, + 0xf0, 0x2e, 0x61, 0xf0, 0x60, 0xad, 0xa9, 0x46, + 0x11, 0xa9, 0x0c, 0x69, 0x14, 0x31, 0x09, 0x36, + 0x8b, 0x70, 0x1b, 0x11, 0x9b, 0x26, 0x39, 0x34, + 0x34, 0xfd, 0xf1, 0x9a, 0x89, 0x51, 0x63, 0x0a, + 0xc6, 0x60, 0x0b, 0xba, 0x18, 0x8e, 0xc8, 0x01 + } + } +}; + static const TPM2B_PUBLIC_KEY_RSA RSA_2048_N = { .t = {256, { 0x9c, 0xd7, 0x61, 0x2e, 0x43, 0x8e, 0x15, 0xbe, @@ -330,6 +400,58 @@ static const TPM2B_PUBLIC_KEY_RSA RSA_2048_D = { } }; +static const TPM2B_PUBLIC_KEY_RSA RSA_2048_P = { + .t = {128, { + 0xc8, 0x80, 0x6f, 0xf6, 0x2f, 0xfb, 0x49, 0x8b, + 0x77, 0x39, 0xe2, 0x3d, 0x3d, 0x1f, 0x4d, 0xf9, + 0xbb, 0x54, 0x06, 0x0d, 0x71, 0xbf, 0x54, 0xb1, + 0x1e, 0xa2, 0x20, 0x7e, 0xdd, 0xcf, 0x21, 0x16, + 0xe9, 0xc0, 0xba, 0x94, 0x02, 0xd2, 0xa4, 0x2e, + 0x78, 0x3c, 0xfb, 0x64, 0xa0, 0xe7, 0xe9, 0x27, + 0x64, 0x29, 0x19, 0x74, 0xc5, 0x77, 0xbb, 0xe1, + 0x6d, 0xb4, 0x83, 0x1d, 0x43, 0x5a, 0x80, 0x72, + 0xec, 0x3c, 0x32, 0xc3, 0x20, 0x2c, 0xce, 0xf7, + 0xba, 0xf6, 0xc6, 0x0c, 0xf4, 0x56, 0xfd, 0xdf, + 0x21, 0x55, 0xf3, 0xe2, 0x56, 0x25, 0xa6, 0xb3, + 0x96, 0xa4, 0x9c, 0xb8, 0xfd, 0x9c, 0xec, 0x87, + 0xfa, 0xda, 0x2e, 0xa4, 0xf6, 0x0f, 0x14, 0xe6, + 0x81, 0x22, 0x84, 0xe7, 0xc0, 0x1d, 0xd1, 0x3f, + 0xed, 0xb0, 0xba, 0xd8, 0xe4, 0xe9, 0xd4, 0x18, + 0x33, 0xae, 0x29, 0x51, 0x79, 0x79, 0xd1, 0x0f + } + } +}; + +static const TPM2B_PUBLIC_KEY_RSA RSA_2048_Q = { + .t = {128, { + 0xc8, 0x41, 0x2a, 0x42, 0xf1, 0x6a, 0x81, 0xac, + 0x06, 0xab, 0xd0, 0xb7, 0xc0, 0xbb, 0xc6, 0x13, + 0xdd, 0xfd, 0x5e, 0x3c, 0x77, 0xfe, 0xc1, 0x2e, + 0x76, 0xf0, 0x94, 0xc0, 0x5d, 0x24, 0x8b, 0x30, + 0x0d, 0xf8, 0x2a, 0xc7, 0x26, 0x78, 0x1b, 0x81, + 0x5a, 0x42, 0x96, 0xad, 0xf7, 0x0e, 0xa4, 0x1b, + 0x2c, 0x8f, 0x38, 0x06, 0x05, 0x8d, 0x98, 0x6e, + 0x37, 0x65, 0xb4, 0x2c, 0x80, 0xe2, 0x38, 0xd5, + 0x79, 0xd2, 0xea, 0x62, 0xf2, 0x32, 0xac, 0x7b, + 0x88, 0x90, 0xc3, 0x4e, 0x9e, 0x53, 0xe5, 0x7e, + 0xef, 0x13, 0xb1, 0xe3, 0xd5, 0x41, 0xd1, 0xa9, + 0x15, 0x04, 0x3c, 0x61, 0x74, 0x5e, 0x1a, 0x00, + 0x5c, 0x8a, 0x8b, 0x17, 0xd5, 0x78, 0xad, 0x5e, + 0xe0, 0xcf, 0x35, 0x63, 0x0a, 0x95, 0x1e, 0x70, + 0xbe, 0x97, 0xf2, 0xd3, 0x78, 0x06, 0x8a, 0x88, + 0x9b, 0x27, 0xc8, 0xb2, 0xb1, 0x3d, 0x8a, 0xd7 + } + } +}; + + +static const RSA_KEY RSA_768 = { + 65537, (TPM2B *) &RSA_768_N.b, (TPM2B *) &RSA_768_D.b +}; +static const RSA_KEY RSA_2048 = { + 65537, (TPM2B *) &RSA_2048_N.b, (TPM2B *) &RSA_2048_D.b +}; + #define MAX_MSG_BYTES RSA_MAX_BYTES static void rsa_command_handler(void *cmd_body, @@ -348,8 +470,12 @@ static void rsa_command_handler(void *cmd_body, uint8_t *out = (uint8_t *) cmd_body; TPM2B_PUBLIC_KEY_RSA N; TPM2B_PUBLIC_KEY_RSA d; + TPM2B_PUBLIC_KEY_RSA p; + TPM2B_PUBLIC_KEY_RSA q; RSA_KEY key; uint32_t *response_size = (uint32_t *) response_size_out; + TPM2B_PUBLIC_KEY_RSA rsa_d; + TPM2B_PUBLIC_KEY_RSA rsa_n; assert(sizeof(size_t) == sizeof(uint32_t)); @@ -397,10 +523,18 @@ static void rsa_command_handler(void *cmd_body, case 768: N = RSA_768_N; d = RSA_768_D; + p = RSA_768_P; + q = RSA_768_Q; + rsa_n.b.size = RSA_768_N.b.size; + rsa_d.b.size = RSA_768_D.b.size; break; case 2048: N = RSA_2048_N; d = RSA_2048_D; + p = RSA_2048_P; + q = RSA_2048_Q; + rsa_n.b.size = RSA_2048_N.b.size; + rsa_d.b.size = RSA_2048_D.b.size; break; default: *response_size = 0; @@ -446,6 +580,33 @@ static void rsa_command_handler(void *cmd_body, case TEST_RSA_KEYGEN: *response_size = 0; break; + case TEST_RSA_KEYTEST: + if (_cpri__TestKeyRSA(&rsa_d.b, 65537, &rsa_n.b, &p.b, &q.b) + != CRYPT_SUCCESS) { + *response_size = 0; + return; + } + if (memcmp(rsa_n.b.buffer, key.publicKey->buffer, + rsa_n.b.size) != 0 || + memcmp(rsa_d.b.buffer, key.privateKey->buffer, + rsa_d.b.size) != 0) { + *response_size = 0; + return; + } + + if (_cpri__TestKeyRSA(&rsa_d.b, 65537, key.publicKey, + &p.b, NULL) != CRYPT_SUCCESS) { + *response_size = 0; + return; + } + if (memcmp(rsa_d.b.buffer, key.privateKey->buffer, + rsa_d.b.size) != 0) { + *response_size = 0; + return; + } + *out = 1; + *response_size = 1; + return; } } diff --git a/board/cr50/tpm2/stubs.c b/board/cr50/tpm2/stubs.c index 56465f7eae..257889a652 100644 --- a/board/cr50/tpm2/stubs.c +++ b/board/cr50/tpm2/stubs.c @@ -81,20 +81,6 @@ BOOL _cpri__Startup( return 1; } -CRYPT_RESULT _cpri__TestKeyRSA( - TPM2B * d, // OUT: the address to receive the - // private exponent - UINT32 exponent, // IN: the public modulu - TPM2B * publicKey, // IN/OUT: an input if only one prime is - // provided. an output if both primes are provided - TPM2B * prime1, // IN: a first prime - TPM2B * prime2 // IN: an optional second prime - ) -{ - ecprintf("%s called\n", __func__); - return CRYPT_FAIL; -} - CRYPT_RESULT _math__Div( const TPM2B * n, // IN: numerator const TPM2B * d, // IN: denominator diff --git a/chip/g/dcrypto/bn.c b/chip/g/dcrypto/bn.c index f4aaf11912..52a1abfc1a 100644 --- a/chip/g/dcrypto/bn.c +++ b/chip/g/dcrypto/bn.c @@ -16,10 +16,15 @@ static inline void watchdog_reload(void) { } void bn_init(struct BIGNUM *b, void *buf, size_t len) { + DCRYPTO_bn_wrap(b, buf, len); + dcrypto_memset(buf, 0x00, len); +} + +void DCRYPTO_bn_wrap(struct BIGNUM *b, void *buf, size_t len) +{ /* Only word-multiple sized buffers accepted. */ assert((len & 0x3) == 0); b->dmax = len / BN_BYTES; - dcrypto_memset(buf, 0x00, len); b->d = (struct access_helper *) buf; } @@ -49,14 +54,26 @@ static int bn_is_bit_set(const struct BIGNUM *a, int n) static int bn_gte(const struct BIGNUM *a, const struct BIGNUM *b) { int i; + uint32_t top = 0; - for (i = a->dmax - 1; BN_DIGIT(a, i) == BN_DIGIT(b, i) && i > 0; --i) + for (i = a->dmax - 1; i > b->dmax - 1; --i) + top |= BN_DIGIT(a, i); + if (top) + return 1; + + for (i = b->dmax - 1; i > a->dmax - 1; --i) + top |= BN_DIGIT(b, i); + if (top) + return 0; + + for (i = MIN(a->dmax, b->dmax) - 1; + BN_DIGIT(a, i) == BN_DIGIT(b, i) && i > 0; --i) ; return BN_DIGIT(a, i) >= BN_DIGIT(b, i); } /* c[] = c[] - a[], assumes c > a. */ -static uint32_t bn_sub(struct BIGNUM *c, const struct BIGNUM *a) +uint32_t bn_sub(struct BIGNUM *c, const struct BIGNUM *a) { int64_t A = 0; int i; @@ -66,11 +83,45 @@ static uint32_t bn_sub(struct BIGNUM *c, const struct BIGNUM *a) BN_DIGIT(c, i) = (uint32_t) A; A >>= 32; } + + for (; A && i < c->dmax; i++) { + A += (uint64_t) BN_DIGIT(c, i); + BN_DIGIT(c, i) = (uint32_t) A; + A >>= 32; + } + return (uint32_t) A; /* 0 or -1. */ } +/* c[] = c[] - a[], negative numbers in 2's complement representation. */ +/* Returns borrow bit. */ +static uint32_t bn_signed_sub(struct BIGNUM *c, int *c_neg, + const struct BIGNUM *a, int a_neg) +{ + uint32_t carry = 0; + uint64_t A = 1; + int i; + + for (i = 0; i < a->dmax; ++i) { + A += (uint64_t) BN_DIGIT(c, i) + ~BN_DIGIT(a, i); + BN_DIGIT(c, i) = (uint32_t) A; + A >>= 32; + } + + for (; i < c->dmax; ++i) { + A += (uint64_t) BN_DIGIT(c, i) + 0xFFFFFFFF; + BN_DIGIT(c, i) = (uint32_t) A; + A >>= 32; + } + + A &= 0x01; + carry = (!*c_neg && a_neg && A) || (*c_neg && !a_neg && !A); + *c_neg = carry ? *c_neg : (*c_neg + !a_neg + A) & 0x01; + return carry; +} + /* c[] = c[] + a[]. */ -static uint32_t bn_add(struct BIGNUM *c, const struct BIGNUM *a) +uint32_t bn_add(struct BIGNUM *c, const struct BIGNUM *a) { uint64_t A = 0; int i; @@ -81,9 +132,28 @@ static uint32_t bn_add(struct BIGNUM *c, const struct BIGNUM *a) A >>= 32; } + for (; A && i < c->dmax; ++i) { + A += (uint64_t) BN_DIGIT(c, i); + BN_DIGIT(c, i) = (uint32_t) A; + A >>= 32; + } + return (uint32_t) A; /* 0 or 1. */ } +/* c[] = c[] + a[], negative numbers in 2's complement representation. */ +/* Returns carry bit. */ +static uint32_t bn_signed_add(struct BIGNUM *c, int *c_neg, + const struct BIGNUM *a, int a_neg) +{ + uint32_t A = bn_add(c, a); + uint32_t carry; + + carry = (!*c_neg && !a_neg && A) || (*c_neg && a_neg && !A); + *c_neg = carry ? *c_neg : (*c_neg + a_neg + A) & 0x01; + return carry; +} + /* r[] <<= 1. */ static uint32_t bn_lshift(struct BIGNUM *r) { @@ -99,6 +169,29 @@ static uint32_t bn_lshift(struct BIGNUM *r) return carry; } +/* r[] >>= 1. Handles 2's complement negative numbers. */ +static void bn_rshift(struct BIGNUM *r, uint32_t carry, uint32_t neg) +{ + int i; + uint32_t ones = ~0; + uint32_t highbit = (!carry && neg) || (carry && !neg); + + for (i = 0; i < r->dmax - 1; ++i) { + uint32_t accu; + + ones &= BN_DIGIT(r, i); + accu = (BN_DIGIT(r, i) >> 1); + accu |= (BN_DIGIT(r, i + 1) << (BN_BITS2 - 1)); + BN_DIGIT(r, i) = accu; + } + ones &= BN_DIGIT(r, i); + BN_DIGIT(r, i) = (BN_DIGIT(r, i) >> 1) | + (highbit << (BN_BITS2 - 1)); + + if (ones == ~0 && highbit && neg) + memset(r->d, 0x00, bn_size(r)); /* -1 >> 1 = 0. */ +} + /* Montgomery c[] += a * b[] / R % N. */ /* TODO(ngm): constant time. */ static void bn_mont_mul_add(struct BIGNUM *c, const uint32_t a, @@ -244,3 +337,151 @@ void bn_mont_modexp(struct BIGNUM *output, const struct BIGNUM *input, dcrypto_memset(acc_buf, 0, sizeof(acc_buf)); dcrypto_memset(aR_buf, 0, sizeof(aR_buf)); } + +/* c[] += a * b[] */ +static uint32_t bn_mul_add(struct BIGNUM *c, uint32_t a, + const struct BIGNUM *b, uint32_t offset) +{ + int i; + uint64_t carry = 0; + + for (i = 0; i < b->dmax; i++) { + carry += BN_DIGIT(c, offset + i) + + (uint64_t) BN_DIGIT(b, i) * a; + BN_DIGIT(c, offset + i) = (uint32_t) carry; + carry >>= 32; + } + + return carry; +} + +/* c[] = a[] * b[] */ +void bn_mul(struct BIGNUM *c, const struct BIGNUM *a, const struct BIGNUM *b) +{ + int i; + uint32_t carry = 0; + + memset(c->d, 0, bn_size(c)); + for (i = 0; i < a->dmax; i++) { + BN_DIGIT(c, i + b->dmax - 1) = carry; + carry = bn_mul_add(c, BN_DIGIT(a, i), b, i); + } + + BN_DIGIT(c, i + b->dmax - 1) = carry; +} + +#define bn_is_even(b) !bn_is_bit_set((b), 0) +#define bn_is_odd(b) bn_is_bit_set((b), 0) + +static int bn_is_zero(const struct BIGNUM *a) +{ + int i, result = 0; + + for (i = 0; i < a->dmax; ++i) + result |= BN_DIGIT(a, i); + return !result; +} + +/* d = (e ^ -1) mod MOD */ +/* TODO(ngm): this method is used in place of division to calculate + * q = N/p, i.e. q = p^-1 mod (N-1). The buffer e may be + * resized to uint32_t once division is implemented. */ +int bn_modinv_vartime(struct BIGNUM *d, const struct BIGNUM *e, + const struct 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 V_buf[RSA_MAX_WORDS]; + int a_neg = 0; + int b_neg = 0; + int c_neg = 0; + int d_neg = 0; + int carry1; + int carry2; + int i = 0; + + struct BIGNUM A; + struct BIGNUM B; + struct BIGNUM C; + struct BIGNUM D; + struct BIGNUM U; + struct BIGNUM V; + + if (bn_size(e) > sizeof(U_buf)) + return 0; + + bn_init(&A, A_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 + * Cryptography, 14.61. */ + for (i = 0;; i++) { + carry1 = 0; + carry2 = 0; + if (bn_is_even(&U)) { + bn_rshift(&U, 0, 0); + if (bn_is_odd(&A) || bn_is_odd(&B)) { + carry1 = bn_signed_add(&A, &a_neg, MOD, 0); + carry2 = bn_signed_sub(&B, &b_neg, e, 0); + } + bn_rshift(&A, carry1, a_neg); + bn_rshift(&B, carry2, b_neg); + } else if (bn_is_even(&V)) { + bn_rshift(&V, 0, 0); + if (bn_is_odd(&C) || bn_is_odd(&D)) { + carry1 = bn_signed_add(&C, &c_neg, MOD, 0); + carry2 = bn_signed_sub(&D, &d_neg, e, 0); + } + bn_rshift(&C, carry1, c_neg); + bn_rshift(&D, carry2, d_neg); + } 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); + 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); + } + } + if ((i + 1) % 1000 == 0) + /* TODO(ngm): Poke the watchdog (only + * necessary for q = N/p). Remove once + * division is implemented. */ + watchdog_reload(); + } + + BN_DIGIT(&V, 0) ^= 0x01; + if (bn_is_zero(&V)) { + while (c_neg) + bn_signed_add(&C, &c_neg, MOD, 0); + while (bn_gte(&C, MOD)) + bn_sub(&C, MOD); + + memcpy(d->d, C.d, bn_size(d)); + return 1; + } else { + return 0; /* Inverse not found. */ + } +} diff --git a/chip/g/dcrypto/dcrypto.h b/chip/g/dcrypto/dcrypto.h index 2147400550..aec3292dae 100644 --- a/chip/g/dcrypto/dcrypto.h +++ b/chip/g/dcrypto/dcrypto.h @@ -80,6 +80,11 @@ const uint8_t *DCRYPTO_SHA256_hash(const uint8_t *data, uint32_t n, uint8_t *digest); /* + * BIGNUM utility methods. + */ +void DCRYPTO_bn_wrap(struct BIGNUM *b, void *buf, size_t len); + +/* * RSA. */ @@ -125,6 +130,10 @@ int DCRYPTO_rsa_verify(struct RSA *rsa, const uint8_t *digest, const uint32_t sig_len, enum padding_mode padding, enum hashing_mode hashing); +/* Calculate n = p * q, d = e ^ -1 mod phi. */ +int DCRYPTO_rsa_key_compute(struct BIGNUM *N, struct BIGNUM *d, + struct BIGNUM *p, struct BIGNUM *q, uint32_t e); + /* * EC. */ diff --git a/chip/g/dcrypto/internal.h b/chip/g/dcrypto/internal.h index 09685c3004..a79e3b1160 100644 --- a/chip/g/dcrypto/internal.h +++ b/chip/g/dcrypto/internal.h @@ -115,6 +115,11 @@ void bn_init(struct BIGNUM *bn, void *buf, size_t len); int bn_check_topbit(const struct BIGNUM *N); void bn_mont_modexp(struct BIGNUM *output, const struct BIGNUM *input, const struct BIGNUM *exp, const struct BIGNUM *N); +uint32_t bn_add(struct BIGNUM *c, const struct BIGNUM *a); +uint32_t bn_sub(struct BIGNUM *c, const struct BIGNUM *a); +void bn_mul(struct BIGNUM *c, const struct BIGNUM *a, const struct BIGNUM *b); +int bn_modinv_vartime(struct BIGNUM *r, const struct BIGNUM *e, + const struct BIGNUM *MOD); /* * EC. diff --git a/chip/g/dcrypto/rsa.c b/chip/g/dcrypto/rsa.c index ff42e00457..7742cea18e 100644 --- a/chip/g/dcrypto/rsa.c +++ b/chip/g/dcrypto/rsa.c @@ -625,3 +625,38 @@ int DCRYPTO_rsa_verify(struct RSA *rsa, const uint8_t *digest, dcrypto_memset(signature_buf, 0, sizeof(signature_buf)); return ret; } + +int DCRYPTO_rsa_key_compute(struct BIGNUM *N, struct BIGNUM *d, + struct BIGNUM *p, struct BIGNUM *q, uint32_t e_buf) +{ + uint32_t ONE_buf = 1; + uint32_t phi_buf[RSA_MAX_WORDS]; + uint32_t q_buf[RSA_MAX_WORDS / 2]; + + struct BIGNUM ONE; + struct BIGNUM e; + struct BIGNUM phi; + struct BIGNUM q_local; + + DCRYPTO_bn_wrap(&ONE, &ONE_buf, sizeof(ONE_buf)); + DCRYPTO_bn_wrap(&phi, phi_buf, bn_size(N)); + if (!q) { + /* q not provided, calculate it. */ + memcpy(phi_buf, N->d, bn_size(N)); + bn_init(&q_local, q_buf, bn_size(p)); + bn_sub(&phi, &ONE); + if (!bn_modinv_vartime(&q_local, p, &phi)) + return 0; + q = &q_local; + bn_add(&phi, &ONE); + } else { + bn_mul(N, p, q); + memcpy(phi_buf, N->d, bn_size(N)); + } + + bn_sub(&phi, p); + bn_sub(&phi, q); + bn_add(&phi, &ONE); + DCRYPTO_bn_wrap(&e, &e_buf, sizeof(e_buf)); + return bn_modinv_vartime(d, &e, &phi); +} diff --git a/test/tpm_test/rsa_test.py b/test/tpm_test/rsa_test.py index 2a751d3ee7..14982d5380 100644 --- a/test/tpm_test/rsa_test.py +++ b/test/tpm_test/rsa_test.py @@ -17,7 +17,8 @@ _RSA_OPCODES = { 'DECRYPT': 0x01, 'SIGN': 0x02, 'VERIFY': 0x03, - 'KEYGEN': 0x04 + 'KEYGEN': 0x04, + 'KEYTEST': 0x05, } @@ -102,6 +103,13 @@ def _verify_cmd(padding, hashing, key_len, sig, msg): ml=struct.pack('>H', sig_len), msg=sig, dl=struct.pack('>H', digest_len), dig=digest) +def _keytest_cmd(key_len): + op = _RSA_OPCODES['KEYTEST'] + return _RSA_CMD_FORMAT.format(o=op, p=0, h=_HASH['NONE'], + kl=struct.pack('>H', key_len), + ml=struct.pack('>H', 0), msg='', + dl='', dig='') + # # TEST VECTORS. @@ -122,6 +130,10 @@ _SIGN_INPUTS = ( ('PKCS1-PSS', 'SHA256', 768), ) +_KEYTEST_INPUTS = ( + (768,), + (2048,), +) def _encrypt_tests(tpm): msg = 'Hello CR50!' @@ -172,6 +184,21 @@ def _sign_tests(tpm): print('%sSUCCESS: %s' % (utils.cursor_back(), test_name)) +def _keytest_tests(tpm): + for data in _KEYTEST_INPUTS: + key_len, = data + test_name = 'RSA-KEYTEST:%d' % data + cmd = _keytest_cmd(key_len) + wrapped_response = tpm.command(tpm.wrap_ext_command(subcmd.RSA, cmd)) + valid = tpm.unwrap_ext_response(subcmd.RSA, wrapped_response) + expected = '\x01' + if valid != expected: + raise subcmd.TpmTestError('%s error:%s%s' % ( + test_name, utils.hex_dump(valid), utils.hex_dump(expected))) + print('%sSUCCESS: %s' % (utils.cursor_back(), test_name)) + + def rsa_test(tpm): _encrypt_tests(tpm) _sign_tests(tpm) + _keytest_tests(tpm) |