[PATCH 00/29] Crypto keys and module signing [ver #4]

May 10th, 2012 - 07:40 pm ET by David Howells | Report spam

Hi Rusty,

Here's my latest take on my module signing patch set. I've retained my
strip-proof[*] signature-in-module concept, but I've shrunk the module
verification code by nearly half. Its .text segment now stands at just over 2K
in size for an x86_64 kernel.

There were a lot of redundant tests, either redundant due to other tests, or
redundant due to the data being tested also being added to the digest before
being used. Also rearranging things helped - and gcc's optimiser doesn't
always make good decisions, particularly when deciding whether to inline large
functions:-/. I've tried to better comment/describe where I've found a
redundancy.

I think that a further reduction in size could probably be achieved by
combining the ELF checks with the layout code in kernel/module.c - but then it
is mandatory to perform the checks.

Note there is a patch in there (look for "Guard check in module loader against
integer overflow") that is a bugfix to kernel/module.c.

Can you please consider applying these patches?

David

[*] Not proof against strip or strip -s which totally break the module by
removing the symbol table entirely, but proof against strip -g, strip -x
and eu-strip.

Here are a set of patches that create a framework for using cryptographic keys
within the kernel. The patches can also be found at:

http://git.kernel.org/?p=linux/kern...ds/modsign

The basic crypto key has no requirements as to how the key is implemented; it's
an anchor for any relevant data. The crypto key uses registerable data parsers
that are used to extract information from key blobs and signature blobs and
from that construct keys and determine signature verification contexts, thus
connecting everything together.

I have provided an asymmetric public-key subtype with one public-key algorithm
(RSA). This only provides signature verification facilities at this time. The
public-key subtype defines a structure for storing key data that is useful to
this algorithm and to DSA, should it be added.

I have provided a PGP parser that can take PGP key blobs and PGP signatures,
set up public-key subtype keys and orchestrate signature verification using the
public key algorithms.

It would be possible to merely refer to keys held in a hardware keystore (such
as a TPM) and have the parser and subtype offload the actual work to that
keystore to be done in hardware.

With kernel module signing enabled, and a pair of keys (one RSA, one DSA)
compiled into the kernel, root can see these keys and the keyring that holds
them in /proc/keys:

195fa736 I-- 1 perm 3f010000 0 0 crypto modsign.1: DSA 5acc2142 []
335ab517 I-- 1 perm 1f030000 0 0 keyring .module_sign: 2/4
38d7d169 I-- 1 perm 3f010000 0 0 crypto modsign.0: RSA 57532ca5 []

Module signing combinations that have been tested: RSA with all the SHA
algorithms. I have a patch (not included here) that does DSA too, and that has
been tested with SHA-1.

The patches break down into a number of areas:

(1) MPI library alterations.

(2) Some small key-handling core code changes to make things easier.

(3) Crypto key type: key handling and verification access functions.

(4) Public key subtype and RSA algorithm.

(5) PGP definitions and parsing utilities library.

(6) PGP data parser for key blobs and signature blobs.

(7) PGP key preloader for module signing to use.

(8) A pair of macros for providing ELF note name wrappers.

(9) A fix for the core module code to handle an integer overflow in a check.

(10) Module ELF verification and module signature verification.

The complete crypto type documentation can be found within the GIT tree here:

http://git.kernel.org/?p=linux/kern...4d60e53;hb8049a9def253735019a5acf19b4c2aeec9f01c

and the module signature verification documentation can be found here:

http://git.kernel.org/?p=linux/kern...13e4b8b;hb8049a9def253735019a5acf19b4c2aeec9f01c

Changes made 10/05/2012:

(*) Overhauled the ELF checking code and module signing code.

- Moved into one file.
- Removed a lot of redundant ELF checks, relying a lot on the signature to
catch stuff.
- Rearranged the ELF checker function.
- Commented thoroughly and documented things better in the commit messages.
- Made it possible to exclude REL or RELA relocation handling.
- Rearranged the modsign patch subset to be more logical.
- Massively reduced the code size.

(*) Applied a patch to handle short signatures.

(*) Fixed a potential overflow in a check in the core module code.

Changes made 07/12/2011:

(*) Dropped the DSA algorithm.

Changes made 02/12/2011:

(*) Completely overhauled the architecture.

- Introduced data parsers.
- Reduced subtype to cryptographic data carrier.
- Extracted out the common PGP bits of DSA and RSA algorithms.
- Defined an asymmetric public-key subtype.
- Reduced DSA and RSA algorithms to minimum.
- Rolled verification initiation and key selection together into one.
- Moved verification add_data/finish/cancel op pointers into verification
context.

Changes made 29/11/2011:

(*) Added RSA signature verification.

(*) Stopped signature verification crashing on unsupported hash algorithm.

(*) Fixed ENOMEM handling bug in MPI.

(*) Worked around ccache problems with compilation of PGP public keyring into
kernel (ccache hashes the preprocessor output, but the assembler includes
the binary data, so ccache doesn't see that it changed).

(*) Added a choice in kernel config for hash algorithm to use; forced the
appropriate crypto module to be built directly into the kernel.

(*) Cleaned out some debugging code.

(*) Updated documentation.

David Howells (29):
MODSIGN: Suppress some redundant ELF checks
MODSIGN: Automatically generate module signing keys if missing
MODSIGN: Create digest of module content and check signature
MODSIGN: Produce a filtered and canonicalised section list
MODSIGN: Check the ELF container
MODSIGN: Provide module signing public keys to the kernel
MODSIGN: Module signature verification stub
MODSIGN: Sign modules during the build process
MODSIGN: Provide Documentation and Kconfig options
MODSIGN: Provide gitignore and make clean rules for extra files
MODSIGN: Add indications of module ELF types
Guard check in module loader against integer overflow
Provide macros for forming the name of an ELF note and its section
KEYS: Provide a function to load keys from a PGP keyring blob
KEYS: PGP format signature parser
KEYS: PGP-based public key signature verification
KEYS: PGP data parser
PGPLIB: Signature parser
PGPLIB: Basic packet parser
PGPLIB: PGP definitions (RFC 4880)
Fix signature verification for shorter signatures
KEYS: RSA signature verification algorithm
KEYS: Asymmetric public-key algorithm crypto key subtype
KEYS: Add signature verification facility
KEYS: Create a key type that can be used for general cryptographic operations
KEYS: Reorganise keys Makefile
KEYS: Announce key type (un)registration
KEYS: Move the key config into security/keys/Kconfig
MPILIB: Export some more symbols

.gitignore | 12
Documentation/module-signing.txt | 194 +++++++
Documentation/security/keys-crypto.txt | 302 +++++++++++
Makefile | 1
arch/alpha/include/asm/module.h | 3
arch/arm/include/asm/module.h | 5
arch/cris/include/asm/module.h | 5
arch/h8300/include/asm/module.h | 5
arch/ia64/include/asm/module.h | 5
arch/m32r/include/asm/module.h | 5
arch/m68k/include/asm/module.h | 5
arch/mips/include/asm/module.h | 12
arch/parisc/include/asm/module.h | 8
arch/powerpc/include/asm/module.h | 10
arch/s390/include/asm/module.h | 3
arch/x86/include/asm/module.h | 6
include/asm-generic/module.h | 10
include/keys/crypto-subtype.h | 77 +++
include/keys/crypto-type.h | 37 +
include/linux/elfnote.h | 4
include/linux/modsign.h | 27 +
include/linux/module.h | 3
include/linux/pgp.h | 255 +++++++++
init/Kconfig | 53 ++
kernel/Makefile | 42 +
kernel/modsign-pubkey.c | 74 +++
kernel/module-verify-defs.h | 81 +++
kernel/module-verify.c | 732 ++++++++++++++++++++++++++
kernel/module-verify.h | 19 +
kernel/module.c | 29 +
lib/mpi/mpi-cmp.c | 2
lib/mpi/mpi-div.c | 1
lib/mpi/mpi-inv.c | 1
lib/mpi/mpi-mpow.c | 1
lib/mpi/mpi-mul.c | 1
net/dns_resolver/dns_key.c | 5
scripts/Makefile.modpost | 87 +++
scripts/mod/.gitignore | 1
scripts/mod/Makefile | 2
scripts/mod/mod-extract.c | 913 ++++++++++++++++++++++++++++++++
scripts/mod/modsign-note.sh | 16 +
security/Kconfig | 68 --
security/keys/Kconfig | 73 +++
security/keys/Makefile | 13
security/keys/crypto/Kconfig | 51 ++
security/keys/crypto/Makefile | 17 +
security/keys/crypto/crypto_keys.h | 28 +
security/keys/crypto/crypto_rsa.c | 290 ++++++++++
security/keys/crypto/crypto_type.c | 228 ++++++++
security/keys/crypto/crypto_verify.c | 111 ++++
security/keys/crypto/pgp_key_parser.c | 344 ++++++++++++
security/keys/crypto/pgp_library.c | 531 +++++++++++++++++++
security/keys/crypto/pgp_parser.h | 35 +
security/keys/crypto/pgp_preload.c | 90 +++
security/keys/crypto/pgp_pubkey_sig.c | 323 +++++++++++
security/keys/crypto/pgp_sig_parser.c | 104 ++++
security/keys/crypto/public_key.c | 55 ++
security/keys/crypto/public_key.h | 108 ++++
security/keys/key.c | 3
59 files changed, 5441 insertions(+), 85 deletions(-)
create mode 100644 Documentation/module-signing.txt
create mode 100644 Documentation/security/keys-crypto.txt
create mode 100644 include/keys/crypto-subtype.h
create mode 100644 include/keys/crypto-type.h
create mode 100644 include/linux/modsign.h
create mode 100644 include/linux/pgp.h
create mode 100644 kernel/modsign-pubkey.c
create mode 100644 kernel/module-verify-defs.h
create mode 100644 kernel/module-verify.c
create mode 100644 kernel/module-verify.h
create mode 100644 scripts/mod/mod-extract.c
create mode 100644 scripts/mod/modsign-note.sh
create mode 100644 security/keys/Kconfig
create mode 100644 security/keys/crypto/Kconfig
create mode 100644 security/keys/crypto/Makefile
create mode 100644 security/keys/crypto/crypto_keys.h
create mode 100644 security/keys/crypto/crypto_rsa.c
create mode 100644 security/keys/crypto/crypto_type.c
create mode 100644 security/keys/crypto/crypto_verify.c
create mode 100644 security/keys/crypto/pgp_key_parser.c
create mode 100644 security/keys/crypto/pgp_library.c
create mode 100644 security/keys/crypto/pgp_parser.h
create mode 100644 security/keys/crypto/pgp_preload.c
create mode 100644 security/keys/crypto/pgp_pubkey_sig.c
create mode 100644 security/keys/crypto/pgp_sig_parser.c
create mode 100644 security/keys/crypto/public_key.c
create mode 100644 security/keys/crypto/public_key.h

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Follow the discussion Replies

29 replies Replies

Make a reply

Replies

#1 David Howells

May 10th, 2012 - 07:50 pm ET | Report spam

Implement the RSA algorithm (PKCS#1 / RFC3447). At this time, only signature
verification is supported. This uses the asymmetric public key subtype to hold
its key data.

Signed-off-by: David Howells

security/keys/crypto/Kconfig | 7 +
security/keys/crypto/Makefile | 1
security/keys/crypto/crypto_rsa.c | 282 +++++++++++++++++++++++++++++++++++++
security/keys/crypto/public_key.h | 2
4 files changed, 292 insertions(+), 0 deletions(-)
create mode 100644 security/keys/crypto/crypto_rsa.c

diff --git a/security/keys/crypto/Kconfig b/security/keys/crypto/Kconfig
index 5f2b8ac..4e3777e 100644
a/security/keys/crypto/Kconfig
+++ b/security/keys/crypto/Kconfig
@@ -15,3 +15,10 @@ config CRYPTO_KEY_PUBLIC_KEY_SUBTYPE
If signature generation and/or verification are to be used,
appropriate hash algorithms (such as SHA-1) must be available.
ENOPKG will be reported if the requisite algorithm is unavailable.
+
+config CRYPTO_KEY_PKEY_ALGO_RSA
+ tristate "RSA public-key algorithm"
+ depends on CRYPTO_KEY_PUBLIC_KEY_SUBTYPE
+ select MPILIB_EXTRA
+ help
+ This option enables support for the RSA algorithm (PKCS#1, RFC3447).
diff --git a/security/keys/crypto/Makefile b/security/keys/crypto/Makefile
index 6384306..b6b1a5a 100644
a/security/keys/crypto/Makefile
+++ b/security/keys/crypto/Makefile
@@ -6,3 +6,4 @@ obj-$(CONFIG_CRYPTO_KEY_TYPE) += crypto_keys.o
crypto_keys-y := crypto_type.o crypto_verify.o

obj-$(CONFIG_CRYPTO_KEY_PUBLIC_KEY_SUBTYPE) += public_key.o
+obj-$(CONFIG_CRYPTO_KEY_PKEY_ALGO_RSA) += crypto_rsa.o
diff --git a/security/keys/crypto/crypto_rsa.c b/security/keys/crypto/crypto_rsa.c
new file mode 100644
index 0000000..beb5181
/dev/null
+++ b/security/keys/crypto/crypto_rsa.c
@@ -0,0 +1,282 @@
+/* RSA asymmetric public-key algorithm [RFC3447]
+ *
+ * Copyright (C) 2011 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells ()
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#define pr_fmt(fmt) "RSA: "fmt
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include "public_key.h"
+
+MODULE_LICENSE("GPL");
+
+#define kenter(FMT, ...) \
+ pr_devel("==> %s("FMT")", __func__, ##__VA_ARGS__)
+#define kleave(FMT, ...) \
+ pr_devel("<== %s()"FMT"", __func__, ##__VA_ARGS__)
+
+/*
+ * 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 const *data;
+ size_t size;
+} RSA_ASN1_templates[PKEY_HASH__LAST] = {
+#define _(X) { RSA_digest_info_##X, sizeof(RSA_digest_info_##X) }
+ [PKEY_HASH_MD5] = _(MD5),
+ [PKEY_HASH_SHA1] = _(SHA1),
+ [PKEY_HASH_RIPE_MD_160] = _(RIPE_MD_160),
+ [PKEY_HASH_SHA256] = _(SHA256),
+ [PKEY_HASH_SHA384] = _(SHA384),
+ [PKEY_HASH_SHA512] = _(SHA512),
+ [PKEY_HASH_SHA224] = _(SHA224),
+#undef _
+};
+
+/*
+ * RSAVP1() function [RFC3447 sec 5.2.2]
+ */
+static int RSAVP1(const struct public_key *key, MPI s, MPI *_m)
+{
+ MPI m;
+ int ret;
+
+ /* (1) Validate 0 <= s < n */
+ if (mpi_cmp_ui(s, 0) < 0) {
+ kleave(" = -EBADMSG [s < 0]");
+ return -EBADMSG;
+ }
+ if (mpi_cmp(s, key->rsa.n) >= 0) {
+ kleave(" = -EBADMSG [s >= n]");
+ return -EBADMSG;
+ }
+
+ m = mpi_alloc(0);
+ if (!m)
+ return -ENOMEM;
+
+ /* (2) m = s^e mod n */
+ ret = mpi_powm(m, s, key->rsa.e, key->rsa.n);
+ if (ret < 0) {
+ mpi_free(m);
+ return ret;
+ }
+
+ *_m = m;
+ return 0;
+}
+
+/*
+ * Integer to Octet String conversion [RFC3447 sec 4.1]
+ */
+static int RSA_I2OSP(MPI x, size_t xLen, u8 **_X)
+{
+ unsigned X_size, x_size;
+ int X_sign;
+ u8 *X;
+
+ /* Make sure the string is the right length. The number should begin
+ * with { 0x00, 0x01, ... } so we have to account for 15 leading zero
+ * bits not being reported by MPI.
+ */
+ x_size = mpi_get_nbits(x);
+ pr_devel("size(x)=%u xLen*8=%zu", x_size, xLen * 8);
+ if (x_size != xLen * 8 - 15)
+ return -ERANGE;
+
+ X = mpi_get_buffer(x, &X_size, &X_sign);
+ if (!X)
+ return -ENOMEM;
+ if (X_sign < 0) {
+ kfree(X);
+ return -EBADMSG;
+ }
+ if (X_size != xLen - 1) {
+ kfree(X);
+ return -EBADMSG;
+ }
+
+ *_X = X;
+ return 0;
+}
+
+/*
+ * Perform the RSA signature verification.
+ * @H: Value of hash of data and metadata
+ * @EM: The computed signature value
+ * @k: The size of EM (EM[0] is an invalid location but should hold 0x00)
+ * @hash_size: The size of H
+ * @asn1_template: The DigestInfo ASN.1 template
+ * @asn1_size: Size of asm1_template[]
+ */
+static int RSA_verify(const u8 *H, const u8 *EM, size_t k, size_t hash_size,
+ const u8 *asn1_template, size_t asn1_size)
+{
+ unsigned PS_end, T_offset, i;
+
+ kenter(",,%zu,%zu,%zu", k, hash_size, asn1_size);
+
+ if (k < 2 + 1 + asn1_size + hash_size)
+ return -EBADMSG;
+
+ /* Decode the EMSA-PKCS1-v1_5 */
+ if (EM[1] != 0x01) {
+ kleave(" = -EBADMSG [EM[1] == %02u]", EM[1]);
+ return -EBADMSG;
+ }
+
+ T_offset = k - (asn1_size + hash_size);
+ PS_end = T_offset - 1;
+ if (EM[PS_end] != 0x00) {
+ kleave(" = -EBADMSG [EM[T-1] == %02u]", EM[PS_end]);
+ return -EBADMSG;
+ }
+
+ for (i = 2; i < PS_end; i++) {
+ if (EM[i] != 0xff) {
+ kleave(" = -EBADMSG [EM[PS%x] == %02u]", i - 2, EM[i]);
+ return -EBADMSG;
+ }
+ }
+
+ if (memcmp(asn1_template, EM + T_offset, asn1_size) != 0) {
+ kleave(" = -EBADMSG [EM[T] ASN.1 mismatch]");
+ return -EBADMSG;
+ }
+
+ if (memcmp(H, EM + T_offset + asn1_size, hash_size) != 0) {
+ kleave(" = -EKEYREJECTED [EM[T] hash mismatch]");
+ return -EKEYREJECTED;
+ }
+
+ kleave(" = 0");
+ return 0;
+}
+
+/*
+ * Perform the verification step [RFC3447 sec 8.2.2].
+ */
+static int RSA_verify_signature(const struct public_key *key,
+ const struct public_key_signature *sig)
+{
+ size_t tsize;
+ int ret;
+
+ /* Variables as per RFC3447 sec 8.2.2 */
+ const u8 *H = sig->digest;
+ u8 *EM = NULL;
+ MPI m = NULL;
+ size_t k;
+
+ kenter("");
+
+ /* (1) Check the signature size against the public key modulus size */
+ k = (mpi_get_nbits(key->rsa.n) + 7) / 8;
+
+ tsize = (mpi_get_nbits(sig->rsa.s) + 7) / 8;
+ pr_devel("step 1: k=%zu size(S)=%zu", k, tsize);
+ if (tsize != k) {
+ ret = -EBADMSG;
+ goto error;
+ }
+
+ /* (2b) Apply the RSAVP1 verification primitive to the public key */
+ ret = RSAVP1(key, sig->rsa.s, &m);
+ if (ret < 0)
+ goto error;
+
+ /* (2c) Convert the message representative (m) to an encoded message
+ * (EM) of length k octets.
+ *
+ * NOTE! The leading zero byte is suppressed by MPI, so we pass a
+ * pointer to the _preceding_ byte to RSA_verify()!
+ */
+ ret = RSA_I2OSP(m, k, &EM);
+ if (ret < 0)
+ goto error;
+
+#if 0
+ {
+ int i;
+ printk("H: ");
+ for (i = 0; i < sig->digest_size; i++)
+ printk("%02x", H[i]);
+ printk("");
+ }
+
+ {
+ int i;
+ printk("EM: 00");
+ for (i = 0; i < k - 1; i++)
+ printk("%02x", EM[i]);
+ printk("");
+ }
+#endif
+
+ ret = RSA_verify(H, EM - 1, k, sig->digest_size,
+ RSA_ASN1_templates[sig->pkey_hash_algo].data,
+ RSA_ASN1_templates[sig->pkey_hash_algo].size);
+
+error:
+ kfree(EM);
+ mpi_free(m);
+ kleave(" = %d", ret);
+ return ret;
+}
+
+const struct public_key_algorithm RSA_public_key_algorithm = {
+ .name = "RSA",
+ .n_pub_mpi = 2,
+ .n_sec_mpi = 3,
+ .n_sig_mpi = 1,
+ .verify = RSA_verify_signature,
+};
+EXPORT_SYMBOL_GPL(RSA_public_key_algorithm);
diff --git a/security/keys/crypto/public_key.h b/security/keys/crypto/public_key.h
index 81ed603..7913615 100644
a/security/keys/crypto/public_key.h
+++ b/security/keys/crypto/public_key.h
@@ -42,6 +42,8 @@ struct public_key_algorithm {
const struct public_key_signature *sig);
};

+extern const struct public_key_algorithm RSA_public_key_algorithm;
+
/*
* Asymmetric public key data
*/

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Read all the answers

[PATCH 00/29] Crypto keys and module signing [ver #4]

Replies

Similar topics