[bitcoin-dev] Satoshilabs secret shared private key scheme

[Pavol Rusnak]

On 08/01/18 05:22, Gregory Maxwell wrote:
>> https://github.com/satoshilabs/slips/blob/master/slip-0039.md

Hey Gregory!

Thanks for looking into the scheme. I appreciate your time!

> This specification forces the key being used through a one way
> function, -- so you cannot take a pre-existing key and encode it with
> this scheme.

Originally, we used a bi-directional function to be able to encode and
decode the key in both directions using the passphrase. We stretched the
passphrase using KDF and then applied AES or other symmetric cipher

We found the following (theoretical) problem:

If an attacker has knowledge of few words from the beginning of shares,
they are able to reconstruct the beginning of the master secret and if
the size of the reconstruced master secret is bigger then the cipher
blocksize (for block ciphers; for stream ciphers 1 bit is enough), then
they can reconstruct the beginning of the seed.

Can you find a scheme which does not have this problem? Or you think
this problem is not worth solving?

> The KDF it specifies is unconfigurable and fairly weak
> (20000xhmac-sha2-- which can be cracked at about 0.7M passwords a
> second on a single motherboard GPU cracker).

Yes. We want this to be possible to be computed on TREZOR-like devices
on boot, similarly how we compute BIP39 on boot right now.

> The construction also
> will silently result in the user getting a different private key if
> they enter the wrong passphrase-- which could lead to funds loss.

Again, this is by design and it is main point why plausible deniability
is achieved both in BIP39 and SLIP39. If we used a different
construction we'd loose plausible deniability.

> It
> is again, unversioned-- so it kinda of seems like it is intentionally
> constructed in a way that will prevent interoperable use, since the
> lack of versioning was a primary complaint from other perspective
> users.  Of course, it fine if you want to make a trezor only thing,
> but why bother BIPing something that was not intended for
> interoperability?  Even for a single vendor spec the lack of
> versioning seems to make things harder to support new key-related
> features such as segwit.

This is argument I keep having all the time.

Suppose we'd introduce a version to encode PBKDF2 rounds or even
different KDFs. We'll end up with different SLIP39 mnemonics, but they
will not be compatible among implementations (because TREZOR can only up
to 100.000 rounds of PBKDF2 and does not support Argon2 at all, while
other desktop implementation would rather use memory-hard Argon2).

My gut feeling is that this would lead to WORSE interoperability, not
better. Look at BIP32 for example. There are lots of wallet that claim
they are BIP32 compatible, but in reality they use different paths, so
they are not compatible. BIP32 is a good standard, but in reality
"BIP32-compatible" does not mean anything, whereas when you say the
wallet is "BIP44-compatible" you can be sure the migration path works.

> The 16-bit "checksum" based on sha2 seems pretty poor since basing
> small checksums on a cryptographic hash results in a fairly poor
> checksum that is surprisingly likely to accept an errored string. Your
> wordlist is 10 bits and you have much less than 1023*10 bits of input,
> so you could easily have a 20 bit code (two words) which guaranteed
> that up to two errored words would always be detected, and probably
> could choose one which catches three words much more often 1:2^20
> (sipa's crc tools can help find codes like this).

Originally, we wanted to use 16-bit of CRC32 for checksum, but after the
discussion with Daan Sprenkels we were suggested to change this for
cryptographically strong function. The argument was that CRC32 contains
less entropy and mixing high-entropy data (secret) with low-entropy data
(checksum) is not a good idea.

Also, there is an argument between a checksum and ECC. We discussed that
ECC might not be a good idea, because it helps the attacker to compute
missing information, while we only want to check for integrity. Also the
word mnemonic is itself a ECC, because if you see the word "acadornic"
it is probably the word "academic".

> The metadata seems to make fairly little affordance to help users
> avoid accidentally mixing shares from distinct sharings of the same
> key. Is it the idea that this is the only likely cause of a checksum
> error? (1:2^16 chance of silently returning the wrong key seems kinda
> bad). -- I'm not sure much could be done here, though, since
> additional payload is precious.

Yes, checksum is supposed to prevent that.

> As an aside, your specification might want to give some better advice
> about the SSS since my experience virtually everyone gets it wrong in
> ways that degrade or destroy its properties e.g. many fail to generate
> the additional coefficients of the polynominal randomly which results
> in insecurity (see armory for an example).   Oh, also, I believe it is
> normally refereed to as "SSS" (three S)-- four S is the name of a
> linux program for secret sharing.

Will fix the spelling. About the generic advice about SSS, anyone is
welcome to contribute to the text.

> I'm happy to see that there is no obvious way to abuse this one as a
> brainwallet scheme!

Agreed!

-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
CTO, SatoshiLabs