From mboxrd@z Thu Jan 1 00:00:00 1970 Return-path: Received: from metis.ext.pengutronix.de ([2001:6f8:1178:4:290:27ff:fe1d:cc33]) by bombadil.infradead.org with esmtps (Exim 4.80.1 #2 (Red Hat Linux)) id 1YW4I5-0005gl-Bl for barebox@lists.infradead.org; Thu, 12 Mar 2015 14:40:51 +0000 From: Jan Luebbe Date: Thu, 12 Mar 2015 15:39:57 +0100 Message-Id: <1426171199-2729-3-git-send-email-jlu@pengutronix.de> In-Reply-To: <1426171199-2729-1-git-send-email-jlu@pengutronix.de> References: <1426171199-2729-1-git-send-email-jlu@pengutronix.de> List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "barebox" Errors-To: barebox-bounces+u.kleine-koenig=pengutronix.de@lists.infradead.org Subject: [RFC 2/4] Add rsa support To: barebox@lists.infradead.org From: Sascha Hauer Signed-off-by: Sascha Hauer --- crypto/Kconfig | 3 + crypto/Makefile | 1 + crypto/rsa.c | 411 ++++++++++++++++++++++++++++++++++++++++++++ include/asm-generic/errno.h | 5 + include/rsa.h | 54 ++++++ 5 files changed, 474 insertions(+) create mode 100644 crypto/rsa.c create mode 100644 include/rsa.h diff --git a/crypto/Kconfig b/crypto/Kconfig index 4bd8dcf359f8..fa9ba491b79b 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -25,3 +25,6 @@ config SHA256 bool "SHA256" endif + +config RSA + bool diff --git a/crypto/Makefile b/crypto/Makefile index 7c5b035b73de..44be124aa368 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -5,3 +5,4 @@ obj-$(CONFIG_MD5) += md5.o obj-$(CONFIG_SHA1) += sha1.o obj-$(CONFIG_SHA224) += sha2.o obj-$(CONFIG_SHA256) += sha2.o +obj-$(CONFIG_RSA) += rsa.o diff --git a/crypto/rsa.c b/crypto/rsa.c new file mode 100644 index 000000000000..6a0c7b8a15cc --- /dev/null +++ b/crypto/rsa.c @@ -0,0 +1,411 @@ +/* + * Copyright (c) 2013, Google Inc. + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby))) + +#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 + +/* This is the minimum/maximum key size we support, in bits */ +#define RSA_MIN_KEY_BITS 1024 +#define RSA_MAX_KEY_BITS 4096 + +/** + * subtract_modulus() - subtract modulus from the given value + * + * @key: Key containing modulus to subtract + * @num: Number to subtract modulus from, as little endian word array + */ +static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[]) +{ + int64_t acc = 0; + uint i; + + for (i = 0; i < key->len; i++) { + acc += (uint64_t)num[i] - key->modulus[i]; + num[i] = (uint32_t)acc; + acc >>= 32; + } +} + +/** + * greater_equal_modulus() - check if a value is >= modulus + * + * @key: Key containing modulus to check + * @num: Number to check against modulus, as little endian word array + * @return 0 if num < modulus, 1 if num >= modulus + */ +static int greater_equal_modulus(const struct rsa_public_key *key, + uint32_t num[]) +{ + int i; + + for (i = (int)key->len - 1; i >= 0; i--) { + if (num[i] < key->modulus[i]) + return 0; + if (num[i] > key->modulus[i]) + return 1; + } + + return 1; /* equal */ +} + +/** + * montgomery_mul_add_step() - Perform montgomery multiply-add step + * + * Operation: montgomery result[] += a * b[] / n0inv % modulus + * + * @key: RSA key + * @result: Place to put result, as little endian word array + * @a: Multiplier + * @b: Multiplicand, as little endian word array + */ +static void montgomery_mul_add_step(const struct rsa_public_key *key, + uint32_t result[], const uint32_t a, const uint32_t b[]) +{ + uint64_t acc_a, acc_b; + uint32_t d0; + uint i; + + acc_a = (uint64_t)a * b[0] + result[0]; + d0 = (uint32_t)acc_a * key->n0inv; + acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a; + for (i = 1; i < key->len; i++) { + acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i]; + acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] + + (uint32_t)acc_a; + result[i - 1] = (uint32_t)acc_b; + } + + acc_a = (acc_a >> 32) + (acc_b >> 32); + + result[i - 1] = (uint32_t)acc_a; + + if (acc_a >> 32) + subtract_modulus(key, result); +} + +/** + * montgomery_mul() - Perform montgomery mutitply + * + * Operation: montgomery result[] = a[] * b[] / n0inv % modulus + * + * @key: RSA key + * @result: Place to put result, as little endian word array + * @a: Multiplier, as little endian word array + * @b: Multiplicand, as little endian word array + */ +static void montgomery_mul(const struct rsa_public_key *key, + uint32_t result[], uint32_t a[], const uint32_t b[]) +{ + uint i; + + for (i = 0; i < key->len; ++i) + result[i] = 0; + for (i = 0; i < key->len; ++i) + montgomery_mul_add_step(key, result, a[i], b); +} + +/** + * 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 + * @inout: Big-endian word array containing value and result + */ +static int pow_mod(const struct rsa_public_key *key, void *__inout) +{ + uint32_t *inout = __inout; + uint32_t *result, *ptr; + uint i; + int j, k; + uint32_t val[RSA_MAX_KEY_BITS / 32], acc[RSA_MAX_KEY_BITS / 32], tmp[RSA_MAX_KEY_BITS / 32]; + uint32_t a_scaled[RSA_MAX_KEY_BITS / 32]; + + /* Sanity check for stack size - key->len is in 32-bit words */ + if (key->len > RSA_MAX_KEY_BITS / 32) { + debug("RSA key words %u exceeds maximum %d\n", key->len, + RSA_MAX_KEY_BITS / 32); + return -EINVAL; + } + + 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); + + 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, 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)) + subtract_modulus(key, result); + + /* Convert to bigendian byte array */ + for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++) + put_unaligned_be32(result[i], ptr); + return 0; +} + +/* + * Hash algorithm OIDs plus ASN.1 DER wrappings [RFC4880 sec 5.2.2]. + */ +static const u8 RSA_digest_info_MD5[] = { + 0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, + 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, /* OID */ + 0x05, 0x00, 0x04, 0x10 +}; + +static const u8 RSA_digest_info_SHA1[] = { + 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, + 0x2B, 0x0E, 0x03, 0x02, 0x1A, + 0x05, 0x00, 0x04, 0x14 +}; + +static const u8 RSA_digest_info_RIPE_MD_160[] = { + 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, + 0x2B, 0x24, 0x03, 0x02, 0x01, + 0x05, 0x00, 0x04, 0x14 +}; + +static const u8 RSA_digest_info_SHA224[] = { + 0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, + 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, + 0x05, 0x00, 0x04, 0x1C +}; + +static const u8 RSA_digest_info_SHA256[] = { + 0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, + 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, + 0x05, 0x00, 0x04, 0x20 +}; + +static const u8 RSA_digest_info_SHA384[] = { + 0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, + 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, + 0x05, 0x00, 0x04, 0x30 +}; + +static const u8 RSA_digest_info_SHA512[] = { + 0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, + 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, + 0x05, 0x00, 0x04, 0x40 +}; + +static const struct { + const u8 *data; + size_t size; +} RSA_ASN1_templates[] = { +#define _(X) { RSA_digest_info_##X, sizeof(RSA_digest_info_##X) } + [HASH_ALGO_MD5] = _(MD5), + [HASH_ALGO_SHA1] = _(SHA1), + [HASH_ALGO_RIPE_MD_160] = _(RIPE_MD_160), + [HASH_ALGO_SHA256] = _(SHA256), + [HASH_ALGO_SHA384] = _(SHA384), + [HASH_ALGO_SHA512] = _(SHA512), + [HASH_ALGO_SHA224] = _(SHA224), +#undef _ +}; + +int rsa_verify(const struct rsa_public_key *key, const uint8_t *sig, + const uint32_t sig_len, const uint8_t *hash, + enum hash_algo algo) +{ + int ret; + uint8_t buf[RSA_MAX_SIG_BITS / 8]; + int i; + unsigned PS_end, T_offset; + const u8 *asn1_template = RSA_ASN1_templates[algo].data; + size_t asn1_size = RSA_ASN1_templates[algo].size; + struct digest *d = digest_get(algo); + + if (!d) + return -EOPNOTSUPP; + + if (sig_len != (key->len * sizeof(uint32_t))) { + debug("Signature is of incorrect length %d, should be %d\n", sig_len, + key->len * sizeof(uint32_t)); + return -EINVAL; + } + + /* Sanity check for stack size */ + if (sig_len > RSA_MAX_SIG_BITS / 8) { + debug("Signature length %u exceeds maximum %d\n", sig_len, + RSA_MAX_SIG_BITS / 8); + return -EINVAL; + } + + memcpy(buf, sig, sig_len); + + ret = pow_mod(key, buf); + if (ret) + return ret; + + T_offset = sig_len - (asn1_size + d->length); + + PS_end = T_offset - 1; + if (buf[PS_end] != 0x00) { + pr_err(" = -EBADMSG [EM[T-1] == %02u]", buf[PS_end]); + return -EBADMSG; + } + + for (i = 2; i < PS_end; i++) { + if (buf[i] != 0xff) { + pr_err(" = -EBADMSG [EM[PS%x] == %02u]", i - 2, buf[i]); + return -EBADMSG; + } + } + + if (memcmp(asn1_template, buf + T_offset, asn1_size) != 0) { + pr_err(" = -EBADMSG [EM[T] ASN.1 mismatch]"); + return -EBADMSG; + } + + if (memcmp(hash, buf + T_offset + asn1_size, d->length) != 0) { + pr_err(" = -EKEYREJECTED [EM[T] hash mismatch]"); + return -EKEYREJECTED; + } + + return 0; +} + +static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len) +{ + int i; + + for (i = 0; i < len; i++) + dst[i] = fdt32_to_cpu(src[len - 1 - i]); +} + +int rsa_of_read_key(struct device_node *node, struct rsa_public_key *key) +{ + const void *modulus, *rr; + const uint64_t *public_exponent; + int length; + + of_property_read_u32(node, "rsa,num-bits", &key->len); + of_property_read_u32(node, "rsa,n0-inverse", &key->n0inv); + + public_exponent = of_get_property(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 = of_get_property(node, "rsa,modulus", NULL); + rr = of_get_property(node, "rsa,r-squared", NULL); + + if (!key->len || !modulus || !rr) { + debug("%s: Missing RSA key info", __func__); + return -EFAULT; + } + + /* Sanity check for stack size */ + if (key->len > RSA_MAX_KEY_BITS || key->len < RSA_MIN_KEY_BITS) { + debug("RSA key bits %u outside allowed range %d..%d\n", + key->len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS); + return -EFAULT; + } + + key->len /= sizeof(uint32_t) * 8; + + key->modulus = xzalloc(RSA_MAX_KEY_BITS / 8); + key->rr = xzalloc(RSA_MAX_KEY_BITS / 8); + + rsa_convert_big_endian(key->modulus, modulus, key->len); + rsa_convert_big_endian(key->rr, rr, key->len); + + return 0; +} diff --git a/include/asm-generic/errno.h b/include/asm-generic/errno.h index bbf493c373ae..b239831bc703 100644 --- a/include/asm-generic/errno.h +++ b/include/asm-generic/errno.h @@ -126,6 +126,11 @@ #define ENOMEDIUM 123 /* No medium found */ #define EMEDIUMTYPE 124 /* Wrong medium type */ +#define ECANCELED 125 /* Operation Canceled */ +#define ENOKEY 126 /* Required key not available */ +#define EKEYEXPIRED 127 /* Key has expired */ +#define EKEYREVOKED 128 /* Key has been revoked */ +#define EKEYREJECTED 129 /* Key was rejected by service */ /* Should never be seen by user programs */ #define ERESTARTSYS 512 diff --git a/include/rsa.h b/include/rsa.h new file mode 100644 index 000000000000..feb8c3120023 --- /dev/null +++ b/include/rsa.h @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2013, Google Inc. + * + * (C) Copyright 2008 Semihalf + * + * (C) Copyright 2000-2006 + * Wolfgang Denk, DENX Software Engineering, wd@denx.de. + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef _RSA_H +#define _RSA_H + +#include +#include + +/** + * struct rsa_public_key - holder for a public key + * + * An RSA public key consists of a modulus (typically called N), the inverse + * and R^2, where R is 2^(# key bits). + */ + +struct rsa_public_key { + uint len; /* len of modulus[] in number of uint32_t */ + 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 */ +}; + +/** + * rsa_verify() - Verify a signature against some data + * + * Verify a RSA PKCS1.5 signature against an expected hash. + * + * @info: Specifies key and FIT information + * @data: Pointer to the input data + * @data_len: Data length + * @sig: Signature + * @sig_len: Number of bytes in signature + * @return 0 if verified, -ve on error + */ +int rsa_verify(const struct rsa_public_key *key, const uint8_t *sig, + const uint32_t sig_len, const uint8_t *hash, + enum hash_algo algo); + +/* This is the maximum signature length that we support, in bits */ +#define RSA_MAX_SIG_BITS 4096 + +int rsa_of_read_key(struct device_node *node, struct rsa_public_key *key); + +#endif -- 2.1.4 _______________________________________________ barebox mailing list barebox@lists.infradead.org http://lists.infradead.org/mailman/listinfo/barebox