[CryptechCommits] [sw/libhal] 01/01: Add point validation check to hal_ecdsa_verify(). Update README.md and code comments.
git at cryptech.is
git at cryptech.is
Thu Aug 27 16:42:52 UTC 2015
This is an automated email from the git hooks/postreceive script.
sra at hactrn.net pushed a commit to branch ecdsa
in repository sw/libhal.
commit 55116cc564649433cf4a8515d4a37cbf00dd6199
Author: Rob Austein <sra at hactrn.net>
Date: Thu Aug 27 12:39:55 2015 0400
Add point validation check to hal_ecdsa_verify(). Update README.md
and code comments.

README.md  67 +++++++++++++++++++++++++++++++++++++++++++++++++
ecdsa.c  48 ++++++++++++++++++++++++++++
tests/testecdsa.c  9 
tests/testecdsa.py  2 +
4 files changed, 99 insertions(+), 27 deletions()
diff git a/README.md b/README.md
index 66669e3..71fc0a0 100644
 a/README.md
+++ b/README.md
@@ 1,6 +1,8 @@
libhal
======
+## Overview ##
+
This library combines a set of lowlevel API functions which talk to
the Cryptech FPGA cores with a set of higherlevel 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 selfcontained, although the PBKDF2
implementation uses the hashcorebased 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 compiletime 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 P256,
+P384, and P521.
+
+The ECDSA implementation includes a compiletime 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 constanttime, 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 constanttime. Point multiplication could probably
+be made faster by using a nonadjacent form (NAF) representation for
+the scalar, but the author doesn't yet understand that well enough to
+implement it as a constanttime 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/autoshortwjacobian3.html
+[Doxygen]: http://www.doxygen.org/
diff git a/ecdsa.c b/ecdsa.c
index 933cb5f..09ab3f6 100644
 a/ecdsa.c
+++ b/ecdsa.c
@@ 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 oneelement 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 constification, 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 handcoded, 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 handcoded, 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 callersupplied 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/testecdsa.c b/tests/testecdsa.c
index c4cf25f..d57b440 100644
 a/tests/testecdsa.c
+++ b/tests/testecdsa.c
@@ 57,15 +57,6 @@
#include "testecdsa.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/testecdsa.py b/tests/testecdsa.py
index a52f85b..1ecfef9 100644
 a/tests/testecdsa.py
+++ b/tests/testecdsa.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:
More information about the Commits
mailing list