[coreboot-gerrit] Change in coreboot[master]: security/crypto: Add RSA signature verification support
Philipp Deppenwiese (Code Review)
gerrit at coreboot.org
Thu Jan 11 15:13:35 CET 2018
Philipp Deppenwiese has uploaded this change for review. ( https://review.coreboot.org/23218
Change subject: security/crypto: Add RSA signature verification support
......................................................................
security/crypto: Add RSA signature verification support
* Add core RSA primitives.
* Add signature verification based on RSA.
* RSA 1024-8192 with PKCS#1.5 padding scheme.
* Integrated code from 3rdparty/boot.
Change-Id: Ic58be92ad184cccaa8d6fc87d2c60bad63f3ec3b
Signed-off-by: Philipp Deppenwiese <zaolin at das-labor.org>
---
M src/security/crypto/Kconfig
M src/security/crypto/Makefile.inc
A src/security/crypto/rsa.h
A src/security/crypto/rsa/rsa.c
4 files changed, 543 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/18/23218/1
diff --git a/src/security/crypto/Kconfig b/src/security/crypto/Kconfig
index b33ff13..4fbb808 100644
--- a/src/security/crypto/Kconfig
+++ b/src/security/crypto/Kconfig
@@ -58,4 +58,14 @@
If unsure, say N.
+config CRYPTO_RSA
+ bool "RSA support"
+ default n
+ select CRYPTO_HASH
+ help
+ Enable this option to to ensure RSA support.
+ Currently only signature verification with PKCS#1.5 is supported.
+
+ If unsure, say N.
+
endmenu # Cryptographic Primitives
diff --git a/src/security/crypto/Makefile.inc b/src/security/crypto/Makefile.inc
index b22ce00..d4e4b1b 100644
--- a/src/security/crypto/Makefile.inc
+++ b/src/security/crypto/Makefile.inc
@@ -24,3 +24,8 @@
romstage-$(CONFIG_CRYPTO_HMAC) += hmac/hmac.c
ramstage-$(CONFIG_CRYPTO_HMAC) += hmac/hmac.c
smm-$(CONFIG_CRYPTO_HMAC) += hmac/hmac.c
+
+verstage-$(CONFIG_CRYPTO_RSA) += rsa/rsa.c common/common.c
+romstage-$(CONFIG_CRYPTO_RSA) += rsa/rsa.c common/common.c
+ramstage-$(CONFIG_CRYPTO_RSA) += rsa/rsa.c common/common.c
+smm-$(CONFIG_CRYPTO_RSA) += rsa/rsa.c common/common.c
diff --git a/src/security/crypto/rsa.h b/src/security/crypto/rsa.h
new file mode 100644
index 0000000..543c8eb
--- /dev/null
+++ b/src/security/crypto/rsa.h
@@ -0,0 +1,102 @@
+/* Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef CRYPTO_RSA_H_
+#define CRYPTO_RSA_H_
+
+#include <security/crypto/hash.h>
+
+struct workbuf;
+
+enum signature_algorithm {
+ /* Invalid or unsupported signature type */
+ SIG_INVALID = 0,
+
+ /*
+ * No signature algorithm. The digest is unsigned. See
+ * ID_NONE_* for key IDs to use with this algorithm.
+ */
+ SIG_NONE = 1,
+
+ /* RSA algorithms of the given length in bits (1024-8192) */
+ SIG_RSA1024 = 2, /* Warning! This is likely to be deprecated! */
+ SIG_RSA2048 = 3,
+ SIG_RSA4096 = 4,
+ SIG_RSA8192 = 5,
+ SIG_RSA2048_EXP3 = 6,
+ SIG_RSA3072_EXP3 = 7,
+
+ /* Last index. Don't add anything below. */
+ SIG_ALG_COUNT,
+};
+
+
+/* Public key structure in RAM */
+struct public_key {
+ uint32_t arrsize; /* Length of n[] and rr[] in number of uint32_t */
+ uint32_t n0inv; /* -1 / n[0] mod 2^32 */
+ const uint32_t *n; /* Modulus as little endian array */
+ const uint32_t *rr; /* R^2 as little endian array */
+ enum signature_algorithm sig_alg; /* Signature algorithm */
+ enum hash_algorithm hash_alg; /* Hash algorithm */
+ const char *desc; /* Description */
+ uint32_t version; /* Key version */
+ const struct id *id; /* Key ID */
+};
+
+/**
+ * Convert crypto_algorithm to signature_algorithm.
+ *
+ * @param algorithm Crypto algorithm (crypto_algorithm)
+ *
+ * @return The signature algorithm for that crypto algorithm, or
+ * SIG_INVALID if the crypto algorithm or its corresponding signature
+ * algorithm is invalid or not supported.
+ */
+enum signature_algorithm crypto_to_signature(uint32_t algorithm);
+
+/**
+ * Return the size of a RSA signature
+ *
+ * @param sig_alg Signature algorithm
+ * @return The size of the signature in bytes, or 0 if error.
+ */
+uint32_t rsa_sig_size(enum signature_algorithm sig_alg);
+
+/**
+ * Return the size of a pre-processed RSA public key.
+ *
+ * @param sig_alg Signature algorithm
+ * @return The size of the preprocessed key in bytes, or 0 if error.
+ */
+uint32_t packed_key_size(enum signature_algorithm sig_alg);
+
+/**
+ * Check pkcs 1.5 padding bytes
+ *
+ * @param sig Signature to verify
+ * @param key Key to take signature and hash algorithms from
+ * @return SUCCESS, or non-zero if error.
+ */
+int check_padding(const uint8_t *sig, const struct public_key *key);
+
+/* Size of work buffer sufficient for rsa_verify_digest() worst case */
+#define VERIFY_RSA_DIGEST_WORKBUF_BYTES (3 * 1024)
+
+/**
+ * Verify a RSA PKCS1.5 signature against an expected hash digest.
+ *
+ * @param key Key to use in signature verification
+ * @param sig Signature to verify (destroyed in process)
+ * @param digest Digest of signed data
+ * @param wb Work buffer
+ * @return SUCCESS, or non-zero if error.
+ */
+int rsa_verify_digest(const struct public_key *key,
+ uint8_t *sig,
+ const uint8_t *digest,
+ const struct workbuf *wb);
+
+#endif /* CRYPTO_RSA_H_ */
diff --git a/src/security/crypto/rsa/rsa.c b/src/security/crypto/rsa/rsa.c
new file mode 100644
index 0000000..5e53b3c
--- /dev/null
+++ b/src/security/crypto/rsa/rsa.c
@@ -0,0 +1,426 @@
+/* Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+/*
+ * Implementation of RSA signature verification which uses a pre-processed key
+ * for computation. The code extends Android's RSA verification code to support
+ * multiple RSA key lengths and hash digest algorithms.
+ */
+
+#include <console/console.h>
+
+#include <security/crypto/rsa.h>
+#include <security/crypto/errors.h>
+#include <security/crypto/common.h>
+
+/**
+ * a[] -= mod
+ */
+static void subM(const struct public_key *key, uint32_t *a)
+{
+ int64_t A = 0;
+ uint32_t i;
+ for (i = 0; i < key->arrsize; ++i) {
+ A += (uint64_t)a[i] - key->n[i];
+ a[i] = (uint32_t)A;
+ A >>= 32;
+ }
+}
+
+/**
+ * Return a[] >= mod
+ */
+static int mont_ge(const struct public_key *key, uint32_t *a)
+{
+ uint32_t i;
+ for (i = key->arrsize; i;) {
+ --i;
+ if (a[i] < key->n[i])
+ return 0;
+ if (a[i] > key->n[i])
+ return 1;
+ }
+ return 1; /* equal */
+}
+
+/**
+ * Montgomery c[] += a * b[] / R % mod
+ */
+static void montMulAdd(const struct public_key *key,
+ uint32_t *c,
+ const uint32_t a,
+ const uint32_t *b)
+{
+ uint64_t A = (uint64_t)a * b[0] + c[0];
+ uint32_t d0 = (uint32_t)A * key->n0inv;
+ uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
+ uint32_t i;
+
+ for (i = 1; i < key->arrsize; ++i) {
+ A = (A >> 32) + (uint64_t)a * b[i] + c[i];
+ B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
+ c[i - 1] = (uint32_t)B;
+ }
+
+ A = (A >> 32) + (B >> 32);
+
+ c[i - 1] = (uint32_t)A;
+
+ if (A >> 32) {
+ subM(key, c);
+ }
+}
+
+/**
+ * Montgomery c[] += 0 * b[] / R % mod
+ */
+static void montMulAdd0(const struct public_key *key,
+ uint32_t *c,
+ const uint32_t *b)
+{
+ uint32_t d0 = c[0] * key->n0inv;
+ uint64_t B = (uint64_t)d0 * key->n[0] + c[0];
+ uint32_t i;
+
+ for (i = 1; i < key->arrsize; ++i) {
+ B = (B >> 32) + (uint64_t)d0 * key->n[i] + c[i];
+ c[i - 1] = (uint32_t)B;
+ }
+
+ c[i - 1] = B >> 32;
+}
+
+/**
+ * Montgomery c[] = a[] * b[] / R % mod
+ */
+static void montMul(const struct public_key *key,
+ uint32_t *c,
+ const uint32_t *a,
+ const uint32_t *b)
+{
+ uint32_t i;
+ for (i = 0; i < key->arrsize; ++i) {
+ c[i] = 0;
+ }
+ for (i = 0; i < key->arrsize; ++i) {
+ montMulAdd(key, c, a[i], b);
+ }
+}
+
+/* Montgomery c[] = a[] * 1 / R % key. */
+static void montMul1(const struct public_key *key,
+ uint32_t *c,
+ const uint32_t *a)
+{
+ int i;
+
+ for (i = 0; i < key->arrsize; ++i)
+ c[i] = 0;
+
+ montMulAdd(key, c, 1, a);
+ for (i = 1; i < key->arrsize; ++i)
+ montMulAdd0(key, c, a);
+}
+
+/**
+ * In-place public exponentiation.
+ *
+ * @param key Key to use in signing
+ * @param inout Input and output big-endian byte array
+ * @param workbuf32 Work buffer; caller must verify this is
+ * (3 * key->arrsize) elements long.
+ * @param exp RSA public exponent: either 65537 (F4) or 3
+ */
+static void modpow(const struct public_key *key, uint8_t *inout,
+ uint32_t *workbuf32, int exp)
+{
+ uint32_t *a = workbuf32;
+ uint32_t *aR = a + key->arrsize;
+ uint32_t *aaR = aR + key->arrsize;
+ uint32_t *aaa = aaR; /* Re-use location. */
+ int i;
+
+ /* Convert from big endian byte array to little endian word array. */
+ for (i = 0; i < (int)key->arrsize; ++i) {
+ uint32_t tmp =
+ (inout[((key->arrsize - 1 - i) * 4) + 0] << 24) |
+ (inout[((key->arrsize - 1 - i) * 4) + 1] << 16) |
+ (inout[((key->arrsize - 1 - i) * 4) + 2] << 8) |
+ (inout[((key->arrsize - 1 - i) * 4) + 3] << 0);
+ a[i] = tmp;
+ }
+
+ montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */
+ if (exp == 3) {
+ montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
+ montMul(key, a, aaR, aR); /* a = aaR * aR / R mod M */
+ montMul1(key, aaa, a); /* aaa = a * 1 / R mod M */
+ } else {
+ /* Exponent 65537 */
+ for (i = 0; i < 16; i+=2) {
+ montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
+ montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
+ }
+ montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
+ }
+
+ /* Make sure aaa < mod; aaa is at most 1x mod too large. */
+ if (mont_ge(key, aaa)) {
+ subM(key, aaa);
+ }
+
+ /* Convert to bigendian byte array */
+ for (i = (int)key->arrsize - 1; i >= 0; --i) {
+ uint32_t tmp = aaa[i];
+ *inout++ = (uint8_t)(tmp >> 24);
+ *inout++ = (uint8_t)(tmp >> 16);
+ *inout++ = (uint8_t)(tmp >> 8);
+ *inout++ = (uint8_t)(tmp >> 0);
+ }
+}
+
+
+static const uint8_t crypto_to_sig[] = {
+ SIG_RSA1024,
+ SIG_RSA1024,
+ SIG_RSA1024,
+ SIG_RSA2048,
+ SIG_RSA2048,
+ SIG_RSA2048,
+ SIG_RSA4096,
+ SIG_RSA4096,
+ SIG_RSA4096,
+ SIG_RSA8192,
+ SIG_RSA8192,
+ SIG_RSA8192,
+ SIG_RSA2048_EXP3,
+ SIG_RSA2048_EXP3,
+ SIG_RSA2048_EXP3,
+ SIG_RSA3072_EXP3,
+ SIG_RSA3072_EXP3,
+ SIG_RSA3072_EXP3,
+};
+
+/**
+ * Convert crypto_algorithm to signature_algorithm.
+ *
+ * @param algorithm Crypto algorithm (crypto_algorithm)
+ *
+ * @return The signature algorithm for that crypto algorithm, or
+ * SIG_INVALID if the crypto algorithm or its corresponding signature
+ * algorithm is invalid or not supported.
+ */
+enum signature_algorithm crypto_to_signature(uint32_t algorithm)
+{
+ if (algorithm < ARRAY_SIZE(crypto_to_sig))
+ return crypto_to_sig[algorithm];
+ else
+ return SIG_INVALID;
+}
+
+uint32_t rsa_sig_size(enum signature_algorithm sig_alg)
+{
+ switch (sig_alg) {
+ case SIG_RSA1024:
+ return 1024 / 8;
+ case SIG_RSA2048:
+ case SIG_RSA2048_EXP3:
+ return 2048 / 8;
+ case SIG_RSA3072_EXP3:
+ return 3072 / 8;
+ case SIG_RSA4096:
+ return 4096 / 8;
+ case SIG_RSA8192:
+ return 8192 / 8;
+ default:
+ return 0;
+ }
+}
+
+/**
+ * Return the exponent used by an RSA algorithm
+ *
+ * @param sig_alg Signature algorithm
+ * @return The exponent to use (3 or 65537(F4)), or 0 if error.
+ */
+static uint32_t rsa_exponent(enum signature_algorithm sig_alg)
+{
+ switch (sig_alg) {
+ case SIG_RSA1024:
+ case SIG_RSA2048:
+ case SIG_RSA4096:
+ case SIG_RSA8192:
+ return 65537;
+ case SIG_RSA2048_EXP3:
+ case SIG_RSA3072_EXP3:
+ return 3;
+ default:
+ return 0;
+ }
+}
+
+uint32_t packed_key_size(enum signature_algorithm sig_alg)
+{
+ uint32_t sig_size = rsa_sig_size(sig_alg);
+
+ if (!sig_size)
+ return 0;
+
+ /*
+ * Total size needed by a RSAPublicKey buffer is =
+ * 2 * key_len bytes for the n and rr arrays
+ * + sizeof len + sizeof n0inv.
+ */
+ return 2 * sig_size + 2 * sizeof(uint32_t);
+}
+
+/*
+ * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard)
+ *
+ * Depending on the RSA key size and hash function, the padding is calculated
+ * as follows:
+ *
+ * 0x00 || 0x01 || PS || 0x00 || T
+ *
+ * T: DER Encoded DigestInfo value which depends on the hash function used.
+ *
+ * SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
+ * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.
+ * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H.
+ *
+ * Length(T) = 35 octets for SHA-1
+ * Length(T) = 51 octets for SHA-256
+ * Length(T) = 83 octets for SHA-512
+ *
+ * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF
+ */
+static const uint8_t sha1_tail[] = {
+ 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,
+ 0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14
+};
+
+static const uint8_t sha256_tail[] = {
+ 0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60,
+ 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01,
+ 0x05,0x00,0x04,0x20
+};
+
+static const uint8_t sha512_tail[] = {
+ 0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60,
+ 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03,
+ 0x05,0x00,0x04,0x40
+};
+
+int check_padding(const uint8_t *sig, const struct public_key *key)
+{
+ /* Determine padding to use depending on the signature type */
+ uint32_t sig_size = rsa_sig_size(key->sig_alg);
+ uint32_t hash_size = digest_size(key->hash_alg);
+ uint32_t pad_size = sig_size - hash_size;
+ const uint8_t *tail;
+ uint32_t tail_size;
+ int result = 0;
+ int i;
+
+ if (!sig_size || !hash_size || hash_size > sig_size)
+ return ERROR_RSA_PADDING_SIZE;
+
+ switch (key->hash_alg) {
+ case HASH_SHA1:
+ tail = sha1_tail;
+ tail_size = sizeof(sha1_tail);
+ break;
+ case HASH_SHA256:
+ tail = sha256_tail;
+ tail_size = sizeof(sha256_tail);
+ break;
+ case HASH_SHA512:
+ tail = sha512_tail;
+ tail_size = sizeof(sha512_tail);
+ break;
+ default:
+ return ERROR_RSA_PADDING_ALGORITHM;
+ }
+
+ /* First 2 bytes are always 0x00 0x01 */
+ result |= *sig++ ^ 0x00;
+ result |= *sig++ ^ 0x01;
+
+ /* Then 0xff bytes until the tail */
+ for (i = 0; i < pad_size - tail_size - 2; i++)
+ result |= *sig++ ^ 0xff;
+
+ /*
+ * Then the tail. Even though there are probably no timing issues
+ * here, we use safe_memcmp() just to be on the safe side.
+ */
+ result |= safe_memcmp(sig, tail, tail_size);
+
+ return result ? ERROR_RSA_PADDING : SUCCESS;
+}
+
+int rsa_verify_digest(const struct public_key *key,
+ uint8_t *sig,
+ const uint8_t *digest,
+ const struct workbuf *wb)
+{
+ struct workbuf wblocal = *wb;
+ uint32_t *workbuf32;
+ uint32_t key_bytes;
+ int sig_size;
+ int pad_size;
+ int exp;
+ int rv;
+
+ if (!key || !sig || !digest)
+ return ERROR_RSA_VERIFY_PARAM;
+
+ sig_size = rsa_sig_size(key->sig_alg);
+ exp = rsa_exponent(key->sig_alg);
+ if (!sig_size || !exp) {
+ printk(BIOS_DEBUG,"Invalid signature type!\n");
+ return ERROR_RSA_VERIFY_ALGORITHM;
+ }
+
+ /* Signature length should be same as key length */
+ key_bytes = key->arrsize * sizeof(uint32_t);
+ if (key_bytes != sig_size) {
+ printk(BIOS_DEBUG,"Signature is of incorrect length!\n");
+ return ERROR_RSA_VERIFY_SIG_LEN;
+ }
+
+ workbuf32 = workbuf_alloc(&wblocal, 3 * key_bytes);
+ if (!workbuf32) {
+ printk(BIOS_DEBUG,"ERROR - vboot2 work buffer too small!\n");
+ return ERROR_RSA_VERIFY_WORKBUF;
+ }
+
+ modpow(key, sig, workbuf32, exp);
+
+ workbuf_free(&wblocal, 3 * key_bytes);
+
+ /*
+ * Check padding. Only fail immediately if the padding size is bad.
+ * Otherwise, continue on to check the digest to reduce the risk of
+ * timing based attacks.
+ */
+ rv = check_padding(sig, key);
+ if (rv == ERROR_RSA_PADDING_SIZE)
+ return rv;
+
+ /*
+ * Check digest. Even though there are probably no timing issues here,
+ * use safe_memcmp() just to be on the safe side. (That's also why
+ * we don't return before this check if the padding check failed.)
+ */
+ pad_size = sig_size - digest_size(key->hash_alg);
+ if (safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) {
+ printk(BIOS_DEBUG,"Digest check failed!\n");
+ if (!rv)
+ rv = ERROR_RSA_VERIFY_DIGEST;
+ }
+
+ return rv;
+}
--
To view, visit https://review.coreboot.org/23218
To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings
Gerrit-Project: coreboot
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ic58be92ad184cccaa8d6fc87d2c60bad63f3ec3b
Gerrit-Change-Number: 23218
Gerrit-PatchSet: 1
Gerrit-Owner: Philipp Deppenwiese <zaolin.daisuki at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.coreboot.org/pipermail/coreboot-gerrit/attachments/20180111/ed145839/attachment-0001.html>
More information about the coreboot-gerrit
mailing list