Adding xpub field to PSBT to make multisig more secure

Hi list,

I was looking at the bip174 PSBT specs, in particular for multisignature setup, and I think with current spec there is a way to steal user funds in M of N setup with M ≤ N/2.

I made a small write-up on this: https://github.com/stepansnigirev/random_notes/blob/master/psbt_multisig.md

To compress:

Currently in PSBT there is no way to reliably say if the output uses the keys derived from the same root keys as the inputs aside from the key owned by the signer => there is no way to verify that the output is a change output in multisig setup.

Therefore an attacker can replace half of the keys in the change address by his own keys and still get the transaction signed.

I suggest to add an xpub field to the inputs and outputs metadata, then signers can verify that the same xpubs are used for public keys in inputs and outputs => output is indeed a change.

Normally change and receiving addresses are derived from the same xpub with non-hardened derivation pathes, so providing xpub after the last hardened index should be enough to see that public keys of inputs and change output are derived from the same xpub.

I suggest to add the following key-value pairs to PSBT:

Type: BIP 32 public key `PSBT_IN_BIP32_XPUB = 0x10`
- Key: derivation path for xpub
  `{0x10}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
- Value: 78-byte xpub value
  `{xpub}`

Type: BIP 32 public key `PSBT_OUT_BIP32_XPUB = 0x03`
- Key: derivation path for xpub
  `{0x03}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
- Value: 78-byte xpub value
  `{xpub}`

Derivation paths are in the key of the key-value pair as they are used for lookup, and xpub itself is the actual value being looked up.

I also want to mention that Trezor for example doesn't suffer from this problem as they use xpubs to verify change outputs. So it may make sense to go through the communication protocols of existing hardware / multisignature wallets and see if there is something else we are missing.

If everyone is happy about the proposal I would prepare a pull request to the bip.

Best regards, Stepan Snigirev.

Hi Stepan,

I think that this would be a good extension.

Just for clairty, by xpub, do you mean the extended serialization format defined in BIP 32 or the Base58 check encoded string of that serialization?

Andrew

On 4/26/19 11:21 AM, Stepan Snigirev via bitcoin-dev wrote:

> Hi list,
>
> I was looking at the bip174 PSBT specs, in particular for
> multisignature setup, and I think with current spec there is a way to
> steal user funds in M of N setup with M ≤ N/2.
>
> I made a small write-up on this:
> https://github.com/stepansnigirev/random_notes/blob/master/psbt_multisig.md
>
> To compress:
>
> Currently in PSBT there is no way to reliably say if the output uses
> the keys derived from the same root keys as the inputs aside from the
> key owned by the signer => there is no way to verify that the output
> is a change output in multisig setup.
>
> Therefore an attacker can replace half of the keys in the change
> address by his own keys and still get the transaction signed.
>
> I suggest to add an xpub field to the inputs and outputs metadata,
> then signers can verify that the same xpubs are used for public keys
> in inputs and outputs => output is indeed a change.
>
> Normally change and receiving addresses are derived from the same xpub
> with non-hardened derivation pathes, so providing xpub after the last
> hardened index should be enough to see that public keys of inputs and
> change output are derived from the same xpub.
>
> I suggest to add the following key-value pairs to PSBT:
>
> Type: BIP 32 public key `PSBT_IN_BIP32_XPUB = 0x10`
> - Key: derivation path for xpub
>   `{0x10}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
> - Value: 78-byte xpub value
>   `{xpub}`
>
> Type: BIP 32 public key `PSBT_OUT_BIP32_XPUB = 0x03`
> - Key: derivation path for xpub
>   `{0x03}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
> - Value: 78-byte xpub value
>   `{xpub}`
>
> Derivation paths are in the key of the key-value pair as they are used
> for lookup, and xpub itself is the actual value being looked up.
>
> I also want to mention that Trezor for example doesn't suffer from
> this problem as they use xpubs to verify change outputs. So it may
> make sense to go through the communication protocols of existing
> hardware / multisignature wallets and see if there is something else
> we are missing.
>
> If everyone is happy about the proposal I would prepare a pull request
> to the bip.
>
> Best regards,
> Stepan Snigirev.
>

On Fri, Apr 26, 2019 at 05:21:06PM +0200, Stepan Snigirev wrote: ...

> Currently in PSBT there is no way to reliably say if the output uses the
> keys derived from the same root keys as the inputs aside from the key owned

Writing the multisig support for Coldcard, I've come to the same conclusion. I've exchanged some helpful mail with Andrew Chow on this subject.

...

> I suggest to add the following key-value pairs to PSBT:
> Type: BIP 32 public key `PSBT_IN_BIP32_XPUB = 0x10`

...

> Type: BIP 32 public key `PSBT_OUT_BIP32_XPUB = 0x03`

I'd rather see the xpubs shared in the global section of the file, with the restriction that they must/should only include the hardened prefix of the path. The existing bip32 derivation path included in individual inputs and outputs be merged in as needed.

After all in a typical PSBT, we would expect the same master keys to be used on all inputs, and at least one output, and there might be as many as 20 co-signers. No need to repeat all that information.

Even with this additions to the PSBT format, I think PSBT-signing devices still need to store the xpubs of their co-signers. It's not possible to safely show an incoming address to the user without a full understanding of the other keys in a "multisig wallet". Also, it represents data that should not change between PSBT instances (ie. tomorrow's co-signers should match today's).

Having said that, the xpubs in the PSBT would allow a "trust on first use" which I think can be a good feature.

---
Peter D. Gray  ||  Founder, Coinkite  ||  Twitter: @dochex  ||  GPG: A3A31BAD 5A2A5B10

> Hi list,
>
> I was looking at the bip174 PSBT specs, in particular for multisignature
> setup, and I think with current spec there is a way to steal user funds in
> M of N setup with M ≤ N/2.
>
> I made a small write-up on this:
> https://github.com/stepansnigirev/random_notes/blob/master/psbt_multisig.md
>
> To compress:
>
> Currently in PSBT there is no way to reliably say if the output uses the
> keys derived from the same root keys as the inputs aside from the key owned
> by the signer => there is no way to verify that the output is a change
> output in multisig setup.
>
> Therefore an attacker can replace half of the keys in the change address by
> his own keys and still get the transaction signed.
>
> I suggest to add an xpub field to the inputs and outputs metadata, then
> signers can verify that the same xpubs are used for public keys in inputs
> and outputs => output is indeed a change.
>
> Normally change and receiving addresses are derived from the same xpub with
> non-hardened derivation pathes, so providing xpub after the last hardened
> index should be enough to see that public keys of inputs and change output
> are derived from the same xpub.
>
> I suggest to add the following key-value pairs to PSBT:
>
> Type: BIP 32 public key `PSBT_IN_BIP32_XPUB = 0x10`
> - Key: derivation path for xpub
>   `{0x10}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
> - Value: 78-byte xpub value
>   `{xpub}`
>
> Type: BIP 32 public key `PSBT_OUT_BIP32_XPUB = 0x03`
> - Key: derivation path for xpub
>   `{0x03}|{master key fingerprint}|{32-bit int}|...|{32-bit int}`
> - Value: 78-byte xpub value
>   `{xpub}`
>
> Derivation paths are in the key of the key-value pair as they are used for
> lookup, and xpub itself is the actual value being looked up.
>
> I also want to mention that Trezor for example doesn't suffer from this
> problem as they use xpubs to verify change outputs. So it may make sense to
> go through the communication protocols of existing hardware /
> multisignature wallets and see if there is something else we are missing.
>
> If everyone is happy about the proposal I would prepare a pull request to
> the bip.
>
> Best regards,
> Stepan Snigirev.

> I'd rather see the xpubs shared in the global section of the file,
> with the restriction that they must/should only include the hardened
> prefix of the path. The existing bip32 derivation path included in
> individual inputs and outputs be merged in as needed.
> After all in a typical PSBT, we would expect the same master keys
> to be used on all inputs, and at least one output, and there might
> be as many as 20 co-signers. No need to repeat all that information.

I agree that it makes sense to put xpubs to the global scope. But I am not sure that restricting xpubs to have only hardened derivation is necessary. People may want to share non-hardened xpubs with co-signers and keep parent xpub on there watch-only wallet. For example, in bip45 cosigner_index is not hardened, and sharing top level xpub is not necessary.

> Even with this additions to the PSBT format, I think PSBT-signing
> devices still need to store the xpubs of their co-signers. It's not
> possible to safely show an incoming address to the user without a
> full understanding of the other keys in a "multisig wallet". Also,
> it represents data that should not change between PSBT instances
> (ie. tomorrow's co-signers should match today's).

I would like to keep hardware wallets state-less, otherwise wiping and recovering them would be problematic. At the setup phase the user can verify a multisignature address (or xpub) on the screens of all devices, after that we just need to verify that xpubs in the inputs and in the change output are the same.

Andrew, regarding your question:

> Just for clairty, by xpub, do you mean the extended serialization format
> defined in BIP 32 or the Base58 check encoded string of that

serialization?

As PSBT is a binary format I think it makes sense to use extension serialization format without any encodings. I am not sure if we need the whole xpub or keeping chain_code and public_key is enough, but I would suggest to keep other data just in case. For example, keeping prefix that defines if the key is used for testnet or mainnet may be useful.

Best regards, Stepan

> > Even with this additions to the PSBT format, I think PSBT-signing
> > devices still need to store the xpubs of their co-signers. It's not
> > possible to safely show an incoming address to the user without a
> > full understanding of the other keys in a "multisig wallet". Also,
> > it represents data that should not change between PSBT instances
> > (ie. tomorrow's co-signers should match today's).
>
> I would like to keep hardware wallets state-less, otherwise wiping and
> recovering them would be problematic.
> At the setup phase the user can verify a multisignature address (or
> xpub) on the screens of all devices,
> after that we just need to verify that xpubs in the inputs and in the
> change output are the same.

At the setup phase, hardware wallet can sign a message that consists of xpubs of participants, and some auxiliary text. It can use the key derived from the master key, with path chosen specifically for this purpose.

Hardware wallet then gives out this signature to the software.

The software will store the message and the signature (or maybe it can take xpubs from PSBT), and will send this 'trusted-xpub-package' to hardware wallet along with the transaction.

Hardware wallet can then verify that the message is indeed signed by the key for that purpose, and then can mark the ouputs that use the pubkeys derived from 'verified' xpubs as 'trusted' outputs. It can also display the auxiliary text along with the information about the 'trusted' output.

This way, hardware wallet does not need to store anything extra besides the master key.

This would allow to distinguish the trusted output even if the inputs are not all derived from the same set of xpubs, that could happen in more complex scenarios (batching, key rotation, etc.), and can possibly be used to have several different types of 'trusted' outputs.

If the user loses the signature for trusted-xpub-package, the signature can be re-created again - but maybe the procedure should be more involved than ordinary signing, because creating creating such 'trusted-xpub-package' with malicious keys can enable attackers to bypass these checks.

hello,

On 07. 05. 19 15:40, Dmitry Petukhov via bitcoin-dev wrote:

> At the setup phase, hardware wallet can sign a message that consists of
> xpubs of participants, and some auxiliary text. It can use the key
> derived from the master key, with path chosen specifically for this
> purpose.

This seems overly complicated.

What is your threat model?

IIUC, each individual multisig signature also signs the set of signers (through signing redeem-script (or scriptPubKey in address-based multisig)) So if an attacker gives me bad xpubs, i will sign them, but the signature won't be valid for the given multisig output - even if the attacker manages to trick 2 of 3 signers and recombine their signatures.

Therefore, the input==output check is sufficient: if I use the same set of signers for an input and an output, I can be sure that the change goes to the same multisig wallet.

Or is there something I'm missing?

The weak spot is the part where you generate receiving address, because that "creates" the particular multisig wallet. But that's nothing to do with PSBT.

> This would allow to distinguish the trusted output even if the inputs
> are not all derived from the same set of xpubs, that could happen in
> more complex scenarios (batching, key rotation, etc.), and can possibly
> be used to have several different types of 'trusted' outputs.

This seems to be an attempt at a different, much broader problem. And it won't help if the attacker can replay a different trusted-xpub package (e.g., one that contains a revoked previously compromised key).

regards m.

> Therefore, the input==output check is sufficient: if I use the same
> set of signers for an input and an output, I can be sure that the
> change goes to the same multisig wallet.

This is sufficient, in a simple case.

I consider cases where spending from different wallets ('wallet compartments') can be aggregated into one transaction, for efficiency and convenience in certain circumstances. (ex: legacy addresses that cannot be abandoned due to users still sending to them, but managing them separately is inconvenient; wallet 'compartments' that each have different multisig policies and spending priorities, and change would go to most secure compartment used, etc.)

This is most likely a 'borader problem', as you said, but this is just what my code already does, although with stateful signers that store trusted xpubs. I had an idea how to apply this to stateless hw wallets, and shared it.

> > This would allow to distinguish the trusted output even if the
> > inputs are not all derived from the same set of xpubs, that could
> > happen in more complex scenarios (batching, key rotation, etc.),
> > and can possibly be used to have several different types of
> > 'trusted' outputs.
>
> This seems to be an attempt at a different, much broader problem. And
> it won't help if the attacker can replay a different trusted-xpub
> package (e.g., one that contains a revoked previously compromised
> key).

The auxiliary text can be constructed to include some code word that would mark 'epoch' of the package, and will be displayed prominently. Upon compromise, new trusted-xpub packages would use different 'epoch' code word. This is one method to make it stateless (stateful way would be to just have a counter inside hw wallet and check package version against it).