public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Satoshilabs secret shared private key scheme
@ 2018-01-08  4:22 Gregory Maxwell
  2018-01-08  6:33 ` nullius
  2018-01-08 12:39 ` Pavol Rusnak
  0 siblings, 2 replies; 36+ messages in thread
From: Gregory Maxwell @ 2018-01-08  4:22 UTC (permalink / raw)
  To: Pavol Rusnak, Bitcoin Protocol Discussion

On Sun, Jan 7, 2018 at 3:16 PM, Pavol Rusnak via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On 05/01/18 14:58, nullius via bitcoin-dev wrote:
> I am currently drafting a new standard[1] which will allow also Shamir
> Secret Scheme Splitting and there we disallow usage of a custom wordlist
> in order to eradicate this mess. Will try to push this as BIP too once
> we get it to the point we are OK with the contents.
>
> https://github.com/satoshilabs/slips/blob/master/slip-0039.md

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.  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).  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. 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.

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).

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.

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.

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


^ permalink raw reply	[flat|nested] 36+ messages in thread
* [bitcoin-dev] Satoshilabs secret shared private key scheme
@ 2018-01-17 11:39 Ondřej Vejpustek
  2018-01-17 15:28 ` Russell O'Connor
  2018-01-17 15:31 ` Gregory Maxwell
  0 siblings, 2 replies; 36+ messages in thread
From: Ondřej Vejpustek @ 2018-01-17 11:39 UTC (permalink / raw)
  To: bitcoin-dev

The entropy argument is as follows:

There is a rule of thumb which says it is safer plaintext to have low
redundancy, see
https://en.wikipedia.org/wiki/Redundancy_(information_theory), i. e.
it's better to encrypt random or compressed data than natural language.
This rule is based on Shannon's information theory which means that a
breach of the rule usually doesn't induce a vulnerability (there is no
known generic attack). This rule is application of a precautionary
principle.

Nevertheless, here are some examples of cryptographic attacks which may
be considered as a consequence of the breach of the rule:
  * Related Message Attack by Coppersmith, Franklin, Patarin, Reiter
(https://pdfs.semanticscholar.org/899a/4fdc048102471875e24f7fecb3fb8998d754.pdf)
- given RSA ciphertext of two plaintexts x and a*x + b, where a, b are
known, it's possible to effectively compute x provided public exponent
is three. From the informaton-theoretic point of view the second message
is redundant, because it's determined by the first one. Which means that
relative redundancy of both messages is at least one half.
  * Stereotyped Messages by Coppersmith
(https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf, section 7) -
given RSA ciphertext and (1-1/e) fraction of plaintext (where e is
public exponent), it's possible to effectively compute x. Message is
highly redundant, because only 1/e of the message is unknown. Relative
redundancy of the message is at least (1-1/e).

Consider a few notes:
  * Nowadays there exists more complicated variants of mentioned attacks
which have weaker premisses.
  * There is a considerable similarity between RSA and SSS. Both schemes
are algebraically-based (rather than boolean function based).
  * CRCs (and error-correcting codes generally) introduce redundancy
into the message. Moreover the redundancy is induced by a linear
relationship among message (compare with the premise of the Related
Message Attack).
  * Related Message Attack wouldn't be possible if you had two
plaintexts x and hash(x). The relationship between messages has to be
(algebraically) uncomplicated. From the information-theoretic point of
view the situation is the same, but from the practical point of view it
is completely different.

To sum it up, there is a precautionary principle which tells us not to
increase redundancy of a message unless it is introduced in a
complicated way (for example by a hash function). That's why we use SHA
rather than CRC. One more reason why we stick to the principle is that
there's no randomisation in our scheme (such as padding or
initialisation vector). We understood advantages of error-correctings
codes over hash functions (minimal codewords distance property,
performance) and we considered it thoroughly.

Ondřej Vejpustek


^ permalink raw reply	[flat|nested] 36+ messages in thread

end of thread, other threads:[~2018-01-23 14:16 UTC | newest]

Thread overview: 36+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-01-08  4:22 [bitcoin-dev] Satoshilabs secret shared private key scheme Gregory Maxwell
2018-01-08  6:33 ` nullius
2018-01-08 12:39 ` Pavol Rusnak
2018-01-08 12:45   ` Peter Todd
2018-01-08 13:00     ` Pavol Rusnak
2018-01-08 19:37       ` Peter Todd
2018-01-08 22:26         ` Ben Kloester
2018-01-09  0:37           ` Peter Todd
2018-01-08 23:47   ` Gregory Maxwell
2018-01-09  0:40     ` Rhavar
2018-01-09  1:13       ` Peter Todd
2018-01-09 12:44         ` jens
     [not found]         ` <274aad5c-4573-2fdd-f8b0-c6c2d662ab7c@gibsonic.org>
2018-01-12  9:50           ` Peter Todd
2018-01-12 11:06             ` [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme) nullius
2018-01-13  2:11               ` Damian Williamson
2018-01-13  3:44                 ` nullius
2018-01-13  6:11                   ` Peter Todd
2018-01-09 15:12     ` [bitcoin-dev] Satoshilabs secret shared private key scheme Pavol Rusnak
2018-01-10 20:28       ` Pavol Rusnak
2018-01-10 23:47         ` Gregory Maxwell
2018-01-11  9:55           ` Pavol Rusnak
2018-01-09 16:20   ` Russell O'Connor
2018-01-17 11:39 Ondřej Vejpustek
2018-01-17 15:28 ` Russell O'Connor
2018-01-17 15:36   ` Gregory Maxwell
2018-01-17 15:31 ` Gregory Maxwell
2018-01-18  5:00   ` Matt Corallo
2018-01-18 13:50   ` Ondřej Vejpustek
2018-01-18 14:34     ` Gregory Maxwell
2018-01-18 16:59       ` Ondřej Vejpustek
2018-01-18 18:58         ` Gregory Maxwell
2018-01-22 15:00           ` Ondřej Vejpustek
2018-01-22 19:21           ` Russell O'Connor
2018-01-23  1:05             ` Gregory Maxwell
2018-01-23 13:54           ` Ondřej Vejpustek
2018-01-23 14:16             ` Adam Back

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox