By Jonas Nick

Introduction

BIP-Schnorr is a Bitcoin Improvement Proposal that suggests a new signature scheme to replace the ECDSA scheme currently used in Bitcoin. Due to a simpler mathematical structure, Schnorr signatures allow simpler compact multisignature transactions, reducing transaction sizes and offering many privacy improvements.

Using BIP-Schnorr-based multisignatures, no matter how many signers are involved, the result is a single public key and a single signature indistinguishable from a regular, single-signer BIP-Schnorr signature.

This article is about optimizing implementations of multisignature protocols and why seemingly harmless changes can totally break the security. Creating BIP-Schnorr-based multisignatures involves multiple communication rounds. In practice, the engineering challenges associated with interactions between signers should be reduced as much as possible.

However, we will see how a simple optimization — committing to the message later in the protocol — opens the door for a Wagner’s attack and signature forgery. Still, secure shortcuts do exist and are implemented in Blockstream’s secp256k1-zkp cryptographic library such that misuse is almost impossible.

Background

MuSig is a compact multisignature scheme compatible with BIP-Schnorr. It allows the aggregation of several public keys into a single public key. For example, recall that cooperatively closing a Lightning channel involves two signature verifications, one for each public key. With MuSig, the channel participants create a single, combined public key and later also only need to create a single Schnorr signature to spend it.

Given a public key and a message, signing for a MuSig-aggregated public key consists of three communication rounds between participants i.

Similar to regular Schnorr-signing creating a partial MuSig for participanti requires computing random nonces Ri = ki*G for a random ki and group generator G. But before giving Ri to the other signers, the participants exchange commitments Ri (e.g. with SHA256) in the first round. In the second round, every node i reveals its public nonceRi to everyone else. The combined public nonce R is the sum of the individual nonces. Lastly, every signer creates a partial signature with the secret key x similar to single-signing. The difference is that in addition to combined public key P and message m the signature commits to the combined public nonce R instead of an individual nonce. If everything went correctly, the combined nonce and the sum of partial signatures is a Schnorr signature on message m for the MuSig-aggregated public keyP.

Pre-shared nonces in MuSig

Having to go through the three rounds every time we want to sign a message is certainly inconvenient. Especially if the signature is time-critical and network messages are slow. So how about this, we do the first two rounds whenever it’s convenient for us. And only once there is a message to sign, we exchange partial signatures. In the case of Lightning, for example, the channel peers exchange a bunch of nonce commitments and nonces immediately when establishing a connection. When it comes to signing a channel update, one of the pre-shared nonces is used and only one communication round is required to complete the signature. THIS IS INSECURE.

So what’s the difference exactly to normal MuSig? What goes into the hash are the public nonce, the public key, and the message m. The public nonce and public key are unbiased because they consist of every individual’s contribution. However, we assume that the message m is under the control of the attacker. Without pre-sharing nonces, this is not a problem because the attacker has to choose the message in the beginning, before knowing what the combined public nonce will look like. Therefore the output of the hash function is also unbiased.

Now with pre-shared nonces, the attacker can choose the message after the combined public nonce is known and is therefore able to bias the hash function. Obviously, a computationally bounded attacker doesn’t have full control over the output of the hash function. But the attacker could enforce that a specific bit is set to 0 in the hash by just trying a couple of different values for m (two tries are expected).

Attacking pre-shared nonces

Let’s move on to look at the concrete attack. Assume the attacker has an aggregated public key with the victim and opens four parallel signing sessions with the victim. Each session will produce a regular Schnorr signature for the aggregated public key. The goal of the attacker is to also get a signature on a message m which has never been signed by the victim. In each session, they go through the first two rounds and the attacker collects the combined nonces from each session, as depicted in the diagram below. Note that the superscripts refer to the individual signing sessions. Then the attacker computes its own nonce R’, which is going to be used for the forgery as the sum of the session combined nonces.

Now what the attacker has to do is find one message for each session such that the hash of his nonce, the public key, and his chosen message is equal to the sum of the individual round hashes.

Is this hard? It looks hard. It looks like you would need some kind of hash collisions, which would be hard. But it’s not hard. The equation can be solved efficiently with Wagner’s algorithm. With four parallel sessions, it would take on the order of about 2⁸⁷ many operations to find a solution. But if the attacker would open 32,000 parallel sessions, solving the generalized birthday problem would only require on the order of 2³² many operations.

Wagner’s algorithm works by generating lists of hashes and efficiently comparing them to recursively find pairs whose addition results in sub-strings matching target hash sub-strings. Have a look at the Equihash paper by Biryukov and Khovratovich for a slightly more concise algorithm than in Wagner’s paper. Let’s continue with the above example on secp256k1 with four parallel sessions and assuming for simplicity that our Generalized Birthday Problem is modulo 2²⁵⁶ and not the prime group order. Wagner’s algorithm creates four lists (one for every term), each with 2⁸⁶ hashes from different messages. Then it creates a new list by finding pairs from list 1 and list 2 such that the 86 least significant bits (LSB) of the sum match the 86 LSBs of the target hash. The new list will have 2⁸⁶ elements. Similarly, lists 3 and 4 are combined into a new list but with the 86 LSBs being 0s. Then the two resulting lists are compared to find a match with the target hash. The expected number of matches given the lists’ length is about 1. Thus, the amount of work in Wagner’s algorithm is far less than the 2¹²⁸ expected operations required for finding collisions. Observe that Wagner’s algorithm relies on being able to solve for sub-strings independently, which does not work with secp256k1 point addition, for example (otherwise the discrete logarithm assumption would be broken).

After the attacker found such m0, m1, m2, m3 the attacker provides them in their corresponding sessions.

The victim proceeds with round three and returns the partial signatures in each session, which are then completed by the attacker. Now it turns out that the sum of the session nonces and the sum of session signatures is a Schnorr signature forgery on a message that the victim has never seen. Verifying that the math checks out is left as an exercise to the reader.

Pre-sharing nonce commitments

There is one variant of pre-sharing that works: you only prepare the exchange of nonce commitments, and when there is a message to sign you exchange the nonces. This still saves one round trip on the critical path.

In contrast to pre-sharing nonces, the output of the hash function is unbiased because the message must be chosen before the public nonces Ri are revealed.

Conclusion

Unfortunately, some useful shortcuts in MuSig are insecure because the Generalized Birthday Problem can be solved efficiently with Wagner’s algorithm. It’s also the reason why there’s a nonce commitment round in MuSig in the first place and why Blind Schnorr Signatures — when implemented naively — are insecure. These attacks are similar to what we’ve discussed above and also make use of parallel sessions.

Blockstream’s MuSig implementation in libsecp-zkp allows pre-sharing nonce-commitments and enforces the correct order of operations to prevent any Wagner’s attack. It should be very difficult to misuse. However, the MuSig module is still experimental, and anyone is welcome to play with it or try to break it.

Note: This blog was originally posted at https://medium.com/blockstream/insecure-shortcuts-in-musig-2ad0d38a97da