Subject: Re: [bitcoin-dev] Proposal: Bitcoin Secure Multisig Setup

From: Hugo Nguyen <[email-masked]>
Date: Mon, 15 Feb 2021 00:44:19 -0800

Hi all,
I have updated the proposal based on further feedback. The new spec is
included at the bottom.

I have also created a public Github PR to make it easier to comment on the
text of the spec itself: https://github.com/nunchuk-io/bips/pull/1 .

Could someone please let me know what else needs to be done before a BIP
number can be assigned?

=== Quick summary of changes from last update ===

1. Define encryption modes

# NO_ENCRYPTION: Encryption is disabled.
# STANDARD : the TOKEN is a 64-bit nonce.
# EXTENDED : the TOKEN is a 128-bit nonce.

2. Define signature algorithm

Follow BIP-0322, legacy format allowed.

3. Multiple TOKENs (optional)

Also add an option where the Coordinator can choose to use one common TOKEN
for all Signers, or use one per Signer.

=== End of summary ===

Cheers,
Hugo

<pre>
  BIP: To be determined
  Layer: Applications
  Title: Bitcoin Secure Multisig Setup (BSMS)
  Author: Hugo Nguyen <hugo at nunchuk.io>, Peter Gray <peter at
coinkite.com>, Marko Bencun <marko at shiftcrypto.ch>, Pavol Rusnak <
[email-masked]>, Aaron Chen <aarondongchen at gmail.com>, Rodolfo
Novak <rodolfo at coinkite.com>
  Comments-Summary: No comments yet.
  Comments-URI:
  Status: Proposed
  Type: Standards Track
  Created: 2020-11-10
  License: BSD-2-Clause
</pre>

==Introduction==

===Abstract===

This document proposes a mechanism to set up multisig wallets securely.

===Copyright===

This BIP is licensed under the 2-clause BSD license.

===Motivation===

The Bitcoin multisig experience has been greatly streamlined under [
https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki BIP-0174
(Partially Signed Bitcoin Transaction)]. However, what is still missing is
a standardized process for setting up multisig wallets securely across
different vendors.

There are a number of concerns when it comes to setting up a multisig
wallet:

# Whether the multisig configuration, such as Signer membership, script
type, derivation paths and number of signatures required, is correct and
not tampered with.
# Whether Signer persists the multisig configuration in their respective
storage, and under what format.
# Whether Signer's storage is tamper-proof.
# Whether Signer subsequently uses the multisig configuration to generate
and verify receive and change addresses.

An attacker who can modify the multisig configuration can steal or hold
funds to ransom by duping the user into sending funds to the wrong address.

This proposal seeks to address concerns #1 and #2: to mitigate the risk of
tampering during the initial setup phase, and to define an interoperable
multisig configuration format.

Concerns #3 and #4 should be handled by Signers and is out of scope of this
proposal.

==Specification==

===Prerequisites===
This proposal assumes the parties in the multisig support [
https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP-0032], [
https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md the
descriptor language] and encryption.

===Roles===
====Coordinator====

The Coordinator initiates the multisig setup. The Coordinator determines
what type of multisig is used and the exact policy script. If encryption is
enabled, the Coordinator also distributes a shared secret or shared secrets
to the parties involved for secure communication. The Coordinator gathers
information from the Signers to generate a descriptor record. The
Coordinator distributes the descriptor record back to the Signers.

====Signer====

The Signer is a participating member in the multisig. Its responsibilities
include providing its key record -- which contains an Extended Public Key
(XPUB) -- to the Coordinator, verifying that its XPUB is included in the
descriptor record and persisting the descriptor record in its storage.

===Setup Process===

====Round 1====

=====Coordinator=====

* The Coordinator creates a multisig wallet creation session. The
Coordinator constructs the multisig script and its policy parameters, such
as the total number of signers and the required number of signatures
(<tt>M</tt> and <tt>N</tt>).
* The session should expire after some time period determined by the
Coordinator, e.g., 24 hours.
* If encryption is enabled, the Coordinator distributes a secret
<tt>TOKEN</tt> to each Signer over a secure channel. The Signer can use the
<tt>TOKEN</tt> to derive an <tt>ENCRYPTION_KEY</tt>. Refer to the
Encryption section below for details on the <tt>TOKEN</tt>, the key
derivation function and the encryption scheme. Depending on the use case,
the Coordinator can decide whether to share one common <tt>TOKEN</tt> for
all Signers, or to have one per Signer.
* If encryption is disabled, <tt>TOKEN</tt> is set to <tt>0</tt>, and all
the encryption/decryption steps below can be skipped.

=====Signer=====

* The Signer initiates a new secure multisig setup session by setting the
<tt>TOKEN</tt>. The Signer derives an <tt>ENCRYPTION_KEY</tt> from the
<tt>TOKEN</tt>. The Signer can keep the session open until a different
value for the <tt>TOKEN</tt> is set.
* The Signer generates a key record by prompting the user for a multisig
derivation path and retrieves the XPUB at that derivation path. Optionally,
the Signer can choose a path on behalf of the user. If the Signer chooses
the path, it should try to avoid reusing XPUBs for different wallets.
* The first line in the record must be the <tt>TOKEN</tt>. The second line
must be the <tt>KEY</tt>. The <tt>KEY</tt> is an XPUB plus its key origin
information, written in the descriptor-defined format, i.e.: <tt>[{master
key fingerprint}/{derivation path}]{XPUB}</tt>. The third line must be a
<tt>SIG</tt>, whereas <tt>SIG</tt> is the signature generated by using the
private key associated with the XPUB to sign the first two lines.  The
signature should follow [
https://github.com/bitcoin/bips/blob/master/bip-0322.mediawiki BIP-0322],
legacy format accepted. Finally, the Signer encrypts the entire record with
<tt>ENCRYPTION_KEY</tt>.

====Round 2====

=====Coordinator=====

* The Coordinator gathers key records from all participating Signers. Abort
the setup if the wallet setup session has expired.
* For each key record, the Coordinator decrypts it using
<tt>ENCRYPTION_KEY</tt>. The Coordinator verifies that the included
<tt>SIG</tt> is valid given the <tt>KEY</tt>.
* If all key records look good, the Coordinator fills in all necessary
information to generate a descriptor record, which is simply the descriptor
string plus a <tt>CHECKSUM</tt>, all in one line. The <tt>CHECKSUM</tt> has
[https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#checksums
BECH32 encoding].
* The Coordinator encrypts this descriptor record with
<tt>ENCRYPTION_KEY</tt>.
* The Coordinator sends the encrypted descriptor record to all
participating Signers.

=====Signer=====

* The Signer imports the descriptor record, decrypts it using the
<tt>ENCRYPTION_KEY</tt> derived from the open session.
* The Signer calculates and verifies the descriptor’s <tt>CHECKSUM</tt>.
Abort the setup if the <tt>CHECKSUM</tt> is incorrect.
* The Signer checks whether one of the <tt>KEY</tt>s in the descriptor
belongs to it, using path and fingerprint information included in the
descriptor. The check must perform an exact match on the <tt>KEY</tt>s, and
not using shortcuts such as matching fingerprints (which is trivial to
spoof). Abort the setup if it doesn’t detect its own <tt>KEY</tt>.
* For confirmation, the Signer must display to the user the
<tt>CHECKSUM</tt>, plus other configurations, such as <tt>M</tt> and
<tt>N</tt>. The total number of Signers, <tt>N</tt>, is important to
prevent a <tt>KEY</tt> insertion attack. All participating Signers should
be able to display the same confirmation.
* If all checks pass, the Signer persists the descriptor record in its
storage.
* The Signer can choose to further restrict post-XPUB derivation paths,
such as to those defined in [
https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki BIP-0044].
* The Signer should subsequently use the descriptor to generate and verify
receive and change addresses.

This completes the setup.

===Encryption===

====The Token====
We define three modes of encryption.

# <tt>NO_ENCRYPTION</tt> : the <tt>TOKEN</tt> is set to <tt>0</tt>.
Encryption is disabled.
# <tt>STANDARD</tt> : the <tt>TOKEN</tt> is a 64-bit nonce.
# <tt>EXTENDED</tt> : the <tt>TOKEN</tt> is a 128-bit nonce.

The <tt>TOKEN</tt> can be converted to one of these formats:
* A mnemonic phrase using [
https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki BIP-0039]
word list (6 words in <tt>STANDARD</tt> mode, 12 words in <tt>EXTENDED</tt>
mode)
* A decimal number (20 digits in <tt>STANDARD</tt> mode, 40 digits in
<tt>EXTENDED</tt> mode)
* A QR code
* Other formats

The flexibility in the data format allows each Signer to customize the User
Experience based on its respective capabilities.

====Key Derivation====
The key derivation function is [https://tools.ietf.org/html/rfc2898
PBKDF2], with PRF = SHA512. Specifically:

<tt>DK = PBKDF2(PRF, Password, Salt, c, dkLen)</tt>

Whereas:

* PRF = <tt>SHA512</tt>
* Password = <tt>"No SPOF"</tt>
* Salt = <tt>TOKEN</tt>
* c = <tt>2048</tt>
* dkLen = <tt>256</tt>
* DK = Derived <tt>ENCRYPTION_KEY</tt>

====Encryption Scheme====
The encryption scheme is [https://tools.ietf.org/html/rfc3686 AES, CTR
mode].

==QR Codes==
For signers that use QR codes to transmit data, key and descriptor records
can be converted to QR codes, following [
https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-005-ur.md
the BCR standard].

Also refer to [
https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-015-account.md
UR Type Definition for BIP44 Accounts] and [
https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-010-output-desc.md
UR Type Definition for Bitcoin Output Descriptors] for more details.

==Security==

This proposal introduces two layers of protection. The first one is a
temporary, secret token, used to encrypt the two rounds of communication
between the Signer and the Coordinator. The second one is through the
descriptor checksum and visual inspection of the descriptor itself.

The token is only needed during the setup phase, and can be safely thrown
away afterwards. The token does not guarantee that the Signer membership
set is not modified, since that depends on the overall security of all
parties in the setup, but it can make it significantly harder for an
attacker to do so.

There are three ways an attacker can modify the membership set: by changing
an existing member, by removing an existing member, or by adding a new
member.

For the first two methods, one of the Signers will be able to detect that
its membership has been changed or removed, and reject the final
descriptor. Thus, it is vital that all participating Signers check that
their membership is intact in the descriptor. Even one Signer failing to
check for its membership means that the setup could be compromised.

For the third type of attack, the descriptor checksum and visual inspection
of the descriptor itself are the only way to guard against malicious
members from being inserted into the set.

==Acknowledgement==

Special thanks to Dmitry Petukhov, Christopher Allen, Craig Raw and others
for their feedback on the specification.

==References==

Original mailing list thread:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-February/018385.html