[bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[Contact Team]

[-- Attachment #1: Type: text/plain, Size: 1472 bytes --]

Hi Everyone,
Seed phrase security has been a subject of discussion for a long time now.
Though there are varying opinions on the subject but the conflict usually
arises due to different security models used by different individuals. The
general practice in the space has been to use paper or metal engraving
options to secure seed phrase but those too act as a single point of
failure when secure storage is concerned. The hardware wallets, no matter
whether use a secure element or not can be hacked either through basic
glitching or through bigger schemes state enforced backdoors in the closed
soured SE used.

The option that Cypherock (Cypherock X1 Wallet)  is working on removes a
single point of failure when it comes to storage of seed phrases. It uses 2
of 4 (with the option of setting up custom threshold limit) Shamir Secret
Sharing to  split the seed phrase into 4 different shares. Each share gets
stored in a PIN ( hardware enforced ) Card with an EAL 6+ secure element.
The user would need any 2 of these 4 cyCards to recover the seed or make a
transaction. Ideally they should all be stored at different locations and
this added security through distribution makes losing seed phrase highly
improbable. We have decoupled storage and computation aspect of a hardware
wallet. More information can be obtained from cypherock.com. The purpose of
this mail is to get feedback from the community. Let us know if there is
any feedback, we would love it.

Thanks

[-- Attachment #2: Type: text/html, Size: 1589 bytes --]

Re: [bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 2249 bytes --]

As a replacement for paper, something like this makes sense v.s. what you
do with a ledger presently.

However, shamir's shares notoriously have the issue that the key does exist
plaintext on a device at some point.

Non-interactive multisig has the benefit of being able to sign transactions
without having keys in the same room/place/device ever.
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Wed, Feb 26, 2020 at 9:14 AM Contact Team via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Everyone,
> Seed phrase security has been a subject of discussion for a long time now.
> Though there are varying opinions on the subject but the conflict usually
> arises due to different security models used by different individuals. The
> general practice in the space has been to use paper or metal engraving
> options to secure seed phrase but those too act as a single point of
> failure when secure storage is concerned. The hardware wallets, no matter
> whether use a secure element or not can be hacked either through basic
> glitching or through bigger schemes state enforced backdoors in the closed
> soured SE used.
>
> The option that Cypherock (Cypherock X1 Wallet)  is working on removes a
> single point of failure when it comes to storage of seed phrases. It uses 2
> of 4 (with the option of setting up custom threshold limit) Shamir Secret
> Sharing to  split the seed phrase into 4 different shares. Each share gets
> stored in a PIN ( hardware enforced ) Card with an EAL 6+ secure element.
> The user would need any 2 of these 4 cyCards to recover the seed or make a
> transaction. Ideally they should all be stored at different locations and
> this added security through distribution makes losing seed phrase highly
> improbable. We have decoupled storage and computation aspect of a hardware
> wallet. More information can be obtained from cypherock.com. The purpose
> of this mail is to get feedback from the community. Let us know if there is
> any feedback, we would love it.
>
> Thanks
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 3570 bytes --]

Re: [bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[Christopher Allen]

[-- Attachment #1.1: Type: text/plain, Size: 3387 bytes --]

On Wed, Feb 26, 2020 at 11:56 AM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As a replacement for paper, something like this makes sense v.s. what you
> do with a ledger presently.
>
> However, shamir's shares notoriously have the issue that the key does
> exist plaintext on a device at some point.
>
> Non-interactive multisig has the benefit of being able to sign
> transactions without having keys in the same room/place/device ever.
>

I agree that that interactive multisig is best for transactional recovery,
but there is still a place in our tool chest for Shamir split backups
especially in operational security scenarios, but as you state, you must be
aware of the limitations of Shamir, not only from the fact that there is
vulnerability in that you must restore keys in one place, but also there
are denial edge cases where when you only have k-1 of n, someone can deny
you knowledge of who gave you the corrupted share.

Right now the best C-library for Shamir sharding of recovery seeds is at
the Blockchain Commons Github
https://github.com/BlockchainCommons/sss/blob/master/README_slip39.md however,
this code base needs refactoring to be a good standalone library. This
requires us separating out the Shamir portions from the SLIP-39 mnemonic
elements and command-line elements. We also want to separate out the
randomness portions of the code so you can test different implementations
against deterministic randomness to ensure they give the same value (but
don't use this for production!) Once this is complete, we will be
submitting this library for formal review.

We are also working on air-gapped open-source open hardware for seed
creations and Shamir restoration. For instance, this device has no wifi,
Bluetooth, or persistent memory, and the serial port is disabled. It is
sized to fit in a bank safe deposit box. See
https://twitter.com/ChristopherA/status/1175465994644574208?s=20

[image: image.png]

Longer-term for seed sharding, we want to leverage the VSS (Verifiable
Secret Sharing) that future Bitcoin musig uses, which we believe has
advantages over Shamir Secret Sharing. It can be used for both traditional
sharding, but also for musig transactional recovery without restoring of
master seeds on a single device, and it is easier to prove that shares are
live and avoid denial use cases.

All this being said, we recommend Bitcoin multisig transactions as the best
solution for self-sovereign recovery of funds vs using Shamir (or SLIP39).
Lately, we've been working on PSBT and bitcoind descriptor support in our
alpha bitcoin wallet for iOS, FullyNoded 2
https://github.com/BlockchainCommons/FullyNoded-2 — in theory, this iOS
wallet can facilitate any scenario that bitcoind supports as a descriptor
as it communicates with your own private full-node over Tor v3.

P.S. If you've not seen it yet, our free #SmartCustody book
http://bit.ly/SmartCustodyBookV101 offers what we think are current best
practices for single seed recovery. We did not include multisig scenarios
in v1 of this book as at the time they were too difficult and error-prone
for most people. We are now working on v2 of the book which will cover
multisign and fiduciary scenarios now that PSBT is maturing and more
wallets are improving multisig support.

— Christopher Allen

[-- Attachment #1.2: Type: text/html, Size: 4640 bytes --]

[-- Attachment #2: image.png --]
[-- Type: image/png, Size: 4330187 bytes --]

Re: [bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[ZmnSCPxj]

Good morning Christopher,

>
> > As a replacement for paper, something like this makes sense v.s. what you do with a ledger presently.
> >
> > However, shamir's shares notoriously have the issue that the key does exist plaintext on a device at some point.
> >
> > Non-interactive multisig has the benefit of being able to sign transactions without having keys in the same room/place/device ever.
>
> I agree that that interactive multisig is best for transactional recovery, but there is still a place in our tool chest for Shamir split backups especially in operational security scenarios, but as you state, you must be aware of the limitations of Shamir, not only from the fact that there is vulnerability in that you must restore keys in one place, but also there are denial edge cases where when you only have k-1 of n, someone can deny you knowledge of who gave you the corrupted share. 
>
> Right now the best C-library for Shamir sharding of recovery seeds is at the Blockchain Commons Github https://github.com/BlockchainCommons/sss/blob/master/README_slip39.md however, this code base needs refactoring to be a good standalone library. This requires us separating out the Shamir portions from the SLIP-39 mnemonic elements and command-line elements. We also want to separate out the randomness portions of the code so you can test different implementations against deterministic randomness to ensure they give the same value (but don't use this for production!) Once this is complete, we will be submitting this library for formal review.
>
> We are also working on air-gapped open-source open hardware for seed creations and Shamir restoration. For instance, this device has no wifi, Bluetooth, or persistent memory, and the serial port is disabled. It is sized to fit in a bank safe deposit box. See https://twitter.com/ChristopherA/status/1175465994644574208?s=20
>
> Longer-term for seed sharding, we want to leverage the VSS (Verifiable Secret Sharing) that future Bitcoin musig uses, which we believe has advantages over Shamir Secret Sharing. It can be used for both traditional sharding, but also for musig transactional recovery without restoring of master seeds on a single device, and it is easier to prove that shares are live and avoid denial use cases.
>
> All this being said, we recommend Bitcoin multisig transactions as the best solution for self-sovereign recovery of funds vs using Shamir (or SLIP39). Lately, we've been working on PSBT and bitcoind descriptor support in our alpha bitcoin wallet for iOS, FullyNoded 2 https://github.com/BlockchainCommons/FullyNoded-2 — in theory, this iOS wallet can facilitate any scenario that bitcoind supports as a descriptor as it communicates with your own private full-node over Tor v3.
>
> P.S. If you've not seen it yet, our free #SmartCustody book http://bit.ly/SmartCustodyBookV101 offers what we think are current best practices for single seed recovery. We did not include multisig scenarios in v1 of this book as at the time they were too difficult and error-prone for most people. We are now working on v2 of the book which will cover multisign and fiduciary scenarios now that PSBT is maturing and more wallets are improving multisig support.

I believe you missed a point that Jeremy was making:

* In a Shamir Secret Sharing Scheme, at some point in the past, some device had to contain the actual original pre-shared secret, and that device might have had backdoors you were unaware of at the time that you were doing the secret sharing.
  * Thus the entire secret might already be compromised long before you recover the secret again.

Verifiable Secret Sharing seems to be better in this regard, as each signer device can generate its own share independently of every other and effectively do an interactive setup to determine their public key (as I understand it --- I am not a mathist, and while I do have some notes regarding this from gmax, I confess I still have only a vague grasp of this math).
It may be better to outright forget Shamir Secret Sharing even exists, and prefer to use Verifiable Secret Sharing instead.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 4064 bytes --]

On Wed, Feb 26, 2020 at 2:56 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As a replacement for paper, something like this makes sense v.s. what you
> do with a ledger presently.
>
> However, shamir's shares notoriously have the issue that the key does
> exist plaintext on a device at some point.
>
> Non-interactive multisig has the benefit of being able to sign
> transactions without having keys in the same room/place/device ever.
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
>

The way I see it, the main benefit of Shamir's Secret Sharing is for those
people who are already willing or wanting to be able to sign transactions
on a single device, in a single room, etc., but would prefer not to keep
their secret backup in a single room/place/device.  It is one thing to go
and gather your shares whenever you need to recover from a broken/wiped
hardware wallet versus having to go gather your shares whenever you want to
make a transaction.  (I do agree that SSS is not a suitabl for creating a
multisig from multiple participants.)

This thread inspired me tidy up and post my concept for creating secret
shares using paper computers (slide charts) and can be found at
https://github.com/roconnor-blockstream/SSS32/blob/master/SSS32.ps. It is a
design for splitting a secret encoded in the Bech32 alphabet into 2-of-n
shares (where n <= 31) using pencil, paper and lookup tables.  There are
numerous issues <https://github.com/roconnor-blockstream/SSS32/issues> and
more that need to be addressed before one could even think about using it
for actual valuable data.  Right now I'm mostly interested to find out if
paper sharing is really feasible.

A secret of 26 random Bech32 characters provides 130 bits of entropy, and a
secret of 51 random Bech32 characters provides 255 bits of entropy.
However, to enable robust recovery, the secret data ought to contain an
error correcting code.  Because each character of the secret is
independently split into shares, any single character error in one of the
shares translates into a single character error in the recovered secret
which can be corrected by the error correcting code.  See the exercise at
the end of "Verifying Bech32 Checksums with Pen and Paper" <
http://r6.ca/blog/20180106T164028Z.html> on how to attach the Bech32 error
correcting code to a raw secret string by hand.  However, protecting the
secret data is so important that one would want to design a checksum BCH
code longer than 6 characters to get strong error correcting capabilities.

I still don't know if this proposed method all a good idea or not.  I've
only experimented with encoding and recovering a 10 character "secret"
data.  Generating 2-of-n shares is quite easy as all the shares are a
function of the secret share and the first random share.  It only takes
lookup up a pair of coordinates in a table to generate one character for
each of the n shares together.  Recovering the secret data is more work;
however, if your plan is to recover a hardware wallet anyways, it is
reasonable for the hardware wallet to do the recovery from the shares
itself for you.  Generating the error correcting code by hand is a bit more
worrying, because it doesn't do you much good if your generate an incorrect
checksum.  However, by doing 1 or 2 manual passes to verify the checksum is
maybe adequate.  Also passing the secret data into the hardware wallet you
wish to use, along with its checksum, would let the hardware wallet tell
you if there was an error in the checksum.  I think creating more general
3-of-n schemes can be implemented too, but require work similar to recovery
to generate rather than the simple lookup table process.  Generating 4-of-n
and higher schemes may also be possible, but would require even more hand
computation (i.e. computing lagrange polynomials.)

Maybe this scheme is workable for the subset of people that this would
appeal to.  In anycase, my document is open source and available for those
who want to tinker with it.

[-- Attachment #2: Type: text/html, Size: 5438 bytes --]

[bitcoin-dev] On the compatibility of Bech32 and Shamir's Secret Sharing

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 4930 bytes --]

With the help of Pieter I've recently made some interesting mathematical
observations about Bech32 codewords and Shamir's secret sharing:

(1) Affine combinations of two Bech32 codewords is again a valid Bech32
codeword.
(2) Lagrange polynomials form a partition of unity.

The consequences of these facts is that when you perform Shamir's secret
sharing where all your shares have valid Bech32 checksums, then the
resulting secret will also have a valid Bech32 checksum.  Conversely, if
your secret has a valid Bech32 checksum, and your random shares have valid
Bech32 checksums, then all your derived shares will have valid Bech32
checksums.  This can form a basis on which we can build a simple secret
sharing scheme for dividing up a BIP-32 master seed.

In order to illustrate this, I'll describe an example scheme for *k*-of-*n*
Shamir's secret sharing scheme where *2 <= k* <= *n* <= 31.

Suppose we have a 128-bit master seed 0xb6721d937d82f238672de4db91b87d0c.
We encode this secret as the following Bech32 codeword: "
donotusesss321s2name00keepmymasterseedunderwraps2n89wr".  Let's deconstruct
this codeword.

"donotusesss32": A Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"s": The first data character is the index of this share. Each index is a
Bech32 character.  In this scheme the secret share is always at index "s",
which stands for "secret".
"2": The second data character is the threshold.  In this example we are
using a 2-of-n threshold.  We use the digits 2-9 for thresholds upto 9.  We
use Bech32 characters a-y for thresholds from 10 to 31.
"name00": The next 6 characters are an id for this set of shares.  This id
isn't part of the secret data. It is used to ensure that the shares you are
reconstructing were generated for the same secret.  This id just needs to
be unique for all the secrets that you are dividing up with this scheme.
The id can be chosen randomly, sequentially, or even set to the constant
such as "qqqqqq" if you do not want to use it for identification.
"keepmymasterseedunderwraps": This is the 128-bit secret master seed
0xb6721d937d82f238672de4db91b87d0c encoded in Bech32.  The master seed can
be a 128-bit, 256-bit or 512-bit value.
"2n89wr" is the Bech32 checksum.

We will generate shares for a 2-of-3 threshold.  We generate the first
share at index "a".  In this example we generate "
donotusesss321a2name00q0h5aajczn04g9sh0wtsl2f0y0g3vlkr".

"donotusesss32": The Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"a": The first data character is the index of this share which we have
chosen to be "a".
"2": The second data character is the threshold, which is 2.
"name00": The next 6 characters is the id we chose above for this set of
shares.
"q0h5aajczn04g9sh0wtsl2f0y0": This is 26 randomly selected bech32 characters
"g3vlkr" is the Bech32 checksum.

We generated the next two shares at index "c" and and index "d".  These
shares are generated using characterwise Lagrange interpolation of the
secret share and the above randomly generated share.
The resulting shares are "
donotusesss321c2name00chzu58ep57hd9xmaw6zmuyjeau0kq4mr" and "
donotusesss321d2name00ung8rmkf2snftj57zu45g7z84hzmzk4r"

Notice that the resulting strings have
(1) valid checksums;
(2) have correct indices;
(3) have the correct threshold values;
(4) have the correct ids.

This scheme still enjoys the perfect information hiding property of
Shamir's secret sharing.  Even when you know *k*-1 shares, every possible
master seed value has exactly one set of shares that includes those
particular *k*-1 shares, so knowing *k*-1 shares tells you nothing about
the secret data value.

One nice property of Lagrange interpolation is that it is simple enough to
compute by hand with the help of a few lookup tables.  Bech32 checksums can
also be computed and checked by hand with the help of lookup tables.  While
the majority of users wouldn't do hand computations, those motivated users
who have a healthy distrust of digital devices can generate and manipulate
the secret shares by hand.  The Bech32 checksum property means that after
generating the shares by hand, you can then validate the checksums by hand.
With extremely high probability, you will catch any computation error you
make.  My SSS32 repository at https://github.com/roconnor-blockstream/SSS32
has a postscript file that generates the lookup tables needed for hand
computation, although the document is a bit disorganized at the moment.

The main deficiency of the scheme presented here is that we want a longer
checksum than used in BIP-173 that is more suitable for error correction,
rather than simply error detection.

This example scheme was inspired in part by SLIP-32
<https://github.com/satoshilabs/slips/blob/master/slip-0032.md> with the
intent to be a hand computable version of the same idea.

P.S. It is possible that this all could be made obsolete by a threshold
musig signature scheme.

[-- Attachment #2: Type: text/html, Size: 6922 bytes --]