[bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes

2018-09-21 Thread Andrew Kozlik via bitcoin-dev
Hello everyone,

We are currently writing a new specification for splitting BIP-32 master
seeds into multiple mnemonics using Shamir's secret sharing scheme. We
would be interested in getting your feedback with regard to the
high-level design of the new spec:
https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Please focus your attention on the section entitled "Master secret
derivation functions", which proposes several different solutions. Note
that there is a Design Rationale section at the very end of the
document, which should answer some of the questions you may have. The
document is a work in progress and we are aware that some technical
details have not been fully specified. These will be completed once the
high level design has been settled.

Thanks,

Andrew Kozlik
TREZOR Team


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes

2018-09-26 Thread Andrew Kozlik via bitcoin-dev
Thank you for your input Ignacio. Looking at your proposal, I see that
its main feature is that it makes one of the shares privileged in the
sense that it must always take part in the reconstruction of the master
secret, while the remaining shares follow the K-of-M scheme. This is an
interesting idea.

To answer your questions:

> Your proposed work provides a way to split the pre-secret into SSS
> shares, a format of encoding the shares, and finally several methods
> to derive the master secret from the pre-secret. Would you envision
> standarizing these different topics under the same proposal?
We intend standardize the encoding format, splitting of the pre-master
secret into shares and the derivation of the master secret from the
pre-master secret in a single document. However, note that only one of
the four proposed master secret derivation functions will be selected
for the final version.

> Also, have you thought of a way to deal with the existing legacy
> privatekeys already encoded into BIP-0039, or stored in other formats,
> and how to migrate them securely into a schema of encoded SSS shares?
Three of the four proposed master secret derivation functions are
symmetric, which means that they allow users to migrate any existing
master secret (including a BIP-0039 mnemonic) to the new scheme.

Thanks,
Andrew Kozlik


On 24.9.2018 21:49, Ignacio Berrozpe wrote:
> Hi Andrew
>
> Please allow me to comment on your work, as I happened to publish an
> article 5 months ago proposing SSS to split bitcoins private keys into
> shares that could be encoded directly using BIP-0039 mnemonic words.
> While cryptographically much simpler than your proposal, the proposal
> had the characteristic that it could be applied directly to existing
> private keys backups, by splitting the keys into SSS shares that could
> benefit from the existing BIP-0039 mnemonic to encode directly the
> shares. I thought it would be a simple path for hardware wallets
> providers such as Trezor into providing a better/more secure
> alternative the existing BIP-0039 privatekey backups of 24 words.
>
> The article can be found here, and I've enclosed a simplified version
>
> https://privatekeys.org/2018/04/24/k-of-m-private-key-generation-and-backup-in-bitcoin-wallets/
>
> Mind two questions? Your proposed work provides a way to split the
> pre-secret into SSS shares, a format of encoding the shares, and
> finally several methods to derive the master secret from the
> pre-secret. Would you envision standarizing these different topics
> under the same proposal? Also, have you thought of a way to deal with
> the existing legacy privatekeys already encoded into BIP-0039, or
> stored in other formats, and how to migrate them securely into a
> schema of encoded SSS shares?
>
> Best regards
> Ignacio Berrozpe
>
>
>
>
>
>
>
> On Fri, Sep 21, 2018 at 8:18 PM Andrew Kozlik via bitcoin-dev
>  <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
>
> Hello everyone,
>
> We are currently writing a new specification for splitting BIP-32
> master
> seeds into multiple mnemonics using Shamir's secret sharing scheme. We
> would be interested in getting your feedback with regard to the
> high-level design of the new spec:
> https://github.com/satoshilabs/slips/blob/master/slip-0039.md
> Please focus your attention on the section entitled "Master secret
> derivation functions", which proposes several different solutions.
> Note
> that there is a Design Rationale section at the very end of the
> document, which should answer some of the questions you may have. The
> document is a work in progress and we are aware that some technical
> details have not been fully specified. These will be completed
> once the
> high level design has been settled.
>
> Thanks,
>
> Andrew Kozlik
> TREZOR Team
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> <mailto:bitcoin-dev@lists.linuxfoundation.org>
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes

2018-09-26 Thread Andrew Kozlik via bitcoin-dev
Thanks for your input Christopher. Since we already have the discussion
about your comments running under the issues in the SLIPs repo on Github
(https://github.com/satoshilabs/slips/issues), let's continue it there.

Andrew Kozlik


On 21.9.2018 21:29, Christopher Allen wrote:
> On Fri, Sep 21, 2018 at 11:18 AM Andrew Kozlik via bitcoin-dev
>  <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
>
> We are currently writing a new specification for splitting BIP-32
> master
> seeds into multiple mnemonics using Shamir's secret sharing scheme. We
> would be interested in getting your feedback with regard to the
> high-level design of the new spec:
> https://github.com/satoshilabs/slips/blob/master/slip-0039.md
> Please focus your attention on the section entitled "Master secret
> derivation functions", which proposes several different solutions.
> Note
> that there is a Design Rationale section at the very end of the
> document, which should answer some of the questions you may have. The
> document is a work in progress and we are aware that some technical
> details have not been fully specified. These will be completed
> once the
> high level design has been settled.
>
>
> I and a number of companies & communities I am involved with are very
> interested in this. 
>
> A challenge is that Shamir Secret Sharing has subtleties. To quote
> Greg Maxwell:
>
> > I think Shamir Secret Sharing (and a number of other things, RNGs
> for example), suffer from a property where they are just complex
> enough that people are excited to implement them often for little good
> reason, and then they are complex enough (or have few enough reasons
> to invest significant time) they implement them poorly”.
>
> Some questions for you:
>
> * What other teams or communities besides Trezor are committed to
> standardizing a Shamir Secret Sharing Scheme? I can say that the
> #RebootingWebOfTrust community (meeting again for the 7th time next
> week in Toronto https://rwot7.eventbrite.com) are very interested.
>
> * Where do you want to hold discussions on this? Do people object to
> having this discussion on this mailing list? Or should it be issues in
> SLIPS repo or on some other mailing list? 
>
> * Presuming a successful split of secrets, I don’t know all the
> adversarial problems that are associated with recovery of a SSS. As
> this would be an interactive event, I presume an attacker can DOS a
> request to reassemble keys (so maybe some the of integrity of each
> share vs all is required). And of course there are the biggest
> problems:  impersonation of a reassembly request and a MitM of a
> reassembly request. Are there other attacks? Are you trying to
> mitigate any of these?
>
> Two comments:
>
> * The Lightning Network community has added to their BIP32 mnemonics
> the ability to have a birthday in the seed, to make it easier  to scan
> the blockchain for keys, as well as a byte with some way to know how
> to derive keys paths for it. I don’t seee a BOLT for this (it was
> mentioned
> in 
> https://bitcoin.stackexchange.com/questions/74805/what-is-birthday-in-the-context-of-bip39-lightning-seed-generation)
>  I would suggest that you also get some of their latest thoughts and
> incorporate them.
>
> * I worked with Chris Vickery while at Blockstrham on various possible
> ways to improve mnemonic word lists. I’m not suggesting that you
> necessarily go as far as we did to try to create a mnemonic that is
> iambic pentameter poetry (inspired by
> https://www.isi.edu/natural-language/mt/memorize-random-60.pdf),
> however, we did find sources for words that are concrete (for example
> table is more concrete than truth
> http://crr.ugent.be/papers/Brysbaert_Warriner_Kuperman_BRM_Concreteness_ratings.pdf
> ) or have strong emotional valence attachment (truth is more emotional
> than table), both of which make can words more memorable. I also found
> lists of words that are hard to pronounce unless you are English
> native, and eliminated them from my own list. 
>
> Among the results of this was a new BIP-39 2048 word compatible word
> list filtered for memorability (concreteness & emotional valence) and
> suitability for iambic pentameter, which is located:
>
>    
> https://github.com/ChristopherA/iambic-mnemonic/blob/master/word-lists/iambic-wordlist.json
>  
>
> …which was created from the repo at
>
>     https://github.com/ChristopherA/password_poem
>
> You can a number of other word lists that I’ve collected here
> https://github.com/ChristopherA/iambic-mnemonic/blob/master/word-lists/
>
> If you want to replicate what we did with your own criteria

Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

2020-05-01 Thread Andrew Kozlik via bitcoin-dev
Hi Jeremy,

What you are saying is correct and I am not disputing that there is
sufficient cryptographic commitment in the signature message. As I tried to
explain, my proposal is about avoiding the need for the metadata protocol
you speak of. Avoiding such a protocol has been a design goal in both
BIP-143 [1, 2] and BIP-341 [3, 4], because having to acquire each of the
transactions being spent in their entirety places a significant burden on
offline signing devices.

Cheers,
Andrew

[1]
https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki#motivation
[2] https://bitcointalk.org/index.php?topic=181734.0
[3]
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-16
[4]
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-17

On Fri, May 1, 2020 at 8:56 AM Jeremy  wrote:

> Hi Andrew,
>
> If you use SIGHASH_ALL it shall sign the COutPoints of all inputs which
> commit to the scriptPubKeys of the txn.
>
> Thus the 341 hash doesn't need to sign any additional data.
>
> As a metadata protocol you can provide all input transactions to check the
> scriptPubKeys.
>
> Best,
>
> Jeremy
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
>
>
> On Thu, Apr 30, 2020 at 1:22 AM Andrew Kozlik via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi everyone,
>>
>> In the current draft of BIP-0341 [1] the signature message commits to the
>> scriptPubKey of the output being spent by the input. I propose that the
>> signature message should commit to the scriptPubKeys of *all* transaction
>> inputs.
>>
>> In certain applications like CoinJoin, a wallet has to deal with
>> transactions containing external inputs. To calculate the actual amount
>> that the user is spending, the wallet needs to reliably determine for each
>> input whether it belongs to the wallet or not. Without such a mechanism an
>> adversary can fool the wallet into displaying incorrect information about
>> the amount being spent, which can result in theft of user funds [2].
>>
>> In order to ascertain non-ownership of an input which is claimed to be
>> external, the wallet needs the scriptPubKey of the previous output spent by
>> this input. It must acquire the full transaction being spent and verify its
>> hash against that which is given in the outpoint. This is an obstacle in
>> the implementation of lightweight air-gapped wallets and hardware wallets
>> in general. If the signature message would commit to the scriptPubKeys of
>> all transaction inputs, then the wallet would only need to acquire the
>> scriptPubKey of the output being spent without having to acquire and verify
>> the hash of the entire previous transaction. If an attacker would provide
>> an incorrect scriptPubKey, then that would cause the wallet to generate an
>> invalid signature message.
>>
>> Note that committing only to the scriptPubKey of the output being spent
>> is insufficient for this application, because the scriptPubKeys which are
>> needed to ascertain non-ownership of external inputs are precisely the ones
>> that would not be included in any of the signature messages produced by the
>> wallet.
>>
>> The obvious way to implement this is to add another hash to the signature
>> message:
>> sha_scriptPubKeys (32): the SHA256 of the serialization of all
>> scriptPubKeys of the previous outputs spent by this transaction.
>>
>> Cheers,
>> Andrew Kozlik
>>
>> [1]
>> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#common-signature-message
>> [2]
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014843.html
>> ___
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

2020-05-04 Thread Andrew Kozlik via bitcoin-dev
>
> A side effect of this proposal is it would seem to make it not possible to
> produce a signature for a transaction without having access to the inputs.
> This is limiting for a number of cases where you don't care about that
> data. There are a litany of use cases where you don't want to have
> SIGHASH_ALL behavior, and having to sign the scriptpubkeys breaks that. So
> at the very least it should respect other flags.
>

I agree, sha_scriptPubKeys should be included only if hash_type does not
match SIGHASH_ANYONECANPAY. I am also sympathetic to aj's idea of making
the scriptPubKey field dependent on hash_type matching SIGHASH_ANYONECANPAY.

I also don't really understand the exact attack. So you submit a
> transaction to the wallet asking them to sign input 10. They sign. They've
> committed to the signature being bound to the specific COutpoint and input
> index, so I don't see how they wouldn't be required to sign a second
> signature with the other output too? Is there an attack you can describe
> end-to-end relying on this behavior?
>

For example, in a CoinJoin transaction the attacker can construct a
transaction with two inputs (in1, in2) of identical value and two outputs
of identical value, one belonging to the user (user_out) and another
belonging to the attacker (attacker_out). If such a transaction is sent to
the hardware wallet twice with in1 marked as external the first time and
in2 marked as external the second time, then the hardware wallet will
display two signing requests to the user with spending amounts of in2 -
user_out and in1 - user_out respectively. The user will think that they are
signing two different CoinJoin transactions, while in reality they are
signing two different inputs to a single transaction and sending half of
the amount to the attacker.

As an alternative proposal, I think you can just make a separate BIP for
> some new sigash flags that can be reviewed separately from taproot. There's
> a lot of value in investing in figuring out more granular controls over
> what the signature hash is you sign, which may have some exciting
> contracting implications!
>

The proposal of adding sha_scriptPubKeys is just an optimization which is
not intended to change what the signature message is committing to. Thus I
don't see it as warranting a new sigash flag.

Alternatively, there's the scheme described in the email you linked by Greg
> Saunders (with the scheme co-attributed to Andrew Poelstra), which seems
> reasonable to me.[1]  It's only downside (AFAICT) is that it requires an
> extra one-way communication from a signing device to a coordinator.  For a
> true offline signer, that can be annoying, but for an automated hardware
> wallet participating in coinjoins or LN, that doesn't seem too burdensome
> to me.
>

Yes, I see this as the correct direction forward. Whatever the exact format
of the ownership proof will be, the proof will need to be signed by the
owner of the UTXO using BIP-0322 or something along those lines. So the
scriptPubKey is needed to verify that signature.

Cheers,
Andrew Kozlik

On Sat, May 2, 2020 at 11:16 PM Russell O'Connor 
wrote:

> On Sat, May 2, 2020 at 10:26 AM Anthony Towns  wrote:
>
>>
>> except that we'd arguably still be missing:
>>
>> is this a coinbase output? (Coin.fCoinBase)
>> what was the height of the coin? (Coin.nHeight)
>>
>> Maybe committing to the coinbase flag would have some use, but committing
>> to the height would make it hard to chain unconfirmed spends, so at
>> least that part doesn't seem worth adding.
>>
>
> To add to this point, the height of the coin is something that is *not*
> currently covered by any signature mode and including it would constitute a
> change of an entirely different  caliber; a change that I would strongly
> caution against for your above reason and more.
>
> The coinbase output flag is currently covered by the signature as the
> outpoint hash has the required information (its prevout index of 0x
> is only legal in a coinbase transaction).  While I'm not particularly
> enthusiastic about making it easier to distinguish coinbase outputs from
> other outputs, and I worry a little about alternative designs for
> implementing the Bitcoin protocol where this information is not so readily
> available, I suppose I won't really oppose adding it.  However, I don't
> think anyone is seriously proposing it.
>
>-
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

2020-04-30 Thread Andrew Kozlik via bitcoin-dev
Hi everyone,

In the current draft of BIP-0341 [1] the signature message commits to the
scriptPubKey of the output being spent by the input. I propose that the
signature message should commit to the scriptPubKeys of *all* transaction
inputs.

In certain applications like CoinJoin, a wallet has to deal with
transactions containing external inputs. To calculate the actual amount
that the user is spending, the wallet needs to reliably determine for each
input whether it belongs to the wallet or not. Without such a mechanism an
adversary can fool the wallet into displaying incorrect information about
the amount being spent, which can result in theft of user funds [2].

In order to ascertain non-ownership of an input which is claimed to be
external, the wallet needs the scriptPubKey of the previous output spent by
this input. It must acquire the full transaction being spent and verify its
hash against that which is given in the outpoint. This is an obstacle in
the implementation of lightweight air-gapped wallets and hardware wallets
in general. If the signature message would commit to the scriptPubKeys of
all transaction inputs, then the wallet would only need to acquire the
scriptPubKey of the output being spent without having to acquire and verify
the hash of the entire previous transaction. If an attacker would provide
an incorrect scriptPubKey, then that would cause the wallet to generate an
invalid signature message.

Note that committing only to the scriptPubKey of the output being spent is
insufficient for this application, because the scriptPubKeys which are
needed to ascertain non-ownership of external inputs are precisely the ones
that would not be included in any of the signature messages produced by the
wallet.

The obvious way to implement this is to add another hash to the signature
message:
sha_scriptPubKeys (32): the SHA256 of the serialization of all
scriptPubKeys of the previous outputs spent by this transaction.

Cheers,
Andrew Kozlik

[1]
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#common-signature-message
[2]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014843.html
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP70 is dead. What now?

2021-02-19 Thread Andrew Kozlik via bitcoin-dev
Hi Thomas,

I am working on an experimental implementation [1] of a new payment request
format in Trezor T. In some respects it's similar to BIP-70. The main
differences are:

1. There is no reliance on X.509, since that seems to have been the main
reason for BIP-70's downfall. The signature is mandatory, since for us the
main feature is protection against a man-in-the-middle attack. So in this
sense it's more similar to BOLT11.

2. It can be used to solve a similar problem with coin exchange. When you
are sending BTC to a trusted exchange service and expecting another
cryptocurrency in return, say LTC, you want to be sure that you not only
have the correct BTC address, but also that the exchange service has your
correct LTC address.

3. It uses an optional nonce for replay protection.

The two interesting parts in [1] are probably the `TxAckPaymentRequest`
protobuf message [2] and the signature verification [3]. The protobuf
message is only for communication between Trezor and the host software
running on the user's computer. It's not intended for interchange between
wallets. We haven't defined the interchange format yet. I intend to create
a SLIP documenting all this.

Andrew

[1] https://github.com/trezor/trezor-firmware/compare/andrewkozlik/payreq2
[2]
https://github.com/trezor/trezor-firmware/blob/andrewkozlik/payreq2/common/protob/messages-bitcoin.proto#L403-L427
[3]
https://github.com/trezor/trezor-firmware/blob/andrewkozlik/payreq2/core/src/apps/bitcoin/sign_tx/payment_request.py

On Fri, Feb 19, 2021 at 1:43 PM Charles Hill via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi, Thomas,
>
> I developed a URL signing scheme for use with LNURL as a method for
> authorizing payments on behalf of offline devices /applications. It's
> not specifically off-chain or on-chain related, but could be repurposed.
> The gist of the scheme is as follows:
>
> Before any signing is done:
>
> 0) Generate an API key (ID/reference, secret, encoding) to be shared
> between a server and an offline device or application.
>
> To generate a signature:
>
> 1) Generate a random nonce (unique per API key)
>
> 2) Build a query string with the `id`, `nonce`, `tag`, "Server
> parameters" (see [Subprotocols](#subprotocols) above), and any custom
> parameters. The `id` parameter should be equal to the API key's ID.
> Example:
> `id=b6cb8e81e3=d585674cf991dbbab42b=withdrawRequest=5000=7000=example=CUSTOM1_PARAM_VALUE=CUSTOM2_PARAM_VALUE`.
>
> Note that both the keys and values for query parameters should be URL
> encoded. The following characters should be __unescaped__: `A-Z a-z 0-9
> - _ . ! ~ * ' ( )`. See
> [encodeURIComponent](
> https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/encodeURIComponent#description)
>
> for more details.
>
> 3) Sort the query parameters by key (alphabetically). This is referred
> to as the "payload". Example:
>
> `custom1=CUSTOM1_PARAM_VALUE=CUSTOM2_PARAM_VALUE=example=b6cb8e81e3=7000=5000=d585674cf991dbbab42b=withdrawRequest`
>
> 4) Sign the payload (the sorted query string) using the API key secret.
> Signatures are generated using HMAC-SHA256, where the API key secret is
> the key.
>
> 5) Append the signature to the payload as follows:
>
> `custom1=CUSTOM1_PARAM_VALUE=CUSTOM2_PARAM_VALUE=example=b6cb8e81e3=7000=5000=d585674cf991dbbab42b=withdrawRequest=HMAC_SHA256_SIGNATURE`.
>
> You can find more details here:
>
> https://github.com/chill117/lnurl-node#how-to-implement-url-signing-scheme
>
>
> I would change a few things with this scheme to fit better with the
> use-case you describe. For example:
>
> * Remove the "tag" and LNURL-specific parameters
>
> * Instead of HMAC-SHA256 with a shared secret, it could use pub/priv key
> signing instead. The lnurl-auth subprotocol has an interesting approach
> to protecting user privacy while allowing verification of signatures.
> See for more details on that:
>
> https://github.com/fiatjaf/lnurl-rfc/blob/master/lnurl-auth.md
>
>
> - chill
>
>
> On 2/19/21 10:14 AM, Thomas Voegtlin via bitcoin-dev wrote:
> > I never liked BIP70. It was too complex, had too many features, and when
> > people discuss it, they do not even agree on what the main feature was.
> >
> > Nevertheless, there is ONE feature of BIP70 that I find useful: the fact
> > that payment requests were signed. I am making this post to discuss this.
> >
> > When I send bitcoins to an exchange, I would like to receive a signed
> > request. I want to have a proof that the exchange asked me to send coins
> > to that address, in case it has been hijacked by some intern working
> > there. If that feature was implemented by an exchange, it would guide my
> > decision to use that exchange over its competitors.
> >
> > I do not think that a single exchange ever implemented that, but I guess
> > this is because BIP70 is a terrible standard. LN payment requests are
> > signed, do not require SSL, do not require interactivity, and therefore
> > exchanges use