By Jonas Nick and Tim Ruffing
The Blockstream Research team have produced a solution for protecting users of the MuSig multisignature scheme against key exfiltration attacks due to bad random number generators and virtual machine reset attacks. This is achieved through a combination of zero-knowledge proofs and Purify, an efficient deterministic nonce-derivation function.
Multisignatures and MuSig
Multisignature schemes allow a group of signers, each having their own key pair, to collaboratively compute a signature on a common message. Bitcoin Script supports multisignatures to distribute control over a coin through the OP_CHECKMULTISIG instruction. Today, this is used in applications such as increasing the robustness of Bitcoin custody, setting up Lightning Network channels, and managing bitcoin on the Liquid sidechain.
In 2018 we proposed the n-of-n multisignature scheme MuSig in collaboration with Yannick Seurin (ANSSI, France). When used in Bitcoin, MuSig offers tremendous advantages over OP_CHECKMULTISIG. Since a signature created via MuSig is simply a normal Schnorr signature, the blockchain footprint of MuSig is indistinguishable from normal, single signatures which increases privacy and reduces transaction fees. Before MuSig can be used, Bitcoin needs to add support for Schnorr signatures, which is currently proposed as part of the “Taproot” soft fork.
Randomness and Determinism
Every Schnorr or ECDSA signature needs a “nonce,” a secret random number generated by the signer. The security of these signatures schemes relies heavily on the uniform random generation of this nonce, and even slight biases in the randomness can make it possible for an attacker to extract the secret key from signatures. A simple and extreme example of bad randomness, which must never occur in practice is reusing a nonce for different messages. If the exact same nonce is generated for two different signatures that sign two different messages with the same secret key, this secret key can immediately be computed from the two signatures, and attacks exploiting this weakness have been performed in the wild.
In order to avoid this fragility in the signing process, it is common to use deterministic nonces, e.g., derived using a hash function as nonce = SHA256(sk, m) or through RFC6979, where sk is the secret key of the signer and m is the message to be signed. Since an attacker does not know sk, the resulting nonce remains unpredictable, even though it is actually derived from a deterministic computation instead of real randomness. As m is part of the input to the hash functions, signatures on different messages will use different nonces, which excludes nonce reuse for different messages. Deterministic nonces also protect against rewinding attacks, in which the attacker tries to obtain signatures with the same nonce on two different messages by resetting the signing algorithm, for example, if it runs in a virtual machine (VM). As a side benefit, deterministic nonce generation allows us to easily test implementations of the signature algorithm in a black-box manner using test vectors.
Due to these advantages, it is a no-brainer to use deterministic nonces when generating signatures, and virtually all serious implementations of signatures rely on some method to derive nonces deterministically. When it comes to multisignatures however, deterministic nonces do not protect from exposing the secret key if they are used naively. Surprisingly, the exact opposite is true: as we described in the original MuSig blog post, an implementation of MuSig with deterministic nonces is vulnerable to exposure of the secret key.
The attack works as follows. A malicious signer engages in two signing sessions with the victim signing for the same message. Since the message is the same in both sessions, the victim generates the exact same nonce deterministically. But nothing in MuSig forces the other malicious signer to generate his nonce deterministically. The malicious signer can just use arbitrary nonces and as a result, the “aggregate nonce” (computed from the nonces of all signers) will be different in both signing sessions. Having different aggregate nonces has the same effect as having different messages: if the victim re-uses her nonce for different aggregate nonces, an attacker can easily extract the victim’s secret key from the signatures. While this attack could be mitigated by adding an increment-only counter to the nonce derivation function, it can be very difficult or even nearly impossible to implement such a counter securely, e.g., when the signing process is run in a VM.
Musig-DN: Rescuing Determinism
Developed in collaboration with our brilliant research colleague Yannick Seurin, MuSig-DN (MuSig with Deterministic Nonces) is our proposal to overcome these difficulties and use secure deterministic nonces in MuSig. The main idea behind MuSig-DN is to use zero-knowledge proofs to enforce that all signers generate their nonces deterministically. Each signer derives a deterministic nonce from an additional secret key (that we call nonce key), the message, and all signers’ public keys. Then the signers communicate their public nonces in the first round of MuSig-DN along with non-interactive zero-knowledge proofs that demonstrate that their public nonces have been derived correctly. These proofs can be checked by all other signers using additional public keys (that we call host keys) associated with the nonce keys of the signers. If any signer tries to cheat by sending two different nonces in different signing sessions, other signers will detect it (because at least one of the two nonces will have an invalid zero-knowledge proof) and simply abort the protocol.
The other main contribution of MuSig-DN is Purify, a specific function to derive the nonce. As opposed to hash functions such as SHA256, which are typical choices for deriving deterministic nonces, Purify is optimized to be used within zero-knowledge proofs. To this end, Purify relies on elliptic curves to extract random-looking nonces. The most computationally intensive part of evaluating the Purify function is two scalar multiplications in elliptic curves that are each other’s quadratic twist. Purify can be used efficiently with zero-knowledge proof frameworks such as Bulletproofs that natively support secret input scalars. The main part of Purify is an arithmetic circuit with low multiplicative complexity that performs two scalar multiplications in curves defined over integers modulo the order group in which signatures are defined.
The arithmetic circuit corresponding to Purify for Schnorr signatures on a 256-bit curve such as secp256k1 (as proposed in the Taproot softfork) has 2030 multiplication gates. The size of a bulletproof created with libsecp256k1-zkp for this arithmetic circuit is 1124 bytes. On an Intel i7 system pinned to 2.90 GHz proving takes 943 ms and (non-batch) verification takes 50 ms.
We suggest that the same techniques to make multisignatures deterministic can be used to verifiably encrypt discrete logarithms to a third party. For example, this can be used in the Lightning Network to implement an escrow agent that is unaware of a transaction as long as buyer and seller cooperate.
A very nice additional property of MuSig-DN is that a signing session needs only two communications rounds to complete, whereas MuSig and other previous multisignature protocols based on Schnorr signatures require three rounds. But if all you need is a round-efficient signing protocol, and you do not require the additional protection offered by deterministic nonces, we have a much simpler solution in mind. We are currently working on MuSig2, which is supposed to be the successor of MuSig. It only needs two rounds of communication without requiring zero-knowledge proofs. By preprocessing the first of the two rounds, a signing session can even be optimized to need effectively only a single round. Stay tuned.
Conclusion
The MuSig-DN paper is to appear at the 2020 ACM Conference on Computer and Communications Security. Read the full paper here.
If you want to play around with MuSig-DN and Purify, we provide python scripts to generate arithmetic circuits for various curves. There is also an experimental branch of libsecp256k1-zkp that uses Bulletproofs to prove and verify Purify arithmetic circuits in zero-knowledge.
Stay tuned.
Note: This blog was originally posted at https://medium.com/blockstream/anti-exfil-stopping-key-exfiltration-589f02facc2e