Description

The eotsmanager's GenerateRandomness↗ function, which generates nonces for extractable one-time signatures (EOTS), uses SetByteSlice without checking the return value, which indicates when an overflow modulo the Secp256k1 group order $n$ occurs.

func GenerateRandomness(key []byte, chainID []byte, height uint64) (*eots.PrivateRand, *eots.PublicRand) {
    // calculate the randomn hash of the key concatenated with chainID and height
    digest := hmac.New(sha256.New, key)
    digest.Write(append(sdk.Uint64ToBigEndian(height), chainID...))
    randPre := digest.Sum(nil)

    // convert the hash into private random
    var randScalar btcec.ModNScalar
    randScalar.SetByteSlice(randPre)
    privRand := secp256k1.NewPrivateKey(&randScalar)
    var j secp256k1.JacobianPoint
    privRand.PubKey().AsJacobian(&j)

    return &privRand.Key, &j.X
}

Since randPre is the output of HMAC-SHA-256, it is a uniformly random value in $\left[0,2^{256}\right)$, and overflow occurs when it is in the range $\left[n,2^{256}\right)$, which happens with probability approximately $2^{-128}$. This results in randScalar having a biased non-uniform distribution over $\left[0,n\right)$, since values in the range $\left[0,2^{256}-n\right)$ are twice as likely to occur as values in the range $\left[2^{256}-n,n\right)$.

Impact

Since this overflow only occurs with probability $2^{-128}$, it is unlikely to occur even once in practice. Samples where the overflow occurs have at least 128 leading zeroes, which makes them useful for recovering the EOTS private key via algorithms for the Hidden Number Problem (such as those mentioned in ref↗), but multiple such samples are required, and determining whether the overflow occurred is not efficiently computable from the public randomness R of a signature.

Recommendations

Add an iteration count to the HMAC and loop if an overflow occurs, in order to get a uniformly random value for randScalar via rejection sampling.

Remediation

This issue has been acknowledged by Babylon Labs, and a fix was implemented in commit 7de1a748↗.