From: Jonas Nick <jonasdnick@gmail.com>
Message-ID: <576db60c-b05b-5b9a-75e5-9610f3e04eda@gmail.com>
Date: Tue, 11 Oct 2022 15:34:23 +0000
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.3.1
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
References: <46175970-d2ab-a58e-7010-f29820849604@gmail.com>
 <6d823ec7-fe88-9311-09e8-be22ca8bfd89@gmail.com>
Content-Language: en-US
In-Reply-To: <6d823ec7-fe88-9311-09e8-be22ca8bfd89@gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [bitcoin-dev] MuSig2 BIP
Precedence: list

It is still true that cryptography is hard, unfortunately. Yannick Seurin, Tim
Ruffing, Elliott Jin, and I discovered an attack against the latest version of
BIP MuSig2 in the case that a signer's individual key A = a*G is tweaked before
giving it as input to key aggregation.

In more detail, a signer may be vulnerable if _all_ of the following conditions
are true:

1. The signer supports signing with a tweaked individual key (as provided to
    key aggregation) and the tweak is known to the attacker (e.g., as in BIP 32
    unhardened derivation).
2. The signer's public key appears at least two times with different tweaks in
    the set of public keys that are aggregated. This would, for example, be the
    case if a signer with public key A=a*G creates partial signatures for an
    aggregate key corresponding to public key set {A, A+t*G} where t is some
    tweak. Note that an attacker could make this condition true by using the key
    B = A+t*G after having seen A.
3. The signer uses "concurrent signing", i.e., the signer stores secnonces for
    multiple signing sessions.
4. The secret key provided to the Sign algorithm is not yet fully determined when the
    NonceGen algorithm is called. This would, for example, be the case if the
    attacker, after having seen the nonce of the signer, can influence whether a
    or a+t will be provided as a secret key to Sign.

In this scenario, an attacker may forge a signature for any message and any
aggregate public key that contains the signer's individual public key A (with
any attacker-chosen tweak). In particular, the attacker may forge a signature
for any message and the public key A itself.

Condition 4 should only apply in relatively rare cases unless the signer is
tricked into such a situation.

Fix:
Note that if the optional secret key argument is provided to the NonceGen
algorithm and matches the secret key provided to the Sign algorithm, then
Condition 4 will not hold. Thus, one definite fix is to make the secret key
argument to the NonceGen algorithm mandatory. We are investigating other options
and will follow up shortly with a concrete fix of the BIP draft.

This discovery does not invalidate the security proof of the scheme as presented
in the MuSig2 paper because the security model in the paper does not support
tweaking a signer's key.

If you've implemented the BIP draft in your library or are already using it in
production don't hesitate to reach out to clarify the implications of this
discovery.

Tim Ruffing, Elliott Jin, Jonas Nick