[Cryptech-Commits] [sw/libhal] 01/01: Add point validation check to hal_ecdsa_verify(). Update README.md and code comments.

[git at cryptech.is]

This is an automated email from the git hooks/post-receive 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/test-ecdsa.c  |  9 -------
 tests/test-ecdsa.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 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/
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 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: