trezor / python-shamir-mnemonic Goto Github PK

Shares generated by version 0.3.0 are rejected during recovery in old versions.
In particular, shares I generate with 0.3.0 cannot be used to restore with in Electrum.

user@user-VirtualBox:~/wspace/tmp$ python3 -m venv env30
user@user-VirtualBox:~/wspace/tmp$ source env30/bin/activate
(env30) user@user-VirtualBox:~/wspace/tmp$ pip install shamir-mnemonic[cli]==0.3.0
Collecting shamir-mnemonic[cli]==0.3.0
  Downloading shamir_mnemonic-0.3.0-py3-none-any.whl (23 kB)
Collecting click<9,>=7
  Using cached click-8.1.7-py3-none-any.whl (97 kB)
Installing collected packages: shamir-mnemonic, click
Successfully installed click-8.1.7 shamir-mnemonic-0.3.0
(env30) user@user-VirtualBox:~/wspace/tmp$ shamir create 2of3 --master-secret="5be935613b67a9d53bfafe03fab5e92ea5bcacc6449cf151714730cdf366b0a7e0a644d571aa2559f201f193231e9dab7a4eb9b2854a19536d2e0fc9bc3d7cc8"
Using master secret: 5be935613b67a9d53bfafe03fab5e92ea5bcacc6449cf151714730cdf366b0a7e0a644d571aa2559f201f193231e9dab7a4eb9b2854a19536d2e0fc9bc3d7cc8
Group 1 of 1 - 2 of 3 shares required:
species biology academic acid acne depart vintage object aluminum grumpy friar season therapy dynamic ivory tracks large spark leaf pleasure dragon dish junction capture render founder marathon tackle float step maiden loud should trust permit decrease total enemy that privacy midst maximum armed mandate carve have symbolic armed payroll news seafood density segment frequent perfect spelling year deadline gesture
species biology academic agency acquire reunion unfair darkness prayer cubic guest glad energy database video patrol smell laden literary sled amount review crucial national river hush lawsuit square inmate training trouble wavy garlic express royal guard mason lend source diminish custody fitness flip rainbow miracle guitar listen course render industry satisfy soldier crucial machine snapshot sheriff bracelet yield mandate
species biology academic always acid critical greatest iris findings vintage listen sidewalk relate carve idle priest aide main document chubby fused fumes steady armed prospect aluminum sunlight smear adjust relate express dryer listen patent hormone organize depart smell learn omit velvet extend physics provide cards already slap round mild elevator slap python agree visual exhaust tracks mild race tension
(env30) user@user-VirtualBox:~/wspace/tmp$ 

user@user-VirtualBox:~/wspace/tmp$ python3 -m venv env22
user@user-VirtualBox:~/wspace/tmp$ source env22/bin/activate
(env22) user@user-VirtualBox:~/wspace/tmp$ pip install shamir-mnemonic==0.2.2
Collecting shamir-mnemonic==0.2.2
  Using cached shamir_mnemonic-0.2.2-py3-none-any.whl (22 kB)
Collecting colorama
  Using cached colorama-0.4.6-py2.py3-none-any.whl (25 kB)
Collecting attrs
  Using cached attrs-23.2.0-py3-none-any.whl (60 kB)
Collecting click<9,>=7
  Using cached click-8.1.7-py3-none-any.whl (97 kB)
Installing collected packages: colorama, click, attrs, shamir-mnemonic
Successfully installed attrs-23.2.0 click-8.1.7 colorama-0.4.6 shamir-mnemonic-0.2.2
(env22) user@user-VirtualBox:~/wspace/tmp$ shamir recover
Enter a recovery share: species biology academic acid acne depart vintage object aluminum grumpy friar season therapy dynamic ivory tracks large spark leaf pleasure dragon dish junction capture render founder marathon tackle float step maiden loud should trust permit decrease total enemy that privacy midst maximum armed mandate carve have symbolic armed payroll news seafood density segment frequent perfect spelling year deadline gesture
ERROR: Invalid mnemonic checksum for "species biology academic acid ...".
Enter a recovery share: 

Note that the other direction works: shares generated by old versions are accepted by 0.3.0.

It would obviously be great if we could also use Shamir's secret to split BIP-0039 seeds directly.

• Software wallets would not have to implement one more protocol.
• Old hardware wallets would work with Shamir mnemonics.
• Custom BIP-0039 extension words would still work.
• The user wouldn't need to move funds from existing BIP-0039 wallets to SLIP-0039 wallets if they feel the original seed is not compromised.

Of course, SLIP-0039 says this could happen

only at the price of all SLIP-0039 shares being 59 words long regardless of the length of the original because the 512 bit seed which is what would need to be split using SLIP-0039.

Furthermore, anyone who is using several different passphrases with one BIP-0039 mnemonic to have several wallets can convert only one of these wallets to SLIP-0039 shares.

Are these points expanded anywhere? I'm probably missing something but, from my ignorant point of view, both statements seem unjustified as they are.

A 12-word BIP-0039 mneumonic encodes 16 bytes (128 bits) + 4 checksum bits of information before the passphrase comes in.

It seems like the SLIP-0039 master secret already also encodes 16 bytes by default:

> shamir create 3of5
Using master secret: 42818ca31b45a696cced1ea399273aca
[...]

So considering:

• There's nothing to be gained by encoding the 512 bit seed if its original information/entropy was 128 bits.
• The checksum obviously needs to be checked but not encoded in the master secret. Not that this changes things much.
• Same with the passphrase / extension word, which is meant to be remembered anyway.

we could just

> shamir create 3of5 --mnemonics='word1 word2 word3 word4 ...
Using master secret: (first 16 bytes of bip39-secret in hex as above)
[...]
(work as usual)

which generates 20 words long secrets rather than

being 59 words long

I implemented that in this fork: https://github.com/alandefreitas/python-shamir-bip39

And then recovering the BIP-0039 seed seems like it would all just be a matter of:

• finding the master secret as usual
• recreating and appending the 4 checksum bits to the 128-bit SLIP-0039 master secret
• converting these 132 bits back to 12 words

And in this case, users can just remember their

several different passphrases

as they are usually expected to and recover any of them and not

only one of these wallets to SLIP-0039 shares

All of this sounds just a little too easy, so there's probably another requirement I'm missing.
But well, maybe something could be improved in SLIP-0039 anyway because there's nothing in there specifically justifying these statements and other people might have the same question.

#27 has changed the internal APIs significantly, and despite the external APIs being identical, it would still be useful to publish the result.

However, I don't want to do that immediately. I would leave this in the repository for a couple of weeks to gather possible feedback, and only release version 0.2.0 in early 2020

After calling shamir create 2of3, master secret is not printed out to the console. It would be useful for checking that recovery produced the same secret.

Hi,

The spec mentions:

This construction yields a beneficial property where the identifier transforms into exactly the first three words of the mnemonic code, so the user can immediately tell whether the correct shares are being combined (i.e. they have to have the same first three words). Moreover, the forth word encodes exactly the index/threshold values, so for example share #2 of 3 required shares will always correspond to the same word.

However, I don't observe this when generating the shares. Could you provide some additional clarification?

Hi,

I've been testing a couple of reference implementations and it looks like jakubtrnka/ShamirsSecretSharingScheme is not producing compatible shares. Is this tool more aligned with the spec at this point?

Thanks!

Hi,

the command in the README.md should be

pip3 install https://github.com/trezor/python-shamir-mnemonic/archive/master.zip

otherwise it produces error:

> pip3 install https://github.com/trezor/python-shamir-mnemonic
Collecting https://github.com/trezor/python-shamir-mnemonic
  Downloading https://github.com/trezor/python-shamir-mnemonic
     | 112kB 513kB/s
  Cannot unpack file /tmp/pip-unpack-06wljlcu/python-shamir-mnemonic (downloaded from /tmp/pip-req-build-8xq2vzvx, content-type: text/html; charset=utf-8); cannot detect archive format
Cannot determine archive format of /tmp/pip-req-build-8xq2vzvx

A little nitpick, password_prompt and passphrase_prompt arguments lack the -- prefix, so they are not recognized by --help correctly.

P.S.: maybe it's a good idea to use capital "P" for the --password option?

1. I used my Trezor to create a 2 out of 3 Shamir, here are 2 of parts:

admit upstairs academic acid disease frequent medal rich domain receiver fragment extra maiden airline triumph airline hormone lips research briefing
admit upstairs academic agency crunch provide spew overall voice exotic smell umbrella dining climate activity club editor item hesitate mustang

2 I used the shamir recover to acquire the master secret, which resulted in the following master secret

0db59247dfa48d61e5809337423e5371

3. I used various services including https://github.com/trezor/python-mnemonic, with this code:

from mnemonic import Mnemonic
mnemo = Mnemonic("english")

data = bytes.fromhex("0db59247dfa48d61e5809337423e5371")
mnemo.to_mnemonic(data)

4. Which resulted in this mnemonic seed

asset prosper music satisfy emotion rail noodle bar dance ball network tiny

When restoring the Trezor with the seed list it doesn't result in the same wallet. There's a chance I'm using the master secret incorrectly, in which case I would appreciate if you could guide me.

Thanks,
Noam.

We want to use this package in our device tests. To remain consistent with the way we use python-mnemonic in the tests we would need this package published on pypi.

Is there any appetite to add the ability to accept a BIP39 passphrase as input?

A simple way to implement this would be to convert the phrase into a canonical hex representation and then pass that in as the master-secret.

One simple and relatively compact way to compress a BIP39 passphrase down is to treat each word as a three-digit hex value between 000 and 7ff, as there are 2048 words in the BIP39 wordlist.

If there's interest, I would be happy to submit a PR.

Is it implemented in Trezor firmware?

I cloned the repo and went to install from the checkout as README says, this way:
mkdir mySetup/ && python3 setup.py develop --install-dir=mySetup/ which went ok.
After that ./mySetup/shamir executes with following error:

Traceback (most recent call last):
  File "./mySetup/shamir", line 33, in <module>
    sys.exit(load_entry_point('shamir-mnemonic', 'console_scripts', 'shamir')())
  File "./mySetup/shamir", line 22, in importlib_load_entry_point
    for entry_point in distribution(dist_name).entry_points
  File "/usr/lib/python3.8/importlib/metadata.py", line 504, in distribution
    return Distribution.from_name(distribution_name)
  File "/usr/lib/python3.8/importlib/metadata.py", line 177, in from_name
    raise PackageNotFoundError(name)
importlib.metadata.PackageNotFoundError: shamir-mnemonic

Side note: pipx install might be worth recommending as that worked well for me exploring the cli. Although I have some trouble to inspect the code 'live' from the repo.

Just wondering, since I would like to do something really flexible with Shamir, being used for weighted voting.

The CLI works pretty well with click 8.0 from my testing, please consider relax the constraint on the dependency and making a new release.

If I understand things well the "not equal" check here

This would allow the following code to work :

mnemonics = shamir.generate_mnemonics(1, [(3, 5)], b"012345678901234567")
recovered = shamir.combine_mnemonics(mnemonics[0])

If I understand spec well and sss, the threshold is the mimimum share count needed to decode the secret, so it should be allowed to pass more shares.

When experimenting with this tool, I am getting shares that are 59 words long each.

I am using a BIP39 hex seed generated with this tool such as 057cc8d68a601e3e8d37c21765b2883e54e5539751a8b4f911ff1a7692d784eac3ca2657b1942e2f63b878d9dce30c61eeb298c74ccf73b1cd9e6e7da610e737 corresponding to the phrase focus list total arrow disease announce latin elbow adult inside ethics nasty.

shamir create --master-secret "057cc8d68a601e3e8d37c21765b2883e54e5539751a8b4f911ff1a7692d784eac3ca2657b1942e2f63b878d9dce30c61eeb298c74ccf73b1cd9e6e7da610e737" 3of5

Another SSSS tool from Ian Coleman (https://iancoleman.io/shamir39/) somehow produces shares of only 15 words long for the same 12 word seed phrase.

Am I doing something wrong here?
Perhaps I misunderstood the expected BIP39 seed format?

I am trying to create the hex string to feed in to the cli as the secret.

The way the code does it in default mode:

>>> import os
>>> secret_bytes = os.urandom(128 // 8)
>>> secret_bytes
b'\xb2\x80;i(\x8d\xbe\xc4#\x85\xcbH.r\xc9p'

I know how to do this a few different ways, but they all yield equivalent results as below:

>>> import codecs
>>> codecs.encode(b"how now brown cow","hex")
b'686f77206e6f772062726f776e20636f77'

This always gives this result:

ValueError: The length of the master secret in bytes must be an even number.

Though my result is even also. This is when I looked at the code and found the different form from above.

I know its something simple, but what am I missing?

Curious, what the reasoning was behind requiring an even byte length for master secrets instead of padding to an even value.

The following warning is unclear:

It is very obviously insecure.
DO NOT USE it for generating or decoding any sort of serious secrets.

• Is this saying this python implementation is incorrect and uses insecure methods of generating shares?
• Or that its shares might be incompatible with other implementations (like the Model T firmware)?
• Or is it saying that generating SLIP-39 shares using a general purpose computer is insecure because of attack surface? (meaning "use an air-gapped system")
• Or something else?

I tried test case 17~19, 20 and 23. I expected the 3rd string is the secret in the vector file, but it seems not. I got different results with cli 'restore'.

I got the following result by cli tool
case17~19: '0x62101a7ce21ebae7893c51426d535c43'
case20: '0xee9ec1ed13996aa575714bd3abb6b8947ac6c7add9cdef39ef55a722eded034d'
case24: '0x8f75a27a9dceb390b10e06d576007c3e7b32ed8ba6b521d5ceaf601df27b48ed'

Do I misunderstand something?

Thanks.

There are some technical improvements to the interface that we might want to consider based on my experience with integrating SLIP39 into Electrum. Below is a list of the modifications that I made in the Electrum implementation. Come to think of it, I actually took some of the code from the Trezor implementation.

1. I bundled everything into one file, taking only the functions which are needed for seed recovery.
   • I didn't want to introduce too many new files into Electrum. After all, in Trezor we also have most of the stuff in one file.
   • I didn't want to introduce dead code (Electrum will not support generating SLIP-39 shares).
2. Used Electrum's native Wordlist module to load and use the wordlist. IIRC Electrum uses this for word hints, so I didn't want to load the wordlist into memory twice. Also added a get_wordlist() function so that the wordlist is loaded only when needed.
3. Rewrote most strings to use the electrum.i18n _() function, but now I see I missed a few spots. Also shortened some error strings so that they would fit more nicely into the UI.
4. Renamed MnemonicError to Slip39Error, which seems more accurate.
5. Introduced an EncryptedSeed class and moved the decrypt function there. The recover_ems() function returns EncryptedSeed, which also carries information about the identifier and interation exponent. This is easier to work with if you want to allow the user to supply the passprase later.
6. recover_ems discards groups that don't meet the member threshold and allows extra shares. In python-shamir-mnemonic if the user provides extra shares, then we fail, which seems like a pointless hassle.
7. Introduced a process_mnemonics() function which formulates the status of the mnemonics and recovers the EMS if all required mnemonics are provided. Pretty much what cli.py does.
8. In some places we used threshold, which is ambiguous. Changed to member_threshold.

Not sure whether it makes sense to do anything about 1, 2 and 3 here, but I think the remaining points would be useful to apply here too. Introducing process_mnemonics() seems handy if we can do it in a non-application-specific manner.

It might make life a bit easier for implementation authors if the test vector data included some metadata denoting why the test should fail. For instance, testing the third vector failed for me, but it took some digging to determine that the point of that particular mnemonic was to test a case where the padding bits aren't all zero.

Ref:

Does this 'Groups' parameter mean that each share can be further sub-split into sub-shares, or am I confusing something?

To for example generate a standard 2of3 do I use code:

sm = shamir_mnemonic.ShamirMnemonic()
mnemonic = sm.generate_mnemonics(2, [(1,1), (1,1), (1,1)], b"secret phrase here")

or should I be using:

mnemonic = sm.generate_mnemonics(2, [(2,3), (2,3), (2,3)], b"secret phrase here")

This second seems to generate 3 x 3 fragments and I need 2 x (2 of 3) to recombine, right?

Below is an example of shares with an invalid digest being provided to the CLI. Currently, no error or message is displayed to the user that the digest was invalid, and the share counter continues to increment and loop.

example shares with invalid digest:

academic flea academic acid adult decent discuss similar branch acquire credit firm believe lecture object slavery eraser withdraw loud trust transfer terminal aunt plains favorite modern rainbow scene depict unknown pistol arcade viral
academic flea academic agency aspect public view ancestor testify greatest item olympic symbolic painting disaster platform ruler unkind debris briefing dive staff client pitch leaves mailman total staff disaster curious taught tofu warmth
academic flea academic always ambition usher remind envy wits exact maximum seafood cultural empty science guest exceed bulge velvet always welcome slim forecast plunge worthy parking become tolerate literary prayer ivory trip kernel
academic flea academic aquatic ajar hybrid inform machine alarm craft surprise arcade tension grasp grumpy arcade script analysis employer wireless critical window husband practice cowboy regular elite video medal hamster deal acid install
academic flea academic axis airline hybrid change perfect general negative join involve kidney shaft client twin email iris holy emperor laden wisdom physics scroll phrase husky timely trust unfold grownup erode faint papa

program output (before):

[sharpiro@localhost python-shamir-mnemonic]$ shamir recover
Enter a recovery share: academic flea academic acid adult decent discuss similar branch acquire credit firm believe lecture object slavery eraser withdraw loud trust transfer terminal aunt plains favorite modern rainbow scene depict unknown pistol arcade viral

⛬ 1 of 2 shares needed from group academic flea academic
Enter a recovery share: academic flea academic agency aspect public view ancestor testify greatest item olympic symbolic painting disaster platform ruler unkind debris briefing dive staff client pitch leaves mailman total staff disaster curious taught tofu warmth

✓ 2 of 2 shares needed from group academic flea academic
Enter a recovery share: academic flea academic always ambition usher remind envy wits exact maximum seafood cultural empty science guest exceed bulge velvet always welcome slim forecast plunge worthy parking become tolerate literary prayer ivory trip kernel

⛬ 3 of 2 shares needed from group academic flea academic
Enter a recovery share: academic flea academic aquatic ajar hybrid inform machine alarm craft surprise arcade tension grasp grumpy arcade script analysis employer wireless critical window husband practice cowboy regular elite video medal hamster deal acid install

⛬ 4 of 2 shares needed from group academic flea academic
Enter a recovery share: academic flea academic axis airline hybrid change perfect general negative join involve kidney shaft client twin email iris holy emperor laden wisdom physics scroll phrase husky timely trust unfold grownup erode faint papa

⛬ 5 of 2 shares needed from group academic flea academic
Enter a recovery share:

Here is a simple fix that logs that the digest is invalid and stops execution:
master...Sharpiro:cli-digest-fix

program output (after):

[sharpiro@localhost python-shamir-mnemonic]$ python3 -m shamir_mnemonic.cli recover
Enter a recovery share: academic flea academic acid adult decent discuss similar branch acquire credit firm believe lecture object slavery eraser withdraw loud trust transfer terminal aunt plains favorite modern rainbow scene depict unknown pistol arcade viral

⛬ 1 of 2 shares needed from group academic flea academic
Enter a recovery share: academic flea academic agency aspect public view ancestor testify greatest item olympic symbolic painting disaster platform ruler unkind debris briefing dive staff client pitch leaves mailman total staff disaster curious taught tofu warmth
ERROR: Invalid digest of the shared secret.

I'd be glad to help on this fix if you'd like.

Hey,

Looking at trezor-firmware, I see a parallel implementation.
I assume some of the code can't be shared because of the different computing environments assumed, but it seems there's currently no code sharing at all.
Why is that?

Thanks

Hi,
When I use the shamir tool in this repo to recover a master secret.
I wonder what other tools I will need to use in order to drive the wallet private key from this secret (with/without passphrase).

Any pointers are highly appreciated.

Thank you!

Remove the ShamirMnemonic class and refactor the CLI and tests accordingly.

Actually there's no reason to use 1ofX for groups with X > 1 and it is rather confusing that shares are almost the same, except indexes. I would rather to communicate by the script that if user want 1ofX for X>1 it is rather an user mistake or misunderstanding of things.

I was myself surprised at first moment and expected that's a bug of the library, when I was testing the tool. Thus this is UX improvement for idiots like me.