* [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes @ 2018-09-20 16:19 Andrew Kozlik 2018-09-21 19:29 ` Christopher Allen 2018-09-24 19:49 ` Ignacio Berrozpe 0 siblings, 2 replies; 6+ messages in thread From: Andrew Kozlik @ 2018-09-20 16:19 UTC (permalink / raw) To: 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes 2018-09-20 16:19 [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes Andrew Kozlik @ 2018-09-21 19:29 ` Christopher Allen 2018-09-22 4:54 ` vizeet srivastava 2018-09-26 12:12 ` Andrew Kozlik 2018-09-24 19:49 ` Ignacio Berrozpe 1 sibling, 2 replies; 6+ messages in thread From: Christopher Allen @ 2018-09-21 19:29 UTC (permalink / raw) To: andrew.kozlik, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4675 bytes --] On Fri, Sep 21, 2018 at 11:18 AM Andrew Kozlik via bitcoin-dev < 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, you may want to incorporate information from the CMU dictitionary http://www.speech.cs.cmu.edu/cgi-bin/cmudict, the top 5000 words https://github.com/ChristopherA/password_poem/blob/master/top5000.json, concrete word lists http://crr.ugent.be/papers/Concreteness_ratings_Brysbaert_et_al_BRM.txt and emotional words (valence) http://crr.ugent.be/archives/1003 — Christopher Allen [-- Attachment #2: Type: text/html, Size: 6844 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes 2018-09-21 19:29 ` Christopher Allen @ 2018-09-22 4:54 ` vizeet srivastava 2018-09-26 12:12 ` Andrew Kozlik 1 sibling, 0 replies; 6+ messages in thread From: vizeet srivastava @ 2018-09-22 4:54 UTC (permalink / raw) To: Christopher Allen, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5561 bytes --] I see one benefit which i am looking for. I may not need to use all public keys in p2sh script instead i can use p2pkh and retrieve funds by using threshold number of keys..so in case i loose a public key along with private key i still may have other public key private key pairs to retrieve. For me it sounds interesting. I need to understand how it is going to get implemented in more detail. On Sat 22 Sep, 2018, 9:53 AM Christopher Allen via bitcoin-dev, < bitcoin-dev@lists•linuxfoundation.org> wrote: > On Fri, Sep 21, 2018 at 11:18 AM Andrew Kozlik via bitcoin-dev < > 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, you may want > to incorporate information from the CMU dictitionary > http://www.speech.cs.cmu.edu/cgi-bin/cmudict, the top 5000 words > https://github.com/ChristopherA/password_poem/blob/master/top5000.json, > concrete word lists > http://crr.ugent.be/papers/Concreteness_ratings_Brysbaert_et_al_BRM.txt > and emotional words (valence) http://crr.ugent.be/archives/1003 > > — Christopher Allen > > > > > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 8426 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes 2018-09-21 19:29 ` Christopher Allen 2018-09-22 4:54 ` vizeet srivastava @ 2018-09-26 12:12 ` Andrew Kozlik 1 sibling, 0 replies; 6+ messages in thread From: Andrew Kozlik @ 2018-09-26 12:12 UTC (permalink / raw) To: Christopher Allen, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5279 bytes --] 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 > <bitcoin-dev@lists•linuxfoundation.org > <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, you may > want to incorporate information from the CMU > dictitionary http://www.speech.cs.cmu.edu/cgi-bin/cmudict, the top > 5000 > words https://github.com/ChristopherA/password_poem/blob/master/top5000.json, > concrete word lists > http://crr.ugent.be/papers/Concreteness_ratings_Brysbaert_et_al_BRM.txt > and emotional words (valence) http://crr.ugent.be/archives/1003 > > — Christopher Allen > > > > > > > [-- Attachment #2: Type: text/html, Size: 21466 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes 2018-09-20 16:19 [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes Andrew Kozlik 2018-09-21 19:29 ` Christopher Allen @ 2018-09-24 19:49 ` Ignacio Berrozpe 2018-09-26 13:44 ` Andrew Kozlik 1 sibling, 1 reply; 6+ messages in thread From: Ignacio Berrozpe @ 2018-09-24 19:49 UTC (permalink / raw) To: andrew.kozlik, bitcoin-dev [-- Attachment #1.1: Type: text/plain, Size: 2528 bytes --] 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 < 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 > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #1.2: Type: text/html, Size: 3540 bytes --] [-- Attachment #2: KofM Private Key Generation and Backup in Bitcoin Wallets _ Submit.rtf --] [-- Type: application/msword, Size: 1074372 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes 2018-09-24 19:49 ` Ignacio Berrozpe @ 2018-09-26 13:44 ` Andrew Kozlik 0 siblings, 0 replies; 6+ messages in thread From: Andrew Kozlik @ 2018-09-26 13:44 UTC (permalink / raw) To: Ignacio Berrozpe, bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 4280 bytes --] 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 > <bitcoin-dev@lists•linuxfoundation.org > <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 > [-- Attachment #2: Type: text/html, Size: 6926 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-09-26 13:44 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-09-20 16:19 [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes Andrew Kozlik 2018-09-21 19:29 ` Christopher Allen 2018-09-22 4:54 ` vizeet srivastava 2018-09-26 12:12 ` Andrew Kozlik 2018-09-24 19:49 ` Ignacio Berrozpe 2018-09-26 13:44 ` Andrew Kozlik
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox