Initial untested implementation of deterministic message signing (#37).
diff --git a/uECC.c b/uECC.c
index fe4b3ea..28b92f9 100644
--- a/uECC.c
+++ b/uECC.c
@@ -2121,9 +2121,8 @@
}
#endif /* (uECC_CURVE != uECC_secp160r1) */
-// 0 < k < curve_n
static int uECC_sign_with_k(const uint8_t private_key[uECC_BYTES],
- const uint8_t hash[uECC_BYTES],
+ const uint8_t message_hash[uECC_BYTES],
uECC_word_t k[uECC_N_WORDS],
uint8_t signature[uECC_BYTES*2]) {
uECC_word_t tmp[uECC_N_WORDS];
@@ -2132,6 +2131,11 @@
EccPoint p;
uECC_word_t carry;
uECC_word_t tries;
+
+ /* Make sure 0 < k < curve_n */
+ if (vli_isZero(k) || vli_cmp_n(curve_n, k) != 1) {
+ return 0;
+ }
#if (uECC_CURVE == uECC_secp160r1)
/* Make sure that we don't leak timing information about k.
@@ -2193,7 +2197,7 @@
vli_set(s, p.x);
vli_modMult_n(s, tmp, s); /* s = r*d */
- vli_bytesToNative(tmp, hash);
+ vli_bytesToNative(tmp, message_hash);
vli_modAdd_n(s, tmp, s, curve_n); /* s = e + r*d */
vli_modMult_n(s, s, k); /* s = (e + r*d) / k */
#if (uECC_CURVE == uECC_secp160r1)
@@ -2206,7 +2210,7 @@
}
int uECC_sign(const uint8_t private_key[uECC_BYTES],
- const uint8_t hash[uECC_BYTES],
+ const uint8_t message_hash[uECC_BYTES],
uint8_t signature[uECC_BYTES*2]) {
uECC_word_t k[uECC_N_WORDS];
uECC_word_t tmp[uECC_N_WORDS];
@@ -2223,16 +2227,126 @@
k[uECC_WORDS] &= 0x01;
#endif
- if (vli_isZero(k) || vli_cmp_n(curve_n, k) != 1) {
- continue;
- }
- if (uECC_sign_with_k(private_key, hash, k, signature)) {
+ if (uECC_sign_with_k(private_key, message_hash, k, signature)) {
return 1;
}
}
return 0;
}
+#if defined(uECC_HASH_BLOCK_SIZE) && defined(uECC_HASH_RESULT_SIZE)
+
+/* Compute an HMAC using K as a key (as in RFC 6979). Note that K is always
+ the same size as the hash result size. */
+static void HMAC_init(uECC_HashContext *hash_context, const uint8_t *K) {
+ uint8_t pad[uECC_HASH_BLOCK_SIZE];
+ unsigned i;
+ for (i = 0; i < uECC_HASH_RESULT_SIZE; ++i)
+ pad[i] = K[i] ^ 0x36;
+ for (i = uECC_HASH_RESULT_SIZE; i < uECC_HASH_BLOCK_SIZE; ++i)
+ pad[i] = 0x36;
+
+ hash_context->init_hash(hash_context);
+ hash_context->update_hash(hash_context, pad, uECC_HASH_BLOCK_SIZE);
+}
+
+static void HMAC_update(uECC_HashContext *hash_context,
+ const uint8_t *message,
+ unsigned message_size) {
+ hash_context->update_hash(hash_context, message, message_size);
+}
+
+static void HMAC_finish(uECC_HashContext *hash_context, const uint8_t *K, uint8_t *result) {
+ uint8_t pad[uECC_HASH_BLOCK_SIZE];
+ unsigned i;
+ for (i = 0; i < uECC_HASH_RESULT_SIZE; ++i)
+ pad[i] = K[i] ^ 0x5c;
+ for (i = uECC_HASH_RESULT_SIZE; i < uECC_HASH_BLOCK_SIZE; ++i)
+ pad[i] = 0x5c;
+
+ hash_context->finish_hash(hash_context, result);
+
+ hash_context->init_hash(hash_context);
+ hash_context->update_hash(hash_context, pad, uECC_HASH_BLOCK_SIZE);
+ hash_context->update_hash(hash_context, result, uECC_HASH_RESULT_SIZE);
+ hash_context->finish_hash(hash_context, result);
+}
+
+/* V = HMAC_K(V) */
+static void update_V(uECC_HashContext *hash_context, uint8_t *K, uint8_t *V) {
+ HMAC_init(hash_context, K);
+ HMAC_update(hash_context, V, uECC_HASH_RESULT_SIZE);
+ HMAC_finish(hash_context, K, V);
+}
+
+/* Deterministic signing, similar to RFC 6979. Differences are:
+ * We just use (truncated) H(m) directly rather than bits2octets(H(m))
+ (it is not reduced modulo curve_n).
+ * We generate a value for k (aka T) directly rather than converting endianness. */
+int uECC_sign_deterministic(const uint8_t private_key[uECC_BYTES],
+ const uint8_t message_hash[uECC_BYTES],
+ uECC_HashContext *hash_context,
+ uint8_t signature[uECC_BYTES*2]) {
+ uint8_t V[uECC_HASH_RESULT_SIZE + 1];
+ uint8_t K[uECC_HASH_RESULT_SIZE];
+ uECC_word_t tries;
+ unsigned i;
+ for (i = 0; i < uECC_HASH_RESULT_SIZE; ++i) {
+ V[i] = 0x01;
+ K[i] = 0;
+ }
+
+ // K = HMAC_K(V || 0x00 || int2octets(x) || h(m))
+ V[uECC_HASH_RESULT_SIZE] = 0x00;
+ HMAC_init(hash_context, K);
+ HMAC_update(hash_context, V, uECC_HASH_RESULT_SIZE + 1);
+ HMAC_update(hash_context, private_key, uECC_BYTES);
+ HMAC_update(hash_context, message_hash, uECC_BYTES);
+ HMAC_finish(hash_context, K, K);
+
+ update_V(hash_context, K, V);
+
+ // K = HMAC_K(V || 0x01 || int2octets(x) || h(m))
+ V[uECC_HASH_RESULT_SIZE] = 0x01;
+ HMAC_init(hash_context, K);
+ HMAC_update(hash_context, V, uECC_HASH_RESULT_SIZE + 1);
+ HMAC_update(hash_context, private_key, uECC_BYTES);
+ HMAC_update(hash_context, message_hash, uECC_BYTES);
+ HMAC_finish(hash_context, K, K);
+
+ update_V(hash_context, K, V);
+
+ for (tries = 0; tries < MAX_TRIES; ++tries) {
+ uECC_word_t T[uECC_N_WORDS];
+ uint8_t *T_ptr = (uint8_t *)T;
+ unsigned T_bytes = 0;
+ while (T_bytes < sizeof(T)) {
+ update_V(hash_context, K, V);
+ for (i = 0; i < uECC_HASH_RESULT_SIZE && T_bytes < sizeof(T); ++i, ++T_bytes) {
+ T_ptr[T_bytes] = V[i];
+ }
+ }
+ #if (uECC_CURVE == uECC_secp160r1)
+ T[uECC_WORDS] &= 0x01;
+ #endif
+
+ if (uECC_sign_with_k(private_key, message_hash, T, signature)) {
+ return 1;
+ }
+
+ // K = HMAC_K(V || 0x00)
+ V[uECC_HASH_RESULT_SIZE] = 0x00;
+ HMAC_init(hash_context, K);
+ HMAC_update(hash_context, V, uECC_HASH_RESULT_SIZE + 1);
+ HMAC_finish(hash_context, K, K);
+
+ update_V(hash_context, K, V);
+ }
+ return 0;
+}
+
+#endif /* defined(uECC_HASH_BLOCK_SIZE) && defined(uECC_HASH_RESULT_SIZE) */
+
static bitcount_t smax(bitcount_t a, bitcount_t b) {
return (a > b ? a : b);
}
diff --git a/uECC.h b/uECC.h
index 282aac3..4d947e9 100644
--- a/uECC.h
+++ b/uECC.h
@@ -72,7 +72,7 @@
uECC_make_key() or uECC_sign().
Setting a correctly functioning RNG function improves the resistance to side-channel attacks
-for uECC_shared_secret().
+for uECC_shared_secret() and uECC_sign_deterministic().
A correct RNG function is set by default when building for Windows, Linux, or OS X.
If you are building on another POSIX-compliant system that supports /dev/random or /dev/urandom,
@@ -129,8 +129,8 @@
this function along with your private key.
Inputs:
- private_key - Your private key.
- hash - The message hash to sign.
+ private_key - Your private key.
+ message_hash - The hash of the message to sign.
Outputs:
signature - Will be filled in with the signature value.
@@ -138,9 +138,88 @@
Returns 1 if the signature generated successfully, 0 if an error occurred.
*/
int uECC_sign(const uint8_t private_key[uECC_BYTES],
- const uint8_t hash[uECC_BYTES],
+ const uint8_t message_hash[uECC_BYTES],
uint8_t signature[uECC_BYTES*2]);
+/* Define uECC_HASH_BLOCK_SIZE to the block size in bytes of your hash algorithm
+ (eg 64 for SHA-256) */
+/* #define uECC_HASH_BLOCK_SIZE 64 */
+/* Define uECC_HASH_RESULT_SIZE to the output size in bytes of your hash algorithm
+ (eg 32 for SHA-256) */
+/* #define uECC_HASH_RESULT_SIZE 32 */
+#if defined(uECC_HASH_BLOCK_SIZE) && defined(uECC_HASH_RESULT_SIZE)
+
+/* uECC_HashContext structure.
+This is used to pass in an arbitrary hash function to uECC_sign_deterministic().
+The structure will be used for multiple hash computations; each time a new hash
+is computed, init_hash() will be called, followed by one or more calls to
+update_hash(), and finally a call to finish_hash() to prudoce the resulting hash.
+
+The intention is that you will create a structure that includes uECC_HashContext
+followed by any hash-specific data. For example:
+
+typedef struct SHA256_HashContext {
+ uECC_HashContext uECC;
+ SHA256_CTX ctx;
+} SHA256_HashContext;
+
+void SHA256_init(uECC_HashContext *base) {
+ SHA256_HashContext *context = (SHA256_HashContext *)base;
+ SHA256_Init(&context->ctx);
+}
+
+void SHA256_update(uECC_HashContext *base,
+ const uint8_t *message,
+ unsigned message_size) {
+ SHA256_HashContext *context = (SHA256_HashContext *)base;
+ SHA256_Update(&context->ctx, message, message_size);
+}
+
+void SHA256_finish(uECC_HashContext *base, uint8_t *hash_result) {
+ SHA256_HashContext *context = (SHA256_HashContext *)base;
+ SHA256_Final(hash_result, &context->ctx);
+}
+
+... when signing ...
+{
+ SHA256_HashContext ctx = {{&SHA256_init, &SHA256_update, &SHA256_finish}};
+ uECC_sign_deterministic(key, message_hash, &ctx, signature);
+}
+*/
+typedef struct uECC_HashContext {
+ void (*init_hash)(struct uECC_HashContext *context);
+ void (*update_hash)(struct uECC_HashContext *context,
+ const uint8_t *message,
+ unsigned message_size);
+ void (*finish_hash)(struct uECC_HashContext *context, uint8_t *hash_result);
+} uECC_HashContext;
+
+/* uECC_sign_deterministic() function.
+Generate an ECDSA signature for a given hash value, using a deterministic algorithm
+(see RFC 6979). You do not need to set the RNG using uECC_set_rng() before calling
+this function; however, if the RNG is defined it will improve resistance to side-channel
+attacks.
+
+Usage: Compute a hash of the data you wish to sign (SHA-2 is recommended) and pass it in to
+this function along with your private key and a hash context.
+
+Inputs:
+ private_key - Your private key.
+ message_hash - The hash of the message to sign.
+ hash_context - A hash context to use.
+
+Outputs:
+ signature - Will be filled in with the signature value.
+
+Returns 1 if the signature generated successfully, 0 if an error occurred.
+*/
+int uECC_sign_deterministic(const uint8_t private_key[uECC_BYTES],
+ const uint8_t message_hash[uECC_BYTES],
+ uECC_HashContext *hash_context,
+ uint8_t signature[uECC_BYTES*2]);
+
+#endif /* defined(uECC_HASH_BLOCK_SIZE) && defined(uECC_HASH_RESULT_SIZE) */
+
/* uECC_verify() function.
Verify an ECDSA signature.
