Practical way to split a bip39 seed into a 2 out of 3 factor auth?

Question

I want to keep off-site paper-backups of my seed, but that increases the risk of a physical attack. Can I somehow split my Mnemonic Code into three parts that I only need two of to recover my trezor?

Answer 1

One can use Shamir's Secret Sharing Scheme, but the input ASCII string must be under 128 ASCII characters in length. Fortunately, the 2048 English BIP 39 words are guaranteed to be unique from their 1st four characters, sometimes even fewer characters.

Let's assume the 24 recovery words are "bunker wreck real edge inflict aerobic buddy mercy divorce wolf bright immune fat foot poet section sustain reveal unique reflect have latin problem chapter", which is longer than 128 characters.

The shortened string becomes "bunk wrec real edge infl aero budd merc divo wolf brig immu fat foot poet sect sust reve uniq refl have lati prob chap". The full word length can be reconstituted by examining complete list of 2048 English BIP 39 words.

You can get ssss-split and ssss-combine from http://point-at-infinity.org/ssss/. On Arch Linux, there is an AUR package providing them.

% echo "bunk wrec real edge infl aero budd merc divo wolf brig immu fat foot poet sect sust reve uniq refl have lati prob chap" | ./ssss-split -t 2 -n 3 -w MyWill

WARNING: couldn't get memory lock (ENOSYS, kernel doesn't allow page locking).
Generating shares using a (2,3) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: Using a 944 bit security level.

**MyWill-1-e77f7d1fbeca7f35fc9735f698df76e3aa6187c5b8b1110ab1b249b69435fd23f3e35724736f0a76aa3157d8c483f9a633ba254dc518fda26ec1ee0907a7dc8dba1a9733ab14038b0f2e42ce8ad457192befa42c8afa7d55d739f07e7f252463610b1030283002941187b0fc2e423730af25d54807da**

**MyWill-2-bbf6fc411a6cce683b26bd888aed207ba3ef8aa8235a89010031f67f565bfbebd6e410e2cd16145bb28475d2b71eba8fccecb5bcf881e3eb26ba8d5f65ee61a6981052f8eab864e8a7b582e969cc34ec917157303005d674584ad57e0097bb9408a83948d4960d29316a548bce8c4ecee23ad7474436**

**MyWill-3-70718374860ea15c8649c5a284fcedf3a4958e7355fc010790b09cc7e87e0653ca192da0a73ee1bf45176bd49995846899dec5ec13f6e9d3e16c5392bbd6f54079e9ee41d5dc46363fc33d0bc8c415bff8fb063ba650b094dd64367e2a0631392fc9219f7f0bf7bdd13108a691366664d9302942736f**

% ./ssss-combine -t 2
WARNING: couldn't get memory lock (ENOSYS, kernel doesn't allow page locking).

Enter 2 shares separated by newlines:
Share [1/2]: MyWill-1-e77f7d1fbeca7f35fc9735f698df76e3aa6187c5b8b1110ab1b249b69435fd23f3e35724736f0a76aa3157d8c483f9a633ba254dc518fda26ec1ee0907a7dc8dba1a9733ab14038b0f2e42ce8ad457192befa42c8afa7d55d739f07e7f252463610b1030283002941187b0fc2e423730af25d54807da

Share [2/2]: MyWill-3-70718374860ea15c8649c5a284fcedf3a4958e7355fc010790b09cc7e87e0653ca192da0a73ee1bf45176bd49995846899dec5ec13f6e9d3e16c5392bbd6f54079e9ee41d5dc46363fc33d0bc8c415bff8fb063ba650b094dd64367e2a0631392fc9219f7f0bf7bdd13108a691366664d9302942736f

**Resulting secret: bunk wrec real edge infl aero budd merc divo wolf brig immu fat foot poet sect sust reve uniq refl have lati prob chap**

The same Shamir's Secret Sharing Scheme can also be applied to a complementary BIP 39 passphrase.

Answer 2

One Time Pad or XOR is an elegant and information-theoretic secure [1] way to split a BIP39 seed. It's a method simple to describe (apt for a will), easy to verify (trust only yourself) and the resulting shares are mnemonics thus easy to record.

Best of all it can be computed entirely with paper and pencil eliminating risks from malware. The method does not scale efficiently for n of m when m is large, but works well for n of n, 2 of 3 and possibly 3 of 5.

Consider an example of a three word mnemonic from the 2048 word BIP-0039 dictionary:

S = "night love grit"

We will split the seed S into two parts, A and B, such that A + B = S (where + is element wise addition mod 2048). First generate a random key A of the same length, say A = "steel siren layer". To find the second key B, go word by word subtracting the dictionary indexes mod 2048 of A from S:

1st: (night - steel) mod 2048 = (1197 - 1706) mod 2048 = 1539 = scare

2nd: (love - siren) mod 2048 = (1060 - 1612) mod 2048 = 1496 = road

3rd: (grit - layer) mod 2048 = (822 - 1011) mod 2048 = 1859 = tribe

Thus B = S - A = "scare road tribe". To retrieve S add the two keys together:

1st: (steel + scare) mod 2048 = (1539 + 1706) mod 2048 = 1197 = night

2nd: (siren + road) mod 2048 = (1496 + 1612) mod 2048 = 1060 = love

3rd: (layer + tribe) mod 2048 = (1859 + 1011) mod 2048 = 822 = grit

As promised, S = A + B. Even with infinite computing power A and B reveal zero information about S. Individually they are nothing but random numbers. 3 of 3 can be achieved by generating two random keys, say A and B. Then the third key C is found as:

C = S - A - B; giving S = A + B + C. This can be extended to n of n.

For 2 of 3 repeat the method three times. Each time use a different random key A; say A1, A2 and A3. This generates three keys B1, B2 and B3. So now we have:

A1 + B1 = S

A2 + B2 = S

A3 + B3 = S

Divide the keys like this:

Switzerland: A1, A2

Canada: A3, B1

New Zealand: B2, B3

Vires in Numeris!

Answer 3

My personal preferences:

• Stick to known-good algorithms like Shamir's Secret Sharing Scheme whose security properties are well-understood, rather than trying to invent something new.

• Reuse existing tools and formats/encodings, so you aren't dependent on something obscure or homemade that might not be maintained 10 years from now.

• Try to encode the seed using mnemonics, with as few words as possible, to reduce the potential for human error. Typing in long hex strings isn't very user-friendly, and passing them around in electronic form can create the potential for inadvertent leaks.

With that in mind, here is what I'd propose:

0) Install the appropriate command-line tools:

$ sudo apt install cpanminus build-essential ssss
$ sudo cpanm App::BIP39Utils

1) Convert your 24-word recovery seed back into a 256-bit hex number:

$ bip39-mnemonic-to-entropy "spider tongue exclude enable wise vacuum cereal cereal rescue stone wash remain ahead goose scene relief buzz believe arm rely result volume appear cave" \
  | tee seed.txt
d1bc8d3ba4afc7e109612cb73acbdddac052c93025aa1f82942edabb7deb82a1

2) Use SSSS to split the raw hex seed. Using the raw seed as the input is important: it means the shares will be 256 bits long and can themselves be encoded using BIP39:

$ ssss-split -q -t 2 -n 3 -x < seed.txt | tee shares.txt
1-0b16c10b9597bc0d6a0223b25c5536b942bfe17ed5887a341e9dfbc1c878c36f
2-d312bb875b9f9273ec8a8cb5a1385274bac3cc5b1d5bf6b17f8b0f1c9953abbe
3-64ee92031e678859910d1648f5e371cfed17d747a51572cda086a357a9b57010

3) Encode each of the shares into a 24-word phrase using BIP39:

$ cat shares.txt | \
  ( IFS=-; while read i s; do echo "$i: `entropy-to-bip39-mnemonic $s`"; done )
1: arch render drill clinic knock allow pool dutch rather tired ethics income cloud vague win rain kick path polar wasp broken detect asset want
2: spread noise tide rescue weird delay rate face remember antenna behind truly promote tower hockey problem wall message tissue bullet sister prefer puzzle stumble
3: gossip innocent liar devote joy coast during people employ pyramid symbol panther sphere two burden pencil index home canvas effort kind survey scare beef

4) Write down each share on a separate sheet of paper. Store (1) in your sock drawer, (2) with your estate lawyer, and (3) in your safe deposit box. Or whatever. Remember to write down both the share number and the threshold on each sheet.

5) To reconstruct the recovery seed phrase, convert any two shares from BIP39 to hex:

$ echo 1-`bip39-mnemonic-to-entropy "arch render drill clinic knock allow pool dutch rather tired ethics income cloud vague win rain kick path polar wasp broken detect asset want"` \
  > combine.txt
$ echo 3-`bip39-mnemonic-to-entropy "gossip innocent liar devote joy coast during people employ pyramid symbol panther sphere two burden pencil index home canvas effort kind survey scare beef"` \
  >> combine.txt
$ cat combine.txt 
1-0b16c10b9597bc0d6a0223b25c5536b942bfe17ed5887a341e9dfbc1c878c36f
3-64ee92031e678859910d1648f5e371cfed17d747a51572cda086a357a9b57010

Or:

$ echo 2-`bip39-mnemonic-to-entropy "spread noise tide rescue weird delay rate face remember antenna behind truly promote tower hockey problem wall message tissue bullet sister prefer puzzle stumble"` \
  > combine.txt
$ echo 3-`bip39-mnemonic-to-entropy "gossip innocent liar devote joy coast during people employ pyramid symbol panther sphere two burden pencil index home canvas effort kind survey scare beef"` \
  >> combine.txt

Or 1 and 2.

6) Then combine them using SSSS, to return the original hex seed from step 1:

$ ssss-combine -q -t 2 -x < combine.txt
d1bc8d3ba4afc7e109612cb73acbdddac052c93025aa1f82942edabb7deb82a1
$ entropy-to-bip39-mnemonic d1bc8d3ba4afc7e109612cb73acbdddac052c93025aa1f82942edabb7deb82a1
spider tongue exclude enable wise vacuum cereal cereal rescue stone wash remain ahead goose scene relief buzz believe arm rely result volume appear cave

Some security considerations:

• Only handle seeds on an air-gapped computer booted from trusted media (e.g. a live Linux CD). Unplug the network and any HDDs prior to entering any secrets on the system, and power off the system before plugging anything back in. You don't want any of this data to be inadvertently stored or transmitted to the network.

• Never use a printer to record seed data. Traces of printed output may be recoverable from e.g. paper rollers. It might persist in the printer's memory.

• Some live CD images might automatically use any swap partitions they find on the system. Beware.

• If you are writing down BIP39 phrases, consider what is underneath the paper. For instance, if you are using 3 consecutive sheets from a notepad, it may be possible to reconstruct information by looking at the impressions left in the paper.

• If you're paranoid, cover up any phone/laptop cameras whenever you handle recovery seeds.

The bip39-standalone web tool may be usable in lieu of App::BIP39Utils.

Answer 4

There are at least three practical tools implementing Shamir Secret Sharing with BIP39 mnemonics:

• https://github.com/iancoleman/slip39/
• https://github.com/unchained-capital/hermit
• https://github.com/trezor/python-shamir-mnemonic/

Answer 5

Here's a 3 of 5 one time pad solution with just 2 series (A is a random key, B is a random key, C is Real⊕A⊕B, Real is A⊕B⊕C. Thanks to @answerevaded, @oisyn, and @Scooper this is just a simplification for the 3 of 5 case: {A1, A2}, {B1, B2}, {C1, A2}, {B1, C2}, {A1, C2}

Implementation in any language is simple, which is why I prefer this solution to SSS: it's easy to audit the code and verify it does exactly what it is supposed to do and nothing more. There are no external dependencies or browser required on an air-gapped computer and the code can be typed in a few minutes, or it can be computed by hand. (Note I used simplified notation in the code below: collect either a, b, and c or x, y, and z to reconstruct the key.)

As a bonus, all the key parts are themselves valid keys, which allows them to fit on standard media (metal key tables, etc.).

The following 54 lines of python does secure key generation, splitting and joining, validates checksums, supports 12 and 24 word mnemonics, and handles mnemonics abbreviated to their first 4 letters. Get bip39-wordlist.txt here: https://github.com/bitcoin/bips/tree/master/bip-0039

import hashlib
import os
import sys

BYTES = int(256 / 8)  # 256 bit key for 24 word mnemonic, 128 bit for 12 words

def rand(bytes=BYTES):
  return os.urandom(bytes)

def xor(key1, key2):
  return bytearray([k1 ^ k2 for k1, k2 in zip(key1, key2)])

def raw_to_indices(key):
  checksum = hashlib.sha256(key).digest()[:1]
  binary = ''.join([bin(b)[2:].rjust(8, '0') for b in key+checksum])
  return [int(binary[i*11:i*11+11], 2) for i in range(int(len(binary) / 11))]

def indices_to_raw(indices, bytes=BYTES):
  binary = ''.join([bin(i)[2:].rjust(11, '0') for i in indices])
  assert len(binary) == (bytes*8+8)/11*11, 'Unexpected key length'
  raw_key = bytearray([int(binary[i*8:i*8+8], 2) for i in range(bytes)])
  assert raw_to_indices(raw_key) == indices, 'Invalid Checksum'
  return raw_key

def words(indices):
  with open('bip39-wordlist.txt') as wordfile:
    wordlist = wordfile.read().splitlines()
    return [wordlist[i] for i in indices]

def indices(words):
  with open('bip39-wordlist.txt') as wordfile:
    wordlist = [w[:4] for w in wordfile.read().splitlines()]
    return [wordlist.index(w[:4]) for w in words]

def print_keys(names, keys):
  for name, key in zip(names, keys):
      print('%s: %s' % (name, ' '.join(words(raw_to_indices(key)))))

real, a, b, x, y = rand(), rand(), rand(), rand(), rand()
c, z = xor(xor(real, a), b), xor(xor(real, x), y)
assert real == xor(a, xor(b, c)) and real == xor(x, xor(y, z)), 'Invalid Keys'
print_keys(['a', 'b', 'c', 'x', 'y', 'z', 'real'], [a, b, c, x, y, z, real])
print('''Recovery proof: p1: ax, p2: by, p3: cx, p4: bz, p5: az
      p123: abc, p124: xyz, p125: xyz, p234: yxz, p235: bca, p345: cba''')
while True:
  k = [0] * 32
  try:
    for n in range(3):
      print('%s> ' % ['a or x', 'b or y', 'c or z'][n], end='')
      sys.stdout.flush()
      k = xor(k, indices_to_raw(indices(sys.stdin.readline().strip().split())))
    print_keys(['real'], [k])
  except Exception as e:
    print(e)

Answer 6

This can be scaled up to 24 word seeds just by continuing the pattern.

Answer 7

Create a 2 of 3 multisig wallet using electrum or copay. You'll get 3 seeds any 2 of which need to be used to spend your coins. Alternatively create a 2 of 4 multisig wallet. You can create any combination involving up to 15 co-signers. Here's a guide for electrum in case you are interested.

Answer 8

The answer by answerevaded seems the safest solution to the problem. In addition to his scale examples for "n of n" and "2 out of 3", here is the example for "3 out of 5":

For "3 out of 5" you need to create 10 random keys in the way answerevaded explains the "3 of 3" system. This will result in keys A1-A10, B1-B10 and C1-C10.

You must divide the keys over the participants in the following fashion:

Person 1: A1, A2, A3, A4, A5, A6

Person 2: B1, B2, B3, A7, A8, A9

Person 3: C1, B4, B5, B7, B8, A10

Person 4: C2, C4, B6, C7, B9, B10

Person 5: C3, C5, C6, C8, C9, C10

Only 3 random persons out of the total 5 will be needed to calculate the real seed word. You must create these keys for each mnemonic word. To make it more comprehensible to the persons attending, you could describe to each person which list of words he needs to use with every combination of 3 persons. Example for person 3:

List 1 (first word C1) in case you are together with person 1 and 2

List 2 (first word B4) in case you are together with person 1 and 4

List 3 (first word B5) in case you are together with person 1 and 5

List 4 (first word B7) in case you are together with person 2 and 4

List 5 (first word B8) in case you are together with person 2 and 5

List 6 (first word A10) in case you are together with person 4 and 5

Answer 9

BIP 39 has no such standard for doing so, and AFAIK, there is no standard for splitting a seed like that. However you could create something that uses Shamir's Secret Sharing to split the seed (which the mnemonic encodes) into parts and then encode those parts as something memorable like the mnemonic. But AFAIK, there is no software that does this for you.

Answer 10

I created a Nodejs library and command line tool that can do exactly this. Currently it only works with a raw private key of almost any length, but I would like to enhance it to work directly with BIP39 seeds as well. It uses one time padding on the keys as well, making any of the 3 split keys as strong as the original one. It also generates bar codes for each of the three split keys.

I'm working on a little webapp (that runs fully client side of course) that can be used to generate the split keys, as well as scan in the split keys to restore the original key.

https://github.com/phulst/keysplitter

Answer 11

https://github.com/GhostOfSatoshi/BitcoinSeedSplitter

Open source Shamir BIP39 implementation in C# (use with usual caution).

Slip39 mentioned earlier is NOT backing up your seed, but the derived master key. From that it is impossible to get the seed back.

Answer 12

There is a very thoughtfully designed system for M of N sharding of seed phrases called SSKR (Sharded Secret Key Reconstruction). It is superior to the SLIP39 that @Gabor mentions in that the actual seed phrase is recoverable once you have the desired number of shards. However, it is not (yet?) widely supported by hardware wallet manufacturers and (like all the Shamir Secret Sharing-based approaches, and unlike some XOR approaches) you would be hard-pressed to do the math by hand or reimplement the calculations yourself.