Score:2

What degree of k bias is acceptable in ECDSA?

ru flag

So there’s LadderLeak.

RFC6979 produces uniformly random nonce $k$.

There are other techniques, such as hash-to-curve standard (draft-irtf-cfrg-hash-to-curve-16 section 5), which allows to produce uniformly random scalars. They mention it’s OK to use 128 additional bits of entropy, e.g 48-byte hash to produce 32-byte private key, when targeting 128-bit security level. The bias is still there but it’s reduced to 2^-64 or so. They mention it in the context of private keys.

How safe could this technique be when used in $k$ generation, instead of RFC6979?

poncho avatar
my flag
"hash-to-curve standard, which allows to produce uniformly random scalars"; actually, a hash-to-curve operation produces a point $H$ that no one knows the discrete log to (that is, no one knows the solution for $H=kG$). That's not what ECDSA needs.
ru flag
@poncho you’re wrong. The standard has methods for hashing to fields. See section 5. Hashing to ec point is irrelevant in this question.
poncho avatar
my flag
I'm sorry, I didn't realize that the hash-to-curve draft talked about hashing to things other than curves...
fgrieu avatar
ng flag
[Not all RFCs are standards](https://datatracker.ietf.org/doc/html/rfc1796); and the [draft RFC](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html) considered starts with "Intended Status: Informational", meaning it's not intended to become a standard.
Score:4
ng flag

Preliminary: no matter how good the method to generate the nonce $k$ in ECDSA is, it will not prevent LadderLeak, which is a side-channel attack independent on bias in the generation of $k$.

The technique in RFC draft-irtf-cfrg-hash-to-curve-16 section 5 can be adapted to generation of nonce $k$ in ECDSA instead of what RFC6979 recommends. The general sketch being that we generate nonce $k$ in range $[1,n)$, deterministically from the ECDSA private key† and hash of message being signed, where $n$ is the curve's order.

The RFC's method generates $m$ values in $[0,p)$ (by their notation), thus we'd want‡ to set $m=1\,$, $p=n-1$, and add $1$ to the one generated integer in $[0,p)$ to obtain nonce $k$ in $[1,n)$. We can do this by inserting a $+1$ as step 7 in the algorithm, making it $e_j=(\operatorname {OS2IP}(\mathrm{tv})\bmod p)+1$.

There's a certificational issue, that we can just ignore: the RFC's technique is intended to generate a field element, thus is stated for prime $p$, which would not be the case for $p=n-1$. However the RFC's technique happens to work unmodified for any $p>0$; it just does not generate a field element (it's stated goal).

Critically, whatever implementation of the RFC's techniques must not create a side channel (on the private key, or on the generated nonce $k$), which could allow an attack.

Regarding the acceptable bias in the generated nonce $k$ in ECDSA: rest assured there is no danger whatsoever in using $\mathtt{L}=48$ byte in the RFC when generating a nonce $k$ of 32 bytes (corresponding to security parameter of 128 bit in the RFC).

  • If we can't distinguish the generated nonce $k$ from random (which is the claim of the RFC), it's good enough for ECDSA without having to even think about what attack we consider (argument: whatever attack on ECDSA based on the bias on nonce $k$ would allow to build a distinguisher invalidating the RFC's security claim).
  • Actual adversaries are limited in the number of signatures they can obtain. Even $2^{64}$ is wildly unrealistic (especially if we consider the fact they must be for the same public/private key pair). Thus we could do with 64-bit security, and 128 is way overkill.

† No relation to the nonce $k$ designated in the question as "32-byte private key".

‡ Alternatively we could as well set $p=n$, and discount the probability that the nonce generated is zero by accident. It's however sensible to test against that at some point, and that must be in a side-channel proof way, including but not limited to constant time. If this condition triggers, either something is broken or we are under attack, and a sensible reaction is to zeroize all sensitive material, perhaps the private key.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.