Add projective coordinates randomization in ECDSA
Why: this protects against potential side-channels attacks. This
counter-measure is for example effective against Template SPA. Also, the
bignum arithmetic as implemented in TinyCrypt isn't entirely regular, which
could in principle be exploited by an attacker; randomizing the coordinates
makes this less likely to happen.
Randomizing projective coordinates is also a well-known countermeasure to DPA.
In the context of the scalar multiplication in ECDSA, DPA isn't a concern
since it requires multiple measurements with various base points and the same
scalar, and the scalar mult in ECDSA is the opposite: the base point's always
the same and the scalar is always unique. But we want protection against the
other attacks as well.
How: we use the same code fragment as in uECC_shared_secret in ecc_dh.c,
adapted as follows: (1) replace p2 with k2 as that's how it's called in this
function; (2) adjust how errors are handled.
The code might not be immediately clear so here are a few more details:
regularize_k() takes two arrays as outputs, and the return value says which one
should be passed to ECCPoint_mult(). The other one is free for us to re-use to
generate a random number to be used as the initial Z value for randomizing
coordinates (otherwise the initial Z value is 1), thus avoiding the use of an
extra stack buffer.
diff --git a/tinycrypt/ecc_dsa.c b/tinycrypt/ecc_dsa.c
index a3893d3..e8c0e0b 100644
--- a/tinycrypt/ecc_dsa.c
+++ b/tinycrypt/ecc_dsa.c
@@ -116,6 +116,7 @@
uECC_word_t s[NUM_ECC_WORDS];
uECC_word_t *k2[2] = {tmp, s};
uECC_word_t p[NUM_ECC_WORDS * 2];
+ uECC_word_t *initial_Z = 0;
uECC_word_t carry;
wordcount_t num_words = curve->num_words;
wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits);
@@ -127,8 +128,20 @@
return 0;
}
+ /* Regularize the bitcount for the private key so that attackers cannot use a
+ * side channel attack to learn the number of leading zeros. */
carry = regularize_k(k, tmp, s, curve);
- EccPoint_mult(p, curve->G, k2[!carry], 0, num_n_bits + 1, curve);
+
+ /* If an RNG function was specified, get a random initial Z value to
+ * protect against side-channel attacks such as Template SPA */
+ if (g_rng_function) {
+ if (!uECC_generate_random_int(k2[carry], curve->p, num_words)) {
+ return 0;
+ }
+ initial_Z = k2[carry];
+ }
+
+ EccPoint_mult(p, curve->G, k2[!carry], initial_Z, num_n_bits + 1, curve);
if (uECC_vli_isZero(p, num_words)) {
return 0;
}