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 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>

1 files changed, 88 insertions, 5 deletions

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) {