diff options
| -rw-r--r-- | GNUmakefile | 6 | ||||
| -rw-r--r-- | asn1.c | 206 | ||||
| -rw-r--r-- | asn1_internal.h | 91 | ||||
| -rw-r--r-- | ecdsa.c | 1105 | ||||
| -rw-r--r-- | ecdsa_curves.h | 92 | ||||
| -rw-r--r-- | hal.h | 62 |
6 files changed, 1561 insertions, 1 deletions
diff --git a/GNUmakefile b/GNUmakefile index 82ec7ec..6a777cc 100644 --- a/GNUmakefile +++ b/GNUmakefile @@ -28,7 +28,7 @@ INC = hal.h LIB = libhal.a OBJ = ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o \ - modexp.o rsa.o errorstrings.o + modexp.o rsa.o ecdsa.o asn1.o errorstrings.o IO_OBJ_EIM = hal_io_eim.o novena-eim.o IO_OBJ_I2C = hal_io_i2c.o @@ -49,6 +49,10 @@ ${OBJ}: ${INC} ${LIB}: ${OBJ} ar rcs $@ $^ +asn1.o rsa.o ecdsa.o: asn1_internal.h + +ecdsa.o: ecdsa_curves.h + test: all cd tests; ${MAKE} -k $@ @@ -0,0 +1,206 @@ +/* + * asn1.c + * ------ + * Minimal ASN.1 implementation in support of Cryptech libhal. + * + * The functions in this module are not intended to be part of the + * public API. Rather, these are utility functions used by more than + * one module within the library, which would otherwise have to be + * duplicated. The main reason for keeping these private is to avoid + * having the public API depend on any details of the underlying + * bignum implementation (currently libtfm, but that might change). + * + * As of this writing, the ASN.1 support we need is quite minimal, so, + * rather than attempting to clean all the unecessary cruft out of a + * general purpose ASN.1 implementation, we hand code the very small + * number of data types we need. At some point this will probably + * become impractical, at which point we might want to look into using + * something like the asn1c compiler. + * + * Authors: Rob Austein + * Copyright (c) 2015, SUNET + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <stddef.h> +#include <string.h> +#include <assert.h> + +#include "hal.h" + +#include "asn1_internal.h" + +/* + * Encode tag and length fields of an ASN.1 object. If der is NULL, + * just return the size that would be encoded. + */ + +hal_error_t hal_asn1_encode_header(const uint8_t tag, + const size_t value_len, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + size_t header_len = 2; /* Shortest encoding is one octet each for tag and length */ + + if (value_len >= 128) /* Add octets for longer length encoding as needed */ + for (size_t n = value_len; n > 0; n >>= 8) + ++header_len; + + if (der_len != NULL) + *der_len = header_len; + + if (der == NULL) /* If caller just wanted the length, we're done */ + return HAL_OK; + + /* + * Make sure there's enough room for header + value, then encode. + */ + + if (value_len + header_len > der_max) + return HAL_ERROR_RESULT_TOO_LONG; + + if (value_len < 128) { + *der = (uint8_t) value_len; + } + + else { + *der = 0x80 | (uint8_t) (header_len -= 2); + for (size_t n = value_len; n > 0 && header_len > 0; n >>= 8) + der[header_len--] = (uint8_t) (n & 0xFF); + } + + return HAL_OK; +} + +/* + * Encode an unsigned ASN.1 INTEGER from a libtfm bignum. If der is + * NULL, just return the length of what we would have encoded. + */ + +hal_error_t hal_asn1_encode_integer(fp_int *bn, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + if (bn == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + /* + * We only handle unsigned INTEGERs, so we need to pad data with a + * leading zero if the most significant bit is set, to avoid + * flipping the ASN.1 sign bit. Conveniently, this also handles the + * difference between libtfm's and ASN.1's encoding of zero. + */ + + if (fp_cmp_d(bn, 0) == FP_LT) + return HAL_ERROR_BAD_ARGUMENTS; + + const int leading_zero = fp_iszero(bn) || (fp_count_bits(bn) & 7) == 0; + const size_t vlen = fp_unsigned_bin_size(bn) + leading_zero; + hal_error_t err; + size_t hlen; + + if ((err = hal_asn1_encode_header(ASN1_INTEGER, vlen, der, &hlen, der_max)) != HAL_OK) + return err; + + if (der_len != NULL) + *der_len = hlen + vlen; + + if (der == NULL) + return HAL_OK; + + if (hlen + vlen > der_max) + return HAL_ERROR_RESULT_TOO_LONG; + + der += hlen; + if (leading_zero) + *der++ = 0x00; + fp_to_unsigned_bin(bn, der); + + return HAL_OK; +} + + +hal_error_t hal_asn1_decode_header(const uint8_t tag, + const uint8_t * const der, size_t der_max, + size_t *hlen, size_t *vlen) +{ + assert(der != NULL && hlen != NULL && vlen != NULL); + + if (der_max < 2 || der[0] != tag) + return HAL_ERROR_ASN1_PARSE_FAILED; + + if ((der[1] & 0x80) == 0) { + *hlen = 2; + *vlen = der[1]; + } + + else { + *hlen = 2 + (der[1] & 0x7F); + *vlen = 0; + + if (*hlen > der_max) + return HAL_ERROR_ASN1_PARSE_FAILED; + + for (size_t i = 2; i < *hlen; i++) + *vlen = (*vlen << 8) + der[i]; + } + + if (*hlen + *vlen > der_max) + return HAL_ERROR_ASN1_PARSE_FAILED; + + return HAL_OK; +} + +hal_error_t hal_asn1_decode_integer(fp_int *bn, + const uint8_t * const der, size_t *der_len, const size_t der_max) +{ + if (bn == NULL || der == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + hal_error_t err; + size_t hlen, vlen; + + if ((err = hal_asn1_decode_header(ASN1_INTEGER, der, der_max, &hlen, &vlen)) != HAL_OK) + return err; + + if (der_len != NULL) + *der_len = hlen + vlen; + + if (vlen < 1 || (der[hlen] & 0x80) != 0x00) + return HAL_ERROR_ASN1_PARSE_FAILED; + + fp_init(bn); + fp_read_unsigned_bin(bn, (uint8_t *) der + hlen, vlen); + return HAL_OK; +} + +/* + * Local variables: + * indent-tabs-mode: nil + * End: + */ diff --git a/asn1_internal.h b/asn1_internal.h new file mode 100644 index 0000000..9d5ab4d --- /dev/null +++ b/asn1_internal.h @@ -0,0 +1,91 @@ +/* + * asn1.h + * ------ + * Library internal header file for ASN.1 routines. + * + * These functions are not part of the public libhal API. + * + * More than 20 years after it was written, the best simple + * introduction to ASN.1 is still Burt Kalski's "A Layman's Guide to a + * Subset of ASN.1, BER, and DER". Ask your nearest search engine. + * + * Authors: Rob Austein + * Copyright (c) 2015, SUNET + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _HAL_ASN1_H_ +#define _HAL_ASN1_H_ + +#include <stdint.h> +#include <stdlib.h> + +#include <tfm.h> + +#define ASN1_UNIVERSAL 0x00 +#define ASN1_APPLICATION 0x40 +#define ASN1_CONTEXT_SPECIFIC 0x80 +#define ASN1_PRIVATE 0xC0 + +#define ASN1_PRIMITIVE 0x00 +#define ASN1_CONSTRUCTED 0x20 + +#define ASN1_TAG_MASK 0x1F + +#define ASN1_INTEGER (ASN1_PRIMITIVE | 0x02) +#define ASN1_BIT_STRING (ASN1_PRIMITIVE | 0x03) +#define ASN1_OCTET_STRING (ASN1_PRIMITIVE | 0x04) +#define ASN1_NULL (ASN1_PRIMITIVE | 0x05) +#define ASN1_OBJECT_IDENTIFIER (ASN1_PRIMITIVE | 0x06) +#define ASN1_SEQUENCE (ASN1_CONSTRUCTED | 0x10) +#define ASN1_SET (ASN1_CONSTRUCTED | 0x11) + +#define ASN1_EXPLICIT_CONTEXT (ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED) +#define ASN1_EXPLICIT_0 (ASN1_EXPLICIT_CONTEXT + 0) +#define ASN1_EXPLICIT_1 (ASN1_EXPLICIT_CONTEXT + 1) + +extern hal_error_t hal_asn1_encode_header(const uint8_t tag, + const size_t value_len, + uint8_t *der, size_t *der_len, const size_t der_max); + +extern hal_error_t hal_asn1_decode_header(const uint8_t tag, + const uint8_t * const der, size_t der_max, + size_t *hlen, size_t *vlen); + +extern hal_error_t hal_asn1_encode_integer(fp_int *bn, + uint8_t *der, size_t *der_len, const size_t der_max); + +extern hal_error_t hal_asn1_decode_integer(fp_int *bn, + const uint8_t * const der, size_t *der_len, const size_t der_max); + +#endif /* _HAL_ASN1_H_ */ + +/* + * Local variables: + * indent-tabs-mode: nil + * End: + */ @@ -0,0 +1,1105 @@ +/* + * ecdsa.c + * ------- + * Basic ECDSA functions. + * + * At some point we may want to refactor this to separate + * functionality that appiles to all elliptic curve cryptography from + * functions specific to ECDSA over the NIST Suite B prime curves, but + * it's simplest to keep this all in one place initially. + * + * Much of the code in this module is based, at least loosely, on Tom + * St Denis's libtomcrypt code. + * + * Authors: Rob Austein + * Copyright (c) 2015, SUNET + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * We use "Tom's Fast Math" library for our bignum implementation. + * This particular implementation has a couple of nice features: + * + * - The code is relatively readable, thus reviewable. + * + * - The bignum representation doesn't use dynamic memory, which + * simplifies things for us. + * + * The price tag for not using dynamic memory is that libtfm has to be + * configured to know about the largest bignum one wants it to be able + * to support at compile time. This should not be a serious problem. + * + * We use a lot of one-element arrays (fp_int[1] instead of plain + * fp_int) to avoid having to prefix every use of an fp_int with "&". + * + * Unfortunately, libtfm is bad about const-ification, but we want to + * hide that from our users, so our public API uses const as + * appropriate and we use inline functions to remove const constraints + * in a relatively type-safe manner before calling libtom. + */ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <stddef.h> +#include <string.h> +#include <assert.h> + +#include "hal.h" +#include <tfm.h> +#include "asn1_internal.h" + +/* + * Whether we want debug output. + */ + +static int debug = 0; + +void hal_ecdsa_set_debug(const int onoff) +{ + debug = onoff; +} + +/* + * ECDSA curve descriptor. We only deal with named curves; at the + * moment, we only deal with NIST prime curves where the elliptic + * curve's "a" parameter is always -3 and its "h" value (order of + * elliptic curve group divided by order of base point) is always 1. + * + * Since the Montgomery parameters we need for the point arithmetic + * depend only on the underlying field prime, we precompute them when + * we load the curve and store them in the field descriptor, even + * though they aren't really curve parameters per se. + * + * For similar reasons, we also include the ASN.1 OBJECT IDENTIFIERs + * used to name these curves. + */ + +typedef struct { + fp_int q[1]; /* Modulus of underlying prime field */ + fp_int b[1]; /* Curve's "b" parameter */ + fp_int Gx[1]; /* x component of base point G */ + fp_int Gy[1]; /* y component of base point G */ + fp_int n[1]; /* Order of base point G */ + fp_int mu[1]; /* Montgomery normalization factor */ + fp_digit rho; /* Montgomery reduction value */ + const uint8_t *oid; /* OBJECT IDENTIFIER */ + size_t oid_len; /* Length of OBJECT IDENTIFIER */ +} ecdsa_curve_t; + +/* + * ECDSA key implementation. This structure type is private to this + * module, anything else that needs to touch one of these just gets a + * typed opaque pointer. We do, however, export the size, so that we + * can make memory allocation the caller's problem. + * + * EC points are stored in Jacobian format such that (x, y, z) => + * (x/z**2, y/z**3, 1) when interpretted as affine coordinates. + */ + +typedef struct { + fp_int x[1], y[1], z[1]; +} ec_point_t; + +struct hal_ecdsa_key { + hal_ecdsa_key_type_t type; /* Public or private is */ + hal_ecdsa_curve_t curve; /* Curve descriptor */ + ec_point_t Q[1]; /* Public key */ + fp_int d[1]; /* Private key */ +}; + +const size_t hal_ecdsa_key_t_size = sizeof(struct hal_ecdsa_key); + +/* + * Error handling. + */ + +#define lose(_code_) do { err = _code_; goto fail; } while (0) + +/* + * Functions to strip const qualifiers from arguments to libtfm calls + * in a relatively type-safe manner. + */ + +static inline fp_int *unconst_fp_int(const fp_int * const arg) +{ + return (fp_int *) arg; +} + +static inline uint8_t *unconst_uint8_t(const uint8_t * const arg) +{ + return (uint8_t *) arg; +} + +/* + * We can't (usefully) initialize fp_int variables at compile time, so + * instead we load all the curve parameters the first time anything + * asks for any of them. + */ + +static const ecdsa_curve_t * const get_curve(const hal_ecdsa_curve_t curve) +{ + static ecdsa_curve_t curve_p256, curve_p384, curve_p521; + static int initialized = 0; + + if (!initialized) { + +#include "ecdsa_curves.h" + + fp_read_unsigned_bin(curve_p256.q, unconst_uint8_t(p256_q), sizeof(p256_q)); + fp_read_unsigned_bin(curve_p256.b, unconst_uint8_t(p256_b), sizeof(p256_b)); + fp_read_unsigned_bin(curve_p256.Gx, unconst_uint8_t(p256_Gx), sizeof(p256_Gx)); + fp_read_unsigned_bin(curve_p256.Gy, unconst_uint8_t(p256_Gy), sizeof(p256_Gy)); + fp_read_unsigned_bin(curve_p256.n, unconst_uint8_t(p256_n), sizeof(p256_n)); + if (fp_montgomery_setup(curve_p256.q, &curve_p256.rho) != FP_OKAY) + return NULL; + fp_zero(curve_p256.mu); + fp_montgomery_calc_normalization(curve_p256.mu, curve_p256.q); + curve_p256.oid = p256_oid; + curve_p256.oid_len = sizeof(p256_oid); + + fp_read_unsigned_bin(curve_p384.q, unconst_uint8_t(p384_q), sizeof(p384_q)); + fp_read_unsigned_bin(curve_p384.b, unconst_uint8_t(p384_b), sizeof(p384_b)); + fp_read_unsigned_bin(curve_p384.Gx, unconst_uint8_t(p384_Gx), sizeof(p384_Gx)); + fp_read_unsigned_bin(curve_p384.Gy, unconst_uint8_t(p384_Gy), sizeof(p384_Gy)); + fp_read_unsigned_bin(curve_p384.n, unconst_uint8_t(p384_n), sizeof(p384_n)); + if (fp_montgomery_setup(curve_p384.q, &curve_p384.rho) != FP_OKAY) + return NULL; + fp_zero(curve_p384.mu); + fp_montgomery_calc_normalization(curve_p384.mu, curve_p384.q); + curve_p384.oid = p384_oid; + curve_p384.oid_len = sizeof(p384_oid); + + fp_read_unsigned_bin(curve_p521.q, unconst_uint8_t(p521_q), sizeof(p521_q)); + fp_read_unsigned_bin(curve_p521.b, unconst_uint8_t(p521_b), sizeof(p521_b)); + fp_read_unsigned_bin(curve_p521.Gx, unconst_uint8_t(p521_Gx), sizeof(p521_Gx)); + fp_read_unsigned_bin(curve_p521.Gy, unconst_uint8_t(p521_Gy), sizeof(p521_Gy)); + fp_read_unsigned_bin(curve_p521.n, unconst_uint8_t(p521_n), sizeof(p521_n)); + if (fp_montgomery_setup(curve_p521.q, &curve_p521.rho) != FP_OKAY) + return NULL; + fp_zero(curve_p521.mu); + fp_montgomery_calc_normalization(curve_p521.mu, curve_p521.q); + curve_p521.oid = p521_oid; + curve_p521.oid_len = sizeof(p521_oid); + + initialized = 1; + } + + switch (curve) { + case HAL_ECDSA_CURVE_P256: return &curve_p256; + case HAL_ECDSA_CURVE_P384: return &curve_p384; + case HAL_ECDSA_CURVE_P521: return &curve_p521; + default: return NULL; + } +} + +/* + * Test whether two points are equal: x and z coordinates identical, y + * coordinates either identical or negated. + */ + +static inline int point_equal(const ec_point_t * const P, + const ec_point_t * const Q, + const ecdsa_curve_t * const curve) +{ + assert(P != NULL && Q != NULL && curve != NULL); + + if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) != FP_EQ || + fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) != FP_EQ) + return 0; + + if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ) + return 1; + + fp_int Qy_neg[1]; + + fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg); + + const int result = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ; + + fp_zero(Qy_neg); + + return result; +} + +/* + * Finite field operations (hence "ff_"). These are basically just + * the usual bignum operations, constrained by the field modulus. + * + * All of these are operations in the field underlying the specified + * curve, and assume that operands are already in Montgomery form. + * + * Several of these are written a bit oddly, in an attempt to make + * them run in constant time. Be warned that an optimizing compiler + * may be clever enough to defeat this. In the long run, the real + * solution is probably to perform these field operations in Verilog. + */ + +static inline void ff_add(const ecdsa_curve_t * const curve, + const fp_int * const a, + const fp_int * const b, + fp_int *c) +{ + fp_int t[2][1]; + memset(t, 0, sizeof(t)); + fp_add(unconst_fp_int(a), unconst_fp_int(b), t[0]); + fp_sub(t[0], unconst_fp_int(curve->q), t[1]); + fp_copy(t[fp_cmp(t[0], unconst_fp_int(curve->q)) != FP_LT], c); + memset(t, 0, sizeof(t)); +} + +static inline void ff_sub(const ecdsa_curve_t * const curve, + const fp_int * const a, + const fp_int * const b, + fp_int *c) +{ + fp_int t[2][1]; + memset(t, 0, sizeof(t)); + fp_sub(unconst_fp_int(a), unconst_fp_int(b), t[0]); + fp_add(t[0], unconst_fp_int(curve->q), t[1]); + fp_copy(t[fp_cmp_d(c, 0) == FP_LT], c); + memset(t, 0, sizeof(t)); +} + +static inline void ff_div2(const ecdsa_curve_t * const curve, + const fp_int * const a, + fp_int *b) +{ + fp_int t[2][1]; + memset(t, 0, sizeof(t)); + fp_copy(unconst_fp_int(a), t[0]); + fp_add(t[0], unconst_fp_int(curve->q), t[1]); + fp_div_2(t[fp_isodd(unconst_fp_int(a))], b); + memset(t, 0, sizeof(t)); +} + +static inline void ff_mul(const ecdsa_curve_t * const curve, + const fp_int * const a, + const fp_int * const b, + fp_int *c) +{ + fp_mul(unconst_fp_int(a), unconst_fp_int(b), c); + fp_montgomery_reduce(c, unconst_fp_int(curve->q), curve->rho); +} + +static inline void ff_sqr(const ecdsa_curve_t * const curve, + const fp_int * const a, + fp_int *b) +{ + fp_sqr(unconst_fp_int(a), b); + fp_montgomery_reduce(b, unconst_fp_int(curve->q), curve->rho); +} + +#warning Change point arithmetic algorithms? +/* + * The point doubling and addition algorithms we use here are from + * libtomcrypt. The formula database at hyperelliptic.org lists + * faster algorithms satisfying the same preconditions, perhaps we + * should use those instead? + * + * Labels in the following refer to entries on the page: + * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html + * + * The libtomcrypt doubling algorithm looks like a trivial variation + * on dbl-2004-hmv. We might want to use dbl-2001-b instead. + * + * The libtomcrypt addition algorithm doesn't match up exactly with + * any listed algorithm, but I suspect it's a variation on + * add-1998-cmo-2. We might want to use add-2007-bl instead. + * + * There are faster algorithms listed, but all of them appear to + * require whacking one or both points back into affine + * representation, which has its own costs, so, at least for now, it'd + * probably be best to stick with algorithms that don't require this. + */ + +/** + * Double an EC point. + * @param P The point to double + * @param R [out] The destination of the double + * @param curve The curve parameters structure + * + * Algorithm is a minor variation on algorithm 3.21 from Guide to + * Elliptic Curve Cryptography. + */ + +static inline void point_double(const ec_point_t * const P, + ec_point_t *R, + const ecdsa_curve_t * const curve) +{ + assert(P != NULL && R != NULL && curve != NULL); + + fp_int t1[1]; fp_init(t1); + fp_int t2[1]; fp_init(t2); + + if (P != R) + *R = *P; + + ff_sqr (curve, R->z, t1); /* t1 = Pz ** 2 */ + ff_sub (curve, R->x, t1, t2); /* t2 = Px - Pz ** 2 */ + ff_add (curve, R->x, t1, t1); /* t1 = Px + Pz ** 2 */ + ff_mul (curve, t1, t2, t2); /* t2 = 1 * (Px - Pz ** 2) * (Px + Pz ** 2) */ + ff_add (curve, t2, t2, t1); /* t1 = 2 * (Px - Pz ** 2) * (Px + Pz ** 2) */ + ff_add (curve, t1, t2, t1); /* t1 = 3 * (Px - Pz ** 2) * (Px + Pz ** 2) = A */ + + ff_add (curve, R->y, R->y, R->y); /* Ry = 2 * Py = B */ + ff_mul (curve, R->z, R->y, R->z); /* Rz = B * Pz */ + + ff_sqr (curve, R->y, R->y); /* Ry = B ** 2 = C */ + ff_sqr (curve, R->y, t2); /* t2 = C ** 2 */ + ff_div2 (curve, t2, t2); /* t2 = C ** 2 / 2 */ + ff_mul (curve, R->y, R->x, R->y); /* Ry = C * Px = D */ + + ff_sqr (curve, t1, R->x); /* Rx = A ** 2 */ + ff_sub (curve, R->x, R->y, R->x); /* Rx = A ** 2 - D */ + ff_sub (curve, R->x, R->y, R->x); /* Rx = A ** 2 - 2 * D */ + + ff_sub (curve, R->y, R->x, R->y); /* Ry = D - Rx */ + ff_mul (curve, R->y, t1, R->y); /* Ry = (D - Rx) * A */ + ff_sub (curve, R->y, t2, R->y); /* Ry = (D - Rx) * A - C ** 2 / 2 */ + + fp_zero(t1); fp_zero(t2); +} + +/** + * Add two EC points + * @param P The point to add + * @param Q The point to add + * @param R [out] The destination of the double + * @param curve The curve parameters structure +*/ + +static inline void point_add(const ec_point_t * const P, + const ec_point_t * const Q, + ec_point_t *R, + const ecdsa_curve_t * const curve) +{ + assert(P != NULL && Q != NULL && R != NULL && curve != NULL); + + if (point_equal(P, Q, curve)) + return point_double(P, R, curve); + + fp_int t1[1]; fp_init(t1); + fp_int t2[1]; fp_init(t2); + + if (P != R) + *R = *P; + + /* + * Operations marked {@} are no-ops when Q.z == 1, but probably + * don't save us enough in the long run for optimizing them out to + * be worth even a low-probability risk of a timing channel attack. + */ + + ff_sqr (curve, Q->z, t1); /* t1 = z' ** 2 {@} */ + ff_mul (curve, t1, R->x, R->x); /* x = x * z' ** 2 {@} */ + ff_mul (curve, Q->z, t1, t1); /* t1 = z' ** 3 {@} */ + ff_mul (curve, t1, R->y, R->y); /* y = y * z' ** 3 {@} */ + + ff_sqr (curve, R->z, t1); /* t1 = z * z */ + ff_mul (curve, Q->x, t1, t2); /* t2 = x' * t1 */ + ff_mul (curve, R->z, t1, t1); /* t1 = z * t1 */ + ff_mul (curve, Q->y, t1, t1); /* t1 = y' * t1 */ + + ff_sub (curve, R->y, t1, R->y); /* y = y - t1 */ + ff_add (curve, t1, t1, t1); /* t1 = 2 * t1 */ + ff_add (curve, t1, R->y, t1); /* t1 = y + t1 */ + ff_sub (curve, R->x, t2, R->x); /* x = x - t2 */ + ff_add (curve, t2, t2, t2); /* t2 = 2 * t2 */ + ff_add (curve, t2, R->x, t2); /* t2 = x + t2 */ + + ff_mul (curve, R->z, Q->z, R->z); /* z = z * z' {@} */ + + ff_mul (curve, R->z, R->x, R->z); /* z = z * x */ + + ff_mul (curve, t1, R->x, t1); /* t1 = t1 * x */ + ff_sqr (curve, R->x, R->x); /* x = x * x */ + ff_mul (curve, t2, R->x, t2); /* t2 = t2 * x */ + ff_mul (curve, t1, R->x, t1); /* t1 = t1 * x */ + + ff_sqr (curve, R->y, R->x); /* x = y * y */ + ff_sub (curve, R->x, t2, R->x); /* x = x - t2 */ + + ff_sub (curve, t2, R->x, t2); /* t2 = t2 - x */ + ff_sub (curve, t2, R->x, t2); /* t2 = t2 - x */ + ff_mul (curve, t2, R->y, t2); /* t2 = t2 * y */ + ff_sub (curve, t2, t1, R->y); /* y = t2 - t1 */ + ff_div2 (curve, R->y, R->y); /* y = y / 2 */ + + fp_zero(t1); fp_zero(t2); +} + +/** + * Map a projective jacbobian point back to affine space + * @param P [in/out] The point to map + * @param curve The curve parameters structure + */ + +static inline hal_error_t point_to_affine(ec_point_t *P, + const ecdsa_curve_t * const curve) +{ + assert(P != NULL && curve != NULL); + + hal_error_t err = HAL_ERROR_IMPOSSIBLE; + + fp_int t1[1]; fp_init(t1); + fp_int t2[1]; fp_init(t2); + + fp_int * const q = unconst_fp_int(curve->q); + + fp_montgomery_reduce(P->z, q, curve->rho); + + if (fp_invmod (P->z, q, t1) != FP_OKAY || /* t1 = 1 / z */ + fp_sqrmod (t1, q, t2) != FP_OKAY || /* t2 = 1 / z**2 */ + fp_mulmod (t1, t2, q, t1) != FP_OKAY) /* t1 = 1 / z**3 */ + goto fail; + + fp_mul (P->x, t2, P->x); /* x = x / z**2 */ + fp_mul (P->y, t1, P->y); /* y = y / z**3 */ + fp_set (P->z, 1); /* z = 1 */ + + fp_montgomery_reduce(P->x, q, curve->rho); + fp_montgomery_reduce(P->y, q, curve->rho); + + err = HAL_OK; + + fail: + fp_zero(t1); + fp_zero(t2); + return err; +} + +/** + * Perform a point multiplication. + * @param k The scalar to multiply by + * @param P The base point + * @param R [out] Destination for kP + * @param curve Curve parameters + * @param map Boolean whether to map back to affine (1: map, 0: leave projective) + * @return HAL_OK on success + * + * This implementation uses the "Montgomery Ladder" approach, which is + * relatively robust against timing channel attacks if nothing else + * goes wrong, but many other things can indeed go wrong. + */ + +static hal_error_t point_scalar_multiply(const fp_int * const k, + const ec_point_t * const P, + ec_point_t *R, + const ecdsa_curve_t * const curve, + const int map) +{ + assert(k != NULL && P != NULL && R != NULL && curve != NULL); + + if (fp_iszero(k)) + return HAL_ERROR_BAD_ARGUMENTS; + + /* + * Convert to Montgomery form and initialize table. Initial values: + * + * M[0] = 1P + * M[1] = 2P + * M[2] = don't care, only used for timing-attack resistance + */ + + ec_point_t M[3][1]; + memset(M, 0, sizeof(M)); + + if (fp_mulmod(unconst_fp_int(P->x), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->x) != FP_OKAY || + fp_mulmod(unconst_fp_int(P->y), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->y) != FP_OKAY || + fp_mulmod(unconst_fp_int(P->z), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->z) != FP_OKAY) { + memset(M, 0, sizeof(M)); + return HAL_ERROR_IMPOSSIBLE; + } + + point_double(M[0], M[1], curve); + + /* + * Walk down bits of the scalar, performing dummy operations to mask + * timing while hunting for the most significant bit. + */ + + int dummy_mode = 1; + + for (int digit_index = k->used - 1; digit_index >= 0; digit_index--) { + + fp_digit digit = k->dp[digit_index]; + + for (int bits_left = DIGIT_BIT; bits_left > 0; bits_left--) { + + const int bit = (digit >> (DIGIT_BIT - 1)) & 1; + digit <<= 1; + + if (dummy_mode) { + point_add (M[0], M[1], M[2], curve); + point_double (M[1], M[2], curve); + dummy_mode = !bit; /* Dummy until we find MSB */ + } + + else { + point_add (M[0], M[1], M[bit^1], curve); + point_double (M[bit], M[bit], curve); + } + } + } + + /* + * Copy result out, map back to affine if requested, then done. + */ + + *R = *M[0]; + hal_error_t err = map ? point_to_affine(R, curve) : HAL_OK; + memset(M, 0, sizeof(M)); + return err; +} + +/* + * Pick a random point on the curve, return random scalar and + * resulting point. + */ + +static hal_error_t point_pick_random(const ecdsa_curve_t * const curve, + fp_int *k, + ec_point_t *P) +{ + hal_error_t err; + + assert(curve != NULL && k != NULL && P != NULL); + + /* + * Pick a random scalar corresponding to a point on the curve. Per + * the NSA (gulp) Suite B guidelines, we ask the CSPRNG for 64 more + * bits than we need, which should be enough to mask any bias + * induced by the modular reduction. + * + * We're picking a point out of the subgroup generated by the base + * point on the elliptic curve, so the modulus for this calculation + * is order of the base point. + * + * Zero is an excluded value, but the chance of a non-broken CSPRNG + * returning zero is so low that it would almost certainly indicate + * an undiagnosed bug in the CSPRNG. + */ + uint8_t k_buf[fp_unsigned_bin_size(unconst_fp_int(curve->n)) + 8]; + + do { + if ((err = hal_get_random(k_buf, sizeof(k_buf))) != HAL_OK) + return err; + fp_read_unsigned_bin(k, k_buf, sizeof(k_buf)); + if (fp_iszero(k) || fp_mod(k, unconst_fp_int(curve->n), k) != FP_OKAY) + return HAL_ERROR_IMPOSSIBLE; + } while (fp_iszero(k)); + + memset(k_buf, 0, sizeof(k_buf)); + + /* + * Calculate P = kG and return. + */ + + fp_copy(curve->Gx, P->x); + fp_copy(curve->Gy, P->y); + fp_set(P->z, 1); + + return point_scalar_multiply(k, P, P, curve, 1); +} + +/* + * Test whether a point really is on a particular curve (sometimes + * called "validation when applied to a public key"). + */ + +static int point_is_on_curve(const ec_point_t * const P, + const ecdsa_curve_t * const curve) +{ + assert(P != NULL && curve != NULL); + + fp_int t1[1]; fp_init(t1); + fp_int t2[1]; fp_init(t2); + + /* + * Compute y**2 - x**3 + 3*x. + */ + + fp_sqr(unconst_fp_int(P->y), t1); /* t1 = y**2 */ + fp_sqr(unconst_fp_int(P->x), t2); /* t2 = x**2 */ + if (fp_mod(t2, unconst_fp_int(curve->q), t2) != FP_OKAY) + return 0; + fp_mul(unconst_fp_int(P->x), t2, t2); /* t2 = x**3 */ + fp_sub(t1, t2, t1); /* t1 = y**2 - x**3 */ + fp_add(t1, unconst_fp_int(P->x), t1); /* t1 = y**2 - x**3 + 1*x */ + fp_add(t1, unconst_fp_int(P->x), t1); /* t1 = y**2 - x**3 + 2*x */ + fp_add(t1, unconst_fp_int(P->x), t1); /* t1 = y**2 - x**3 + 3*x */ + + /* + * Normalize and test whether computed value matches b. + */ + + if (fp_mod(t1, unconst_fp_int(curve->q), t1) != FP_OKAY) + return 0; + while (fp_cmp_d(t1, 0) == FP_LT) + fp_add(t1, unconst_fp_int(curve->q), t1); + while (fp_cmp(t1, unconst_fp_int(curve->q)) != FP_LT) + fp_sub(t1, unconst_fp_int(curve->q), t1); + + return fp_cmp(t1, unconst_fp_int(curve->b)) == FP_EQ; +} + +/* + * Generate a new ECDSA key. + */ + +hal_error_t hal_ecdsa_key_gen(hal_ecdsa_key_t **key_, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve_) +{ + const ecdsa_curve_t * const curve = get_curve(curve_); + hal_ecdsa_key_t *key = keybuf; + hal_error_t err; + + if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key) || curve == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + memset(keybuf, 0, keybuf_len); + + key->type = HAL_ECDSA_PRIVATE; + key->curve = curve_; + + if ((err = point_pick_random(curve, key->d, key->Q)) != HAL_OK) + return err; + + assert(point_is_on_curve(key->Q, curve)); + + *key_ = key; + return HAL_OK; +} + +/* + * Extract key type (public or private). + */ + +hal_error_t hal_ecdsa_key_get_type(const hal_ecdsa_key_t * const key, + hal_ecdsa_key_type_t *key_type) +{ + if (key == NULL || key_type == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + *key_type = key->type; + return HAL_OK; +} + +/* + * Extract name of curve underlying a key. + */ + +hal_error_t hal_ecdsa_key_get_curve(const hal_ecdsa_key_t * const key, + hal_ecdsa_curve_t *curve) +{ + if (key == NULL || curve == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + *curve = key->curve; + return HAL_OK; +} + +/* + * Extract public key components. + */ + +hal_error_t hal_ecdsa_key_get_public(const hal_ecdsa_key_t * const key, + uint8_t *x, size_t *x_len, const size_t x_max, + uint8_t *y, size_t *y_len, const size_t y_max) +{ + if (key == NULL || (x_len == NULL && x != NULL) || (y_len == NULL && y != NULL)) + return HAL_ERROR_BAD_ARGUMENTS; + + if (x_len != NULL) + *x_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->x)); + + if (y_len != NULL) + *y_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->y)); + + if ((x != NULL && *x_len > x_max) || + (y != NULL && *y_len > y_max)) + return HAL_ERROR_RESULT_TOO_LONG; + + if (x != NULL) + fp_to_unsigned_bin(unconst_fp_int(key->Q->x), x); + + if (y != NULL) + fp_to_unsigned_bin(unconst_fp_int(key->Q->y), y); + + return HAL_OK; +} + +/* + * Clear a key. + */ + +void hal_ecdsa_key_clear(hal_ecdsa_key_t *key) +{ + if (key != NULL) + memset(key, 0, sizeof(*key)); +} + +/* + * Load a public key from components, and validate that the public key + * really is on the named curve. + */ + +hal_error_t hal_ecdsa_key_load_public(hal_ecdsa_key_t **key_, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve_, + const uint8_t * const x, const size_t x_len, + const uint8_t * const y, const size_t y_len) +{ + const ecdsa_curve_t * const curve = get_curve(curve_); + hal_ecdsa_key_t *key = keybuf; + + if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key) || curve == NULL || x == NULL || y == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + memset(keybuf, 0, keybuf_len); + + key->type = HAL_ECDSA_PUBLIC; + key->curve = curve_; + + fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(x), x_len); + fp_read_unsigned_bin(key->Q->y, unconst_uint8_t(y), y_len); + fp_set(key->Q->z, 1); + + if (!point_is_on_curve(key->Q, curve)) + return HAL_ERROR_KEY_NOT_ON_CURVE; + + *key_ = key; + + return HAL_OK; +} + +/* + * Load a private key from components. + * + * For extra paranoia, we could check Q == dG. + */ + +hal_error_t hal_ecdsa_key_load_private(hal_ecdsa_key_t **key_, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve_, + const uint8_t * const x, const size_t x_len, + const uint8_t * const y, const size_t y_len, + const uint8_t * const d, const size_t d_len) +{ + hal_ecdsa_key_t *key = keybuf; + hal_error_t err; + + if (d == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + if ((err = hal_ecdsa_key_load_public(key_, keybuf, keybuf_len, curve_, x, x_len, y, y_len)) != HAL_OK) + return err; + + key->type = HAL_ECDSA_PRIVATE; + fp_read_unsigned_bin(key->d, unconst_uint8_t(d), d_len); + return HAL_OK; +} + +/* + * Write private key in RFC 5915 ASN.1 DER format. + */ + +hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + if (key == NULL || key->type != HAL_ECDSA_PRIVATE) + return HAL_ERROR_BAD_ARGUMENTS; + + const ecdsa_curve_t * const curve = get_curve(key->curve); + if (curve == NULL) + return HAL_ERROR_IMPOSSIBLE; + + const size_t q_len = fp_unsigned_bin_size(unconst_fp_int(curve->q)); + const size_t d_len = fp_unsigned_bin_size(unconst_fp_int(key->d)); + const size_t Qx_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->x)); + const size_t Qy_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->y)); + assert(q_len >= d_len && q_len >= Qx_len && q_len >= Qy_len); + + fp_int version[1]; + fp_set(version, 1); + + hal_error_t err; + + size_t version_len, hlen, hlen2, hlen3, hlen4; + + if ((err = hal_asn1_encode_integer(version, NULL, &version_len, 0)) != HAL_OK || + (err = hal_asn1_encode_header(ASN1_OCTET_STRING, q_len, NULL, &hlen2, 0)) != HAL_OK || + (err = hal_asn1_encode_header(ASN1_EXPLICIT_0, curve->oid_len, NULL, &hlen3, 0)) != HAL_OK || + (err = hal_asn1_encode_header(ASN1_EXPLICIT_1, (q_len + 1) * 2, NULL, &hlen4, 0)) != HAL_OK) + return err; + + const size_t vlen = (version_len + + hlen2 + q_len + + hlen3 + curve->oid_len + + hlen4 + (q_len + 1) * 2); + + if ((err = hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)) != HAL_OK) + return err; + + if (der_len != NULL) + *der_len = hlen + vlen; + + if (der == NULL) + return HAL_OK; + + uint8_t *d = der + hlen; + memset(d, 0, vlen); + + if ((err = hal_asn1_encode_integer(version, d, NULL, der + der_max - d)) != HAL_OK) + return err; + d += version_len; + + if ((err = hal_asn1_encode_header(ASN1_OCTET_STRING, q_len, d, NULL, der + der_max - d)) != HAL_OK) + return err; + d += hlen2; + fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - d_len); + d += q_len; + + if ((err = hal_asn1_encode_header(ASN1_EXPLICIT_0, curve->oid_len, d, NULL, der + der_max - d)) != HAL_OK) + return err; + d += hlen3; + memcpy(d, curve->oid, curve->oid_len); + d += curve->oid_len; + + if ((err = hal_asn1_encode_header(ASN1_EXPLICIT_1, (q_len + 1) * 2, d, NULL, der + der_max - d)) != HAL_OK) + return err; + d += hlen4; + *d++ = 0x00; + *d++ = 0x04; + fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - Qx_len); + d += q_len; + fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - Qy_len); + d += q_len; + + assert(d == der + der_max); + + return HAL_OK; +} + +size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key) +{ + size_t len; + return hal_ecdsa_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0; +} + +/* + * Read private key in RFC 5915 ASN.1 DER format. + */ + +hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key_, + void *keybuf, const size_t keybuf_len, + const uint8_t * const der, const size_t der_len) +{ + hal_ecdsa_key_t *key = keybuf; + + if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key)) + return HAL_ERROR_BAD_ARGUMENTS; + + memset(keybuf, 0, keybuf_len); + key->type = HAL_ECDSA_PRIVATE; + + size_t hlen, vlen; + hal_error_t err; + + if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, der, der_len, &hlen, &vlen)) != HAL_OK) + return err; + + const uint8_t * const der_end = der + hlen + vlen; + const uint8_t *d = der + hlen; + const ecdsa_curve_t *curve = NULL; + fp_int version[1]; + + if ((err = hal_asn1_decode_integer(version, d, &hlen, vlen)) != HAL_OK) + goto fail; + if (fp_cmp_d(version, 1) != FP_EQ) + lose(HAL_ERROR_ASN1_PARSE_FAILED); + d += hlen; + + if ((err = hal_asn1_decode_header(ASN1_OCTET_STRING, d, der_end - d, &hlen, &vlen)) != HAL_OK) + return err; + d += hlen; + fp_read_unsigned_bin(key->d, unconst_uint8_t(d), vlen); + d += vlen; + + if ((err = hal_asn1_decode_header(ASN1_EXPLICIT_0, d, der_end - d, &hlen, &vlen)) != HAL_OK) + return err; + d += hlen; + for (key->curve = (hal_ecdsa_curve_t) 0; (curve = get_curve(key->curve)) != NULL; key->curve++) + if (vlen == curve->oid_len && memcmp(d, curve->oid, vlen) == 0) + break; + if (curve == NULL) + lose(HAL_ERROR_ASN1_PARSE_FAILED); + d += vlen; + + if ((err = hal_asn1_decode_header(ASN1_EXPLICIT_1, d, der_end - d, &hlen, &vlen)) != HAL_OK) + return err; + d += hlen; + if (vlen < 4 || (vlen & 1) != 0 || *d++ != 0x00 || *d++ != 0x04) + lose(HAL_ERROR_ASN1_PARSE_FAILED); + vlen = vlen/2 - 1; + fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(d), vlen); + d += vlen; + fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(d), vlen); + d += vlen; + + if (d != der_end) + lose(HAL_ERROR_ASN1_PARSE_FAILED); + + return HAL_OK; + + fail: + memset(keybuf, 0, keybuf_len); + return err; +} + +hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, + const hal_hash_descriptor_t * const hash_descriptor, + const uint8_t * const input, const size_t input_len, + uint8_t *output, size_t *output_len, const size_t output_max) +{ + if (key == NULL || hash_descriptor == NULL || input == NULL || + output == NULL || output_len == NULL || key->type != HAL_ECDSA_PRIVATE) + return HAL_ERROR_BAD_ARGUMENTS; + + const ecdsa_curve_t * const curve = get_curve(key->curve); + if (curve == NULL) + return HAL_ERROR_IMPOSSIBLE; + + fp_int k[1]; fp_init(k); + fp_int r[1]; fp_init(r); + fp_int s[1]; fp_init(s); + fp_int e[1]; fp_init(e); + + fp_int * const n = unconst_fp_int(curve->n); + fp_int * const d = unconst_fp_int(key->d); + + ec_point_t R[1]; + memset(R, 0, sizeof(R)); + + hal_error_t err; + +#warning Should we be hashing here, or should API have caller do it? What does PKCS 11 do for ECDSA? + + /* + * Hash the input and load result into e. + */ + + { + uint8_t statebuf[hash_descriptor->hash_state_length]; + uint8_t hashbuf[hash_descriptor->digest_length]; + hal_hash_state_t state = { NULL }; + + if ((err = hal_hash_initialize(hash_descriptor, &state, + statebuf, sizeof(statebuf))) != HAL_OK || + (err = hal_hash_update(state, input, input_len)) != HAL_OK || + (err = hal_hash_finalize(state, hashbuf, sizeof(hashbuf))) != HAL_OK) + return err; + + fp_read_unsigned_bin(e, hashbuf, sizeof(hashbuf)); + } + + do { + + /* + * Pick random curve point R, then calculate r = R.x % n. + * If r == 0, we can't use this point, so go try again. + */ + + if ((err = point_pick_random(curve, k, R)) != HAL_OK) + goto fail; + + assert(point_is_on_curve(R, curve)); + + if (fp_mod(R->x, n, r) != FP_OKAY) + lose(HAL_ERROR_IMPOSSIBLE); + + if (fp_iszero(r)) + continue; + + /* + * Calculate s = ((e + dr)/k) % n. + * If s == 0, we can't use this point, so go try again. + */ + + if (fp_mulmod (d, r, n, s) != FP_OKAY) + lose(HAL_ERROR_IMPOSSIBLE); + + fp_add (e, s, s); + + if (fp_mod (s, n, s) != FP_OKAY || + fp_invmod (k, n, k) != FP_OKAY || + fp_mulmod (s, k, n, s) != FP_OKAY) + lose(HAL_ERROR_IMPOSSIBLE); + + } while (fp_iszero(s)); + + /* + * Final signature is ASN.1 DER encoding of SEQUENCE { INTEGER r, INTEGER s }. + */ + + size_t r_len, s_len; + + if ((err = hal_asn1_encode_integer(r, NULL, &r_len, 0)) != HAL_OK || + (err = hal_asn1_encode_integer(s, NULL, &s_len, 0)) != HAL_OK || + (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len, output, output_len, output_max)) != HAL_OK) + goto fail; + + uint8_t * const r_out = output + *output_len; + uint8_t * const s_out = r_out + r_len; + output_len += r_len + s_len; + assert(*output_len <= output_max); + + if ((err = hal_asn1_encode_integer(r, r_out, NULL, output_max - (r_out - output))) != HAL_OK || + (err = hal_asn1_encode_integer(s, s_out, NULL, output_max - (s_out - output))) != HAL_OK) + goto fail; + + err = HAL_OK; + + fail: + fp_zero(k); fp_zero(r); fp_zero(s); fp_zero(e); + memset(R, 0, sizeof(R)); + return err; +} + +hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, + const hal_hash_descriptor_t * const hash_descriptor, + const uint8_t * const input, const size_t input_len) +{ +} + +/* + * Local variables: + * indent-tabs-mode: nil + * End: + */ diff --git a/ecdsa_curves.h b/ecdsa_curves.h new file mode 100644 index 0000000..80896ec --- /dev/null +++ b/ecdsa_curves.h @@ -0,0 +1,92 @@ +/* + * ecdsa_curves.h + * -------------- + * Curve parameters for NIST P-256, P-384, and P-521 curves. + * + * At some point we may want to replace this file with one generated + * by a Python script, to make it easier to check the curve parameters. + * + * Authors: Rob Austein + * Copyright (c) 2015, SUNET + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +static const uint8_t p256_q[] = { 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF }; +static const uint8_t p256_b[] = { 0x5A, 0xC6, 0x35, 0xD8, 0xAA, 0x3A, 0x93, 0xE7, 0xB3, 0xEB, 0xBD, 0x55, 0x76, 0x98, 0x86, 0xBC, + 0x65, 0x1D, 0x06, 0xB0, 0xCC, 0x53, 0xB0, 0xF6, 0x3B, 0xCE, 0x3C, 0x3E, 0x27, 0xD2, 0x60, 0x4B }; +static const uint8_t p256_Gx[] = { 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5, 0x63, 0xA4, 0x40, 0xF2, + 0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0, 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96 }; +static const uint8_t p256_Gy[] = { 0x4F, 0xE3, 0x42, 0xE2, 0xFE, 0x1A, 0x7F, 0x9B, 0x8E, 0xE7, 0xEB, 0x4A, 0x7C, 0x0F, 0x9E, 0x16, + 0x2B, 0xCE, 0x33, 0x57, 0x6B, 0x31, 0x5E, 0xCE, 0xCB, 0xB6, 0x40, 0x68, 0x37, 0xBF, 0x51, 0xF5 }; +static const uint8_t p256_n[] = { 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84, 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, 0x25, 0x51 }; +static const uint8_t p256_oid[] = { 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07 }; + +static const uint8_t p384_q[] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF }; +static const uint8_t p384_b[] = { 0xB3, 0x31, 0x2F, 0xA7, 0xE2, 0x3E, 0xE7, 0xE4, 0x98, 0x8E, 0x05, 0x6B, 0xE3, 0xF8, 0x2D, 0x19, + 0x18, 0x1D, 0x9C, 0x6E, 0xFE, 0x81, 0x41, 0x12, 0x03, 0x14, 0x08, 0x8F, 0x50, 0x13, 0x87, 0x5A, + 0xC6, 0x56, 0x39, 0x8D, 0x8A, 0x2E, 0xD1, 0x9D, 0x2A, 0x85, 0xC8, 0xED, 0xD3, 0xEC, 0x2A, 0xEF }; +static const uint8_t p384_Gx[] = { 0xAA, 0x87, 0xCA, 0x22, 0xBE, 0x8B, 0x05, 0x37, 0x8E, 0xB1, 0xC7, 0x1E, 0xF3, 0x20, 0xAD, 0x74, + 0x6E, 0x1D, 0x3B, 0x62, 0x8B, 0xA7, 0x9B, 0x98, 0x59, 0xF7, 0x41, 0xE0, 0x82, 0x54, 0x2A, 0x38, + 0x55, 0x02, 0xF2, 0x5D, 0xBF, 0x55, 0x29, 0x6C, 0x3A, 0x54, 0x5E, 0x38, 0x72, 0x76, 0x0A, 0xB7 }; +static const uint8_t p384_Gy[] = { 0x36, 0x17, 0xDE, 0x4A, 0x96, 0x26, 0x2C, 0x6F, 0x5D, 0x9E, 0x98, 0xBF, 0x92, 0x92, 0xDC, 0x29, + 0xF8, 0xF4, 0x1D, 0xBD, 0x28, 0x9A, 0x14, 0x7C, 0xE9, 0xDA, 0x31, 0x13, 0xB5, 0xF0, 0xB8, 0xC0, + 0x0A, 0x60, 0xB1, 0xCE, 0x1D, 0x7E, 0x81, 0x9D, 0x7A, 0x43, 0x1D, 0x7C, 0x90, 0xEA, 0x0E, 0x5F }; +static const uint8_t p384_n[] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xC7, 0x63, 0x4D, 0x81, 0xF4, 0x37, 0x2D, 0xDF, + 0x58, 0x1A, 0x0D, 0xB2, 0x48, 0xB0, 0xA7, 0x7A, 0xEC, 0xEC, 0x19, 0x6A, 0xCC, 0xC5, 0x29, 0x73 }; +static const uint8_t p384_oid[] = { 0x2b, 0x81, 0x04, 0x00, 0x22 }; + +static const uint8_t p521_q[] = { 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF }; +static const uint8_t p521_b[] = { 0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A, 0x21, 0xA0, 0xB6, 0x85, + 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3, 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, + 0x09, 0xE1, 0x56, 0x19, 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1, + 0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45, 0x1F, 0xD4, 0x6B, 0x50, + 0x3F, 0x00 }; +static const uint8_t p521_Gx[] = { 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFA, 0x51, 0x86, 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09, + 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F, 0xB7, 0x1E, 0x91, 0x38, + 0x64, 0x09 }; +static const uint8_t p521_Gy[] = { 0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E, 0xCB, 0x66, 0x23, 0x95, + 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F, 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, + 0x3D, 0xBA, 0xA1, 0x4B, 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF, + 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E, 0x7E, 0x31, 0xC2, 0xE5, + 0xBD, 0x66 }; +static const uint8_t p521_n[] = { 0x01, 0x18, 0x39, 0x29, 0x6A, 0x78, 0x9A, 0x3B, 0xC0, 0x04, 0x5C, 0x8A, 0x5F, 0xB4, 0x2C, 0x7D, + 0x1B, 0xD9, 0x98, 0xF5, 0x44, 0x49, 0x57, 0x9B, 0x44, 0x68, 0x17, 0xAF, 0xBD, 0x17, 0x27, 0x3E, + 0x66, 0x2C, 0x97, 0xEE, 0x72, 0x99, 0x5E, 0xF4, 0x26, 0x40, 0xC5, 0x50, 0xB9, 0x01, 0x3F, 0xAD, + 0x07, 0x61, 0x35, 0x3C, 0x70, 0x86, 0xA2, 0x72, 0xC2, 0x40, 0x88, 0xBE, 0x94, 0x76, 0x9F, 0xD1, + 0x66, 0x50 }; +static const uint8_t p521_oid[] = { 0x2b, 0x81, 0x04, 0x00, 0x23 }; @@ -446,6 +446,7 @@ DEFINE_HAL_ERROR(HAL_ERROR_ALLOCATION_FAILURE, "Memory allocation failed") \ DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG, "Result too long for buffer") \ DEFINE_HAL_ERROR(HAL_ERROR_ASN1_PARSE_FAILED, "ASN.1 parse failed") \ + DEFINE_HAL_ERROR(HAL_ERROR_KEY_NOT_ON_CURVE, "EC key is not on its purported curve") \ END_OF_HAL_ERROR_LIST /* Marker to forestall silly line continuation errors */ @@ -671,6 +672,67 @@ extern hal_error_t hal_rsa_key_from_der(hal_rsa_key_t *key, void *keybuf, const size_t keybuf_len, const uint8_t * const der, const size_t der_len); +/* + * ECDSA. + */ + +typedef enum { HAL_ECDSA_PRIVATE, HAL_ECDSA_PUBLIC } hal_ecdsa_key_type_t; + +typedef enum { HAL_ECDSA_CURVE_P256, HAL_ECDSA_CURVE_P384, HAL_ECDSA_CURVE_P521 } hal_ecdsa_curve_t; + +typedef struct hal_ecdsa_key hal_ecdsa_key_t; + +extern const size_t hal_ecdsa_key_t_size; + +extern void hal_ecdsa_set_debug(const int onoff); + +extern hal_error_t hal_ecdsa_key_load_private(hal_ecdsa_key_t **key, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve, + const uint8_t * const x, const size_t x_len, + const uint8_t * const y, const size_t y_len, + const uint8_t * const d, const size_t d_len); + +extern hal_error_t hal_ecdsa_key_load_public(hal_ecdsa_key_t **key, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve, + const uint8_t * const x, const size_t x_len, + const uint8_t * const y, const size_t y_len); + +extern hal_error_t hal_ecdsa_key_get_type(const hal_ecdsa_key_t * const key, + hal_ecdsa_key_type_t *key_type); + +extern hal_error_t hal_ecdsa_key_get_curve(const hal_ecdsa_key_t * const key, + hal_ecdsa_curve_t *curve); + +extern hal_error_t hal_ecdsa_key_get_public(const hal_ecdsa_key_t * const key, + uint8_t *x, size_t *x_len, const size_t x_max, + uint8_t *y, size_t *y_len, const size_t y_max); + +extern void hal_ecdsa_key_clear(hal_ecdsa_key_t *key); + +extern hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, + const hal_hash_descriptor_t * const hash_descriptor, + const uint8_t * const input, const size_t input_len, + uint8_t *output, size_t *output_len, const size_t output_max); + +extern hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, + const hal_hash_descriptor_t * const hash_descriptor, + const uint8_t * const input, const size_t input_len); + +extern hal_error_t hal_ecdsa_key_gen(hal_ecdsa_key_t **key, + void *keybuf, const size_t keybuf_len, + const hal_ecdsa_curve_t curve); + +extern hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key, + uint8_t *der, size_t *der_len, const size_t der_max); + +extern size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key); + +extern hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key, + void *keybuf, const size_t keybuf_len, + const uint8_t * const der, const size_t der_len); + #endif /* _HAL_H_ */ /* |