Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2A441FF4 for ; Wed, 26 Sep 2018 12:12:46 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 989EC27B for ; Wed, 26 Sep 2018 12:12:44 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id v16-v6so26763195wro.11 for ; Wed, 26 Sep 2018 05:12:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=satoshilabs.com; s=google; h=subject:to:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=4yefBnRxm8By0lXGRy/EZodjK/oTKi3k4Wk8hC6CiYo=; b=ANk2CEIgYjuk8sEuIsLJywlw2wAqWCa85h3mNS5M8oN5jkM4U6fKKI+JREpjVvZK1b qBw8TMZr1hZuoToViSBVxHfELvhFiFnEcyfvO1zVPG9qB/zOtru90uA/9CQ8s6S8e7tN emZWe+pNScSCapKhPt0NPmtuingCgVF6JWiaLHdzaCiB7cmM2kOsKU1lDSSkLyZvlv4L rCWEjsbqPrUFUxyE1pzD+w8XBKZ3W2dF9jJDXZ33q2VKeh9OdOjNimEumKoLVx40dz/j sOVIZ3Jw3N1IguEny3w0WfmMyusNceg9NMq2qEOs51q+OXw8/oGQ5YoBRC0BLwzjIMWq GcUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language; bh=4yefBnRxm8By0lXGRy/EZodjK/oTKi3k4Wk8hC6CiYo=; b=jYbw/tnkfgIIy4Wwh1Iy4pjEg7u2xceAMrhQsrcUUuSmj0oG22Jf6+1ARSeRHVGcXV 5Th8WfLf39eQF/IdcOqtoR6O5EmBf9BB2DXOYJDOUCdut80OSyRmwjYGQ3MHWsbsDdLh JM8J7afpsz+DPCaEbkzdzVV/Pr5u7V5CNm6R3Gvh9G+Zru4Zrn6F8sgr7oVw3qyl2+Yk TmUOLpBF0WonS3NvDuVRD1gUcjemgv6BTbm3ndW7K0LrUfHoFCgP4r7mIlEdjfcMFpcd II1644dPDCV1ZEo040jrW3UNCkJ6Ks3g7KtshSJOD+GV5PI3MQ1xsZTJQKgmNoyl1gM6 ZD0w== X-Gm-Message-State: ABuFfoidTs8Hx5HZ+1bxo9qV3pjdOs9N/lhZwKCmnZZngXVf0gP/VhGj Dsn3eK0Qi08eZr9lhJNzupdjskkjhI0= X-Google-Smtp-Source: ACcGV62ZRe5TQzkaC612l0OAhAgE/bKBvM48UN4+O4sjFv90FJPFUmflBUQyvVw2zn3N4sTdSVvuow== X-Received: by 2002:adf:8523:: with SMTP id 32-v6mr4587626wrh.72.1537963962643; Wed, 26 Sep 2018 05:12:42 -0700 (PDT) Received: from [192.168.255.205] ([88.208.115.69]) by smtp.gmail.com with ESMTPSA id h17-v6sm6358322wrq.73.2018.09.26.05.12.41 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 26 Sep 2018 05:12:42 -0700 (PDT) To: Christopher Allen , Bitcoin Protocol Discussion References: <4e2c7b41-1e16-b89a-04d8-776f3469141a@satoshilabs.com> From: Andrew Kozlik Openpgp: preference=signencrypt Autocrypt: addr=andrew.kozlik@satoshilabs.com; keydata= xsFNBFt62C4BEAC+pOtoQthf9I0vZIfVPbebk/1i1Znw0AmbqZr36fqfdGcCdZ2gDJDLjisd QZVsHbZ4WAlFL5AKH2YJlwBrjxN+gTh0W231QTWUNGqOR2v61gBo3tBhxmr+9yP/iNuQpLCn E+P1hN6si9IkaxbqCVW6eUiexKsY4gK8RR6UgqJ73h/Y5p57NVpbuYvrKpFp17qEfKO0ToNC kSQzLZsOFRGZzbIp5dipPWDR04TbvliPR+Gn0HBnGC9wvfqFSlJiHxqB8GSCyviGXiGCOwAs SDEfr2yybxR/hnCURDm9jWX7Rv+1MSJzlRikQ/NFoLsH2FFRG5RPbRLGHBEeRioP5FcCtCsq rAvICud4Hvqm9FjjsIDL8YpKsRsC6VdphPVV2vggeDulMtl9jlZb38vMrQMyT5NnQr04oPmI DdD5puYcs1eoYhryOf4g6dEj/Zyndg9wXTQC6nXSTIFPEMNVv4aUwMr1z/pPW3f7zokIRc0a h/Kxn9kUe9UB5ASgH7UoKD13pPmf6XSEpwUVXGp97s7JmlaheN45a3odM9y3rn8doSdLacB2 dRKSBWaebYEnMitHpiBVdTCVYkbq35bblGYC/RURaGUBA/aGWv0ozPYq+7uJY4VJ1nz/T9fu g8Mes1Z03YAOoHP9uDZDa8Ops/9N7ygUzCqL/LWeQC5I6YdoyQARAQABzS1BbmRyZXcgS296 bGlrIDxhbmRyZXcua296bGlrQHNhdG9zaGlsYWJzLmNvbT7CwX0EEwEIACcFAlt62C4CGyMF CQlmAYAFCwkIBwIGFQgJCgsCBBYCAwECHgECF4AACgkQUemaa1Zc2aTb9w/+MFYbXAbpYOVG 3m3kLtPnWVpMXOIWVoK1r4j5/J8L2oBjf6JD/br55ZU6VaE5RYwuAW9NfU6OqP0NVTARGXpH sf3p4mZ7W7FtwdkBm36//R9DN76eQXfu1GoyYjLTbF7KqbqQjckNVYNMx4kIIShID7nMasN7 Vt/zhB0jc8Ay5T5/5YynNqR0WQAw6dF979xHrKXuAvuJ0bSVU+tUaDm07jp09tB5nM2dUQGn vUh0D6aZYVhW+hO0tfWvY/RSwHP9+TdT0VH8sd8mFUM4TIT7fbdk4Ceq2oCy3/VusDQWQljQ AHXQ7mEJWeRX0XSACTU/337igFbW45AvJAy0bPL4wz8Jfm8x0W0f3x/U78yQIYsTFJIAba4U RKONJ0AxVGPIRy4jH1sddkP1xEgS4m3QjQGnlsjmjHcCX4gMlQLowJz5JQ4x/CnnGd8Aiki8 n4rrov0VDEwPQUdVSWHB9cIagAPfS7p6j7hVc51DyxMFwb7fkBcuEhwTd90TAo843igGVYbv 4xnvaUgGvvjZZcOjbfHwzUmhvCtJYW9GQjFfGcTmYHBaRvIQeNYLrrsGtpUj83qaUgwe1GAl u0RXB+YXUKM55MbvHBq0yABRku+AbGlqGzfm46giaFlqTxji3qjP/M44hOgbOqmDemfc9BDx iATyQgGry8TFZeAOGqXRd+7OwU0EW3rYLgEQAMpVn2xMtJuaH7fU9STafUCbSwzP3CS4wseD ijEeo/Pce46cqMNYx4u0AQBxwtIReDe9KSUugVUDkywsXIweZytY+RXYwV12bcxmStP06+LH 79UKDFN2DqsJRg5KzG91+fPIX4XnEpdufKy2EF6Isio8wlwfLCtJgrcXLLlSUXmavv+QNqU7 /HLT5gsSaIPUns8t+miZ2lHxMjKDJCbuWdWZymhZXc5e0sGkLVo0mq1CzjObyDuYyvXhAJZa jDFsMY9dF8iA5bIGmhAQmfEgQSxe6za60i/M92TNHKENb2x1rqXXr0ctjNd73TKPkOIVYPPx 0IBJiltC7BRExE7FSNc70JJxg3amJHlPPVtz/MkkiW8mLbJrcTTV1Zrq4U8Dm8ErNjA6L5Fc S6p/Z4F1ZlQFDdao5V24jGti2tpGbP7zQqkcieeoSh7luK8a5AfQy+Im2C4BgrHseCqpd8Ik Vfwmiy90nGtgScqn52fr18rWE3zfx5Uu7IbRPxLNL6VBfCeI+w2HkY0LTp3/iYvBZU6Dt12s Z2XYrwYuuf+Pf6CAuITyXjIEdaKPuYYrkxG5U5EFeefwhpQgmT2BH+Jgp9+4fuu6W8wQMYbt 7yXtm/Z1KI2tzZ/x006shhzG0b5hiJu5wf+vJxaREv3cnkPjGGXmLLMXerlXzPJys5hJ0lhx ABEBAAHCwWUEGAEIAA8FAlt62C4CGwwFCQlmAYAACgkQUemaa1Zc2aTPZxAAop/Zj3xA6f9M sl9hTAYdodSwXtXr1xdtRkciO0CitqSvBLB7xeohfHxfUa06aXyBNMA0jwIMIn4yjOD7jNOy 9cj5Alql644Dt0/fRVniSnV+b2ebfnbywa6jBIIR/FPq4nJaJ0AgzwJm/0OR7+1LOCONA72w tUCAvGyhM2c4yPYjULCKYPUlQPy5fKpGBggP3cbPZLH1gmEL61Ph27rejnW2XC1EL3J/BPcL ixKXk8po/x94qkV6f506isszuRmJBnAXzYa6lXNjpDySfXhrlspY1OJlR0CK+4D3nJiaePYt lh3LoJbqsuK/ERfiV8vsJRV/SENtjqTrd9tbb8Ab+3v6ilCYJ6mXUMOy0Jc1rGcOSGyH6JVz WHDzk/AvZbP9Uai/hDIskLFq5i/6fQY+uaKHKFrc9S2rQ8g1deKWqVZEGyUYA5ICkTUpHgJT IwZzFZyKmFzmI1f3gLh9hHKKLHrq/zv6myXCko6Tn2PyeNXyekmqKk4M61J7v9SJc0H2iVuR 0yVdBihwBDm18cA+a2T4u6NtQVtI4eIfA79aBF0IIJ/VbKxgFOjQmWWL1ej5BAdwA752f6rr rpSashtUuLDAcUnS6PKZK3qZltDAJeOhK+B2ejX7GPAVf5UYT1JB9pn9urN+C5v9aDPjyRrU ADdTkt305KgIVcafMVR1Brg= Message-ID: <5c36fdb3-304f-ce43-d41a-0c1d66c7cc41@satoshilabs.com> Date: Wed, 26 Sep 2018 14:12:40 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/alternative; boundary="------------CEAF1CC0E5C4570D928071F1" Content-Language: en-US X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Wed, 26 Sep 2018 12:19:24 +0000 Subject: Re: [bitcoin-dev] SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 26 Sep 2018 12:12:46 -0000 This is a multi-part message in MIME format. --------------CEAF1CC0E5C4570D928071F1 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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 > > 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. T= he > 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.=C2=A0 > > 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=E2=80=9D. > > 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=C2=A0issue= s in > SLIPS repo or on some other mailing list?=C2=A0 > > * Presuming a successful split of secrets, I don=E2=80=99t 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: =C2=A0impersonation 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 =C2=A0to = scan > the blockchain for keys, as well as a byte with some way to know how > to derive keys paths for it. I don=E2=80=99t seee a BOLT for this (it w= as > mentioned > in=C2=A0https://bitcoin.stackexchange.com/questions/74805/what-is-birth= day-in-the-context-of-bip39-lightning-seed-generation) > =C2=A0I would suggest that you also get some of their latest thoughts a= nd > incorporate them. > > * I worked with Chris Vickery while at Blockstrham on various possible > ways to improve mnemonic word lists. I=E2=80=99m not suggesting that yo= u > 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.=C2=A0 > > 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: > > =C2=A0 =C2=A0 > https://github.com/ChristopherA/iambic-mnemonic/blob/master/word-lists/= iambic-wordlist.json=C2=A0 > > =E2=80=A6which was created from the repo at > > =C2=A0 =C2=A0 https://github.com/ChristopherA/password_poem > > You can a number of other word lists that I=E2=80=99ve 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=C2=A0http://www.speech.cs.cmu.edu/cgi-bin/cmudict, the top= > 5000 > words=C2=A0https://github.com/ChristopherA/password_poem/blob/master/to= p5000.json, > =C2=A0concrete word lists > http://crr.ugent.be/papers/Concreteness_ratings_Brysbaert_et_al_BRM.txt= > and emotional words =C2=A0(valence)=C2=A0http://crr.ugent.be/archives/1= 003 > > =E2=80=94 Christopher Allen > > > > > > > --------------CEAF1CC0E5C4570D928071F1 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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> 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:


…which was created from the repo at

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








--------------CEAF1CC0E5C4570D928071F1--