[U-Boot] [PATCH] Implement generalised RSA public exponents for verified boot
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 --- 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
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
Hi Michael,
On 26 May 2014 08:56, michael@smart-africa.com wrote:
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.
This looks good. I mostly have some nits below.
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)
rsa_get_exponent() might be better. Also s/e/exponent/ or perhaps exp (although I see I made the same mistake in the following function).
+{
int ret;BIGNUM *bn_te;uint64_t te;ret = -1;
-EINVAL
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)
If you don't mind, you could change 'e' to 'exp' or 'exponent' in the same patch.
{ 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;
And here.
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
Then why use hex? Can we decide on either decimal or hex?
/**
- 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)
s/k/keyp/ or something like that.
Also is this function able to just use ffs() or similar?
+{
uint64_t e;
s/e/exponent/ or exp
const uint nbits = (sizeof(e) * 8);*k = 0;
How about a local variable for this instead of using *k everywhere?
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);
If this is 64-but, then perhaps 1ULL << 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);
What is invalid about it? Perhaps expand the message?
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 */
Join these two comments, also the style should be:
/* * The bit at ... * ... */
memcpy(a_scaled, acc, key->len * 4);
What is 4? is it sizeof(uint32_t?). I wonder if we could replace the line immediately above and remove this memcpy()?
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */
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);
Do you need this special case, or if bit 0 of e is always 1, perhaps you can just extend the loop by one more step?
/* 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;
s/pe/public_exponent/ or similar?
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;elsekey.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
Do we need this, or can we just do:
if [ -n "${PUBLIC_EXPONENT}" ]; then
# 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 -- 2.0.0.rc0
Regards, Simon
Hi Simon,
Thanks for the feedback.
I'll take care of the nits and look into removing some special casing.
On 30 May 2014, at 9:04 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
<snip>
/**
- 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)
s/k/keyp/ or something like that.
Also is this function able to just use ffs() or similar?
flsll() yes, but that's not portable to Linux.
<snip>
+}
+/**
- 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);What is invalid about it? Perhaps expand the message?
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 */Join these two comments, also the style should be:
/*
- The bit at ...
- ...
*/
memcpy(a_scaled, acc, key->len * 4);What is 4? is it sizeof(uint32_t?). I wonder if we could replace the line immediately above and remove this memcpy()?
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */
Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.
result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?
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);
<snip>
Michael
Hi Michael,
On 30 May 2014 14:47, Michael van der Westhuizen michael@smart-africa.com wrote:
Hi Simon,
Thanks for the feedback.
I'll take care of the nits and look into removing some special casing.
On 30 May 2014, at 9:04 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
<snip> >> >> /** >> + * 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) > > s/k/keyp/ or something like that. > > Also is this function able to just use ffs() or similar?
flsll() yes, but that's not portable to Linux.
Does that matter?
<snip>
+}
+/**
- 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);What is invalid about it? Perhaps expand the message?
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 */Join these two comments, also the style should be:
/*
- The bit at ...
- ...
*/
memcpy(a_scaled, acc, key->len * 4);What is 4? is it sizeof(uint32_t?). I wonder if we could replace the line immediately above and remove this memcpy()?
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.
result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?
OK I see thanks. Perhaps add a new temporary instead of using memcpy()?
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);<snip>
Regards, Simon
Hi Simon,
On 30 May 2014, at 10:50 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
On 30 May 2014 14:47, Michael van der Westhuizen michael@smart-africa.com wrote:
Hi Simon,
Thanks for the feedback.
I'll take care of the nits and look into removing some special casing.
On 30 May 2014, at 9:04 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
<snip> >> >> /** >> + * 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) > > s/k/keyp/ or something like that. > > Also is this function able to just use ffs() or similar?
flsll() yes, but that's not portable to Linux.
Does that matter?
This code compiles on the host, so unfortunately yes. That's the same reason I had to work around the lack of handy *_u64 fdt helpers when reading the public exponent.
<snip>
+}
+/**
- 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);What is invalid about it? Perhaps expand the message?
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 */Join these two comments, also the style should be:
/*
- The bit at ...
- ...
*/
memcpy(a_scaled, acc, key->len * 4);What is 4? is it sizeof(uint32_t?). I wonder if we could replace the line immediately above and remove this memcpy()?
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.
result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?
OK I see thanks. Perhaps add a new temporary instead of using memcpy()?
And set it up using montgomery_mul? Would that not be more expensive than a memcpy?
Thanks, Michael
Hi Michael,
On 30 May 2014 15:03, Michael van der Westhuizen michael@smart-africa.com wrote:
Hi Simon,
On 30 May 2014, at 10:50 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
On 30 May 2014 14:47, Michael van der Westhuizen michael@smart-africa.com wrote:
Hi Simon,
Thanks for the feedback.
I'll take care of the nits and look into removing some special casing.
On 30 May 2014, at 9:04 PM, Simon Glass sjg@chromium.org wrote:
Hi Michael,
<snip>
/**
- 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)
s/k/keyp/ or something like that.
Also is this function able to just use ffs() or similar?
flsll() yes, but that's not portable to Linux.
Does that matter?
This code compiles on the host, so unfortunately yes. That's the same reason I had to work around the lack of handy *_u64 fdt helpers when reading the public exponent.
OK, although Linux might have replacements. But if not, perhaps add a comment as to why you need the helper function.
[snip]
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.
result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?
OK I see thanks. Perhaps add a new temporary instead of using memcpy()?
And set it up using montgomery_mul? Would that not be more expensive than a memcpy?
On the host? Not sure we care about that. I was really just wondering if an assignment is better than a memcpy() which makes assumptions about the format.
Regards, Simon
Hi Simon,
On 30 May 2014, at 11:11 PM, Simon Glass sjg@chromium.org wrote:
<snip>
This code compiles on the host, so unfortunately yes. That's the same reason I had to work around the lack of handy *_u64 fdt helpers when reading the public exponent.
OK, although Linux might have replacements. But if not, perhaps add a comment as to why you need the helper function.
Will do.
[snip]
For example, if you did:
montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.
result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?
OK I see thanks. Perhaps add a new temporary instead of using memcpy()?
And set it up using montgomery_mul? Would that not be more expensive than a memcpy?
On the host? Not sure we care about that. I was really just wondering if an assignment is better than a memcpy() which makes assumptions about the format.
In theory it should optimise to the same code, but I'll run tests with assignment to make sure it works as expected.
Michael
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 change 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.
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 Cc: Simon Glass sjg@chromium.org --- Changes for v2: - None. Resend to address line wrapping issues. Changes for v3: - Address review comments, cleaning up variable names and rewording error messages. - Rebase against current master. - Apply as many suggested simplifications as feasible.
doc/uImage.FIT/signature.txt | 4 +- include/u-boot/rsa.h | 1 + lib/rsa/rsa-sign.c | 60 ++++++++++++++++++++++++++-- lib/rsa/rsa-verify.c | 93 +++++++++++++++++++++++++++++++++++++++++--- test/vboot/vboot_test.sh | 10 ++++- 5 files changed, 158 insertions(+), 10 deletions(-)
diff --git a/doc/uImage.FIT/signature.txt b/doc/uImage.FIT/signature.txt index a6ab543..b2f89fc 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/u-boot/rsa.h b/include/u-boot/rsa.h index 325751a..fd08a61 100644 --- a/include/u-boot/rsa.h +++ b/include/u-boot/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 83f5e87..f4d4338 100644 --- a/lib/rsa/rsa-sign.c +++ b/lib/rsa/rsa-sign.c @@ -261,10 +261,57 @@ err_priv: }
/* + * rsa_get_exponent(): - Get the public exponent from an RSA key + */ +static int rsa_get_exponent(RSA *key, uint64_t *e) +{ + int ret; + BIGNUM *bn_te; + uint64_t te; + + ret = -EINVAL; + 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, - BIGNUM **r_squaredp) +int rsa_get_params(RSA *key, uint64_t *exponent, uint32_t *n0_invp, + BIGNUM **modulusp, BIGNUM **r_squaredp) { BIGNUM *big1, *big2, *big32, *big2_32; BIGNUM *n, *r, *r_squared, *tmp; @@ -286,6 +333,9 @@ int rsa_get_params(RSA *key, uint32_t *n0_invp, BIGNUM **modulusp, return -ENOMEM; }
+ if (0 != rsa_get_exponent(key, exponent)) + 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 exponent; 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, &exponent, &n0_inv, &modulus, &r_squared); if (ret) return ret; bits = BN_num_bits(modulus); @@ -442,6 +493,9 @@ int rsa_add_verify_data(struct image_sign_info *info, void *keydest) if (!ret) ret = fdt_setprop_u32(keydest, node, "rsa,n0-inverse", n0_inv); if (!ret) { + ret = fdt_setprop_u64(keydest, node, "rsa,exponent", exponent); + } + if (!ret) { ret = fdt_add_bignum(keydest, node, "rsa,modulus", modulus, bits); } diff --git a/lib/rsa/rsa-verify.c b/lib/rsa/rsa-verify.c index bcb9063..c5bcdb6 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))
+/* Default public exponent for backward compatibility */ +#define RSA_DEFAULT_PUBEXP 65537 + /** * subtract_modulus() - subtract modulus from the given value * @@ -123,6 +126,48 @@ static void montgomery_mul(const struct rsa_public_key *key, }
/** + * num_pub_exponent_bits() - Number of bits in the public exponent + * + * @key: RSA key + * @num_bits: Storage for the number of public exponent bits + */ +static int num_public_exponent_bits(const struct rsa_public_key *key, + int *num_bits) +{ + uint64_t exponent; + int exponent_bits; + const uint max_bits = (sizeof(exponent) * 8); + + exponent = key->exponent; + exponent_bits = 0; + + if (!exponent) { + *num_bits = exponent_bits; + return 0; + } + + for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits) + if (!(exponent >>= 1)) { + *num_bits = exponent_bits; + 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 & (1ULL << pos); +} + +/** * pow_mod() - in-place public exponentiation * * @key: RSA key @@ -132,6 +177,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 +187,48 @@ 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; } - montgomery_mul(key, result, acc, val); /* result = XX * a / R mod M */ + + if (!is_public_exponent_bit_set(key, 0)) { + debug("LSB of RSA public exponent must be set.\n"); + 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 * sizeof(a_scaled[0])); + + 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 * sizeof(acc[0])); + } + } + + /* 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 * sizeof(result[0]));
/* Make sure result < mod; result is at most 1x mod too large. */ if (greater_equal_modulus(key, result)) @@ -229,6 +305,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 *public_exponent; + int length; int ret;
if (node < 0) { @@ -241,6 +319,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); + public_exponent = fdt_getprop(blob, node, "rsa,exponent", &length); + if (!public_exponent || length < sizeof(*public_exponent)) + key.exponent = RSA_DEFAULT_PUBEXP; + else + key.exponent = fdt64_to_cpu(*public_exponent); 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 8074fc6..6d7abb8 100755 --- a/test/vboot/vboot_test.sh +++ b/test/vboot/vboot_test.sh @@ -54,8 +54,16 @@ echo ${mkimage} -D "${dtc}" echo "Build keys" mkdir -p ${keys}
+PUBLIC_EXPONENT=${1} + +if [ -z "${PUBLIC_EXPONENT}" ]; 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
Hi Michael,
On 2 July 2014 02:17, michael@smart-africa.com wrote:
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 change 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.
Mathematics and other hard work by Andrew Bott.
Sorry, I still have a few nits on this, but it looks good.
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 Cc: Simon Glass sjg@chromium.org
Changes for v2:
- None. Resend to address line wrapping issues.
Changes for v3:
- Address review comments, cleaning up variable names and rewording error messages.
- Rebase against current master.
- Apply as many suggested simplifications as feasible.
doc/uImage.FIT/signature.txt | 4 +- include/u-boot/rsa.h | 1 + lib/rsa/rsa-sign.c | 60 ++++++++++++++++++++++++++-- lib/rsa/rsa-verify.c | 93 +++++++++++++++++++++++++++++++++++++++++--- test/vboot/vboot_test.sh | 10 ++++- 5 files changed, 158 insertions(+), 10 deletions(-)
diff --git a/doc/uImage.FIT/signature.txt b/doc/uImage.FIT/signature.txt index a6ab543..b2f89fc 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
This is listed as mandatory, but the code makes it options. I think it should probably be optional, and documented that way here.
- 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/u-boot/rsa.h b/include/u-boot/rsa.h index 325751a..fd08a61 100644 --- a/include/u-boot/rsa.h +++ b/include/u-boot/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 83f5e87..f4d4338 100644 --- a/lib/rsa/rsa-sign.c +++ b/lib/rsa/rsa-sign.c @@ -261,10 +261,57 @@ err_priv: }
/*
- rsa_get_exponent(): - Get the public exponent from an RSA key
- */
+static int rsa_get_exponent(RSA *key, uint64_t *e)
+{
int ret;BIGNUM *bn_te;uint64_t te;ret = -EINVAL;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,
BIGNUM **r_squaredp)+int rsa_get_params(RSA *key, uint64_t *exponent, uint32_t *n0_invp,
BIGNUM **modulusp, BIGNUM **r_squaredp)
To be consistent, can we use exponentp as the parameter name? It makes it clear it is a pointer.
{ BIGNUM *big1, *big2, *big32, *big2_32; BIGNUM *n, *r, *r_squared, *tmp; @@ -286,6 +333,9 @@ int rsa_get_params(RSA *key, uint32_t *n0_invp, BIGNUM **modulusp, return -ENOMEM; }
if (0 != rsa_get_exponent(key, exponent))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 exponent; 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, &exponent, &n0_inv, &modulus, &r_squared); if (ret) return ret; bits = BN_num_bits(modulus);@@ -442,6 +493,9 @@ int rsa_add_verify_data(struct image_sign_info *info, void *keydest) if (!ret) ret = fdt_setprop_u32(keydest, node, "rsa,n0-inverse", n0_inv); if (!ret) {
ret = fdt_setprop_u64(keydest, node, "rsa,exponent", exponent);}
You don't need the {} around this.
if (!ret) { ret = fdt_add_bignum(keydest, node, "rsa,modulus", modulus, bits); }diff --git a/lib/rsa/rsa-verify.c b/lib/rsa/rsa-verify.c index bcb9063..c5bcdb6 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))
+/* Default public exponent for backward compatibility */ +#define RSA_DEFAULT_PUBEXP 65537
/**
- subtract_modulus() - subtract modulus from the given value
@@ -123,6 +126,48 @@ static void montgomery_mul(const struct rsa_public_key *key, }
/**
- num_pub_exponent_bits() - Number of bits in the public exponent
- @key: RSA key
- @num_bits: Storage for the number of public exponent bits
- */
+static int num_public_exponent_bits(const struct rsa_public_key *key,
int *num_bits)+{
uint64_t exponent;int exponent_bits;const uint max_bits = (sizeof(exponent) * 8);exponent = key->exponent;exponent_bits = 0;if (!exponent) {*num_bits = exponent_bits;return 0;}for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits)if (!(exponent >>= 1)) {*num_bits = exponent_bits;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 & (1ULL << pos);+}
+/**
- pow_mod() - in-place public exponentiation
- @key: RSA key
@@ -132,6 +177,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 +187,48 @@ 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; }
montgomery_mul(key, result, acc, val); /* result = XX * a / R mod M */
if (!is_public_exponent_bit_set(key, 0)) {debug("LSB of RSA public exponent must be set.\n");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 * sizeof(a_scaled[0]));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 * sizeof(acc[0]));}}/* 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 * sizeof(result[0])); /* Make sure result < mod; result is at most 1x mod too large. */ if (greater_equal_modulus(key, result))@@ -229,6 +305,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 *public_exponent;int length; int ret; if (node < 0) {@@ -241,6 +319,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);
public_exponent = fdt_getprop(blob, node, "rsa,exponent", &length);if (!public_exponent || length < sizeof(*public_exponent))key.exponent = RSA_DEFAULT_PUBEXP;elsekey.exponent = fdt64_to_cpu(*public_exponent); 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 8074fc6..6d7abb8 100755 --- a/test/vboot/vboot_test.sh +++ b/test/vboot/vboot_test.sh @@ -54,8 +54,16 @@ echo ${mkimage} -D "${dtc}" echo "Build keys" mkdir -p ${keys}
+PUBLIC_EXPONENT=${1}
+if [ -z "${PUBLIC_EXPONENT}" ]; then
PUBLIC_EXPONENT=65537+fi
Tests should not take parameters - you should adjust the script to run the tests twice - once with the default exponent and once with another chosen exponent. Then running the test tests all the code. See what was done for sha256 and sha1 as an example. Note you don't need to test all combinations of sha1/sha256/default exp,/special exp. unless that is easier.
# 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 -- 1.9.1
Regards, Simon
On Wed, Jul 02, 2014 at 10:17:26AM +0200, Michael van der Westhuizen wrote:
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 change 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.
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 Cc: Simon Glass sjg@chromium.org
Applied to u-boot/master, thanks!
participants (4)
-
Michael van der Westhuizen -
michael＠smart-africa.com
-
Simon Glass -
Tom Rini