diff options
| -rw-r--r-- | README.md | 67 | ||||
| -rw-r--r-- | ecdsa.c | 48 | ||||
| -rw-r--r-- | tests/test-ecdsa.c | 9 | ||||
| -rw-r--r-- | tests/test-ecdsa.py | 2 |
4 files changed, 99 insertions, 27 deletions
@@ -1,6 +1,8 @@ libhal ====== +## Overview ## + This library combines a set of low-level API functions which talk to the Cryptech FPGA cores with a set of higher-level functions providing various cryptographic services. @@ -25,16 +27,21 @@ Current contents of the library: * An implementation of RSA using the Cryptech ModExp core. +* An implementation of ECDSA, currently entirely in software. + * Test code for all of the above. Most of these are fairly well self-contained, although the PBKDF2 implementation uses the hash-core-based HMAC implementation. -The major exception is the RSA implementation, which uses an external -bignum implementation (libtfm) to handle a lot of the arithmetic. In -the long run, much or all of this may end up being implemented in -Verilog, but for the moment all of the RSA math except for modular -exponentiation is happening in software. +The major exceptions are the RSA and ECDSA implementations, which uses +an external bignum implementation (libtfm) to handle a lot of the +arithmetic. In the long run, much or all of this may end up being +implemented in Verilog, but for the moment all of the RSA math except +for modular exponentiation is happening in software, as is all of the +math for ECDSA. + +## RSA ## The RSA implementation includes a compile-time option to bypass the ModExp core and do everything in software, because the ModExp core is @@ -44,3 +51,53 @@ The RSA implementation includes optional blinding (enabled by default) and just enough ASN.1 code to read and write private keys; the expectation is that the latter will be used in combination with the AES Key Wrap code. + +## ECDSA ## + +The ECDSA implementation is specific to the NIST prime curves P-256, +P-384, and P-521. + +The ECDSA implementation includes a compile-time option to allow test +code to bypass the CSPRNG in order to test against known test vectors. +Do **NOT** enable this in production builds, as ECDSA depends on good +random numbers not just for private keys but for individual +signatures, and an attacker who knows the random number used for a +particular signature can use this to recover the private key. +Arguably, this option should be removed from the code entirely, once +the implementation is stable. + +The ECDSA implementation includes enough ASN.1 to read and write ECDSA +signatures and ECDSA private keys in RFC 5915 format; the expectation +is that the latter will be used in combination with AES Key Wrap. + +The ECDSA implementation attempts to be constant-time, to reduce the +risk of timing channel attacks. The algorithms chosen for the point +arithmetic are a tradeoff between speed and code complexity, and can +probably be improved upon even in software; reimplementing at least +the field arithmetic in hardware would probably also help. + +The current point addition and point doubling algorithms come from the +[EFD][]. At least at the moment, we're only interested in ECDSA with +the NIST prime curves, so we use algorithms optimized for a=-3. + +The point multiplication algorithm is a Montgomery Ladder, which is +not the fastest possible algorithm, but is relatively easy to confirm +by inspection as constant-time. Point multiplication could probably +be made faster by using a non-adjacent form (NAF) representation for +the scalar, but the author doesn't yet understand that well enough to +implement it as a constant-time algorithm. In theory, changing to a +NAF representation could be done without any change to the public API. + +Points stored in keys and curve parameters are in affine format, but +all point arithmetic is performed in Jacobian projective coordinates, +with the coordinates in Montgomery form; final mapping back to affine +coordinates also handles the final Montgomery reduction. + +## API ## + +Yeah, we ought to document the API, Real Soon Now, perhaps using +[Doxygen][]. For the moment, see the function prototypes in hal.h and +comments in the code. + +[EFD]: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html +[Doxygen]: http://www.doxygen.org/ @@ -1,15 +1,17 @@ /* * ecdsa.c * ------- - * Basic ECDSA functions. + * Elliptic Curve Digital Signature Algorithm for NIST prime curves. * - * 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. + * At some point we may want to refactor this code to separate + * functionality that applies to all elliptic curve cryptography into + * a separate module from functions specific to ECDSA over the NIST + * 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. + * St Denis's libtomcrypt code. Algorithms for point addition and + * point doubling courtesy of the hyperelliptic.org formula database. * * Authors: Rob Austein * Copyright (c) 2015, SUNET @@ -55,6 +57,7 @@ * * 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 "&". + * Perhaps we should encapsulate this idiom in a typedef. * * Unfortunately, libtfm is bad about const-ification, but we want to * hide that from our users, so our public API uses const as @@ -632,7 +635,7 @@ static hal_error_t point_scalar_multiply(const fp_int * const k, #if HAL_ECDSA_DEBUG_ONLY_STATIC_TEST_VECTOR_RANDOM -#warning hal_ecdsa random number generator overriden for test purposes +#warning hal_ecdsa random number generator overridden for test purposes #warning DO NOT USE THIS IN PRODUCTION typedef hal_error_t (*rng_override_test_function_t)(void *, const size_t); @@ -719,8 +722,9 @@ static hal_error_t point_pick_random(const ecdsa_curve_t * const curve, } /* - * Test whether a point really is on a particular curve (sometimes - * called "validation when applied to a public key"). + * Test whether a point really is on a particular curve. This is + * called "validation" when applied to a public key, and is required + * before verifying a signature. */ static int point_is_on_curve(const ec_point_t * const P, @@ -891,7 +895,9 @@ hal_error_t hal_ecdsa_key_load_public(hal_ecdsa_key_t **key_, } /* - * Load a private key from components. + * Load a private key from components; does all the same things as + * hal_ecdsa_key_load_public(), then loads the private key itself and + * adjusts the key type. * * For extra paranoia, we could check Q == dG. */ @@ -919,6 +925,9 @@ hal_error_t hal_ecdsa_key_load_private(hal_ecdsa_key_t **key_, /* * Write private key in RFC 5915 ASN.1 DER format. + * + * This is hand-coded, and is approaching the limit where one should + * probably be using an ASN.1 compiler like asn1c instead. */ hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key, @@ -1006,6 +1015,11 @@ hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key, return HAL_OK; } +/* + * Convenience wrapper to return how many bytes a private key would + * take if encoded as DER. + */ + size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key) { size_t len; @@ -1014,6 +1028,9 @@ size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key) /* * Read private key in RFC 5915 ASN.1 DER format. + * + * This is hand-coded, and is approaching the limit where one should + * probably be using an ASN.1 compiler like asn1c instead. */ hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key_, @@ -1127,7 +1144,7 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, do { /* - * Pick random curve point R, then calculate r = R.x % n. + * Pick random curve point R, then calculate r = Rx % n. * If r == 0, we can't use this point, so go try again. */ @@ -1188,6 +1205,10 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, return err; } +/* + * Verify a signature using a caller-supplied hash. + */ + hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, const uint8_t * const hash, const size_t hash_len, const uint8_t * const signature, const size_t signature_len) @@ -1199,6 +1220,9 @@ hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, if (curve == NULL) return HAL_ERROR_IMPOSSIBLE; + if (!point_is_on_curve(key->Q, curve)) + return HAL_ERROR_KEY_NOT_ON_CURVE; + fp_int * const n = unconst_fp_int(curve->n); size_t len1, len2; @@ -1212,7 +1236,7 @@ hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, memset(R, 0, sizeof(R)); /* - * First, we have to parse the ASN.1 SEQUENCE { INTEGER r, INTEGER s }. + * Parse the ASN.1 SEQUENCE { INTEGER r, INTEGER s }. */ if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, signature, signature_len, &len1, &len2)) != HAL_OK) diff --git a/tests/test-ecdsa.c b/tests/test-ecdsa.c index c4cf25f..d57b440 100644 --- a/tests/test-ecdsa.c +++ b/tests/test-ecdsa.c @@ -57,15 +57,6 @@ #include "test-ecdsa.h" -/* - * Supplied test vectors don't use ASN.1 encoding. Don't want to - * trust our own ASN.1 code for this (it's one of the things we're - * testing) so use Python pyasn1 or ecdsa.der code to build what we - * need and supply them as test vector data too. This is probably - * also the right way to test our encoding and decoding of private - * keys too. - */ - #if HAL_ECDSA_DEBUG_ONLY_STATIC_TEST_VECTOR_RANDOM /* diff --git a/tests/test-ecdsa.py b/tests/test-ecdsa.py index a52f85b..1ecfef9 100644 --- a/tests/test-ecdsa.py +++ b/tests/test-ecdsa.py @@ -60,7 +60,7 @@ def long_to_bytes(l): def bytes_to_bits(b): # # This, on the other hand, is not just plain nasty, this is fancy nasty. - # This is nasty with rasins in it. + # This is nasty with raisins in it. # bits = bin(long(b.encode("hex"), 16))[2:] if len(bits) % 8: |