From ca6432daebfcca16d55c07e588f96202d77109fb Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Sat, 9 Sep 2017 00:59:35 -0400 Subject: Start hacking for systolic modexp. Work in progress. Probably won't even compile, much less run. Requires corresponding new core/math/modexpa7 core. No support (yet) for ASN.1 encoding of speedup factors or storage of same in keystore. No support (yet) for running CRT algorithm in parallel cores. Minor cleanup of ancient bus I/O code, including EIM and I2C bus code we'll probably never use again. --- rsa.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 71 insertions(+), 31 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index eeb611c..90a878f 100644 --- a/rsa.c +++ b/rsa.c @@ -70,7 +70,6 @@ #include #include #include -#include #include "hal.h" #include "hal_internal.h" @@ -93,6 +92,15 @@ #define hal_get_random(core, buffer, length) hal_rpc_get_random(buffer, length) #endif +/* + * How big to make the buffers for the modulus coefficient and + * Montgomery factor. This will almost certainly want tuning. + */ + +#ifndef HAL_RSA_MAX_OPERAND_LENGTH +#define HAL_RSA_MAX_OPERAND_LENGTH (4096 / 8) +#endif + /* * Whether we want debug output. */ @@ -123,7 +131,7 @@ void hal_rsa_set_blinding(const int onoff) */ struct hal_rsa_key { - hal_key_type_t type; /* What kind of key this is */ + hal_key_type_t type; /* What kind of key this is */ fp_int n[1]; /* The modulus */ fp_int e[1]; /* Public exponent */ fp_int d[1]; /* Private exponent */ @@ -132,8 +140,17 @@ struct hal_rsa_key { fp_int u[1]; /* 1/q mod p */ fp_int dP[1]; /* d mod (p - 1) */ fp_int dQ[1]; /* d mod (q - 1) */ + unsigned flags; /* Internal key flags */ + uint8_t /* ModExpA7 speedup factors */ + nC[HAL_RSA_MAX_OPERAND_LENGTH], nF[HAL_RSA_MAX_OPERAND_LENGTH], + pC[HAL_RSA_MAX_OPERAND_LENGTH/2], pF[HAL_RSA_MAX_OPERAND_LENGTH/2], + qC[HAL_RSA_MAX_OPERAND_LENGTH/2], qF[HAL_RSA_MAX_OPERAND_LENGTH/2]; }; +#define RSA_FLAG_PRECALC_N_DONE (1 << 0) +#define RSA_FLAG_PRECALC_P_DONE (1 << 1) +#define RSA_FLAG_PRECALC_Q_DONE (1 << 2) + const size_t hal_rsa_key_t_size = sizeof(hal_rsa_key_t); /* @@ -158,7 +175,7 @@ const size_t hal_rsa_key_t_size = sizeof(hal_rsa_key_t); case FP_OKAY: break; \ case FP_VAL: lose(HAL_ERROR_BAD_ARGUMENTS); \ case FP_MEM: lose(HAL_ERROR_ALLOCATION_FAILURE); \ - default: lose(HAL_ERROR_IMPOSSIBLE); \ + default: lose(HAL_ERROR_IMPOSSIBLE); \ } \ } while (0) @@ -171,7 +188,8 @@ static hal_error_t unpack_fp(const fp_int * const bn, uint8_t *buffer, const siz { hal_error_t err = HAL_OK; - assert(bn != NULL && buffer != NULL); + if (bn == NULL || buffer == NULL) + return HAL_ERROR_IMPOSSIBLE; const size_t bytes = fp_unsigned_bin_size(unconst_fp_int(bn)); @@ -193,22 +211,18 @@ static hal_error_t unpack_fp(const fp_int * const bn, uint8_t *buffer, const siz */ static hal_error_t modexp(hal_core_t *core, - const fp_int * msg, + const int precalc_done, + const fp_int * const msg, const fp_int * const exp, const fp_int * const mod, - fp_int *res) + fp_int *res, + uint8_t *coeff, const size_t coeff_len, + uint8_t *mont, const size_t mont_len) { hal_error_t err = HAL_OK; - assert(msg != NULL && exp != NULL && mod != NULL && res != NULL); - - fp_int reduced_msg[1] = INIT_FP_INT; - - if (fp_cmp_mag(unconst_fp_int(msg), unconst_fp_int(mod)) != FP_LT) { - fp_init(reduced_msg); - fp_mod(unconst_fp_int(msg), unconst_fp_int(mod), reduced_msg); - msg = reduced_msg; - } + if (msg == NULL || exp == NULL || mod == NULL || res == NULL || coeff == NULL || mont == NULL) + return HAL_ERROR_IMPOSSIBLE; const size_t msg_len = (fp_unsigned_bin_size(unconst_fp_int(msg)) + 3) & ~3; const size_t exp_len = (fp_unsigned_bin_size(unconst_fp_int(exp)) + 3) & ~3; @@ -222,11 +236,13 @@ static hal_error_t modexp(hal_core_t *core, if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK || (err = unpack_fp(exp, expbuf, sizeof(expbuf))) != HAL_OK || (err = unpack_fp(mod, modbuf, sizeof(modbuf))) != HAL_OK || - (err = hal_modexp(core, + (err = hal_modexp(core, precalc_done, msgbuf, sizeof(msgbuf), expbuf, sizeof(expbuf), modbuf, sizeof(modbuf), - resbuf, sizeof(resbuf))) != HAL_OK) + resbuf, sizeof(resbuf), + coeff, coeff_len, + mont, mont_len)) != HAL_OK) goto fail; fp_read_unsigned_bin(res, resbuf, sizeof(resbuf)); @@ -249,10 +265,14 @@ static hal_error_t modexp(hal_core_t *core, */ static hal_error_t modexp(const hal_core_t *core, /* ignored */ + const int precalc_done, /* ignored */ const fp_int * const msg, const fp_int * const exp, const fp_int * const mod, - fp_int *res) + fp_int *res, + uint8_t *coeff, const size_t coeff_len, /* ignored */ + uint8_t *mont, const size_t mont_len) /* ignored */ + { hal_error_t err = HAL_OK; FP_CHECK(fp_exptmod(unconst_fp_int(msg), unconst_fp_int(exp), unconst_fp_int(mod), res)); @@ -281,7 +301,12 @@ static hal_error_t modexp(const hal_core_t *core, /* ignored */ int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d) { - return modexp(NULL, a, b, c, d) == HAL_OK ? FP_OKAY : FP_VAL; + const size_t len = (fp_unsigned_bin_size(unconst_fp_int(b)) + 3) & ~3; + uint8_t C[len], F[len]; + const hal_error_t err = modexp(NULL, 0, a, b, c, d, C, sizeof(C), F, sizeof(F)); + memset(C, 0, sizeof(C)); + memset(F, 0, sizeof(F)); + return err == HAL_OK ? FP_OKAY : FP_VAL; } #endif /* HAL_RSA_SIGN_USE_MODEXP && HAL_RSA_KEYGEN_USE_MODEXP */ @@ -294,7 +319,8 @@ int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d) static hal_error_t create_blinding_factors(hal_core_t *core, const hal_rsa_key_t * const key, fp_int *bf, fp_int *ubf) { - assert(key != NULL && bf != NULL && ubf != NULL); + if (key == NULL || bf == NULL || ubf == NULL) + return HAL_ERROR_IMPOSSIBLE; uint8_t rnd[fp_unsigned_bin_size(unconst_fp_int(key->n))]; hal_error_t err = HAL_OK; @@ -306,9 +332,12 @@ static hal_error_t create_blinding_factors(hal_core_t *core, const hal_rsa_key_t fp_read_unsigned_bin(bf, rnd, sizeof(rnd)); fp_copy(bf, ubf); - if ((err = modexp(core, bf, key->e, key->n, bf)) != HAL_OK) + if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), bf, key->e, key->n, bf, + key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) != HAL_OK) goto fail; + key->flags |= RSA_FLAG_PRECALC_N_DONE; + FP_CHECK(fp_invmod(ubf, unconst_fp_int(key->n), ubf)); fail: @@ -322,7 +351,8 @@ static hal_error_t create_blinding_factors(hal_core_t *core, const hal_rsa_key_t static hal_error_t rsa_crt(hal_core_t *core, const hal_rsa_key_t * const key, fp_int *msg, fp_int *sig) { - assert(key != NULL && msg != NULL && sig != NULL); + if (key == NULL || msg == NULL || sig == NULL) + return HAL_ERROR_IMPOSSIBLE; hal_error_t err = HAL_OK; fp_int t[1] = INIT_FP_INT; @@ -343,11 +373,18 @@ static hal_error_t rsa_crt(hal_core_t *core, const hal_rsa_key_t * const key, fp /* * m1 = msg ** dP mod p * m2 = msg ** dQ mod q + * + * This is just crying out to be done with parallel cores, but get + * the boring version working before jumping off that cliff. */ - if ((err = modexp(core, msg, key->dP, key->p, m1)) != HAL_OK || - (err = modexp(core, msg, key->dQ, key->q, m2)) != HAL_OK) + if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_P_DONE), + msg, key->dP, key->p, m1, key->pC, sizeof(key->pC), key->pF, sizeof(key->pF))) != HAL_OK || + (err = modexp(core, (key->flags & RSA_FLAG_PRECALC_Q_DONE), + msg, key->dQ, key->q, m2, key->qC, sizeof(key->qC), key->qF, sizeof(key->qF))) != HAL_OK) goto fail; + key->flags |= RSA_FLAG_PRECALC_P_DONE | RSA_FLAG_PRECALC_Q_DONE; + /* * t = m1 - m2. */ @@ -406,11 +443,12 @@ hal_error_t hal_rsa_encrypt(hal_core_t *core, fp_read_unsigned_bin(i, unconst_uint8_t(input), input_len); - if ((err = modexp(core, i, key->e, key->n, o)) != HAL_OK || - (err = unpack_fp(o, output, output_len)) != HAL_OK) - goto fail; + if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), i, key->e, key->n, o, + key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) == HAL_OK) { + key->flags |= RSA_FLAG_PRECALC_N_DONE; + err = unpack_fp(o, output, output_len); + } - fail: fp_zero(i); fp_zero(o); return err; @@ -436,11 +474,13 @@ hal_error_t hal_rsa_decrypt(hal_core_t *core, * just do brute force ModExp. */ - if (fp_iszero(key->p) || fp_iszero(key->q) || fp_iszero(key->u) || fp_iszero(key->dP) || fp_iszero(key->dQ)) - err = modexp(core, i, key->d, key->n, o); - else + if (!fp_iszero(key->p) && !fp_iszero(key->q) && !fp_iszero(key->u) && !fp_iszero(key->dP) && !fp_iszero(key->dQ)) err = rsa_crt(core, key, i, o); + else if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), i, key->d, key->n, o, + key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) == HAL_OK) + key->flags |= RSA_FLAG_PRECALC_N_DONE; + if (err != HAL_OK || (err = unpack_fp(o, output, output_len)) != HAL_OK) goto fail; -- cgit v1.2.3 From 68019ff9624747d3505ef60d3dfb3cfc9b5d7720 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Sat, 9 Sep 2017 02:08:16 -0400 Subject: Whack with club until compiles. --- rsa.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index 90a878f..d964210 100644 --- a/rsa.c +++ b/rsa.c @@ -317,7 +317,7 @@ int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d) * try. Come back to this if it looks like a bottleneck. */ -static hal_error_t create_blinding_factors(hal_core_t *core, const hal_rsa_key_t * const key, fp_int *bf, fp_int *ubf) +static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key, fp_int *bf, fp_int *ubf) { if (key == NULL || bf == NULL || ubf == NULL) return HAL_ERROR_IMPOSSIBLE; @@ -349,7 +349,7 @@ static hal_error_t create_blinding_factors(hal_core_t *core, const hal_rsa_key_t * RSA decryption via Chinese Remainder Theorem (Garner's formula). */ -static hal_error_t rsa_crt(hal_core_t *core, const hal_rsa_key_t * const key, fp_int *msg, fp_int *sig) +static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp_int *sig) { if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_IMPOSSIBLE; @@ -429,7 +429,7 @@ static hal_error_t rsa_crt(hal_core_t *core, const hal_rsa_key_t * const key, fp */ hal_error_t hal_rsa_encrypt(hal_core_t *core, - const hal_rsa_key_t * const key, + hal_rsa_key_t *key, const uint8_t * const input, const size_t input_len, uint8_t * output, const size_t output_len) { @@ -455,7 +455,7 @@ hal_error_t hal_rsa_encrypt(hal_core_t *core, } hal_error_t hal_rsa_decrypt(hal_core_t *core, - const hal_rsa_key_t * const key, + hal_rsa_key_t *key, const uint8_t * const input, const size_t input_len, uint8_t * output, const size_t output_len) { -- cgit v1.2.3 From e3895a788129f57e27716d1ab00df002c96b81a3 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Sat, 9 Sep 2017 23:45:20 -0400 Subject: Far too much fun with modexpa7 operand lengths and locations. --- rsa.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index d964210..9cc940c 100644 --- a/rsa.c +++ b/rsa.c @@ -98,7 +98,7 @@ */ #ifndef HAL_RSA_MAX_OPERAND_LENGTH -#define HAL_RSA_MAX_OPERAND_LENGTH (4096 / 8) +#define HAL_RSA_MAX_OPERAND_LENGTH MODEXPA7_OPERAND_BYTES #endif /* -- cgit v1.2.3 From 8ff9d4131bf79b36551c2ed995881a88fb9c0a61 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Tue, 12 Sep 2017 10:04:55 -0400 Subject: Untested ASN.1 support for ModExpA7 private speedup factors. --- rsa.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 122 insertions(+), 25 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index 9cc940c..e414e93 100644 --- a/rsa.c +++ b/rsa.c @@ -147,9 +147,9 @@ struct hal_rsa_key { qC[HAL_RSA_MAX_OPERAND_LENGTH/2], qF[HAL_RSA_MAX_OPERAND_LENGTH/2]; }; -#define RSA_FLAG_PRECALC_N_DONE (1 << 0) -#define RSA_FLAG_PRECALC_P_DONE (1 << 1) -#define RSA_FLAG_PRECALC_Q_DONE (1 << 2) +#define RSA_FLAG_NEEDS_SAVING (1 << 0) +#define RSA_FLAG_PRECALC_N_DONE (1 << 1) +#define RSA_FLAG_PRECALC_PQ_DONE (1 << 2) const size_t hal_rsa_key_t_size = sizeof(hal_rsa_key_t); @@ -211,7 +211,7 @@ static hal_error_t unpack_fp(const fp_int * const bn, uint8_t *buffer, const siz */ static hal_error_t modexp(hal_core_t *core, - const int precalc_done, + const int precalc, const fp_int * const msg, const fp_int * const exp, const fp_int * const mod, @@ -236,7 +236,7 @@ static hal_error_t modexp(hal_core_t *core, if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK || (err = unpack_fp(exp, expbuf, sizeof(expbuf))) != HAL_OK || (err = unpack_fp(mod, modbuf, sizeof(modbuf))) != HAL_OK || - (err = hal_modexp(core, precalc_done, + (err = hal_modexp(core, precalc, msgbuf, sizeof(msgbuf), expbuf, sizeof(expbuf), modbuf, sizeof(modbuf), @@ -265,7 +265,7 @@ static hal_error_t modexp(hal_core_t *core, */ static hal_error_t modexp(const hal_core_t *core, /* ignored */ - const int precalc_done, /* ignored */ + const int precalc, /* ignored */ const fp_int * const msg, const fp_int * const exp, const fp_int * const mod, @@ -322,6 +322,7 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key, if (key == NULL || bf == NULL || ubf == NULL) return HAL_ERROR_IMPOSSIBLE; + const int precalc = !(key->flags & RSA_FLAG_PRECALC_N_DONE); uint8_t rnd[fp_unsigned_bin_size(unconst_fp_int(key->n))]; hal_error_t err = HAL_OK; @@ -332,11 +333,12 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key, fp_read_unsigned_bin(bf, rnd, sizeof(rnd)); fp_copy(bf, ubf); - if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), bf, key->e, key->n, bf, + if ((err = modexp(core, precalc, bf, key->e, key->n, bf, key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) != HAL_OK) goto fail; - key->flags |= RSA_FLAG_PRECALC_N_DONE; + if (precalc) + key->flags |= RSA_FLAG_PRECALC_N_DONE | RSA_FLAG_NEEDS_SAVING; FP_CHECK(fp_invmod(ubf, unconst_fp_int(key->n), ubf)); @@ -354,6 +356,7 @@ static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_IMPOSSIBLE; + const int precalc = !(key->flags & RSA_FLAG_PRECALC_PQ_DONE); hal_error_t err = HAL_OK; fp_int t[1] = INIT_FP_INT; fp_int m1[1] = INIT_FP_INT; @@ -377,13 +380,14 @@ static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp * This is just crying out to be done with parallel cores, but get * the boring version working before jumping off that cliff. */ - if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_P_DONE), - msg, key->dP, key->p, m1, key->pC, sizeof(key->pC), key->pF, sizeof(key->pF))) != HAL_OK || - (err = modexp(core, (key->flags & RSA_FLAG_PRECALC_Q_DONE), - msg, key->dQ, key->q, m2, key->qC, sizeof(key->qC), key->qF, sizeof(key->qF))) != HAL_OK) + if ((err = modexp(core, precalc, msg, key->dP, key->p, m1, + key->pC, sizeof(key->pC), key->pF, sizeof(key->pF))) != HAL_OK || + (err = modexp(core, precalc, msg, key->dQ, key->q, m2, + key->qC, sizeof(key->qC), key->qF, sizeof(key->qF))) != HAL_OK) goto fail; - key->flags |= RSA_FLAG_PRECALC_P_DONE | RSA_FLAG_PRECALC_Q_DONE; + if (precalc) + key->flags |= RSA_FLAG_PRECALC_PQ_DONE | RSA_FLAG_NEEDS_SAVING; /* * t = m1 - m2. @@ -438,16 +442,20 @@ hal_error_t hal_rsa_encrypt(hal_core_t *core, if (key == NULL || input == NULL || output == NULL || input_len > output_len) return HAL_ERROR_BAD_ARGUMENTS; + const int precalc = !(key->flags & RSA_FLAG_PRECALC_N_DONE); fp_int i[1] = INIT_FP_INT; fp_int o[1] = INIT_FP_INT; fp_read_unsigned_bin(i, unconst_uint8_t(input), input_len); - if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), i, key->e, key->n, o, - key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) == HAL_OK) { - key->flags |= RSA_FLAG_PRECALC_N_DONE; + err = modexp(core, precalc, i, key->e, key->n, o, + key->nC, sizeof(key->nC), key->nF, sizeof(key->nF)); + + if (err == HAL_OK && precalc) + key->flags |= RSA_FLAG_PRECALC_N_DONE | RSA_FLAG_NEEDS_SAVING; + + if (err == HAL_OK) err = unpack_fp(o, output, output_len); - } fp_zero(i); fp_zero(o); @@ -474,12 +482,17 @@ hal_error_t hal_rsa_decrypt(hal_core_t *core, * just do brute force ModExp. */ - if (!fp_iszero(key->p) && !fp_iszero(key->q) && !fp_iszero(key->u) && !fp_iszero(key->dP) && !fp_iszero(key->dQ)) + if (!fp_iszero(key->p) && !fp_iszero(key->q) && !fp_iszero(key->u) && + !fp_iszero(key->dP) && !fp_iszero(key->dQ)) err = rsa_crt(core, key, i, o); - else if ((err = modexp(core, (key->flags & RSA_FLAG_PRECALC_N_DONE), i, key->d, key->n, o, - key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) == HAL_OK) - key->flags |= RSA_FLAG_PRECALC_N_DONE; + else { + const int precalc = !(key->flags & RSA_FLAG_PRECALC_N_DONE); + err = modexp(core, precalc, i, key->d, key->n, o, key->nC, sizeof(key->nC), + key->nF, sizeof(key->nF)); + if (err == HAL_OK && precalc) + key->flags |= RSA_FLAG_PRECALC_N_DONE | RSA_FLAG_NEEDS_SAVING; + } if (err != HAL_OK || (err = unpack_fp(o, output, output_len)) != HAL_OK) goto fail; @@ -802,6 +815,8 @@ hal_error_t hal_rsa_key_gen(hal_core_t *core, FP_CHECK(fp_mod(key->d, q_1, key->dQ)); /* dQ = d % (q-1) */ FP_CHECK(fp_invmod(key->q, key->p, key->u)); /* u = (1/q) % p */ + key->flags |= RSA_FLAG_NEEDS_SAVING; + *key_ = key; /* Fall through to cleanup */ @@ -814,11 +829,27 @@ hal_error_t hal_rsa_key_gen(hal_core_t *core, return err; } +/* + * Whether a key contains new data that need saving (newly generated + * key, updated speedup components, whatever). + */ + +int hal_rsa_key_needs_saving(const hal_rsa_key_t * const key) +{ + return key != NULL && (key->flags & RSA_FLAG_NEEDS_SAVING); +} + /* * Just enough ASN.1 to read and write PKCS #1.5 RSAPrivateKey syntax * (RFC 2313 section 7.2) wrapped in a PKCS #8 PrivateKeyInfo (RFC 5208). * * RSAPrivateKey fields in the required order. + * + * The "extra" fields are additional key components specific to the + * systolic modexpa7 core. We represent these in ASN.1 as OPTIONAL + * fields using IMPLICIT PRIVATE tags, since this is neither + * standardized nor meaningful to anybody else. Underlying encoding + * is INTEGER or OCTET STRING (currently the latter). */ #define RSAPrivateKey_fields \ @@ -832,8 +863,17 @@ hal_error_t hal_rsa_key_gen(hal_core_t *core, _(key->dQ); \ _(key->u); -hal_error_t hal_rsa_private_key_to_der(const hal_rsa_key_t * const key, - uint8_t *der, size_t *der_len, const size_t der_max) +#define RSAPrivateKey_extra_fields \ + _(ASN1_PRIVATE + 0, nC, RSA_FLAG_PRECALC_N_DONE); \ + _(ASN1_PRIVATE + 1, nF, RSA_FLAG_PRECALC_N_DONE); \ + _(ASN1_PRIVATE + 2, pC, RSA_FLAG_PRECALC_PQ_DONE); \ + _(ASN1_PRIVATE + 3, pF, RSA_FLAG_PRECALC_PQ_DONE); \ + _(ASN1_PRIVATE + 4, qC, RSA_FLAG_PRECALC_PQ_DONE); \ + _(ASN1_PRIVATE + 5, qF, RSA_FLAG_PRECALC_PQ_DONE); + +hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const key, + const int include_extra, + uint8_t *der, size_t *der_len, const size_t der_max) { hal_error_t err = HAL_OK; @@ -848,10 +888,24 @@ hal_error_t hal_rsa_private_key_to_der(const hal_rsa_key_t * const key, size_t hlen = 0, vlen = 0; -#define _(x) { size_t n; if ((err = hal_asn1_encode_integer(x, NULL, &n, der_max - vlen)) != HAL_OK) return err; vlen += n; } +#define _(x) { size_t n = 0; if ((err = hal_asn1_encode_integer(x, NULL, &n, der_max - vlen)) != HAL_OK) return err; vlen += n; } RSAPrivateKey_fields; #undef _ +#define _(x,y,z) \ + if ((key->flags & z) != 0) { \ + size_t n = 0; \ + if ((err = hal_asn1_encode_HEADER(x, sizeof(key->y), NULL, \ + &n, 0)) != HAL_OK) \ + return err; \ + vlen += n + sizeof(key->y); \ + } + + if (include_extra) { + RSAPrivateKey_extra_fields; + } +#undef _ + if ((err = hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0)) != HAL_OK) return err; @@ -872,14 +926,41 @@ hal_error_t hal_rsa_private_key_to_der(const hal_rsa_key_t * const key, uint8_t *d = der + hlen; memset(d, 0, vlen); -#define _(x) { size_t n; if ((err = hal_asn1_encode_integer(x, d, &n, vlen)) != HAL_OK) return err; d += n; vlen -= n; } +#define _(x) { size_t n = 0; if ((err = hal_asn1_encode_integer(x, d, &n, vlen)) != HAL_OK) return err; d += n; vlen -= n; } RSAPrivateKey_fields; #undef _ +#define _(x,y,z) \ + if ((key->flags & z) != 0) { \ + size_t n = 0; \ + if ((err = hal_asn1_encode_header(x, sizeof(key->y), d, \ + &n, vlen)) != HAL_OK) \ + return err; \ + d += n + sizeof(key->y); \ + vlen -= n + sizeof(key->y); \ + } + + if (include_extra) { + RSAPrivateKey_extra_fields; + } +#undef _ + return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_rsaEncryption, hal_asn1_oid_rsaEncryption_len, NULL, 0, der, d - der, der, der_len, der_max); } +hal_error_t hal_rsa_private_key_to_der(const hal_rsa_key_t * const key, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + return hal_rsa_private_key_to_der_extra_maybe(key, 0, der, der_len, der_max); +} + +hal_error_t hal_rsa_private_key_to_der_extra(const hal_rsa_key_t * const key, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + return hal_rsa_private_key_to_der_extra_maybe(key, 1, der, der_len, der_max); +} + size_t hal_rsa_private_key_to_der_len(const hal_rsa_key_t * const key) { size_t len = 0; @@ -925,6 +1006,22 @@ hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, RSAPrivateKey_fields; #undef _ +#define _(x,y,z) \ + if (hal_asn1_peek(d, vlen, x) { \ + size_t hl = 0, vl = 0; \ + if ((err = hal_asn1_decode_header(x, d, vlen, &hl, &vl)) != HAL_OK) \ + return err; \ + if (vl > sizeof(key->y)) \ + return HAL_ERROR_ASN1_PARSE_FAILED; \ + memcpy(key->y, d + hl, vl); \ + key->flags |= z; \ + d += hl + vl; \ + vlen -= hl + vl; \ + } + + RSAPrivateKey_extra_fields; +#undef _ + if (d != privkey + privkey_len || !fp_iszero(version)) return HAL_ERROR_ASN1_PARSE_FAILED; -- cgit v1.2.3 From ae2985215d2329ac9663bbbedd925ec1b61cfaa1 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Tue, 12 Sep 2017 10:19:27 -0400 Subject: Silly macro bugs. --- rsa.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index e414e93..24dc66f 100644 --- a/rsa.c +++ b/rsa.c @@ -895,7 +895,7 @@ hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const k #define _(x,y,z) \ if ((key->flags & z) != 0) { \ size_t n = 0; \ - if ((err = hal_asn1_encode_HEADER(x, sizeof(key->y), NULL, \ + if ((err = hal_asn1_encode_header(x, sizeof(key->y), NULL, \ &n, 0)) != HAL_OK) \ return err; \ vlen += n + sizeof(key->y); \ @@ -1007,7 +1007,7 @@ hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, #undef _ #define _(x,y,z) \ - if (hal_asn1_peek(d, vlen, x) { \ + if (hal_asn1_peek(x, d, vlen)) { \ size_t hl = 0, vl = 0; \ if ((err = hal_asn1_decode_header(x, d, vlen, &hl, &vl)) != HAL_OK) \ return err; \ -- cgit v1.2.3 From 5522df4f68bfa66b9b4446fdfb92783694586f70 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Wed, 13 Sep 2017 11:28:13 -0400 Subject: Sort-of-working, large (4096-bit) RSA keys broken. Snapshot of mostly but not entirely working code to include the extra ModExpA7 key components in the keystore. Need to investigate whether a more compact representation is practical for these components, as the current one bloats the key object so much that a bare 4096-bit key won't fit in a single hash block, and there may not be enough room for PKCS #11 attributes even for smaller keys. If more compact representation not possible or insufficient, the other option is to double the size of a keystore object, making it two flash subsectors for a total of 8192 octets. Which would of course halve the number of keys we can store and require a bunch of little tweaks all through the ks code (particularly flash erase), so definitely worth trying for a more compact representation first. --- rsa.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 52 insertions(+), 18 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index 24dc66f..dace19b 100644 --- a/rsa.c +++ b/rsa.c @@ -871,9 +871,9 @@ int hal_rsa_key_needs_saving(const hal_rsa_key_t * const key) _(ASN1_PRIVATE + 4, qC, RSA_FLAG_PRECALC_PQ_DONE); \ _(ASN1_PRIVATE + 5, qF, RSA_FLAG_PRECALC_PQ_DONE); -hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const key, - const int include_extra, - uint8_t *der, size_t *der_len, const size_t der_max) +hal_error_t hal_rsa_private_key_to_der_internal(const hal_rsa_key_t * const key, + const int include_extra, + uint8_t *der, size_t *der_len, const size_t der_max) { hal_error_t err = HAL_OK; @@ -888,7 +888,15 @@ hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const k size_t hlen = 0, vlen = 0; -#define _(x) { size_t n = 0; if ((err = hal_asn1_encode_integer(x, NULL, &n, der_max - vlen)) != HAL_OK) return err; vlen += n; } +#define _(x) \ + { \ + size_t n = 0; \ + err = hal_asn1_encode_integer(x, NULL, &n, der_max - vlen); \ + if (err != HAL_OK) \ + return err; \ + vlen += n; \ + } + RSAPrivateKey_fields; #undef _ @@ -926,7 +934,16 @@ hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const k uint8_t *d = der + hlen; memset(d, 0, vlen); -#define _(x) { size_t n = 0; if ((err = hal_asn1_encode_integer(x, d, &n, vlen)) != HAL_OK) return err; d += n; vlen -= n; } +#define _(x) \ + { \ + size_t n = 0; \ + err = hal_asn1_encode_integer(x, d, &n, vlen); \ + if (err != HAL_OK) \ + return err; \ + d += n; \ + vlen -= n; \ + } + RSAPrivateKey_fields; #undef _ @@ -936,8 +953,11 @@ hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const k if ((err = hal_asn1_encode_header(x, sizeof(key->y), d, \ &n, vlen)) != HAL_OK) \ return err; \ - d += n + sizeof(key->y); \ - vlen -= n + sizeof(key->y); \ + d += n; \ + vlen -= n; \ + memcpy(d, key->y, sizeof(key->y)); \ + d += sizeof(key->y); \ + vlen -= sizeof(key->y); \ } if (include_extra) { @@ -952,19 +972,13 @@ hal_error_t hal_rsa_private_key_to_der_extra_maybe(const hal_rsa_key_t * const k hal_error_t hal_rsa_private_key_to_der(const hal_rsa_key_t * const key, uint8_t *der, size_t *der_len, const size_t der_max) { - return hal_rsa_private_key_to_der_extra_maybe(key, 0, der, der_len, der_max); + return hal_rsa_private_key_to_der_internal(key, 0, der, der_len, der_max); } hal_error_t hal_rsa_private_key_to_der_extra(const hal_rsa_key_t * const key, uint8_t *der, size_t *der_len, const size_t der_max) { - return hal_rsa_private_key_to_der_extra_maybe(key, 1, der, der_len, der_max); -} - -size_t hal_rsa_private_key_to_der_len(const hal_rsa_key_t * const key) -{ - size_t len = 0; - return hal_rsa_private_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0; + return hal_rsa_private_key_to_der_internal(key, 1, der, der_len, der_max); } hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, @@ -1002,7 +1016,16 @@ hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, fp_int version[1] = INIT_FP_INT; -#define _(x) { size_t n; if ((err = hal_asn1_decode_integer(x, d, &n, vlen)) != HAL_OK) return err; d += n; vlen -= n; } +#define _(x) \ + { \ + size_t n; \ + err = hal_asn1_decode_integer(x, d, &n, vlen); \ + if (err != HAL_OK) \ + return err; \ + d += n; \ + vlen -= n; \ + } + RSAPrivateKey_fields; #undef _ @@ -1011,8 +1034,11 @@ hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, size_t hl = 0, vl = 0; \ if ((err = hal_asn1_decode_header(x, d, vlen, &hl, &vl)) != HAL_OK) \ return err; \ - if (vl > sizeof(key->y)) \ + if (vl > sizeof(key->y)) { \ + hal_log(HAL_LOG_DEBUG, "extra factor %s too big (%lu > %lu)", \ + #y, (unsigned long) vl, (unsigned long) sizeof(key->y)); \ return HAL_ERROR_ASN1_PARSE_FAILED; \ + } \ memcpy(key->y, d + hl, vl); \ key->flags |= z; \ d += hl + vl; \ @@ -1022,8 +1048,16 @@ hal_error_t hal_rsa_private_key_from_der(hal_rsa_key_t **key_, RSAPrivateKey_extra_fields; #undef _ - if (d != privkey + privkey_len || !fp_iszero(version)) + if (d != privkey + privkey_len) { + hal_log(HAL_LOG_DEBUG, "not at end of buffer (0x%lx != 0x%lx)", + (unsigned long) d, (unsigned long) privkey + privkey_len); return HAL_ERROR_ASN1_PARSE_FAILED; + } + + if (!fp_iszero(version)) { + hal_log(HAL_LOG_DEBUG, "nonzero version"); + return HAL_ERROR_ASN1_PARSE_FAILED; + } *key_ = key; -- cgit v1.2.3 From 410e0cf1d22c67585f0a5346e62f60aa4e90fe05 Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Wed, 13 Sep 2017 20:20:55 -0400 Subject: Preliminary support for parallel core RSA CRT. --- rsa.c | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 119 insertions(+), 19 deletions(-) (limited to 'rsa.c') diff --git a/rsa.c b/rsa.c index dace19b..44ad84e 100644 --- a/rsa.c +++ b/rsa.c @@ -233,16 +233,20 @@ static hal_error_t modexp(hal_core_t *core, uint8_t modbuf[mod_len]; uint8_t resbuf[mod_len]; + hal_modexp_arg_t args = { + .core = core, + .msg = msgbuf, .msg_len = sizeof(msgbuf), + .exp = expbuf, .exp_len = sizeof(expbuf), + .mod = modbuf, .mod_len = sizeof(modbuf), + .result = resbuf, .result_len = sizeof(resbuf), + .coeff = coeff, .coeff_len = coeff_len, + .mont = mont, .mont_len = mont_len + }; + if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK || (err = unpack_fp(exp, expbuf, sizeof(expbuf))) != HAL_OK || (err = unpack_fp(mod, modbuf, sizeof(modbuf))) != HAL_OK || - (err = hal_modexp(core, precalc, - msgbuf, sizeof(msgbuf), - expbuf, sizeof(expbuf), - modbuf, sizeof(modbuf), - resbuf, sizeof(resbuf), - coeff, coeff_len, - mont, mont_len)) != HAL_OK) + (err = hal_modexp(precalc, &args)) != HAL_OK) goto fail; fp_read_unsigned_bin(res, resbuf, sizeof(resbuf)); @@ -252,6 +256,83 @@ static hal_error_t modexp(hal_core_t *core, memset(expbuf, 0, sizeof(expbuf)); memset(modbuf, 0, sizeof(modbuf)); memset(resbuf, 0, sizeof(resbuf)); + memset(&args, 0, sizeof(args)); + return err; +} + +static hal_error_t modexp2(const int precalc, + const fp_int * const msg, + hal_core_t *core1, + const fp_int * const exp1, + const fp_int * const mod1, + fp_int * res1, + uint8_t *coeff1, const size_t coeff1_len, + uint8_t *mont1, const size_t mont1_len, + hal_core_t *core2, + const fp_int * const exp2, + const fp_int * const mod2, + fp_int * res2, + uint8_t *coeff2, const size_t coeff2_len, + uint8_t *mont2, const size_t mont2_len) +{ + hal_error_t err = HAL_OK; + + if (msg == NULL || + exp1 == NULL || mod1 == NULL || res1 == NULL || coeff1 == NULL || mont1 == NULL || + exp2 == NULL || mod2 == NULL || res2 == NULL || coeff2 == NULL || mont2 == NULL) + return HAL_ERROR_IMPOSSIBLE; + + const size_t msg_len = (fp_unsigned_bin_size(unconst_fp_int(msg)) + 3) & ~3; + const size_t exp1_len = (fp_unsigned_bin_size(unconst_fp_int(exp1)) + 3) & ~3; + const size_t mod1_len = (fp_unsigned_bin_size(unconst_fp_int(mod1)) + 3) & ~3; + const size_t exp2_len = (fp_unsigned_bin_size(unconst_fp_int(exp2)) + 3) & ~3; + const size_t mod2_len = (fp_unsigned_bin_size(unconst_fp_int(mod2)) + 3) & ~3; + + uint8_t msgbuf[msg_len]; + uint8_t expbuf1[exp1_len], modbuf1[mod1_len], resbuf1[mod1_len]; + uint8_t expbuf2[exp2_len], modbuf2[mod2_len], resbuf2[mod2_len]; + + hal_modexp_arg_t args1 = { + .core = core1, + .msg = msgbuf, .msg_len = sizeof(msgbuf), + .exp = expbuf1, .exp_len = sizeof(expbuf1), + .mod = modbuf1, .mod_len = sizeof(modbuf1), + .result = resbuf1, .result_len = sizeof(resbuf1), + .coeff = coeff1, .coeff_len = coeff1_len, + .mont = mont1, .mont_len = mont1_len + }; + + hal_modexp_arg_t args2 = { + .core = core2, + .msg = msgbuf, .msg_len = sizeof(msgbuf), + .exp = expbuf2, .exp_len = sizeof(expbuf2), + .mod = modbuf2, .mod_len = sizeof(modbuf2), + .result = resbuf2, .result_len = sizeof(resbuf2), + .coeff = coeff2, .coeff_len = coeff2_len, + .mont = mont2, .mont_len = mont2_len + }; + + if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK || + (err = unpack_fp(exp1, expbuf1, sizeof(expbuf1))) != HAL_OK || + (err = unpack_fp(mod1, modbuf1, sizeof(modbuf1))) != HAL_OK || + (err = unpack_fp(exp2, expbuf2, sizeof(expbuf2))) != HAL_OK || + (err = unpack_fp(mod2, modbuf2, sizeof(modbuf2))) != HAL_OK || + (err = hal_modexp2(precalc, &args1, &args2)) != HAL_OK) + goto fail; + + fp_read_unsigned_bin(res1, resbuf1, sizeof(resbuf1)); + fp_read_unsigned_bin(res2, resbuf2, sizeof(resbuf2)); + + fail: + memset(msgbuf, 0, sizeof(msgbuf)); + memset(expbuf1, 0, sizeof(expbuf1)); + memset(modbuf1, 0, sizeof(modbuf1)); + memset(resbuf1, 0, sizeof(resbuf1)); + memset(&args1, 0, sizeof(args1)); + memset(expbuf2, 0, sizeof(expbuf2)); + memset(modbuf2, 0, sizeof(modbuf2)); + memset(resbuf2, 0, sizeof(resbuf2)); + memset(&args2, 0, sizeof(args2)); return err; } @@ -280,6 +361,28 @@ static hal_error_t modexp(const hal_core_t *core, /* ignored */ return err; } +static hal_error_t modexp2(const int precalc, /* ignored */ + const fp_int * const msg, + hal_core_t *core1, /* ignored */ + const fp_int * const exp1, + const fp_int * const mod1, + fp_int * res1, + uint8_t *coeff1, const size_t coeff1_len, /* ignored */ + uint8_t *mont1, const size_t mont1_len, /* ignored */ + hal_core_t *core2, /* ignored */ + const fp_int * const exp2, + const fp_int * const mod2, + fp_int * res2, + uint8_t *coeff2, const size_t coeff2_len, /* ignored */ + uint8_t *mont2, const size_t mont2_len) /* ignored */ +{ + hal_error_t err = HAL_OK; + FP_CHECK(fp_exptmod(unconst_fp_int(msg), unconst_fp_int(exp1), unconst_fp_int(mod1), res1)); + FP_CHECK(fp_exptmod(unconst_fp_int(msg), unconst_fp_int(exp2), unconst_fp_int(mod2), res2)); + fail: + return err; +} + #endif /* HAL_RSA_SIGN_USE_MODEXP */ /* @@ -351,7 +454,7 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key, * RSA decryption via Chinese Remainder Theorem (Garner's formula). */ -static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp_int *sig) +static hal_error_t rsa_crt(hal_core_t *core1, hal_core_t *core2, hal_rsa_key_t *key, fp_int *msg, fp_int *sig) { if (key == NULL || msg == NULL || sig == NULL) return HAL_ERROR_IMPOSSIBLE; @@ -368,7 +471,7 @@ static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp * Handle blinding if requested. */ if (blinding) { - if ((err = create_blinding_factors(core, key, bf, ubf)) != HAL_OK) + if ((err = create_blinding_factors(core1, key, bf, ubf)) != HAL_OK) goto fail; FP_CHECK(fp_mulmod(msg, bf, unconst_fp_int(key->n), msg)); } @@ -376,14 +479,10 @@ static hal_error_t rsa_crt(hal_core_t *core, hal_rsa_key_t *key, fp_int *msg, fp /* * m1 = msg ** dP mod p * m2 = msg ** dQ mod q - * - * This is just crying out to be done with parallel cores, but get - * the boring version working before jumping off that cliff. */ - if ((err = modexp(core, precalc, msg, key->dP, key->p, m1, - key->pC, sizeof(key->pC), key->pF, sizeof(key->pF))) != HAL_OK || - (err = modexp(core, precalc, msg, key->dQ, key->q, m2, - key->qC, sizeof(key->qC), key->qF, sizeof(key->qF))) != HAL_OK) + if ((err = modexp2(precalc, msg, + core1, key->dP, key->p, m1, key->pC, sizeof(key->pC), key->pF, sizeof(key->pF), + core2, key->dQ, key->q, m2, key->qC, sizeof(key->qC), key->qF, sizeof(key->qF))) != HAL_OK) goto fail; if (precalc) @@ -462,7 +561,8 @@ hal_error_t hal_rsa_encrypt(hal_core_t *core, return err; } -hal_error_t hal_rsa_decrypt(hal_core_t *core, +hal_error_t hal_rsa_decrypt(hal_core_t *core1, + hal_core_t *core2, hal_rsa_key_t *key, const uint8_t * const input, const size_t input_len, uint8_t * output, const size_t output_len) @@ -484,11 +584,11 @@ hal_error_t hal_rsa_decrypt(hal_core_t *core, if (!fp_iszero(key->p) && !fp_iszero(key->q) && !fp_iszero(key->u) && !fp_iszero(key->dP) && !fp_iszero(key->dQ)) - err = rsa_crt(core, key, i, o); + err = rsa_crt(core1, core2, key, i, o); else { const int precalc = !(key->flags & RSA_FLAG_PRECALC_N_DONE); - err = modexp(core, precalc, i, key->d, key->n, o, key->nC, sizeof(key->nC), + err = modexp(core1, precalc, i, key->d, key->n, o, key->nC, sizeof(key->nC), key->nF, sizeof(key->nF)); if (err == HAL_OK && precalc) key->flags |= RSA_FLAG_PRECALC_N_DONE | RSA_FLAG_NEEDS_SAVING; -- cgit v1.2.3