insecure nonce generation

[lts-rad]

nano-ecc/ecc.c

Line 1290 in a91209d

vli_sub(k, k, curve_n);

the nonce generation here is biased and could lead to potential key recovery attacks. looks like micro-ecc has already fixed these issues, so this old repo might need a warning that its out of date. https://github.com/kmackay/micro-ecc

[werner-kingo]

Hi, I am currently planning on using this. Are you stating tat the solution from micro-ecc could be applied to nano Ecc in order to fix this issue or a refactor of nano Ecc should take place in order to fix it? I am interested in fixing it if it wont take me 3 months

[werner-kingo]

The definition of vli_sub on uECC is :

uECC_VLI_API uECC_word_t uECC_vli_sub(uECC_word_t *result,
                                      const uECC_word_t *left,
                                      const uECC_word_t *right,
                                      wordcount_t num_words);

/* Returns sign of left - right, in constant time. */
uECC_VLI_API cmpresult_t uECC_vli_cmp(const uECC_word_t *left,
                                      const uECC_word_t *right,
                                      wordcount_t num_words) {
    uECC_word_t tmp[uECC_MAX_WORDS];
    uECC_word_t neg = !!uECC_vli_sub(tmp, left, right, num_words);
    uECC_word_t equal = uECC_vli_isZero(tmp, num_words);
    return (!equal - 2 * neg);
}

And the definition on nECC is :

static uint8_t vli_sub(uint8_t *p_result, uint8_t *p_left, uint8_t *p_right) { uint8_t l_borrow = 0; uint i; for(i=0; i<NUM_ECC_DIGITS; ++i) { uint8_t l_diff = p_left[i] - p_right[i] - l_borrow; if(l_diff != p_left[i]) { l_borrow = (l_diff > p_left[i]); } p_result[i] = l_diff; } return l_borrow; }

[lts-rad]

@werner-kingo if you want to bring a fix in for this particular issue it isn't too hard, but this project is not maintained. micro-ecc would be a better choice if you can choose, but i can't vouch for its security either as it may also have not undergone a security audit.

[werner-kingo]

The thing is that the low size of the 128 curve is ideal to my application and uECC is bigger. BTW thanks for the fast response. Do you have any advice on how to approach this in order to test the bias? Or just printing the numbers and checking the distribution?

[werner-kingo]

Found it, the extra regularization process. So I guess this is the code to port.

static uECC_word_t regularize_k(const uECC_word_t * const k, uECC_word_t *k0, uECC_word_t *k1, uECC_Curve curve) { wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); bitcount_t num_n_bits = curve->num_n_bits; uECC_word_t carry = uECC_vli_add(k0, k, curve->n, num_n_words) || (num_n_bits < ((bitcount_t)num_n_words * uECC_WORD_SIZE * 8) && uECC_vli_testBit(k0, num_n_bits)); uECC_vli_add(k1, k0, curve->n, num_n_words); return carry; }

Thanks for pointing it out.

[lts-rad]

you might want to checkout https://tools.ietf.org/html/rfc6979 for nonce generation. it addresses biased nonce issues as well as problems with entropy that would result in nonce bias or reuse. a single bit bias in your nonce is enough to be devastating to ecdsa