From 83bd850f3fd45648bb811f6080efac396c8a2062 Mon Sep 17 00:00:00 2001 From: Nicolas Boichat Date: Tue, 7 Feb 2017 11:40:59 +0800 Subject: vboot_reference: Add support for 2048-bit exponent 3 keys This also adds the required tests (keys, testcases). BRANCH=none BUG=chromium:684354 TEST=make runtests Change-Id: I5e148f8792ea325f813d76089271f3c4bcc2935d Reviewed-on: https://chromium-review.googlesource.com/438951 Commit-Ready: Nicolas Boichat Tested-by: Nicolas Boichat Reviewed-by: Randall Spangler --- firmware/2lib/2rsa.c | 88 +++++++++++++++++++--- firmware/2lib/2sha_utility.c | 3 + firmware/2lib/include/2crypto.h | 5 +- futility/file_type_usbpd1.c | 2 + host/lib21/host_key.c | 34 ++++++--- tests/common.sh | 2 +- tests/futility/test_show_rwsig.sh | 2 +- tests/gen_test_keys.sh | 10 ++- tests/testcases/test_file.rsa2048_exp3_sha1.sig | Bin 0 -> 256 bytes tests/testcases/test_file.rsa2048_exp3_sha256.sig | 2 + tests/testcases/test_file.rsa2048_exp3_sha512.sig | Bin 0 -> 256 bytes tests/testkeys/key_rsa2048_exp3.crt | 20 +++++ tests/testkeys/key_rsa2048_exp3.keyb | Bin 0 -> 520 bytes tests/testkeys/key_rsa2048_exp3.pem | 27 +++++++ tests/testkeys/key_rsa2048_exp3.sha1.vbprivk | Bin 0 -> 1200 bytes tests/testkeys/key_rsa2048_exp3.sha1.vbpubk | Bin 0 -> 552 bytes tests/testkeys/key_rsa2048_exp3.sha256.vbprivk | Bin 0 -> 1200 bytes tests/testkeys/key_rsa2048_exp3.sha256.vbpubk | Bin 0 -> 552 bytes tests/testkeys/key_rsa2048_exp3.sha512.vbprivk | Bin 0 -> 1200 bytes tests/testkeys/key_rsa2048_exp3.sha512.vbpubk | Bin 0 -> 552 bytes utility/dumpRSAPublicKey.c | 5 +- 21 files changed, 174 insertions(+), 26 deletions(-) create mode 100644 tests/testcases/test_file.rsa2048_exp3_sha1.sig create mode 100644 tests/testcases/test_file.rsa2048_exp3_sha256.sig create mode 100644 tests/testcases/test_file.rsa2048_exp3_sha512.sig create mode 100644 tests/testkeys/key_rsa2048_exp3.crt create mode 100644 tests/testkeys/key_rsa2048_exp3.keyb create mode 100644 tests/testkeys/key_rsa2048_exp3.pem create mode 100644 tests/testkeys/key_rsa2048_exp3.sha1.vbprivk create mode 100644 tests/testkeys/key_rsa2048_exp3.sha1.vbpubk create mode 100644 tests/testkeys/key_rsa2048_exp3.sha256.vbprivk create mode 100644 tests/testkeys/key_rsa2048_exp3.sha256.vbpubk create mode 100644 tests/testkeys/key_rsa2048_exp3.sha512.vbprivk create mode 100644 tests/testkeys/key_rsa2048_exp3.sha512.vbpubk diff --git a/firmware/2lib/2rsa.c b/firmware/2lib/2rsa.c index 7862b133..48e1ec33 100644 --- a/firmware/2lib/2rsa.c +++ b/firmware/2lib/2rsa.c @@ -72,6 +72,25 @@ static void montMulAdd(const struct vb2_public_key *key, } } +/** + * Montgomery c[] += 0 * b[] / R % mod + */ +static void montMulAdd0(const struct vb2_public_key *key, + uint32_t *c, + const uint32_t *b) +{ + uint32_t d0 = c[0] * key->n0inv; + uint64_t B = (uint64_t)d0 * key->n[0] + c[0]; + uint32_t i; + + for (i = 1; i < key->arrsize; ++i) { + B = (B >> 32) + (uint64_t)d0 * key->n[i] + c[i]; + c[i - 1] = (uint32_t)B; + } + + c[i - 1] = B >> 32; +} + /** * Montgomery c[] = a[] * b[] / R % mod */ @@ -89,16 +108,32 @@ static void montMul(const struct vb2_public_key *key, } } +/* Montgomery c[] = a[] * 1 / R % key. */ +static void montMul1(const struct vb2_public_key *key, + uint32_t *c, + const uint32_t *a) +{ + int i; + + for (i = 0; i < key->arrsize; ++i) + c[i] = 0; + + montMulAdd(key, c, 1, a); + for (i = 1; i < key->arrsize; ++i) + montMulAdd0(key, c, a); +} + /** - * In-place public exponentiation. (65537} + * In-place public exponentiation. * * @param key Key to use in signing * @param inout Input and output big-endian byte array * @param workbuf32 Work buffer; caller must verify this is * (3 * key->arrsize) elements long. + * @param exp RSA public exponent: either 65537 (F4) or 3 */ -static void modpowF4(const struct vb2_public_key *key, uint8_t *inout, - uint32_t *workbuf32) +static void modpow(const struct vb2_public_key *key, uint8_t *inout, + uint32_t *workbuf32, int exp) { uint32_t *a = workbuf32; uint32_t *aR = a + key->arrsize; @@ -117,12 +152,18 @@ static void modpowF4(const struct vb2_public_key *key, uint8_t *inout, } montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ - for (i = 0; i < 16; i+=2) { - montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ - montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ + if (exp == 3) { + montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ + montMul(key, a, aaR, aR); /* a = aaR * aR / R mod M */ + montMul1(key, aaa, a); /* aaa = a * 1 / R mod M */ + } else { + /* Exponent 65537 */ + for (i = 0; i < 16; i+=2) { + montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ + montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ + } + montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ } - montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ - /* Make sure aaa < mod; aaa is at most 1x mod too large. */ if (vb2_mont_ge(key, aaa)) { @@ -153,6 +194,9 @@ static const uint8_t crypto_to_sig[] = { VB2_SIG_RSA8192, VB2_SIG_RSA8192, VB2_SIG_RSA8192, + VB2_SIG_RSA2048_EXP3, + VB2_SIG_RSA2048_EXP3, + VB2_SIG_RSA2048_EXP3, }; /** @@ -178,6 +222,7 @@ uint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg) case VB2_SIG_RSA1024: return 1024 / 8; case VB2_SIG_RSA2048: + case VB2_SIG_RSA2048_EXP3: return 2048 / 8; case VB2_SIG_RSA4096: return 4096 / 8; @@ -188,6 +233,27 @@ uint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg) } } +/** + * Return the exponent used by an RSA algorithm + * + * @param sig_alg Signature algorithm + * @return The exponent to use (3 or 65537(F4)), or 0 if error. + */ +static uint32_t vb2_rsa_exponent(enum vb2_signature_algorithm sig_alg) +{ + switch (sig_alg) { + case VB2_SIG_RSA1024: + case VB2_SIG_RSA2048: + case VB2_SIG_RSA4096: + case VB2_SIG_RSA8192: + return 65537; + case VB2_SIG_RSA2048_EXP3: + return 3; + default: + return 0; + } +} + uint32_t vb2_packed_key_size(enum vb2_signature_algorithm sig_alg) { uint32_t sig_size = vb2_rsa_sig_size(sig_alg); @@ -298,13 +364,15 @@ int vb2_rsa_verify_digest(const struct vb2_public_key *key, uint32_t key_bytes; int sig_size; int pad_size; + int exp; int rv; if (!key || !sig || !digest) return VB2_ERROR_RSA_VERIFY_PARAM; sig_size = vb2_rsa_sig_size(key->sig_alg); - if (!sig_size) { + exp = vb2_rsa_exponent(key->sig_alg); + if (!sig_size || !exp) { VB2_DEBUG("Invalid signature type!\n"); return VB2_ERROR_RSA_VERIFY_ALGORITHM; } @@ -322,7 +390,7 @@ int vb2_rsa_verify_digest(const struct vb2_public_key *key, return VB2_ERROR_RSA_VERIFY_WORKBUF; } - modpowF4(key, sig, workbuf32); + modpow(key, sig, workbuf32, exp); vb2_workbuf_free(&wblocal, 3 * key_bytes); diff --git a/firmware/2lib/2sha_utility.c b/firmware/2lib/2sha_utility.c index dd74f290..7193091b 100644 --- a/firmware/2lib/2sha_utility.c +++ b/firmware/2lib/2sha_utility.c @@ -40,6 +40,9 @@ static const uint8_t crypto_to_hash[] = { CTH_SHA1, CTH_SHA256, CTH_SHA512, + CTH_SHA1, + CTH_SHA256, + CTH_SHA512, }; enum vb2_hash_algorithm vb2_crypto_to_hash(uint32_t algorithm) diff --git a/firmware/2lib/include/2crypto.h b/firmware/2lib/include/2crypto.h index da1c2ddf..a33b5360 100644 --- a/firmware/2lib/include/2crypto.h +++ b/firmware/2lib/include/2crypto.h @@ -23,7 +23,9 @@ enum vb2_crypto_algorithm { VB2_ALG_RSA8192_SHA1 = 9, VB2_ALG_RSA8192_SHA256 = 10, VB2_ALG_RSA8192_SHA512 = 11, - + VB2_ALG_RSA2048_EXP3_SHA1 = 12, + VB2_ALG_RSA2048_EXP3_SHA256 = 13, + VB2_ALG_RSA2048_EXP3_SHA512 = 14, /* Number of algorithms */ VB2_ALG_COUNT }; @@ -44,6 +46,7 @@ enum vb2_signature_algorithm { VB2_SIG_RSA2048 = 3, VB2_SIG_RSA4096 = 4, VB2_SIG_RSA8192 = 5, + VB2_SIG_RSA2048_EXP3 = 6, /* Last index. Don't add anything below. */ VB2_SIG_ALG_COUNT, diff --git a/futility/file_type_usbpd1.c b/futility/file_type_usbpd1.c index 81430855..131e0033 100644 --- a/futility/file_type_usbpd1.c +++ b/futility/file_type_usbpd1.c @@ -256,6 +256,7 @@ done: */ static enum vb2_signature_algorithm sigs[] = { VB2_SIG_RSA2048, + VB2_SIG_RSA2048_EXP3, VB2_SIG_RSA1024, VB2_SIG_RSA4096, VB2_SIG_RSA8192, @@ -277,6 +278,7 @@ static uint32_t usbpd1_packed_key_size(enum vb2_signature_algorithm sig_alg) case VB2_SIG_RSA1024: return 272; case VB2_SIG_RSA2048: + case VB2_SIG_RSA2048_EXP3: return 528; case VB2_SIG_RSA4096: return 1040; diff --git a/host/lib21/host_key.c b/host/lib21/host_key.c index ecb7328b..be36df71 100644 --- a/host/lib21/host_key.c +++ b/host/lib21/host_key.c @@ -23,6 +23,7 @@ const struct vb2_text_vs_enum vb2_text_vs_sig[] = { {"RSA2048", VB2_SIG_RSA2048}, {"RSA4096", VB2_SIG_RSA4096}, {"RSA8192", VB2_SIG_RSA8192}, + {"RSA2048EXP3", VB2_SIG_RSA2048_EXP3}, {0, 0} }; @@ -403,7 +404,10 @@ int vb2_public_key_read_keyb(struct vb2_public_key **key_ptr, if (vb2_read_file(filename, &key_data, &key_size)) return VB2_ERROR_READ_KEYB_DATA; - /* Guess the signature algorithm from the key size */ + /* Guess the signature algorithm from the key size + * Note: This only considers exponent F4 keys, as there is no way to + * distinguish between exp 3 and F4 based on size. Vboot API 2.1 is + * required to make proper use of exp 3 keys. */ for (sig_alg = VB2_SIG_RSA1024; sig_alg <= VB2_SIG_RSA8192; sig_alg++) { if (key_size == vb2_packed_key_size(sig_alg)) break; @@ -560,17 +564,27 @@ int vb2_public_key_hash(struct vb2_public_key *key, enum vb2_signature_algorithm vb2_rsa_sig_alg(struct rsa_st *rsa) { + int exp = BN_get_word(rsa->e); int bits = BN_num_bits(rsa->n); - switch (bits) { - case 1024: - return VB2_SIG_RSA1024; - case 2048: - return VB2_SIG_RSA2048; - case 4096: - return VB2_SIG_RSA4096; - case 8192: - return VB2_SIG_RSA8192; + switch (exp) { + case RSA_3: + switch (bits) { + case 2048: + return VB2_SIG_RSA2048_EXP3; + } + break; + case RSA_F4: + switch (bits) { + case 1024: + return VB2_SIG_RSA1024; + case 2048: + return VB2_SIG_RSA2048; + case 4096: + return VB2_SIG_RSA4096; + case 8192: + return VB2_SIG_RSA8192; + } } /* no clue */ diff --git a/tests/common.sh b/tests/common.sh index 2b017cc5..78a47fa8 100644 --- a/tests/common.sh +++ b/tests/common.sh @@ -28,7 +28,7 @@ COL_BLUE='\E[34;1m' COL_STOP='\E[0;m' hash_algos=( sha1 sha256 sha512 ) -key_lengths=( 1024 2048 4096 8192 ) +key_lengths=( 1024 2048 4096 8192 2048_exp3 ) function happy { echo -e "${COL_GREEN}$*${COL_STOP}" 1>&2 diff --git a/tests/futility/test_show_rwsig.sh b/tests/futility/test_show_rwsig.sh index 7ff25571..915842d6 100755 --- a/tests/futility/test_show_rwsig.sh +++ b/tests/futility/test_show_rwsig.sh @@ -13,7 +13,7 @@ DATADIR="${SCRIPTDIR}/data" TESTKEYS=${SRCDIR}/tests/testkeys # Do not test 8192 as the signature length is > 1024 bytes -SIGS="1024 2048 4096" +SIGS="1024 2048 4096 2048_exp3" HASHES="SHA1 SHA256 SHA512" set -o pipefail diff --git a/tests/gen_test_keys.sh b/tests/gen_test_keys.sh index dbb17419..04315ac3 100755 --- a/tests/gen_test_keys.sh +++ b/tests/gen_test_keys.sh @@ -25,7 +25,15 @@ function generate_keys { continue fi - openssl genrsa -F4 -out ${key_base}.pem $i + # Extract exponent from key_length name, if necessary + exp="F4" + bits=$i + if [ "${i##*_exp}" != "${i}" ]; then + exp="${i##*_exp}" + bits="${i%%_exp${exp}}" + fi + + openssl genrsa -${exp} -out ${key_base}.pem ${bits} # Generate self-signed certificate from key. openssl req -batch -new -x509 -key ${key_base}.pem \ -out ${key_base}.crt diff --git a/tests/testcases/test_file.rsa2048_exp3_sha1.sig b/tests/testcases/test_file.rsa2048_exp3_sha1.sig new file mode 100644 index 00000000..75cd3ba4 Binary files /dev/null and b/tests/testcases/test_file.rsa2048_exp3_sha1.sig differ diff --git a/tests/testcases/test_file.rsa2048_exp3_sha256.sig b/tests/testcases/test_file.rsa2048_exp3_sha256.sig new file mode 100644 index 00000000..1192c8e3 --- /dev/null +++ b/tests/testcases/test_file.rsa2048_exp3_sha256.sig @@ -0,0 +1,2 @@ + _#ٌ%:a ollnLNAUʩu4y ѷ_02mԩ*a.Ъa-f@9+"+|+YxH4~ƛVWe); int modulus = BN_num_bits(key->n); - if (public_exponent != 65537) { - fprintf(stderr, "WARNING: Public exponent should be 65537 (but is %d).\n", + if (public_exponent != 3 && public_exponent != 65537) { + fprintf(stderr, + "WARNING: Public exponent should be 3 or 65537 (but is %d).\n", public_exponent); } -- cgit v1.2.1