Description

The EncSign function uses the private key and message to derive a deterministic nonce↗.

nonce := btcec.NonceRFC6979(
    privKeyBytes[:], msgHash, rfc6979ExtraDataV0[:], nil, iteration,
)

This results in the same nonce being used when producing adaptor signatures for the same message with different encryption keys, which allows recovering the signing key from a pair of adaptor signatures. This does not require the adaptor signatures to be decrypted into signatures first.

Due to the incorrect parity check in encVerify (see Finding ref↗), a variable number of iterations are used when producing signatures, and two messages only share a nonce if they are produced with the same number of signing iterations. Empirically, for random keys, two adaptor signatures share the same nonce approximately one third of the time, independently per message. If multiple adaptor signatures are generated with the same signing key and different encryption keys, the probability of recovering the signing key is the probability that any pair of adaptor signatures have the same iteration count, which increases combinatorially with the number of different encryption keys.

In Babylon's usage of adaptor signatures, the signing keys are covenant committee member keys, and the encryption keys are finality-provider keys.

Impact

The following function recovers the signing key used to produce two adaptor signatures if they have the same nonce.

func RecoverNonceReuse(pk *btcec.PublicKey, asig1, asig2 *AdaptorSignature, msgHash []byte) *btcec.PrivateKey {
    // Compute e1
    var r1Bytes [chainhash.HashSize]byte
    r1 := asig1.r.X
    r1.PutBytesUnchecked(r1Bytes[:])
    p1Bytes := schnorr.SerializePubKey(pk)
    commitment1 := chainhash.TaggedHash(chainhash.TagBIP0340Challenge, r1Bytes[:], p1Bytes, msgHash,)
    var e1 btcec.ModNScalar
    e1.SetBytes((*[32]byte)(commitment1))

    // Compute e2
    var r2Bytes [chainhash.HashSize]byte
    r2 := asig2.r.X
    r2.PutBytesUnchecked(r2Bytes[:])
    p2Bytes := schnorr.SerializePubKey(pk)
    commitment2 := chainhash.TaggedHash(chainhash.TagBIP0340Challenge, r2Bytes[:], p2Bytes, msgHash,)
    var e2 btcec.ModNScalar
    e2.SetBytes((*[32]byte)(commitment2))

    sHat1 := asig1.sHat // k + e1*d
    sHat2 := asig2.sHat // k + e2*d

    if asig1.needNegation {
        sHat1.Negate()
        e1.Negate()
    }
    if asig2.needNegation {
        sHat2.Negate()
        e2.Negate()
    }

    // deltaS = (k + e2*d) - (k + e1*d) = (e2 - e1) * d
    var deltaS btcec.ModNScalar
    deltaS.Add2(&sHat2, sHat1.Negate())

    // d = (e2 - e1)^{-1} * deltaS
    var recoveredSk btcec.ModNScalar
    recoveredSk.Add2(&e2, e1.Negate()).InverseNonConst().Mul(&deltaS)
    pkOdd := pk.SerializeCompressed()[0] == secp.PubKeyFormatCompressedOdd
    if pkOdd {
        recoveredSk.Negate()
    }
    return btcec.PrivKeyFromScalar(&recoveredSk)
}

We provided unit tests ref↗ to demonstrate the empirical key-recovery probabilities.

The first test shows that for a random key pair, a single pair of signatures lets the key be recovered approximately one third of the time. The second test shows that if each random key pair produces 10 pairs of signatures, almost all of the keys are recovered, showing that the success is independent per message. The third test shows that if the same message is encrypted to six different encryption keys and every subset is tested for key recovery, the probability of key recovery is higher than the second test.

Below is the output of these tests:

% go test -run TestAdaptorSigRecoverNonceReuse
Individual message successes: 334
Independent message successes: 980
Combinatorial message successes: 999
PASS
ok      github.com/babylonlabs-io/babylon/crypto/schnorr-adaptor-signature      12.064s

Below is the output from a test ref↗ which shows key recovery succeeding on output from a btc-delegations query:

% go test -run TestAdaptorSigRecoverNonceReuseData
recoveredSk &{565feb0e755175ad7832950aa8b1f7ecfb8631e3fd37f359299ad0e2431fb69e}
recoveredPk 2d4ccbe538f846a750d82a77cd742895e51afcf23d86d05004a356b783902748
covenantPk  2d4ccbe538f846a750d82a77cd742895e51afcf23d86d05004a356b783902748
PASS
ok      github.com/babylonlabs-io/babylon/crypto/schnorr-adaptor-signature      0.417s

Recommendations

Use the encryption key as an input to the nonce derivation, similar to the reference implementation↗ of adaptor signatures, for example by using a hash of a serialization of encKey and msgHash (and possibly pubKeyBytes, to match X in the reference implementation) instead of just msgHash.

Additionally, using a more specific value than sha256("BIP-340") for rfc6979ExtraDataV0↗ (such as sha256("BIP-340/babylon-adaptor-signature") would decrease the risk of nonce reuse if the signing keys are reused with another BIP-340 implementation.

Remediation

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