4 ms·

Deterministic nonces are a good idea, but they don't necessarily prevent biases. Generally speaking, for (EC)DSA/Schnorr in a group of cardinality n, using a no

by mti 12y ago

Deterministic nonces are a good idea, but they don't necessarily prevent biases. Generally speaking, for (EC)DSA/Schnorr in a group of cardinality n, using a nonce of the form k=F_x(m) (where m is the message and x the public key) is safe if F is chosen as a Z/nZ-valued PRF; but if you use a PRF with values in bitstrings of the same length as n, the attack in the paper does apply. So RFC 6979 is fine, but k=HMAC-SHA-256(x,m) is not a secure choice for 256-bit elliptic curves over random base fields.

nullc 12y ago
It's common to see implementations want to remove debiasing steps too. E.g. I've seen several implementations of "derandomized DSA" for Bitcoin (e.g. javascript tools, hardware wallets, etc. We obviously do this right in Bitcoin core) that do not re-roll if the result is over the order, they just take it mod the order. Complaining to the implementers has just resulted in <whine>thats more complicated, mod is fine</white> And, indeed, for secp256k1 the differences is 1 part in 10^38, so its not likely of practical importance; unless you can assume an attack that can extract an _awful_ lot of signatures from you. I expect the same behaviours are common for different parameters where it's not such a small bias.
- mti 12y ago
  When the base field is pseudo-Mersenne, taking mods is actually fine, since the statistical distance to uniform of the resulting distribution is O(2^{-λ}) at the λ-bit security level. In other words, an attack that exploits the bias is at least as costly as breaking the discrete log problem directly, and therefore not a security concern. So I wouldn't worry about implementations of secp256k1 that do it like that (although it would be simpler and less "leaky" to just use the non-reduced 256-bit MAC value as the nonce; of course, anything shorter than 256 bits would be a huge problem). But careful approaches like RFC 6979 are very important for curves over random fields, like the Brainpool parameters. [By the way, a more regular contributor of this site suggested that it would be appropriate for me to mention that I'm one of the authors of the OP.]
  - deleted 12y ago
    [deleted]

by mti 12y ago

nullc 12y ago

It's common to see implementations want to remove debiasing steps too. E.g. I've seen several implementations of "derandomized DSA" for Bitcoin (e.g. javascript tools, hardware wallets, etc. We obviously do this right in Bitcoin core) that do not re-roll if the result is over the order, they just take it mod the order. Complaining to the implementers has just resulted in <whine>thats more complicated, mod is fine</white> And, indeed, for secp256k1 the differences is 1 part in 10^38, so its not likely of practical importance; unless you can assume an attack that can extract an _awful_ lot of signatures from you. I expect the same behaviours are common for different parameters where it's not such a small bias.

mti 12y ago
When the base field is pseudo-Mersenne, taking mods is actually fine, since the statistical distance to uniform of the resulting distribution is O(2^{-λ}) at the λ-bit security level. In other words, an attack that exploits the bias is at least as costly as breaking the discrete log problem directly, and therefore not a security concern. So I wouldn't worry about implementations of secp256k1 that do it like that (although it would be simpler and less "leaky" to just use the non-reduced 256-bit MAC value as the nonce; of course, anything shorter than 256 bits would be a huge problem). But careful approaches like RFC 6979 are very important for curves over random fields, like the Brainpool parameters. [By the way, a more regular contributor of this site suggested that it would be appropriate for me to mention that I'm one of the authors of the OP.]
- deleted 12y ago
  [deleted]