From: Michael van der Westhuizen michael@smart-africa.com
Remove the verified boot limitation that only allows a single RSA public exponent of 65537 (F4). This allows use with existing PKI infrastructure, and has been tested with HSM-based PKI.
Change the configuration OF tree format to store the RSA public exponent as a 64 bit integer and implement backward compatibility for verified boot configuration trees without this extra field.
Parameterise vboot_test.sh to test different public exponents and do a drive-by fix to get vboot_test.sh working again.
Mathematics and other hard work by Andrew Bott.
Tested with the following public exponents: 3, 5, 17, 257, 39981, 50457, 65537 and 4294967297.
Signed-off-by: Andrew Bott Andrew.Bott@ipaccess.com Signed-off-by: Andrew Wishart Andrew.Wishart@ipaccess.com Signed-off-by: Neil Piercy Neil.Piercy@ipaccess.com Signed-off-by: Michael van der Westhuizen michael@smart-africa.com --- Changes for v2: - None. Resend to address line wrapping issues.
doc/uImage.FIT/signature.txt | 4 +- include/rsa.h | 1 + lib/rsa/rsa-sign.c | 56 +++++++++++++++++++++++++++- lib/rsa/rsa-verify.c | 88 +++++++++++++++++++++++++++++++++++++++++--- test/vboot/vboot_test.sh | 11 +++++- 5 files changed, 151 insertions(+), 9 deletions(-)
diff --git a/doc/uImage.FIT/signature.txt b/doc/uImage.FIT/signature.txt index 9502037..cc314a3 100644 --- a/doc/uImage.FIT/signature.txt +++ b/doc/uImage.FIT/signature.txt @@ -66,7 +66,8 @@ Creating an RSA key and certificate ----------------------------------- To create a new public key, size 2048 bits:
-$ openssl genrsa -F4 -out keys/dev.key 2048 +$ openssl genpkey -algorithm RSA -out keys/dev.key \ + -pkeyopt rsa_keygen_bits:2048 -pkeyopt rsa_keygen_pubexp:65537
To create a certificate for this:
@@ -159,6 +160,7 @@ For RSA the following are mandatory:
- rsa,num-bits: Number of key bits (e.g. 2048) - rsa,modulus: Modulus (N) as a big-endian multi-word integer +- rsa,exponent: Public exponent (E) as a 64 bit unsigned integer - rsa,r-squared: (2^num-bits)^2 as a big-endian multi-word integer - rsa,n0-inverse: -1 / modulus[0] mod 2^32
diff --git a/include/rsa.h b/include/rsa.h index a5680ab..b84d82a 100644 --- a/include/rsa.h +++ b/include/rsa.h @@ -27,6 +27,7 @@ struct rsa_public_key { uint32_t n0inv; /* -1 / modulus[0] mod 2^32 */ uint32_t *modulus; /* modulus as little endian array */ uint32_t *rr; /* R^2 as little endian array */ + uint64_t exponent; /* public exponent */ };
#if IMAGE_ENABLE_SIGN diff --git a/lib/rsa/rsa-sign.c b/lib/rsa/rsa-sign.c index ca8c120..f20ae28 100644 --- a/lib/rsa/rsa-sign.c +++ b/lib/rsa/rsa-sign.c @@ -261,9 +261,56 @@ err_priv: }
/* + * rsa_get_e(): - Get the public exponent from an RSA public key + */ +static int rsa_get_e(RSA *key, uint64_t *e) +{ + int ret; + BIGNUM *bn_te; + uint64_t te; + + ret = -1; + bn_te = NULL; + + if (!e) + goto cleanup; + + if (BN_num_bits(key->e) > 64) + goto cleanup; + + *e = BN_get_word(key->e); + + if (BN_num_bits(key->e) < 33) { + ret = 0; + goto cleanup; + } + + bn_te = BN_dup(key->e); + if (!bn_te) + goto cleanup; + + if (!BN_rshift(bn_te, bn_te, 32)) + goto cleanup; + + if (!BN_mask_bits(bn_te, 32)) + goto cleanup; + + te = BN_get_word(bn_te); + te <<= 32; + *e |= te; + ret = 0; + +cleanup: + if (bn_te) + BN_free(bn_te); + + return ret; +} + +/* * rsa_get_params(): - Get the important parameters of an RSA public key */ -int rsa_get_params(RSA *key, uint32_t *n0_invp, BIGNUM **modulusp, +int rsa_get_params(RSA *key, uint64_t *e, uint32_t *n0_invp, BIGNUM **modulusp, BIGNUM **r_squaredp) { BIGNUM *big1, *big2, *big32, *big2_32; @@ -286,6 +333,9 @@ int rsa_get_params(RSA *key, uint32_t *n0_invp, BIGNUM **modulusp, return -ENOMEM; }
+ if (0 != rsa_get_e(key, e)) + ret = -1; + if (!BN_copy(n, key->n) || !BN_set_word(big1, 1L) || !BN_set_word(big2, 2L) || !BN_set_word(big32, 32L)) ret = -1; @@ -386,6 +436,7 @@ static int fdt_add_bignum(void *blob, int noffset, const char *prop_name, int rsa_add_verify_data(struct image_sign_info *info, void *keydest) { BIGNUM *modulus, *r_squared; + uint64_t e; uint32_t n0_inv; int parent, node; char name[100]; @@ -397,7 +448,7 @@ int rsa_add_verify_data(struct image_sign_info *info, void *keydest) ret = rsa_get_pub_key(info->keydir, info->keyname, &rsa); if (ret) return ret; - ret = rsa_get_params(rsa, &n0_inv, &modulus, &r_squared); + ret = rsa_get_params(rsa, &e, &n0_inv, &modulus, &r_squared); if (ret) return ret; bits = BN_num_bits(modulus); @@ -431,6 +482,7 @@ int rsa_add_verify_data(struct image_sign_info *info, void *keydest) info->keyname); ret |= fdt_setprop_u32(keydest, node, "rsa,num-bits", bits); ret |= fdt_setprop_u32(keydest, node, "rsa,n0-inverse", n0_inv); + ret |= fdt_setprop_u64(keydest, node, "rsa,exponent", e); ret |= fdt_add_bignum(keydest, node, "rsa,modulus", modulus, bits); ret |= fdt_add_bignum(keydest, node, "rsa,r-squared", r_squared, bits); ret |= fdt_setprop_string(keydest, node, FIT_ALGO_PROP, diff --git a/lib/rsa/rsa-verify.c b/lib/rsa/rsa-verify.c index 587da5b..878f92a 100644 --- a/lib/rsa/rsa-verify.c +++ b/lib/rsa/rsa-verify.c @@ -26,6 +26,9 @@ #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a) #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a))
+/* The default public exponent is 65537 */ +#define RSA_DEFAULT_PUBEXP 0x10001 + /** * subtract_modulus() - subtract modulus from the given value * @@ -123,6 +126,42 @@ static void montgomery_mul(const struct rsa_public_key *key, }
/** + * num_pub_exponent_bits() - Number of bits in the public exponent + * + * @key: RSA key + * @k: Storage for the number of public exponent bits + */ +static int num_public_exponent_bits(const struct rsa_public_key *key, int *k) +{ + uint64_t e; + const uint nbits = (sizeof(e) * 8); + + *k = 0; + e = key->exponent; + + if (!e) + return 0; + + for (*k = 1; *k < nbits + 1; ++*k) + if (!(e >>= 1)) + return 0; + + return -EINVAL; +} + +/** + * is_public_exponent_bit_set() - Check if a bit in the public exponent is set + * + * @key: RSA key + * @pos: The bit position to check + */ +static int is_public_exponent_bit_set(const struct rsa_public_key *key, + int pos) +{ + return key->exponent & (1 << pos); +} + +/** * pow_mod() - in-place public exponentiation * * @key: RSA key @@ -132,6 +171,7 @@ static int pow_mod(const struct rsa_public_key *key, uint32_t *inout) { uint32_t *result, *ptr; uint i; + int j, k;
/* Sanity check for stack size - key->len is in 32-bit words */ if (key->len > RSA_MAX_KEY_BITS / 32) { @@ -141,18 +181,49 @@ static int pow_mod(const struct rsa_public_key *key, uint32_t *inout) }
uint32_t val[key->len], acc[key->len], tmp[key->len]; + uint32_t a_scaled[key->len]; result = tmp; /* Re-use location. */
/* Convert from big endian byte array to little endian word array. */ for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--) val[i] = get_unaligned_be32(ptr);
- montgomery_mul(key, acc, val, key->rr); /* axx = a * RR / R mod M */ - for (i = 0; i < 16; i += 2) { - montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */ - montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */ + if (0 != num_public_exponent_bits(key, &k)) + return -EINVAL; + + if (k < 2) { + debug("Public exponent is too short (%d bits, minimum 2)\n", + k); + return -EINVAL; + } + + if (!is_public_exponent_bit_set(key, k - 1) || + !is_public_exponent_bit_set(key, 0)) { + debug("Invalid RSA public exponent 0x%llx.\n", key->exponent); + return -EINVAL; + } + + /* the bit at e[k-1] is 1 by definition, so start with: C := M */ + montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */ + /* retain scaled version for intermediate use */ + memcpy(a_scaled, acc, key->len * 4); + + for (j = k - 2; j > 0; --j) { + montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ + + if (is_public_exponent_bit_set(key, j)) { + /* acc = tmp * val / R mod n */ + montgomery_mul(key, acc, tmp, a_scaled); + } else { + /* e[j] == 0, copy tmp back to acc for next operation */ + memcpy(acc, tmp, key->len * 4); + } } - montgomery_mul(key, result, acc, val); /* result = XX * a / R mod M */ + + /* the bit at e[0] is always 1 */ + montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ + montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */ + memcpy(result, acc, key->len * 4);
/* Make sure result < mod; result is at most 1x mod too large. */ if (greater_equal_modulus(key, result)) @@ -229,6 +300,8 @@ static int rsa_verify_with_keynode(struct image_sign_info *info, const void *blob = info->fdt_blob; struct rsa_public_key key; const void *modulus, *rr; + const uint64_t *pe; + int length; int ret;
if (node < 0) { @@ -241,6 +314,11 @@ static int rsa_verify_with_keynode(struct image_sign_info *info, } key.len = fdtdec_get_int(blob, node, "rsa,num-bits", 0); key.n0inv = fdtdec_get_int(blob, node, "rsa,n0-inverse", 0); + pe = fdt_getprop(blob, node, "rsa,exponent", &length); + if (!pe || length < sizeof(*pe)) + key.exponent = RSA_DEFAULT_PUBEXP; + else + key.exponent = fdt64_to_cpu(*pe); modulus = fdt_getprop(blob, node, "rsa,modulus", NULL); rr = fdt_getprop(blob, node, "rsa,r-squared", NULL); if (!key.len || !modulus || !rr) { diff --git a/test/vboot/vboot_test.sh b/test/vboot/vboot_test.sh index 3c6efa7..885e869 100755 --- a/test/vboot/vboot_test.sh +++ b/test/vboot/vboot_test.sh @@ -14,6 +14,7 @@ set -e run_uboot() { echo -n "Test Verified Boot Run: $1: " ${uboot} -d sandbox-u-boot.dtb >${tmp} -c ' +sb bind 0 test.fit; sb load host 0 100 test.fit; fdt addr 100; bootm 100; @@ -54,8 +55,16 @@ echo ${mkimage} -D "${dtc}" echo "Build keys" mkdir -p ${keys}
+PUBLIC_EXPONENT=${1} + +if [ x"${PUBLIC_EXPONENT}" = x"" ]; then + PUBLIC_EXPONENT=65537 +fi + # Create an RSA key pair -openssl genrsa -F4 -out ${keys}/dev.key 2048 2>/dev/null +openssl genpkey -algorithm RSA -out ${keys}/dev.key \ + -pkeyopt rsa_keygen_bits:2048 \ + -pkeyopt rsa_keygen_pubexp:${PUBLIC_EXPONENT} 2>/dev/null
# Create a certificate containing the public key openssl req -batch -new -x509 -key ${keys}/dev.key -out ${keys}/dev.crt