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

michael at smart-africa.com michael at smart-africa.com
Mon May 26 16:56:53 CEST 2014


From: Michael van der Westhuizen <michael at 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 at ipaccess.com>
Signed-off-by: Andrew Wishart <Andrew.Wishart at ipaccess.com>
Signed-off-by: Neil Piercy <Neil.Piercy at ipaccess.com>
Signed-off-by: Michael van der Westhuizen <michael at 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
-- 
2.0.0.rc0



More information about the U-Boot mailing list