Wishlist for BIP32/39/43/44/49 and SLIP44 replacement about slips HOT 94 CLOSED

I am talking about the fact that once mnemonic encodes something more than the entropy (because it defines WHAT to do next with that entropy in order to derive keys to be used), you need to generate a new one every time you want to use it for something new.

from slips.

BIP39: I am already thinking about creating a standard that will supersede BIP39. I want to support Shamir Secret Sharing Scheme (M out of N), where old mnemonic is just special case when M=1 and N=1.

BIP 44 is too detailed.

That is the main feature of it. We wanted to BIP44-compatible actually mean something. If you had one standard that would do normal addresses, segwit addresses, etc. You would need to distinguish between various variants of BIP44 and I think it is better to say, this is a BIP44+BIP49 compatible wallet than saying BIP44-normal and BIP44-segwit.

In my own experience the current limit of 20 has downsides.

Trust me on that increasing this limit or removing it completely is a suicide.

But if not, I suggest that when a wallet scans ...

I don't agree. I think we should treat P2PKH, P2SH-P2WPKH and Bech32 as separate chains, because they ARE separate address chains. You are introducing a lot of logic and hopefully most of this won't be necessary in the future once we migrate all coins to Bech32 addresses. If we did your way, we'd need to keep this logic forever.

Account / address (hardened) derivation: Can this be improved?

I don't think so. You would not be able to use XPUB for account.

Duress passphrase

Agree that this is bad. Plausible deniable passphrase is much better and already implemented.

Other languages

I was against foreign langauges wordlists in BIP39 and still am. The new mnemonic standard should have English only words.

from slips.

@Arachnid Agreed. I've always thought it was a mistake to use BIP-0044 for Ethereum (and other non Bitcoin-like coins).

from slips.

Haven't read this all yet but I wouldn't mind something where we could encode further information. e.g. A SSSS scheme where the mnemonics have the first word as shamir and the second word encoding the m for the m-of-n.

EDIT: Didn't even read the start of @prusnak's response, ignore me.

from slips.

@prusnak regarding separate receive chains: makes sense. Question: can P2SH-P2WPKH be derived from bech32?

Shamir Secret Sharing Scheme (M out of N) sounds really useful. That can be done on the existing BIP39 word set as well as a new set I assume? Does that get easier if mnemonic words are mapped to integer values instead of the literal strings they are now?

from slips.

Agreed on pretty much everything in the initial post. I'd also suggest that new wordlist should also ensure all words have unique metaphone codes.

I personally quite like the idea of deriving the seed from the sequence numbers of the words rather than their text; this makes it possible to express the same mnemonic in different languages/dictionaries.

A while ago I wrote up a spec on 'extended mnemonics' that can encode additional data; an adaption of this may be useful for a future BIP39 replacement.

from slips.

/cc @ecdsa

from slips.

@Sjors A BIP39 mnemonic is the encoding of (number of words × 11 ÷ 8) bytes (which includes a 4 byte checksum) which would be what you want to encode for SSSS (as having (m - 1) parts would be dangerous if you encode the mnemonic itself)

from slips.

I think we should definitely version the mnemonic and make it incompatible with BIP39 and implementations should check that they support that version, else refuse to import it. Then we can add newer features with reduced risk of people not being able to import it in, e.g. 5 years, because they can't remember which piece of broken software they used.

Also, Electrum doesn't check the checksum for BIP39 mnemonics which is very problematic (because even if we use a new word list, Electrum would accept it as BIP39)

from slips.

@saleemrashid Electrum does check the bip39 checksum (in git master).

@Sjors Electrum has versioned mnemonic seeds. I tried to propose this idea to the trezor team years ago, but they rejected it because it was going to slow down the commercialization of their product. If you want versioned seeds, you should use the Electrum standard instead of creating a new one.

from slips.

@ecdsa Could you point me to BIP standard where is your seed documented?

from slips.

@prusnak http://docs.electrum.org/en/latest/seedphrase.html
There is no BIP at this point, but we can create one

from slips.

Thank you for the link, no need to create BIP, though, because I do think we still need to create a new standard, which will take best of the both worlds and also adds M-of-N SSSS into the mix.

Also I don't like the fact the version stored in mnemonic defines the derivation scheme. IMO mnemonic should only encode entropy (or entropies) and a way how to generate master private key from it, not the derivation scheme.

I think this is the main philosophical difference between your and our approach. I see the benefits of your solution (you don't have to try several schemes), but at the same time I really like that our seed is "upgradable" and I think this feature is much better than having to try several schemes (and you only do this once - during restore procedure).

Let's take the current SegWit situtation. If you created Electrum seed 2 years ago and buried it in the garden 500 km from your house, you would need to go to that place today again to store the new SegWit-enabled seed. How about next year when native SegWit and Bech32 is widely used? What if you want to use the seed to generate U2F or SSH keys? My example is far stretched, maybe your garden is just 25 km from your house, but I think that illustrates my point.

I'd like to invite you to drafting a new standard with me, if we find a way how to make the seed upgradable (or if you decide that not storing a derivation scheme in seed is a good idea).

from slips.

Also I don't like the fact the version stored in mnemonic defines the derivation scheme.

What do you mean by derivation scheme? Are you talking about BIP-0032 or BIP-0044/49?

from slips.

I'm talking about this: http://docs.electrum.org/en/latest/seedphrase.html#list-of-reserved-numbers

Not sure if Electrum follows BIP-32/BIP-44/BIP-49 for these particular cases.

from slips.

Totally agree, there's no reason why you need to encode anything more than the entropy in the mnemonic.

from slips.

also adds M-of-N SSSS into the mix

Please let's not hardcode just that, though - personally I'd much prefer a system like the one I linked, that permits different types of mnemonic, with different means of deriving the secret data.

I am talking about the fact that once mnemonic encodes something more than the entropy (because it defines WHAT to do next with that entropy in order to derive keys to be used), you need to generate a new one every time you want to use it for something new.

I agree, but I would like to be super clear that every (mnemonic type, network) tuple should have a single canonical derivation defined by an extension proposal. We're currently suffering from a glut of different derivation paths in Ethereum, and I wouldn't wish it on anyone.

from slips.

@Arachnid The way I see it, Bitcoin can be an "application" for this new derivation scheme and Ethereum can be another "application". Then we can have something like m/bitcoin/<coin_type>/<...> for Bitcoin, Testnet, Litecoin, etc. and m/ethereum/<chain_id>/<...> for Ethereum. (Of course, we won't use strings for it). Sounds good?

from slips.

Yes, I agree - I'm just saying that we should do everything we can to make sure the derivation path(s) can be known based on the code and the context it's used in; any ambiguity there will lead to multiple competing derivation paths.

from slips.

@saleemrashid wrote:

A BIP39 mnemonic is the encoding of (number of words × 11 ÷ 8) bytes (which includes a 4 byte checksum)

Just to clarify, my concern is with this sequence: N × 11 ÷ 8 bytes -> N words -> pbkdf2(words + passphrase) -> key space. This makes the key space depend on the specific language, which creates a compatibility risk for non-english languages (and I find it inelegant, but that's not a strong argument).

I would like to see the following sequence instead: N words -> M bytes -> key space, where I don't have any preference as to whether M = N × 11 ÷ 8 or some other scheme. This allows for different ways to create the M bytes, e.g. words in another language, SSSS, something like BIP38 or a combination.

If people really want a passphrase, that could go either in the step N words -> M bytes or in the step M bytes ->key space.

from slips.

@Sjors I agree entirely.

from slips.

@prusnak wrote:

In my own experience the current limit of 20 has downsides.

Trust me on that increasing this limit or removing it completely is a suicide.

The ValueShuffle proposal seems to require never using an address it it was revealed in a failed mixing attempt.

• http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final6.pdf
• https://youtu.be/BPNs9EVxWrA?t=1h24m45s

There's probably more use cases like this.

from slips.

I would like a BIP-39 replacement to have the property that it be plausible (although not necessarily easy) to derive a master seed by hand, by rolling dice, or flipping coins, etc. For BIP-39 there are many reasonable ways of transforming dice rolls or coin flips into a uniform selection of of choices of words, and I don't think any particular method need be prescribed. However, the SHA-256 based checksum in BIP-39 is what kills the ability to generate a master seed by hand.

A BCH code, such as the one used for Bech32 in BIP-173 provides a checksum that I believe can be plausibly computed by hand, though I suppose I need to validate this by trying it.

For Bech32, the pencil and paper algorithm for generating a checksum works by operating on a string of 6 characters from the bech32 alphabet, starting with the expanded HRP data (which is a fixed value and can be safely precomputed and published). The checksum computation works by appending one data character to the end of this 6 character buffer and removing a character from the other end of the 6 character buffer. Using a precomputed printed lookup table of 32 entries (Table 1), one for each Bech32 character, one finds the corresponding entry for the removed character and it will have an associated 6 character (from the bech32 alphabet) entry. One needs to combine this value, with the current 6 character buffer using a second table (Table 2). Table 2 contains a 32x32 "addition" table for Bech32 characters. Working character-wise one "adds" each character from the current buffer to the corresponding character from the entry picked out from Table 1. This "sum" becomes the new 6 character buffer.

This process repeats until all the data character have be processed. After that, there is a bit of post processing work where you process 6 more 'q' characters in the same way and then you need to change the last character according to a third table, and you are done. The resulting 6 characters is the Bech32 checksum.

My point of writing out the above is to illustrate that it is plausible to do such computation by hand and still get a powerful error-correcting checksum like what Bech32 uses. Creating a checksum by hand isn't too dangerous. The failure scenario is that the checksum computed is incorrect. One would be expected to test one's master seed in the hardware device one is using before committing to it, or otherwise repeat the computation independently 2 or 3 times. In any case, no one would be forcing one to generated master seeds this way; I only want it to be possible for sophisticated users to be able to do this sort of calculation. The process doesn't even need to be documented as far as I'm concerned.

From what you have written above, it sounds like you were leaning towards using such a checksum anyways, which is great!

from slips.

@roconnor-blockstream Take a look at https://github.com/satoshilabs/slips/blob/master/slip-0039.md for the current status of this.

from slips.

Thanks. Where is an appropriate place for me to comment on Slip-39?

Given the 10-bit word list, I think it would be nice to simply replace GF(256) with G(32) and make everything a multiple of 5 bits except for the result of the key derivation function. (We would want to round the master seed size to 130-bit / 255-bit (or maybe 230-bit). Then you could drop in Bech32's 30-bit checksum, since it too works over G(32) (though I do feel like having a checksum on the master seed itself is a bit overkill). Everything could plausibly be computed by hand (while I wouldn't expect anyone to do SSSS for by hand for any threshold other than M=1, I do think SSSS could be done by hand this way without more effort than a typical World War 2 spy would expend on a hand-cypher of that era.)

With 10-bit words, there is a canonical mapping between words and pairs of bech32 characters, allowing one to have a choice between compressed encoding (bech32) and word-list encodings of the share data, which is a nice property of your word list.

I think having the option of constructing master seeds without the use of modern digital computer is important, but not everyone may agree on this point.

from slips.

@roconnor-blockstream Bear in mind that it can be used for secret data that isn't a BIP32 master secret, so we don't want to put unnecessary restrictions on the length of the secret.

I agree with your last point, but I don't think you need to be able to generate the recovery seed.
Being able to provide the entropy would be sufficient and you can always verify that the entropy gives the expected recovery seed. If you cannot do that for whatever reason, generating the recovery seed without a computer is equally useless because you cannot verify that private keys are being derived correctly.

from slips.

I don't think anything I suggested would put any unnecessary restrictions on the length of secret data (though I'm unclear if by "secret" you mean the master secret or the resulting seed).

I agree with your last paragraph. But just to emphasize, there is a huge difference between trusting a device such as a Trezor with correctly computing deterministic private keys and deterministic signatures versus trusting such a device to produce genuine random data.

But yes, A college suggested it would be sufficient to write an app for whatever hardware device will be holding the secret anyways that computes checksums from data. As far as I'm aware there are no such apps for the Trezor, etc. Perhaps the onus is on me to create these apps if I think it is so important. There are other schemes where you could enter random data and get a certificate that proves that the given data was incorporated into the device's generation of the random seed, which would also work. Although ideally those certificates would need be such that one could validate them by hand, and I don't know if that is the case.

Still I'm a big fan of Bech32. I think error correcting codes is be great way for storing share data and why not use an ECC that you'll already be needing anyways?

from slips.

computing deterministic private keys and deterministic signatures versus trusting such a device to produce genuine random data

I think you misunderstood what I was saying.

To be clear, you can currently verify that entropy the connected computer provided (either from the CSPRNG or your own entropy) was used combined with the TREZOR's internal entropy because the device displays the internal entropy it used.

But I'm talking about a new feature that would allow you to securely provide all of the entropy. The TREZOR would compute the checksum and output a recovery seed as usual, but you could verify that the entropy you provided was used by the TREZOR.

As far as I'm aware there are no such apps for the Trezor, etc.

There are a huge number of BIP39 implementations and any of those should allow you to generate (the same) mnemonic from the entropy.

Still I'm a big fan of Bech32. I think error correcting codes is be great way for storing share data and why not use an ECC that you'll already be needing anyways?

Totally agree but, even if we switch to ECC, the usage of PBKDF2 and AES would still cause an issue for you.

from slips.

from slips.

I think it would be nice to simply replace GF(256) with G(32)

There are already nice implementations of GF(256), so I would rather stick to these, not go with GF(32).

Bech32's 30-bit checksum

This is just too much, effectively adding 3 extra words to the share.

I think having the option of constructing master seeds without the use of modern digital computer is important, but not everyone may agree on this point.

You can create a seed using a dice or whatever other means. It will not be a valid BIP39 seed, but you can still use it. I don't think you want to create SLIP39 mnemonics by hand.

why not use an ECC?

For mnemonics you don't want to use ECC. Mnemonic generated from a wordlist is itself already an error correcting code (if you see a word acadrrnic - it's most probably the word academic). Also you don't want to use ECC, because it would help an attacker to reconstruct the seed if they don't have the full information, which is something you don't want.

Also as Saleem indicated above, in case of TREZOR - two sources of entropy are mixed, so it is very hard for an attacker to meaningfully exploit both processors at the same time.

from slips.

Mnemonic generated from a wordlist is itself already an error correcting code

Good point!

from slips.

Bech32's 30-bit checksum

This is just too much, effectively adding 3 extra words to the share.

I'm suggesting getting rid of the master secret checksum and only having share checksums. That is replacing your two 16-bit checksums with one 30-bit checksum.

There are a huge number of BIP39 implementations and any of those should allow you to generate (the same) mnemonic from the entropy.

No way am I going to run any of those implementations on a modern digital computer. The only digital device that is ever allowed to touch my mnemonic is my hardware wallet. Every other digital device is considered compromised for this purpose. Hence I need a hardware wallet app to help or preferably I want to have the ability to generate a SLIP39 mnemonics by hand.

If I can construct the entire mnemonic by hand I am (almost) completely assured there is no funny business going on in the seed creation. If I can construct the mnemonic prefix by hand and have the hardware wallet generate the checksum for me, then it is very easy to validate that there is no funny business going on because I can validate that the mnemonic prefix is identical to the words I generated with my dice or coins.

The TREZOR's display of internal+external entropy is inadequate because it gets the external entropy from a computer (AFAIU you cannot enter the external entropy using the buttons on the Trezor, but correct me if I'm wrong here). You are asking me either to trust that I have an uncompromised computer to plug my TREZOR device into to input my dice entropy, and I don't trust any of my digital computers for something this important, or trust the internal entropy generated by the TREZOR is secure, which I also don't want to have to trust because it is basically impossible to audit. I do trust my dice and my coin tosses (at least more that the alternatives).

But I'm talking about a new feature that would allow you to securely provide all of the entropy. The TREZOR would compute the checksum and output a recovery seed as usual, but you could verify that the entropy you provided was used by the TREZOR.

Yes that would be super. As long as it is designed so that it is plausible that I can verify the master seed was generated by my input entropy by hand. (For example, if we consider BIP 39, I would input a set of random words, and the feature would replace the last one with one with a correct checksum, and then I can by hand double check that the last word is in the same 256 word bucket as the last word I entered. This is plausible to do by hand.) I do not want to have to use a modern digital computer to do the validation because I cannot safely enter my master seed into such a device.

Totally agree but, even if we switch to ECC, the usage of PBKDF2 and AES would still cause an issue for you.

I don't see a problem. The master seed comes before the PBKDF2 function, so everything is fine. I'm willing to trust that my hardware wallet is properly deriving private keys from my master seed that I type into the device. I'm just not willing to trust the hardware wallet's random number generator.

Also you don't want to use ECC, because it would help an attacker to reconstruct the seed if they don't have the full information, which is something you don't want.

All checksums are in a sense error correcting codes. The difference between an proper ECC such as BCH and a truncated SHA256 sum is that with BCH you have some understanding on the minimum distances between valid codes in the space of all codes and have fast algorithms to reconstruct values given errors. With truncated SHA256 sum you have a randomly distributed valid codes with no known structure so you have no understanding of how easy or hard it will be for an attacker to reconstruct values from partial information and which partial information. (Error correction is simply finding the closest valid code to a given code according to some metric such as edit distance. Error correction can always be done using any checksum just by doing a search.)

Let's try to quantify these properties: IIUC (and someone should check my math here), Bech32 correct any 2 letter error (within a 71 letter message) with a very fast algorithm. Words from the SLIP39 word list correspond, entropy-wise, to a pair of Bech32 letters. So this means that a Bech32 code can quickly correct any single word error. From the attackers perspective he can quickly reconstruct the correct mnemonics even when any one of the words is missing or wrong.

Let's try to prevent this attack using a SHA-256 checksum instead. The attacker is given the master seed except that one of the words is incorrect and the attacker don't know which one. Given a 30 word mnemonic, the attacker must perform 30*1024 SHA-256 operations to generate a list of valid mnemonics within that edit distance. The attacker then can try every one of those valid mnemonics (of which there will only be a small handful, and very likely only one) to see if they have funds. Yes, 30,000 SHA-256 operations slow the attacker. Does it provide significant protection? I don't think it does. Is it worth the loss of easy error correction? In my opinion, no.

If you don't want attackers to reconstruct the seed from partial data, you need to remove the checksum entirely. If you want a checksum, then use a proper checksum with fast error correction and guarantees instead of one with slightly slower error correction and no known guarentees.

from slips.

Anyhow. My important comment is that I would like a hardware wallet that lets me input entropy directly into the device and lets me verify that the generated master secret used that entropy without using a computer. Everything else I've commented on is less important.

I think the design of a BIP 39 replacement could facilitate this property, universally for every application using it, by making it plausible for one to generate the mnemonic, with checksum, by hand. I believe BCH checksums are amenable to hand computation, and are strictly superior to SHA-256 checksums even without the hand computation property. Bech32 doesn't have to be used, though it is convent that a pair of letters corresponds to a SLIP39 word, it is ready made, and would provide for an alternative bech32 style encoding of the master secret for people who want something compact. It seems likely that a GF(1024) BCH checksum would have more suitable error correction properties for shares (while more irritating to hand compute than Bech32's BCH checksum, I think it would still be possible).

from slips.

I'm suggesting getting rid of the master secret checksum and only having share checksums.

We do want to have master secret checksum, so the user knows they combined the shares correctly (i.e. there was no share from a different set) and don't freak out when something like this happens.

BCH checksums are strictly superior to SHA-256 checksums

I had a discussion with Daan at 34c4 and he suggested to replace CRC checksums with SHA, because CRC/BCH checksums have much less entropy than SHA checksum. His gut feeling was that mixing a high-entropy data (master secret) and low-entropy data (checksum) was not a good idea for SSS algo. But then you don't want to use checksum for the master secret, so you probably have not thought about that, but I really do want it to have better UX.

My important comment is that I would like a hardware wallet that lets me input entropy directly into the device

This is somewhere down in the roadmap.

and lets me verify that the generated master secret used that entropy without using a computer.

That's more tricky.

from slips.

That's more tricky.

It's also semi-useless as far as I understand it. It doesn't matter if the recovery seed is correct if the device isn't generating the correct receiving addresses.

If you don't trust the wallet, you must verify the addresses. If you're verifying the addresses, you can verify the entropy was used in the recovery seed.

from slips.

Ultimately it would be useful to have an encrypted/signed data transfer protocol standard for sharing important information between hardware devices. The data could be transferred through online computers (e.g. via USB) but it wouldn't matter because it would be end-to-end authenticated and encrypted.

Allowing a user to verify entropy, addresses, public keys, and tx info on different devices from different manufactures would help a lot.

from slips.

Allowing a user to verify entropy, addresses, public keys, and tx info on different devices from different manufactures would help a lot.

If all manufacturers add support for importing custom entropy, then users could import the entropy into multiple devices, verify the recovery seed generated is identical and verify the addresses the device generates.

from slips.

If all manufacturers add support for importing custom entropy, then users could import the entropy into multiple devices, verify the recovery seed generated is identical and verify the addresses the device generates.

Right, however securely entering things like entropy and public keys on multiple hardware wallets is inconvenient for users, so automating this would improve security because more people would actually do it.

from slips.

Right, however securely entering things like entropy and public keys on multiple hardware wallets is inconvenient for users

But the hardware wallet would then have to compromise the entropy and all decent hardware wallets will never give up the private keys after the initial recovery seed generation.

Once you have verified the entropy on at least one other hardware wallet, it is safe to assume the recovery seed was actually generated from your entropy. From that point, you can use the recovery seed to initialize other wallets.

from slips.

I had a discussion with Daan at 34c4 and he suggested to replace CRC checksums with SHA, because CRC/BCH checksums have much less entropy than SHA checksum. His gut feeling was that mixing a high-entropy data (master secret) and low-entropy data (checksum) was not a good idea for SSS algo.

Interesting; my intuition is the opposite. I expect that we can prove that (asymptotically?) CRC/BCH checksums all occur equally as often as one another (due to their uniform algebraic layout), and therefore contain maximum entropy (a claim that should be verified). For SHA-256, this maximum entropy property is derivable from the random oracle assumption, but isn't something that we know how to prove about SHA-256. The key property of SHA-256 is that it is supposed to be infeasible to find collisions and preimages; something that isn't relevant to this application at all.

(Edit: I also think this isn't relevent to SSSS since SSSS hides information perfectly)

from slips.

Is there any possibility of still getting rid of the "plausible deniability" passwords or am I alone in this line of thinking?

While I appreciate the value of plausible deniability in concept, I have spent far more hours (probably a few hundred at this point) working with users to find coins across derivation paths AND passphrases and ultimately, especially as it concerns usability, this form of password does more harm than good.

Additionally, I have yet to encounter someone hit over the head with a wrench and utilizing their "plausible deniability password" to escape that dire situation. 😉

From a usability standpoint, there are a number of wallets and applications that hide these passwords under "advanced" settings for exactly this reason. We personally won't be encouraging users to use passwords with their phrases up front as we are not confident in new users ability to grasp that concept along with everything else we need to teach them during the onboarding process.

If the goal is to have as many people having password-protected phrases as possible, plausible deniability isn't the way to go.

from slips.

12-24 word mnemonics are great for new users, but they're not great if someone gets their hand on your piece of paper.

This is what the 'password' part of bip39 is for in the 'master seed derivation' section. Because of the way pbkdf2 works, a given mnemonic is essentially encrypted with a secure stream cipher during generation if you use the password provisions of bip39.

It would be nice if the seed can also be exported in a BIP38-like encrypted fashion, perhaps printed as a QR code. More generally, it should be possible to take advantage of hierarchical deterministic wallets without having to use the mnemonic.

It is possible to take advantage of HD wallets without having to use the mnemonic. You can use the master seed directly (a-la bip32), which is entropy that stands alone and is not derived from a mnemonic. Most wallets don't support this, and they should, but the standard already does.

from slips.

We did some substantial improvements to our standard and we feel it's moving into right direction. Feel free to comment: https://github.com/satoshilabs/slips/blob/master/slip-0039.md

from slips.

That looks like it should be a BIP, not a SLIP?

from slips.

That looks like it should be a BIP, not a SLIP?

There is a certain opposition against not using version and birthday fields in the mnemonics, and I'd rather not spend my time defending my decision why not to include them again and again. I think we've incorporated all meaningful feedback from the bitcoin-dev mailing list and I can perfectly live with this document not being a BIP, only a SLIP.

from slips.

Thanks for the update. It does seem like a huge improvement. I'll have to study the proposal more carefully, but there is one thing that immediately jumps out at me.

In normal SSS you can prove information theoretic security by showing that for any N-1 shares and any message M there exists an Nth share such that those shares encode M. You can (and should) construct a program to generate this Nth share from M and the N-1 shares. However the way you use the PBKDF2 in this proposal precludes this possibility. For the same reason it precludes splitting any existing secret with this proposal. I don't know how I feel about this part of the design.

I'm also worried that the Bech32 30-bit checksum is too short. A longer checksum would allow for more error correction (see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016112.html and https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016152.html) Perhaps you will argue that the use of a word list provides sufficient additional redundancy already. I'd have to think more about it. I'd kinda like to see the wordlist scraped for a Bech32 string with a longer checksum. This would make the amount of redundancy and error correction plain as day.

But let me stress how much of an improvement I think this new proposal is. Yes I appreciate I'm the one who advocated for Bech32 above and now I'm arguing for a longer checksum. However, I believe using Bech32 much better than the old truncated SHA-256.

Nit: Converting the mnemonic shares to master secret should mention verification of the checksum as a first step.

P.S. I have been mulling my own SSS proposal in my free time. I should post about it in order to make some comparisons.

from slips.

Thanks for the update. It does seem like a huge improvement.

Thank you!

In normal SSS you can prove information theoretic security by showing that for any N-1 shares and any message M there exists an Nth share such that those shares encode M.

Is there any good reason why we should care about this for this particular application? We use KDF to extract the shares to eliminate the possibility of the following scenario: an attacker knows the first half of the first share and second half of the second share. Because it's highly impractical to use GF(2^256), this attack is possible. Stretching shares with KDF eliminates this.

It precludes splitting any existing secret with this proposal. I don't know how I feel about this part of the design.

This is part of the design. Gmaxwell criticised BIP-39 as "a thinly disguised brainwallet" and making it very easy to encode existing entropy (and thus possibly insecure) into a valid BIP-39 via bruteforcing the weak checksum. Also, it's not possible to migrate existing BIP-39 seeds into SLIP-39 ones if the original one used a passphrase (i.e. the passphrase feature is not migrated), which kind of invalidates our desire to include splitting existing entropy into shares in our design.

I'm also worried that the Bech32 30-bit checksum is too short.

It's already a massive improvement over BIP-39 (8-bits) and even over the original SLIP-39 proposal (16-bits), I think I am quite happy about 30-bits of checksum already.

But let me stress how much of an improvement I think this new proposal is.

Thanks again!

Nit: Converting the mnemonic shares to master secret should mention verification of the checksum as a first step.

Sure, will do.

from slips.

@prusnak BIPs don't require defending...

from slips.

Is this scheme limited to M-of-M SSS? That seems like quite a restriction.

from slips.

Is this scheme limited to M-of-M SSS?

No, it's not.

from slips.

@prusnak BIPs don't require defending...

Comments-Summary: Unanimously Discourage for implementation says otherwise

from slips.

I'm afraid I don't see how to derive an N-of-M share scheme with this system. Normally to do this you need to create the first N random shares. This part is fine: you just use random values for the shares. But then, in SSS, to derive the remaining M-N shares you need to run Lagrange interpolation of the first N shares to derive the share values at index >N. However in order to encode these derived shares as a mnemonic shares in your scheme, you need to invert the PBKDF2 function, which is impossible to do.

Am I misunderstanding something?

from slips.

@prusnak What about it? People can discourage implementing SLIPs too.

from slips.

Am I misunderstanding something?

Most probably an oversight on our side. Will fix it tomorrow (probably by removing KDF which stretches the shares :-/)

from slips.

Replacing the KDF (for the shares) with a fixed-key AES function would probably make you happy, although I personally don't find the attacker-knows-half-of-one-share-and-half-of-another-share threat very compelling.

Edit: maybe even using the nonce as the AES key.

Edit 2: maybe using the former salt parameter as the AES key and the SSS share value as the data being encrypted. No matter what, I think you will be forced into 256-bit payload values for the SSS parameter.

from slips.

Replacing the KDF (for the shares) with a fixed-key AES function would probably make you happy, although I personally don't find the attacker-knows-half-of-one-share-and-half-of-another-share threat very compelling.

This doesn't really solve the issue if the block-size of the symmetric cypher is smaller than the share (which it is when share is 256 bits and the AES block-size is 128-bit).

I removed the pbkdf2 for shares in f8573bc

from slips.

from slips.

@Steve132 You should really read the slip again. This is about producing shamir secret shares.

from slips.

It's a bit confusing to use N for both the number of Shamir parts and for the nonce. Maybe use n for the number of Shamir parts?

from slips.

Maybe use n for the number of Shamir parts?

I used n for nonce in de1189e

from slips.

You may want to refine the ASCII character suggestion in for the passphrase to suggest printable ASCII characters at codepoints 32-126.

from slips.

from slips.

I understand exactly what it's for.

How do you split secret into N shares using BIP39?

from slips.

from slips.

Don't reinvent the wheel.

Why? I am the author of BIP39 and in the next iteration of the mnemonic standard (SLIP39) I want to change some minor stuff in the old design. Your simple code change is a very good proof that it should be trivial for any software which implements BIP39 to also implement SLIP39. The only reason why NOT to change the PBKDF2 parameters is that someone already has a working cracking rig for BIP39 and they want to keep using that to crack SLIP39 too. So unless you give a VERY good reason why we should stick to old params, I'll keep them changed.

from slips.

from slips.

Requirements on engineers discourage adoption

But user demand encourages adoption. The ability to split the HD seed into Shamir Shares will be so compelling that I see SLIP-0039 getting adopted very quickly.

from slips.

from slips.

So why reinvent the wheel?

The reason why I wanted the change from PBKDF2-HMAC-SHA512 to PBKDF2-HMAC-SHA256 is that SHA512 is MUCH faster on 64-bit processors than on 32-bit processors, making it easier to bruteforce on desktop computers (as opposed to a computation that takes place on an embedded hardware). SHA256 does not have that big difference.

from slips.

@roconnor-blockstream what do you think about 947f4b9 ? This is a slight advantage that it is possible to convert existing BIP39_seed + one of its passphrases into a new SLIP39_split_seed that produces the same seed using the same passphrase (it will produce different seeds with different passphrases though ...)

from slips.

Looks good to me. I like having the option to migrate to an SSS key without necessarily having to re-key everything and/or move all my coins.

from slips.

human-readable part (hrp) of Bech32 is "SLIP0039"

The hrp for Bech32 should be lowercase otherwise you are going to have a bad time. When you make this change, you might want to also lowercase the same string in the salt to keep them matching.

from slips.

from slips.

Yes but mixed case is not allowed in Bech32 and all characters are converted to lowercase, including the HRP, prior to computing the checksum. Effectively, the uppercase and lowercase forms of an HRP are equivalent and the lowercase form is canonical. I think casually putting the uppercase form into the spec is liable to cause implementation errors where programmers use the uppercase form in the checksum computation, especially in this case where the Bech32 alphabet isn't being used.

I mean, maybe I'm an idiot, but that's what I started to do before I caught myself.

from slips.

Looks good to me. I like having the option to migrate to an SSS key without necessarily having to re-key everything and/or move all my coins.

I still might revert this change. The reason is that AES is a block cipher and you can recover the first half of the master seed only by having the first half of the first share (in 1-of-2 scenario). Stream ciphers are even worse in that regard. Also there are couple of other reasons why it's not a good idea, but it would take a lot of time to explain.

from slips.

lowercase form is canonical

Fixed in 52bb7c6

from slips.

I still might revert this change. The reason is that AES is a block cipher and you can recover the first half of the master seed only by having the first half of the first share (in 1-of-2 scenario).

I think the AES is fine. Here is my argument (for the 256 master secret case). Barring a change of replacing GF(256) with GF(2^256), if an attacker manages to get the first half of M shares, they can recover the first half of the master secret no matter what. Whether you use PBKDF2 or you use AES, in both cases, the attacker needs to do 2^128 work to recover the full master seed, so the two procedures offer effectively the same security.

At most you need to recommend the master seed be hashed as the first step of any application (like bip-32 does).

from slips.

My argument for not using this method is the following:

1. I am using BIP39 seed with passphrase A, I don't think I use any other passphrases
2. I migrate to SLIP39 using the passphrase A
3. I destroy BIP39 backups, because I don't need them anymore
4. after few years I realize that I also used a passphrase B with BIP39 seed for storing something special
5. I am screwed

This is going to happen and this scenario is very strong reason why we should be very explicit about moving stuff to a new mnemonic, although it might be less comfortable.

from slips.

I'm confused by your scenario. Where does passphrase B fit into the story?

from slips.

point 4. is BIP39 seed + passphrase B

from slips.

So you are arguing for using AES because it allows a user to keep their master seed when migrating to SLIP39?

from slips.

Okay I think I get what you are saying. You meant "4. after few years I realize that I also used a passphrase B the BIP39 mnemonic from 1 for storing something special."

from slips.

from slips.

But how does using PBKDF2 over AES help?

In your scenario you are going to create a brand new SLIP39 derived seed, spend a lot of time, effort and money to rekey all your infrastructure, move all your funds, probably eroding your financial privacy in doing so. Then you will toss out your old BIP39 mnemonic and still end up realizing later that you hand something else using passphrase B with the discarded mnemonic.

from slips.

from slips.

@Steve132 the point is that sha512 is much slower on 32-bit arm and other similar architectures than sha256, because the architecture is not suited for this hash. sha512 uses 8 64 bit values, which can't be kept in registers making the operations much slower. This means that a single iteration is ten times slower for sha512, while on other hardware sha512 is sometimes faster than sha256. If we want to keep the iterations low enough for the hardware wallets, this means that we gain about 10 times more security by switching to sha256 with 10 times more iterations.

Slip39 and BIP39 are already incompatible because of other changes, e.g., the master secret is not reinterpreted as a BIP39 mnemonic with a bip39 english word list.

AES vs. PBKDF only:

Both allow multiple wallets with passphrases. AES allows in addition to reuse one existing wallet with some arbitrary passphrase. However then you obviously can't choose what wallets are generated for the other passphrases.

@prusnak I like the possiblity of encoding a previous wallet with slip39 with an additional passphrase protection. Whether or not a wallet should allow you to export your existing wallets as slip39 is a different issue. Some wallets that don't have multiple accounts with plausible deniability may want to use this feature.

from slips.

However then you obviously can't choose what wallets are generated for the other passphrases.

@roconnor-blockstream There is another hidden problem. There are some applications (namely U2F, but password manager is another one) which do not use passphrase by design (there were technical reasons for this), so people use two passphrases even if they don't know they do. The passphrase A, passphrase B scenario from above applies to this as well. (just replace 4 with "I want to use new SLIP39 seed with U2F/password manager). But I agree this is an implementation issue, not an issue of the standard.

from slips.

Those people using a passwordless BIP39 HD-wallet are using the same master seed as their U2F application? So they could port both their master seed and U2F service to AES-SLIP39? Just making sure I understand.

from slips.

Those people using a passwordless BIP39 HD-wallet are using the same master seed as their U2F application?

Yes, the same BIP39 seed + passphrase = HD-wallet, the same BIP39 seed + no passphrase = U2F, password manager, etc.

So they could port both their master seed and U2F service to AES-SLIP39?

Yes, but it's not so trivial to understand you have to do it twice. Personally, I think that it's easier to just unlink the U2F device. The password manager is a bigger problem though.

from slips.

I see. I can't help but see enormous benefits in allowing the possibility of porting one master seed to a SLIP39 encoding. I'm not sure how broadly you are hoping SLIP39 to be supported throughout the ecosystem, but allowing for the possibility of porting one master seed doesn't necessarily obligate implementations to support this porting for all applications. For example, an application may just choose only to allow porting of passwordless BIP39 seeds to avoid dragging users into confusing technical issues.

AES-SLIP39 would allow some other valuable features. For example, users who are using a single password AES-SLIP39 could change their password (in case they think it has been compromised) by generating a new set of shares, without having to rekey their whole infrastructure or move their funds. (Same issues for users who use multiple passphrases applies here though; not all application can be moved this way).

Perhaps you guys want to write a public key encrypted export/import function for your password manager for migration by securely sweeping that data to a new device? I don't know; perhaps this isn't so easy to do.

from slips.

from slips.

from slips.

I'm not a cryptographer but Wikipedia suggests you can use a (3 or) 4 round Luby–Rackoff construction to construct a pseudo-random permutation from a pseudo-random function (like SHA256 is assumed to be): https://en.wikipedia.org/wiki/Feistel_cipher#Theoretical_work

This would be like your AES idea, but, if I understand correctly, get you a full permutation over all 256-bits.

I suppose you'd use the PBKDF to generate the four rounds of sub keys, then use HMAC-SHA256 for the F function in each round.

from slips.

This would be like your AES idea, but, if I understand correctly, get you a full permutation over all 256-bits.

Thanks! We'll investigate this. AES giving permutation over just 128-bits was one of the main reasons why I was hesitant to use it.

from slips.