Observable Discrepancy

Summary

Generating the ECDSA nonce `k` samples a random number `r` and then truncates this randomness with a modular reduction `mod n` where `n` is the order of the elliptic curve. Meaning `k = r mod n`. The division used during the reduction estimates a factor `q_e` by dividing the upper two digits (a digit having, e.g., a size of 8 byte) of `r` by the upper digit of `n` and then decrements `q_e` in a loop until it has the correct size. Observing the number of times `q_e` is decremented through a control flow revealing side-channel reveals a bias in the most significant bits of `k`. Depending on the curve, this is either a negligible bias or a significant bias large enough to reconstruct `k` with lattice reduction methods. For SECP160R1, e.g., we find a bias of 15 bits. This issue affects wolfssl versions prior to 5.6.6.