From: David Howells Subject: [PATCH 10/16] KEYS: DSA key signature verification [ver #2] Date: Tue, 29 Nov 2011 23:45:04 +0000 Message-ID: <20111129234504.13625.82660.stgit@warthog.procyon.org.uk> References: <20111129234258.13625.21153.stgit@warthog.procyon.org.uk> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: linux-crypto@vger.kernel.org, linux-security-module@vger.kernel.org, linux-kernel@vger.kernel.org, dmitry.kasatkin@intel.com, zohar@linux.vnet.ibm.com, arjan.van.de.ven@intel.com, alan.cox@intel.com, David Howells To: keyrings@linux-nfs.org Return-path: In-Reply-To: <20111129234258.13625.21153.stgit@warthog.procyon.org.uk> Sender: linux-kernel-owner@vger.kernel.org List-Id: linux-crypto.vger.kernel.org Signature verification routines for DSA crypto key subtype. Signed-off-by: David Howells --- security/keys/Makefile | 2 security/keys/crypto_dsa.h | 11 + security/keys/crypto_dsa_verify.c | 384 +++++++++++++++++++++++++++++++++++++ 3 files changed, 396 insertions(+), 1 deletions(-) create mode 100644 security/keys/crypto_dsa_verify.c diff --git a/security/keys/Makefile b/security/keys/Makefile index 8f48527..bde336e 100644 --- a/security/keys/Makefile +++ b/security/keys/Makefile @@ -23,5 +23,5 @@ obj-$(CONFIG_PROC_FS) += proc.o obj-$(CONFIG_SYSCTL) += sysctl.o crypto_keys-y := crypto_type.o pgp_parse.o crypto_verify.o -crypto_dsa-y := crypto_dsa_subtype.o +crypto_dsa-y := crypto_dsa_subtype.o crypto_dsa_verify.o crypto_rsa-y := crypto_rsa_subtype.o diff --git a/security/keys/crypto_dsa.h b/security/keys/crypto_dsa.h index 0455634..8c7c6e9 100644 --- a/security/keys/crypto_dsa.h +++ b/security/keys/crypto_dsa.h @@ -34,3 +34,14 @@ struct DSA_payload { u8 key_id_size; /* Number of bytes in key_id */ struct DSA_public_key *public_key; }; + +/* + * crypto_dsa_verify.c + */ +extern struct crypto_key_verify_context *DSA_verify_sig_begin( + struct key *key, const u8 *sig, size_t siglen); +extern int DSA_verify_sig_add_data(struct crypto_key_verify_context *ctx, + const void *data, size_t datalen); +extern int DSA_verify_sig_end(struct crypto_key_verify_context *ctx, + const u8 *sig, size_t siglen); +extern void DSA_verify_sig_cancel(struct crypto_key_verify_context *ctx); diff --git a/security/keys/crypto_dsa_verify.c b/security/keys/crypto_dsa_verify.c new file mode 100644 index 0000000..c9dc180 --- /dev/null +++ b/security/keys/crypto_dsa_verify.c @@ -0,0 +1,384 @@ +/* DSA signature verification algorithm + * + * Copyright (C) 2011 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * + * 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 DEBUG +#define pr_fmt(fmt) "DSA: "fmt +#include +#include +#include +#include +#include +#include +#include +#include "internal.h" +#include "crypto_dsa.h" + +#define DSA_NSIG 2 /* number of MPI's in DSA signature */ + +struct DSA_signature { + struct crypto_key_verify_context base; + enum pgp_hash_algo hash_algo : 8; + u8 signed_hash_msw[2]; + union { + MPI mpi[2]; + struct { + MPI r; + MPI s; + }; + }; + struct shash_desc hash; /* This must go last! */ +}; + +struct DSA_sig_parse_context { + struct pgp_parse_context pgp; + struct pgp_sig_parameters params; +}; + +static int DSA_parse_signature(struct pgp_parse_context *context, + enum pgp_packet_tag type, + u8 headerlen, + const u8 *data, + size_t datalen) +{ + struct DSA_sig_parse_context *ctx = + container_of(context, struct DSA_sig_parse_context, pgp); + + return pgp_parse_sig_params(&data, &datalen, &ctx->params); +} + +/* + * Begin the process of verifying a DSA signature. + * + * This involves allocating the hash into which first the data and then the + * metadata will be put, and parsing the signature to check that it matches the + * key. + */ +struct crypto_key_verify_context *DSA_verify_sig_begin( + struct key *key, const u8 *sigdata, size_t siglen) +{ + struct DSA_sig_parse_context p; + struct DSA_signature *sig; + struct crypto_shash *tfm; + struct DSA_payload *dsa = key->payload.data; + int ret; + + kenter("{%d},,%zu", key_serial(key), siglen); + + if (!dsa->public_key) { + kleave(" = -ENOKEY [no public key]"); + return ERR_PTR(-ENOKEY); + } + + p.pgp.types_of_interest = (1 << PGP_PKT_SIGNATURE); + p.pgp.process_packet = DSA_parse_signature; + ret = pgp_parse_packets(sigdata, siglen, &p.pgp); + if (ret < 0) + return ERR_PTR(ret); + + if (p.params.pubkey_algo != PGP_PUBKEY_DSA) { + kleave(" = -ENOKEY [wrong pk algo]"); + return ERR_PTR(-ENOKEY); + } + + if (p.params.hash_algo >= PGP_HASH__LAST || + !pgp_hash_algorithms[p.params.hash_algo]) { + kleave(" = -ENOPKG [hash]"); + return ERR_PTR(-ENOPKG); + } + + pr_notice("Signature generated with %s hash\n", + pgp_hash_algorithms[p.params.hash_algo]); + + if (memcmp(&p.params.issuer, dsa->key_id, 8) != 0) { + kleave(" = -ENOKEY [wrong key ID]"); + return ERR_PTR(-ENOKEY); + } + + if (p.params.signature_type != PGP_SIG_BINARY_DOCUMENT_SIG && + p.params.signature_type != PGP_SIG_STANDALONE_SIG) { + /* We don't want to canonicalise */ + kleave(" = -EOPNOTSUPP [canon]"); + return ERR_PTR(-EOPNOTSUPP); + } + + /* Allocate the hashing algorithm we're going to need and find out how + * big the hash operational data will be. + */ + tfm = crypto_alloc_shash(pgp_hash_algorithms[p.params.hash_algo], 0, 0); + if (IS_ERR(tfm)) + return PTR_ERR(tfm) == -ENOENT ? + ERR_PTR(-ENOPKG) : ERR_CAST(tfm); + + /* We allocate the hash operational data storage on the end of our + * context data. + */ + sig = kzalloc(sizeof(*sig) + crypto_shash_descsize(tfm), GFP_KERNEL); + if (!sig) { + crypto_free_shash(tfm); + return ERR_PTR(-ENOMEM); + } + + sig->base.key = key; + sig->hash_algo = p.params.hash_algo; + sig->hash.tfm = tfm; + sig->hash.flags = CRYPTO_TFM_REQ_MAY_SLEEP; + + ret = crypto_shash_init(&sig->hash); + if (ret < 0) { + crypto_free_shash(sig->hash.tfm); + kfree(sig); + return ERR_PTR(ret); + } + + key_get(sig->base.key); + kleave(" = %p", sig); + return &sig->base; +} + +/* + * Load data into the hash + */ +int DSA_verify_sig_add_data(struct crypto_key_verify_context *ctx, + const void *data, size_t datalen) +{ + struct DSA_signature *sig = + container_of(ctx, struct DSA_signature, base); + + return crypto_shash_update(&sig->hash, data, datalen); +} + +/* + * Perform the actual mathematical DSA signature verification. + */ +static int DSA_verify(const MPI datahash, + const struct DSA_signature *sig, + const struct DSA_public_key *pub) +{ + MPI w = NULL, u1 = NULL, u2 = NULL, v = NULL; + MPI base[3]; + MPI exp[3]; + int rc; + + kenter(""); + + if (!(mpi_cmp_ui(sig->r, 0) > 0 && mpi_cmp(sig->r, pub->q) < 0)) { + pr_warning("Assertion failed [0 < r < q]\n"); + return -EKEYREJECTED; + } + + if (!(mpi_cmp_ui(sig->s, 0) > 0 && mpi_cmp(sig->s, pub->q) < 0)) { + pr_warning("Assertion failed [0 < s < q]\n"); + return -EKEYREJECTED; + } + + rc = -ENOMEM; + w = mpi_alloc(mpi_get_nlimbs(pub->q)); if (!w ) goto cleanup; + u1 = mpi_alloc(mpi_get_nlimbs(pub->q)); if (!u1) goto cleanup; + u2 = mpi_alloc(mpi_get_nlimbs(pub->q)); if (!u2) goto cleanup; + v = mpi_alloc(mpi_get_nlimbs(pub->p)); if (!v ) goto cleanup; + + /* w = s^(-1) mod q */ + if (mpi_invm(w, sig->s, pub->q) < 0) + goto cleanup; + + /* u1 = (datahash * w) mod q */ + if (mpi_mulm(u1, datahash, w, pub->q) < 0) + goto cleanup; + + /* u2 = r * w mod q */ + if (mpi_mulm(u2, sig->r, w, pub->q) < 0) + goto cleanup; + + /* v = g^u1 * y^u2 mod p mod q */ + base[0] = pub->g; exp[0] = u1; + base[1] = pub->y; exp[1] = u2; + base[2] = NULL; exp[2] = NULL; + + if (mpi_mulpowm(v, base, exp, pub->p) < 0) + goto cleanup; + + if (mpi_fdiv_r(v, v, pub->q) < 0) + goto cleanup; + + rc = (mpi_cmp(v, sig->r) == 0) ? 0 : -EKEYREJECTED; + +cleanup: + mpi_free(w); + mpi_free(u1); + mpi_free(u2); + mpi_free(v); + kleave(" = %d", rc); + return rc; +} + +struct DSA_sig_digest_context { + struct pgp_parse_context pgp; + struct DSA_signature *sig; +}; + +/* + * Extract required metadata from the signature packet and add what we need to + * to the hash. + */ +static int DSA_digest_signature(struct pgp_parse_context *context, + enum pgp_packet_tag type, + u8 headerlen, + const u8 *data, + size_t datalen) +{ + enum pgp_signature_version version; + struct DSA_sig_digest_context *ctx = + container_of(context, struct DSA_sig_digest_context, pgp); + int i; + + kenter(""); + + version = *data; + if (version == PGP_SIG_VERSION_3) { + /* We just include an excerpt of the metadata from a V3 + * signature. + */ + crypto_shash_update(&ctx->sig->hash, data + 1, 5); + data += sizeof(struct pgp_signature_v3_packet); + datalen -= sizeof(struct pgp_signature_v3_packet); + } else if (version == PGP_SIG_VERSION_4) { + /* We add the whole metadata header and some of the hashed data + * for a V4 signature, plus a trailer. + */ + size_t hashedsz, unhashedsz; + u8 trailer[6]; + + hashedsz = 4 + 2 + (data[4] << 8) + data[5]; + crypto_shash_update(&ctx->sig->hash, data, hashedsz); + + trailer[0] = version; + trailer[1] = 0xffU; + trailer[2] = hashedsz >> 24; + trailer[3] = hashedsz >> 16; + trailer[4] = hashedsz >> 8; + trailer[5] = hashedsz; + + crypto_shash_update(&ctx->sig->hash, trailer, 6); + data += hashedsz; + datalen -= hashedsz; + + unhashedsz = 2 + (data[0] << 8) + data[1]; + data += unhashedsz; + datalen -= unhashedsz; + } + + if (datalen <= 2) { + kleave(" = -EBADMSG"); + return -EBADMSG; + } + + /* There's a quick check on the hash available. */ + ctx->sig->signed_hash_msw[0] = *data++; + ctx->sig->signed_hash_msw[1] = *data++; + datalen -= 2; + + /* And then the cryptographic data, which we'll need for the + * algorithm. + */ + for (i = 0; i < DSA_NSIG; i++) { + unsigned int remaining = datalen; + ctx->sig->mpi[i] = mpi_read_from_buffer(data, &remaining); + if (!ctx->sig->mpi[i]) + return -ENOMEM; + data += remaining; + datalen -= remaining; + } + + if (datalen != 0) { + kleave(" = -EBADMSG [trailer %zu]", datalen); + return -EBADMSG; + } + + kleave(" = 0"); + return 0; +} + +/* + * The data is now all loaded into the hash; load the metadata, finalise the + * hash and perform the verification step. + */ +int DSA_verify_sig_end(struct crypto_key_verify_context *ctx, + const u8 *sigdata, size_t siglen) +{ + struct DSA_signature *sig = + container_of(ctx, struct DSA_signature, base); + struct DSA_payload *dsa = sig->base.key->payload.data; + struct DSA_sig_digest_context p; + void *digest = NULL; + MPI datahash = NULL; + size_t digest_size; + int ret; + + kenter(""); + + /* Firstly we add metadata, starting with some of the data from the + * signature packet */ + p.pgp.types_of_interest = (1 << PGP_PKT_SIGNATURE); + p.pgp.process_packet = DSA_digest_signature; + p.sig = sig; + ret = pgp_parse_packets(sigdata, siglen, &p.pgp); + if (ret < 0) + goto error_free_ctx; + + ret = -ENOMEM; + digest_size = crypto_shash_digestsize(sig->hash.tfm); + digest = kmalloc(digest_size, GFP_KERNEL); + if (!digest) + goto error_free_ctx; + + crypto_shash_final(&sig->hash, digest); + + ret = -ENOMEM; + datahash = mpi_alloc((digest_size + BYTES_PER_MPI_LIMB - 1) / + BYTES_PER_MPI_LIMB); + if (!datahash) + goto error_free_digest; + + ret = mpi_set_buffer(datahash, digest, digest_size, 0); + if (ret < 0) + goto error_free_mpi; + + ret = DSA_verify(datahash, sig, dsa->public_key); + +error_free_mpi: + mpi_free(datahash); +error_free_digest: + kfree(digest); +error_free_ctx: + DSA_verify_sig_cancel(ctx); + kleave(" = %d", ret); + return ret; +} + +/* + * Cancel an in-progress data loading + */ +void DSA_verify_sig_cancel(struct crypto_key_verify_context *_ctx) +{ + struct DSA_signature *sig = + container_of(_ctx, struct DSA_signature, base); + + kenter(""); + + /* !!! Do we need to tell the crypto layer to cancel too? */ + crypto_free_shash(sig->hash.tfm); + key_put(sig->base.key); + mpi_free(sig->r); + mpi_free(sig->s); + kfree(sig); + + kleave(""); +}