Re: [U-Boot] [PATCH v2] Implement generalised RSA public exponents for verified boot

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;
  

•   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

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