2
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ "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. $\endgroup$
    – poncho
    Feb 23, 2023 at 14:21
  • $\begingroup$ @poncho you’re wrong. The standard has methods for hashing to fields. See section 5. Hashing to ec point is irrelevant in this question. $\endgroup$ Feb 23, 2023 at 14:40
  • $\begingroup$ I'm sorry, I didn't realize that the hash-to-curve draft talked about hashing to things other than curves... $\endgroup$
    – poncho
    Feb 23, 2023 at 14:58
  • 1
    $\begingroup$ Not all RFCs are standards; and the draft RFC considered starts with "Intended Status: Informational", meaning it's not intended to become a standard. $\endgroup$
    – fgrieu
    Feb 23, 2023 at 16:41

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.