[bitcoin-dev] Satoshilabs secret shared private key scheme

[bitcoin-dev] Satoshilabs secret shared private key scheme

[Ondřej Vejpustek]

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

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 4336 bytes --]

Hi Ondřej,

1. There is no similarity between SSS and RSA or any other public-key or
symmetric crypto.  SSS is effectively a one-time pad and is
information-theoretically secure.

2. Even if there were a problem (which there cannot be, due to (1)), using
error correcting codes and truncated hash functions create identical
amounts of information theoretic redundancy.

Let me repeat that SSS is "information-theoretically secure"!  It isn't
only computationally infeasible to break SSS; it is impossible to break
SSS.  If you have all but one necessary share of SSS, there is no
information leaked about the the hidden data, because for every possible
message that could be encoded, there exists some final share that would
decode to that message.  Any of the possibilities for the missing final
share are equally as likely.

It is of no use to apply the precautionary principle against impossible
attacks, especially at the cost of losing the useful properties of a real
error correcting codes that would provide actual guarantees against likely
errors.

On Wed, Jan 17, 2018 at 6:39 AM, Ondřej Vejpustek via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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/4fdc048102471875e24f7fecb3fb89
> 98d754.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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5503 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Wed, Jan 17, 2018 at 11:39 AM, Ondřej Vejpustek via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> 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).

I'm sorry but I must not be following your message. I read the above
as "these are similar because they are based on math"...

Shamir secret sharing, correctly implemented (which indeed seems to be
many parties problem...) achieves information theoretic security. In
this critical sense it is utterly unrelated to RSA.

In fact this applies generally given any fixed threashold-1 set of
shares there is an value of the final remaining share which decodes to
every possible message. So without knowing of an extra share you know
nothing of the message.

The simplest demonstration is the 2 of 2 case, which can most simply
be constructed over GF(2) as in the traditional "one time pad":
message = share1 xor share2.  For any given share1 or given share2
there exist a value of share2 or share1 respectively which yields
every possible message.

If the generalization isn't obvious, it might be helpful to make a
little test utility that tries all possible one byte messages with all
possible share values using the GF(256) sharing scheme proposed in the
draft-- in this case information theory is why we can know SSS (and
similar) have (within their limited scope) _perfect_ security, rather
than it being a reason to speculate that they might not turn out to be
secure at all. (or, instead of a test utility just work through some
examples on paper in a small field).

This doesn't change when you add additional conditionals on it-- e.g.
Say you a 2-of-3 sharing where you have your choice of any of the
three shares but do not know the others and assume you know every bit
of the plaintext save one bit or any linear or non-linear relationship
between plaintext bits (excepting for actually knowing the secret)...

In these case there can still be no attack arising out of this
charitably bad plaintext structure because-- as pointed out above--
all possible plaintexts are equal-probable you know nothing of which
of the two possible solutions is correct without knowing about the
other shares because for each possible value there exists a value for
the unknown shares which would cause that decoding-- there is no
leakage at all, the share doesn't teach you anything you didn't
already know.

In my view any SSS tool should also include a forgery utility which
demonstrates this property, both as a critical test-- but also because
being able to forge an alternative answer to deceive an attacker which
has compromised some of your shares is one of the (at least
theoretical) arguments for using SSS over computational secret
sharing.

> unless it is introduced in a complicated way

Complicated does not mean secure. And from an information theoretic
perspective the hash does almost nothing (other then some small
destruction of entropy due to its lack of perfect uniformity which is
information theoretically equivalent to using a smaller perfect code).
There are many cases where I too am more comfortable using a hash --
where it may destroy some structure which I cannot _prove_ would be
safe to retain, but this is not one of those cases.

>   * CRCs (and error-correcting codes generally) introduce redundancy
into the message

The discussion of using a proper code was primarily related to the
outer check value which protects the shares themselves and is sitting
unprotected in plaintext; not so much the one inside the sharing in
any case; since its the outer one which could be structured to provide
perfect detection of errors that align with words (e.g. transposing
two words).

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Wed, Jan 17, 2018 at 3:28 PM, Russell O'Connor via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> it is impossible to break SSS.

Obligatory repeated point: if the scheme being used actually is SSS
and not a Shamir-Shaped-Sharing instead. This should go without
mention by my experience is that a great many things which claim to be
SSS aren't. Sometimes precisely because they stuck in some hashes in
arbitrary places and destroyed the properties (in fact, the really old
broken armory implementation effectively did that, and in fact
resulted in a real weakness not just a theoretical one).

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Matt Corallo]

Or make it a part of your secret-split logic... Gotta love how fast GF(2^8) is:
https://github.com/TheBlueMatt/shamirs/blob/master/main.c#L57

On January 17, 2018 3:31:44 PM UTC, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>If the generalization isn't obvious, it might be helpful to make a
>little test utility that tries all possible one byte messages with all
>possible share values using the GF(256) sharing scheme proposed in the
>draft-- in this case information theory is why we can know SSS (and
>similar) have (within their limited scope) _perfect_ security, rather
>than it being a reason to speculate that they might not turn out to be
>secure at all. (or, instead of a test utility just work through some
>examples on paper in a small field).
>

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Ondřej Vejpustek]

Thank you for your comments, Gregory and Russell!

Gregory, thank you for you explanation of perfect secrecy, there is no
need for that, however. I'm professional mathematician and cryptographer.

> I read the above
> as "these are similar because they are based on math"...
They are based on algebra (group and commutative ring theory), which is
a great similarity. RSA and SHA, for example, are based on completely
distinct parts of mathematics.

> Complicated does not mean secure. And from an information theoretic
> perspective the hash does almost nothing (other then some small
> destruction of entropy due to its lack of perfect uniformity which is
> information theoretically equivalent to using a smaller perfect code).
> using error correcting codes and truncated hash functions create
identical amounts of information theoretic redundancy
I agree, see my last note in the previous mail. Adding redundancy by a
hash function is more secure than adding redundancy by a linear
relations. Just my opinion.

I see the difference between RSA and SSS you mentioned and I understand
your arguments about perfect secrecy. Just two comments:
  (1) Our proposal doesn't use SSS for the whole secret, but it divides
the secret into bytes and uses SSS for every byte separately. This
scheme is weaker because to reconstruct n-th byte it suffices to have
n-th bytes from k shares.
  (2) SSS is information-theoretic secure if you know k-1 or less
shares, where k is the threshold. But the proof doesn't hold if you know
for example a small part of every share.

> It is of no use to apply the precautionary principle against
impossible attacks, especially at the cost of losing the useful
properties of a real error correcting codes that would provide actual
guarantees against likely errors.
The discussion isn't about mathematics or about security proofs but
about cryptographic scheme design. In our use case you cannot assume
that all premises of security proof theorems (including SSS's perfect
secrecy) hold true (see the comment above).

In my opinion, to make a cryptographic scheme more robust it's better to
stick to general "intuitive" principles. Of course you have to consider
the advantages and disadvantages of this approach. That's why we
disclosed our draft and welcome all comments.

> The discussion of using a proper code was primarily related to the
> outer check value which protects the shares themselves and is sitting
> unprotected in plaintext
OK then. I was defending the hash in the inner check value.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Thu, Jan 18, 2018 at 1:50 PM, Ondřej Vejpustek
<ondrej.vejpustek@satoshilabs.com> wrote:
>   (1) Our proposal doesn't use SSS for the whole secret, but it divides
> the secret into bytes and uses SSS for every byte separately. This
> scheme is weaker because to reconstruct n-th byte it suffices to have
> n-th bytes from k shares.

If being secure against partial share leakage is really part of your
threat model the current proposal is gratuitously insecure against it.
And the choice of check algorithm really doesn't matter for that.

For example,  in a 2-of-3 share  say I have the first half of shares
1,2 and the second half of shares 2,3  with the current proposal the
secret is directly revealed, even though I didn't have any single
complete share.

If partial share disclosure were an actual concern, I would recommend
that after sharing and before encoding for transmission (e.g. before
applying check values and word encoding to the share) the individual
shares be passed through a large block unkeyed cryptographic
permutation.  Under reasonable-ish assumptions about the difficulty of
inverting the permutation with partial knowledge, this transformation
would prevent attacks from leaks of partial share information.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Ondřej Vejpustek]

> If being secure against partial share leakage is really part of your
> threat model the current proposal is gratuitously insecure against it.

I don't think that is true. Shared secret is an input of KDF which
should prevent this kind of attack.

> If partial share disclosure were an actual concern, I would recommend
> that after sharing and before encoding for transmission (e.g. before
> applying check values and word encoding to the share) the individual
> shares be passed through a large block unkeyed cryptographic
> permutation.  Under reasonable-ish assumptions about the difficulty of
> inverting the permutation with partial knowledge, this transformation
> would prevent attacks from leaks of partial share information.

Actually, we've been considering something like that. We concluded that
it is to much "rolling your own crypto". Instead of diffusion layer we
decided to apply KDF on the shared secret.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek
<ondrej.vejpustek@satoshilabs.com> wrote:
>> If being secure against partial share leakage is really part of your
>> threat model the current proposal is gratuitously insecure against it.
>
> I don't think that is true. Shared secret is an input of KDF which
> should prevent this kind of attack.

My post provided a concrete example. I'd be happy to answer any
questions about it, but otherwise I'm not sure how to make it more
clear.

> Actually, we've been considering something like that. We concluded that it is to much "rolling your own crypto". Instead of diffusion layer we decided to apply KDF on the shared secret.


Quite the opposite-- a large block cipher is a standard
construction... and the off-label application of a KDF that you've
used here doesn't provide any protection against the example I gave.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Ondřej Vejpustek]

> 
> My post provided a concrete example. I'd be happy to answer any
> questions about it, but otherwise I'm not sure how to make it more
> clear.

My apologies, I didn't read it carefully. You are absolutely right. Our
scheme doesn't protect against the scenario.

> Quite the opposite-- a large block cipher is a standard
> construction

I'm happy to hear it. Nevertheless, I didn't find any standartisation or
implementation of the CMC mode (excluding the paper).

Do you have some experience with other modes (such as HCTR, HEH)?

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1245 bytes --]

On Thu, Jan 18, 2018 at 1:58 PM, Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek
> <ondrej.vejpustek@satoshilabs.com> wrote:
> >> If being secure against partial share leakage is really part of your
> >> threat model the current proposal is gratuitously insecure against it.
> >
> > I don't think that is true. Shared secret is an input of KDF which
> > should prevent this kind of attack.
>
> My post provided a concrete example. I'd be happy to answer any
> questions about it, but otherwise I'm not sure how to make it more
> clear.
>
> > Actually, we've been considering something like that. We concluded that
> it is to much "rolling your own crypto". Instead of diffusion layer we
> decided to apply KDF on the shared secret.
>
>
> Quite the opposite-- a large block cipher is a standard
> construction... and the off-label application of a KDF that you've
> used here doesn't provide any protection against the example I gave.
>

At this point, is it better just to use GF(2^256+n)?  Is GF(2^256+n) going
to be that much slower than GF(2^8) that we care to make things this
complicated?  (I honestly don't know the answer.)

[-- Attachment #2: Type: text/html, Size: 1800 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Mon, Jan 22, 2018 at 7:21 PM, Russell O'Connor
<roconnor@blockstream.io> wrote:
> At this point, is it better just to use GF(2^256+n)?  Is GF(2^256+n) going
> to be that much slower than GF(2^8) that we care to make things this
> complicated?  (I honestly don't know the answer.)

I expect it would be especially since operations must be implemented
in sidechannel resistant manners.

Also, binary extension fields are doing to have linear subgroup
properties where leaking part of elements wouldn't be good. Not as
obviously broken as the example I gave above, but still in the domain
of "get chunks of a lot of a supra threshold set of shares, and setup
a latices basis problem that can provide an efficient subspace to
search".

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Ondřej Vejpustek]

> Yes, this scheme.
> https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217

In addition to the scheme, I found out, that Makwa
(https://www.bolet.org/makwa/), a hashing function which received a
special recognition in the Password Hashing Competition, supports a
delegation. In fact, Makwa is similar to the suggested scheme.

Unfortunately, both schemes have two drawbacks:
  (1) There is no proof that the host computes what he's suppose to do.
  (2) The delegation is far more slower than the normal computation.
According to the Makwa paper
(https://www.bolet.org/makwa/makwa-spec-20150422.pdf) the delegation is
typically 100 to 1000 slower. So I see little advantage in delegating.

I doubt there is a scheme that suits our needs.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Adam Back]

Makwa sites [1] https://bitcointalk.org/index.php?topic=311000.0

Seems like they independently rediscovered it.

Adam


On 23 January 2018 at 05:54, Ondřej Vejpustek via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>> Yes, this scheme.
>> https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217
>
> In addition to the scheme, I found out, that Makwa
> (https://www.bolet.org/makwa/), a hashing function which received a
> special recognition in the Password Hashing Competition, supports a
> delegation. In fact, Makwa is similar to the suggested scheme.
>
> Unfortunately, both schemes have two drawbacks:
>   (1) There is no proof that the host computes what he's suppose to do.
>   (2) The delegation is far more slower than the normal computation.
> According to the Makwa paper
> (https://www.bolet.org/makwa/makwa-spec-20150422.pdf) the delegation is
> typically 100 to 1000 slower. So I see little advantage in delegating.
>
> I doubt there is a scheme that suits our needs.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1728 bytes --]

On Tue, Jan 09, 2018 at 12:43:48PM +0000, Perry Gibson wrote:
> >Trezor's "plausible deniability" scheme could very well result in you going to
> >jail for lying to border security, because it's so easy for them to simply
> >brute force alternate passwords based on your seeds. With that, they have proof
> >that you lied to customs, a serious offense.
> The passphrase scheme as I understand it allows a maximum of 50 characters
> to be used.  Surely even with the HD seed, that search space is too large to
> brute force.  Or is there a weakness in the scheme I haven't clocked?

While passphrases *can* be long, most user's aren't going to understand the
risk. For example, Trezors blog(1) doesn't make it clear that the passphrases
could be bruteforced and used as evidence against you, and even suggests the
contrary:

    Since the passphrase is never saved on the device, this means that there is no
    wrong passphrase. The device does not know which one you have chosen, and
    therefore all of them are correct! Given the same seed, for each and every
    letter combination used as a passphrase, a different wallet will be generated.

and:

    Since there is no way to prove that there is any wallet beyond the ones
    that you have admitted to, the “attacker” will have to be satisfied with
    the revealed ones.


Also note how this blog doesn't mention anti-forensics: the wallet software
itself may leave traces of the other wallets on the computer. Have they really
audited it sufficiently to be sure this isn't the case?

1) https://blog.trezor.io/hide-your-trezor-wallets-with-multiple-passphrases-f2e0834026eb

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Pavol Rusnak]

On 11/01/18 00:47, Gregory Maxwell wrote:
> I believe that can be avoided by having the computer do somewhat more
> work and checking the consistency after the fact.
>
> (or for decode time, having a check value under the encryption...)

Can you describe these two methods more in detail? How exactly would
they work? What crypto primitives would you use and how?


-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
CTO, SatoshiLabs

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Wed, Jan 10, 2018 at 8:28 PM, Pavol Rusnak <stick@satoshilabs.com> wrote:
> On 09/01/18 16:12, Pavol Rusnak via bitcoin-dev wrote:
>> On 09/01/18 00:47, Gregory Maxwell wrote:
>>> Have you considered using blind host-delegated KDFs, where the KDF
>>> runs on the user's computer instead of the hardware wallet, but the
>>> computer doesn't learn anything about they keys?
>>
>> Any examples of these?

Yes, this scheme.
https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217

> Actually, scratch that. HW wallet would not know whether the host
> computer is lying or not. The computer would not learn about the keys,
> but still could be malicious and provide invalid result. Is that correct?


I believe that can be avoided by having the computer do somewhat more
work and checking the consistency after the fact.

(or for decode time, having a check value under the encryption...)

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Pavol Rusnak]

On 09/01/18 16:12, Pavol Rusnak via bitcoin-dev wrote:
> On 09/01/18 00:47, Gregory Maxwell wrote:
>> Have you considered using blind host-delegated KDFs, where the KDF
>> runs on the user's computer instead of the hardware wallet, but the
>> computer doesn't learn anything about they keys?
> 
> Any examples of these?

Actually, scratch that. HW wallet would not know whether the host
computer is lying or not. The computer would not learn about the keys,
but still could be malicious and provide invalid result. Is that correct?

-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
CTO, SatoshiLabs

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 4106 bytes --]

On Mon, Jan 8, 2018 at 7:39 AM, Pavol Rusnak via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

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

This entropy argument seems confused.  Ignoring constant factors, the
entropy of a checksum is the sum over all possible checksums, i, of
-n_i*log(n_i), where n_i is the number of times the ith checksum occurs
over the space of all possible data being checksummed.  In this application
the checksum is being applied to a fixed m-bit blob of uniformly random
data.

The entropy is maximized when every possible checksum occurs equally as
frequently, that is we achieve maximum entropy when all the n_i values are
equal to each other.  Any error correcting code worth it's salt will try to
achieve this property because the designers want every checksum value to
have as much error correcting power as every other checksum value.  I'm
almost certain that the algebraic properties of your typical error
correcting codes allow you to prove that maximum entropy is perfectly
achieved whenever the data-blob size is at least as large as the checksum
size.

Meanwhile the truncated value of a cryptographic hash function is expected
to be slightly under the maximum entropy value, under the assumption that
the hash function it behaves like a random function.

The main properties of a "strong cryptographic hash function" is that it is
infeasible to find collisions and preimages.  However these properties are
lost when you truncate the hash down to 16-bits.  At this point is it
entirely feasible to find collisions and preimages.

So using a truncated cryptographic hash function doesn't provide you with
more entropy (and, in fact, probably a sliver less entropy), and doesn't
provide you with any of the befits of strong cryptographic hash function.


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

Every checksum is error correcting.  Given an failed checksum, all you have
to do is search around the space of edits to find the smallest set edits
that yield a valid checksum.  With a 2^16 bit checksum one will expect to
find a nearby checksum within 2^16 trails, even when using a truncated hash
function.

What an error-correcting codes gives you isn't the ability to correct
errors, which we have seen is something that all short checksums provide,
rather they provide *guarantees* about the ability to detect (and correct)
certain common classes of errors.  For example we can have an ECC that
guarantees to find the error where are word is accidentally written down
twice (see
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015506.html
).

The advice you have been given will only result in losing any guarantees
about detecting common classes or errors; it won't stop attackers from
recovering missing information, and it won't provide a cryptographically
strong function.

[-- Attachment #2: Type: text/html, Size: 5185 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Pavol Rusnak]

On 09/01/18 00:47, Gregory Maxwell wrote:
> Have you considered using blind host-delegated KDFs, where the KDF
> runs on the user's computer instead of the hardware wallet, but the
> computer doesn't learn anything about they keys?

Any examples of these?


-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
CTO, SatoshiLabs

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[jens]

[-- Attachment #1: Type: text/plain, Size: 1812 bytes --]


> Trezor's "plausible deniability" scheme could very well result in you going to
> jail for lying to border security, because it's so easy for them to simply
> brute force alternate passwords based on your seeds. With that, they have proof
> that you lied to customs, a serious offense.
The passphrase scheme as I understand it allows a maximum of 50 
characters to be used.  Surely even with the HD seed, that search space 
is too large to brute force.  Or is there a weakness in the scheme I 
haven't clocked?

On 09/01/18 01:13, Peter Todd via bitcoin-dev wrote:
> On Mon, Jan 08, 2018 at 07:40:38PM -0500, Rhavar via bitcoin-dev wrote:
>> I think you're under-appreciating how useful the "plausible deniability". Someone I know was (solo) traveling to the United States when a border agent asked her to unlocked her phone; thumbed through her apps, ended up finding tinder and went through all her recent conversations to make sure she wasn't involved in any "pay for sex things".
>>
>> In the same light, I travel frequently and constantly have my trezor on me. If I am asked to unlock it, I will have no problems doing so (as refusal will no doubt lead to deportation) and showing my personal wallet (which sadly hasn't had much use since fees became ridiculous).
> Trezor's "plausible deniability" scheme could very well result in you going to
> jail for lying to border security, because it's so easy for them to simply
> brute force alternate passwords based on your seeds. With that, they have proof
> that you lied to customs, a serious offense.
>
> I would strongly advise you not to use it in that situation.
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Type: text/html, Size: 2725 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1110 bytes --]

On Mon, Jan 08, 2018 at 07:40:38PM -0500, Rhavar via bitcoin-dev wrote:
> I think you're under-appreciating how useful the "plausible deniability". Someone I know was (solo) traveling to the United States when a border agent asked her to unlocked her phone; thumbed through her apps, ended up finding tinder and went through all her recent conversations to make sure she wasn't involved in any "pay for sex things".
> 
> In the same light, I travel frequently and constantly have my trezor on me. If I am asked to unlock it, I will have no problems doing so (as refusal will no doubt lead to deportation) and showing my personal wallet (which sadly hasn't had much use since fees became ridiculous).

Trezor's "plausible deniability" scheme could very well result in you going to
jail for lying to border security, because it's so easy for them to simply
brute force alternate passwords based on your seeds. With that, they have proof
that you lied to customs, a serious offense.

I would strongly advise you not to use it in that situation.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Rhavar]

I think you're under-appreciating how useful the "plausible deniability". Someone I know was (solo) traveling to the United States when a border agent asked her to unlocked her phone; thumbed through her apps, ended up finding tinder and went through all her recent conversations to make sure she wasn't involved in any "pay for sex things".

In the same light, I travel frequently and constantly have my trezor on me. If I am asked to unlock it, I will have no problems doing so (as refusal will no doubt lead to deportation) and showing my personal wallet (which sadly hasn't had much use since fees became ridiculous).

And by doing so, I won't be revealing the half a dozen other accounts I keep. Which is the other big of such "plausible deniability" schemes, they make it trivial to create multiple wallets that are all firewalled away from each other.

I will hypothesize that if one of my wallets was for something like buying stuff on dark markets there's simply no way anyone is going to ever know way you're going to be to tell short of some movie-plot level police effort. 



​-Ryan

​

>-------- Original Message --------
>Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
>Local Time: January 8, 2018 5:47 PM
>UTC Time: January 8, 2018 11:47 PM
>From: bitcoin-dev@lists.linuxfoundation.org
>To: Pavol Rusnak <stick@satoshilabs.com>
>Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
>
>On Mon, Jan 8, 2018 at 12:39 PM, Pavol Rusnak stick@satoshilabs.com wrote:
>>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?
>>
> You can use a large block cipher. E.g. CMC cipher mode.
>
> Though I am doubtful that this is a very relevant concern: What
> consequence is it if someone with partial access to more than a
> threshold of the shares can recover part of the seed?  This doesn't
> seem like a very interesting threat.   A large block mode would be
> more complete, but this isn't something that would keep me up at night
> in the slightest.
>
> Perhaps I'm missing something, -- but the only real attack I see here
> is that a enduser mistakenly shows the first or couple words of all
> their shares on national television or what not... but doing so would
> not really harm their security unless they showed almost all of them,
> and in that case an attacker could simply search the remaining couple
> words.
>
> Also, if we are going to assume that users will leak parts, the
> mnemonic encoding ends up being pretty bad... since just leaking a
> letter or two of each word would quite likely give the whole thing
> away.
>
> In any case, to whatever extent partial leaks are a concern, using a
> large block cipher would be the obvious approach.
>
>>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.
>>
> Under this constraint it might be arguably to just eliminate the KDF.
> I think it provides false security and makes the implementation much
> more complicated.
>
> Have you considered using blind host-delegated KDFs, where the KDF
> runs on the user's computer instead of the hardware wallet, but the
> computer doesn't learn anything about they keys?
>
>>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.
>>
> I don't believe you can justify this design decision with any kind of
> rigorous threat model.
>
> The probability that a user loses funds because they have at some
> point recovered with the wrong key and don't know it would almost
> certainly dwarf the probability that the user face some kind of
> movie-plot threat where someone is attempting to forcibly extract a
> key and yet somehow has no information about the user's actual
> wallet-- through, for example, leaked data on the users computers, the
> users past payments to online accounts, or through a compromise or
> lawful order to satoshilab's web service which the users send private
> information to-- which would allow them to determine the key they were
> given was not correct.
>
> But even there, given the weak level of false input rejection that you
> have used (16 bits), it would be fairly straight forward to grind out
> an alternative passphrase that also passed the test.  Might that not
> make for a better compromise?
>
> Another thing to consider is that the main advantage of SSS over
> ordinary computational secret sharing is that it's possible to
> generate alternative shares to an sub-threshold set of primary shares
> that decodes to arbitrarily selected alternative data-- but it seems
> the proposal makes no use of this fact.
>
>>>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 end result is no better-- I think.  If you compromise
> functionality or security (e.g. pretextual KDF) because your product
> doesn't yet support -- say, aggregate signatures-- or won't ever
> support a strong KDF; then other software will just not be
> interoperable.  In cases were you won't ever support it, that doesn't
> matter-- but presumably you would later support new signature styles
> and the loss of interoperability would potentially be gratitious.
>
> That said, I'm generally skeptical of key interoperability to begin
> with. Wallets can't share keys unless their functionality is
> identical, half-interoperability can lead to funds loss. Identical
> functionality would mean constraining to the least common denominator.
>
> But even if we exclude cross vendor interoperability entirely,
> wouldn't you want your next version of your firmware to be able to
> support new and old key styles (e.g. aggregate signatures vs plain
> segwit) without having to define a whole new encoding?
>
>>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.
>>
> That sounds like a kind of hand-wave and cargo cult argument-- pleas
> be more specific, because that just sounds like amateur block cipher
> design.
>
> There isn't any difference in "entropy" in either of these cases.
>
> As an aside, using "n bits of a longer CRC" usually results in a low
> quality code for error detection similar to using a cryptographic
> hash.
>
>>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
>>
> Not meaningfully more than the truncated cryptographic hash.
>
> The best possible code of that length would allow you to list decode
> to around two errors with a lot of computation.
> With the cryptographic hash the attacker need only check the 2^28
> two-error candidates to do exactly the same thing.
>
> So the attacker there is no real difference-- he can brute force
> search to the same radius as correction would allow, but for the
> honest users and software the probability of undetected error is
> greater.  Similarly, while 2^28 operations is nothing to an attacker,
> if user software wants to use the correction for error hinting,
> running a hash 2^28 times would lead to a somewhat unfriendly user
> experience so non-attack tools would be pretty unlikely to implement
> it.
>
>bitcoin-dev mailing list
>bitcoin-dev@lists.linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1335 bytes --]

On Tue, Jan 09, 2018 at 09:26:17AM +1100, Ben Kloester wrote:
> > This sounds very dangerous. As Gregory Maxwell pointed out, the key
> derivation
> > function is weak enough that passphrases could be easily brute forced
> 
> So you are essentially imagining that a perpetrator will combine the
> crypto-nerd fantasy (brute forcing the passphrase) *with* the 5-dollar
> wrench attack, merging both panes of Randall Munroe's comic? Seems
> vanishingly unlikely to me - attackers are generally either the wrench
> type, or the crypto-nerd type.

We're talking about seeds here, not hardware wallets.

For a hardware wallet theft scenario, if you're worried about muggers you can
make the hardware have secret accounts with different seeds, *without* risking
user funds getting lost - a much more likely scenario - due to mistyped
passwords.

In any case, even if you were to do this type of design, a much better idea is
to use a checksum by default to reject invalid passwords, while having an
advanced-use-only option to override that checksum. The virtual file encryption
filesystem encfs does exactly this with its --anykey flag. This allows advanced
users to do their thing, while protecting the majority of users for whome this
feature is dangerous.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

On Mon, Jan 8, 2018 at 12:39 PM, Pavol Rusnak <stick@satoshilabs.com> wrote:
> 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?

You can use a large block cipher. E.g. CMC cipher mode.

Though I am doubtful that this is a very relevant concern: What
consequence is it if someone with partial access to more than a
threshold of the shares can recover part of the seed?  This doesn't
seem like a very interesting threat.   A large block mode would be
more complete, but this isn't something that would keep me up at night
in the slightest.

Perhaps I'm missing something, -- but the only real attack I see here
is that a enduser mistakenly shows the first or couple words of all
their shares on national television or what not... but doing so would
not really harm their security unless they showed almost all of them,
and in that case an attacker could simply search the remaining couple
words.

Also, if we are going to assume that users will leak parts, the
mnemonic encoding ends up being pretty bad... since just leaking a
letter or two of each word would quite likely give the whole thing
away.

In any case, to whatever extent partial leaks are a concern, using a
large block cipher would be the obvious approach.

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

Under this constraint it might be arguably to just eliminate the KDF.
I think it provides false security and makes the implementation much
more complicated.

Have you considered using blind host-delegated KDFs, where the KDF
runs on the user's computer instead of the hardware wallet, but the
computer doesn't learn anything about they keys?

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

I don't believe you can justify this design decision with any kind of
rigorous threat model.

The probability that a user loses funds because they have at some
point recovered with the wrong key and don't know it would almost
certainly dwarf the probability that the user face some kind of
movie-plot threat where someone is attempting to forcibly extract a
key and yet somehow has no information about the user's actual
wallet-- through, for example, leaked data on the users computers, the
users past payments to online accounts, or through a compromise or
lawful order to satoshilab's web service which the users send private
information to-- which would allow them to determine the key they were
given was not correct.

But even there, given the weak level of false input rejection that you
have used (16 bits), it would be fairly straight forward to grind out
an alternative passphrase that also passed the test.  Might that not
make for a better compromise?

Another thing to consider is that the main advantage of SSS over
ordinary computational secret sharing is that it's possible to
generate alternative shares to an sub-threshold set of primary shares
that decodes to arbitrarily selected alternative data-- but it seems
the proposal makes no use of this fact.

>> 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 end result is no better-- I think.  If you compromise
functionality or security (e.g. pretextual KDF) because your product
doesn't yet support -- say, aggregate signatures-- or won't ever
support a strong KDF; then other software will just not be
interoperable.  In cases were you won't ever support it, that doesn't
matter-- but presumably you would later support new signature styles
and the loss of interoperability would potentially be gratitious.

That said, I'm generally skeptical of key interoperability to begin
with. Wallets can't share keys unless their functionality is
identical, half-interoperability can lead to funds loss. Identical
functionality would mean constraining to the least common denominator.

But even if we exclude cross vendor interoperability entirely,
wouldn't you want your next version of your firmware to be able to
support new and old key styles (e.g. aggregate signatures vs plain
segwit) without having to define a whole new encoding?

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

That sounds like a kind of hand-wave and cargo cult argument-- pleas
be more specific, because that just sounds like amateur block cipher
design.

There isn't any difference in "entropy" in either of these cases.

As an aside, using "n bits of a longer CRC" usually results in a low
quality code for error detection similar to using a cryptographic
hash.

> 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

Not meaningfully more than the truncated cryptographic hash.

The best possible code of that length would allow you to list decode
to around two errors with a lot of computation.
With the cryptographic hash the attacker need only check the 2^28
two-error candidates to do exactly the same thing.

So the attacker there is no real difference-- he can brute force
search to the same radius as correction would allow, but for the
honest users and software the probability of undetected error is
greater.  Similarly, while 2^28 operations is nothing to an attacker,
if user software wants to use the correction for error hinting,
running a hash 2^28 times would lead to a somewhat unfriendly user
experience so non-attack tools would be pretty unlikely to implement
it.

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Ben Kloester]

[-- Attachment #1: Type: text/plain, Size: 2785 bytes --]

> This sounds very dangerous. As Gregory Maxwell pointed out, the key
derivation
> function is weak enough that passphrases could be easily brute forced

So you are essentially imagining that a perpetrator will combine the
crypto-nerd fantasy (brute forcing the passphrase) *with* the 5-dollar
wrench attack, merging both panes of Randall Munroe's comic? Seems
vanishingly unlikely to me - attackers are generally either the wrench
type, or the crypto-nerd type.

This thread started by you asking Pavol to give an example of a real-life
scenario in which this functionality would be used, and your rebuttal is a
scenario that is even less likely to occur. "Very dangerous" is a huge
stretch.

When living in Brazil I often carried two (IRL) wallets - one a decoy to
give to muggers, the other with more value stored in it. I heard of plenty
of people getting mugged, but I never heard of anyone who gave a decoy
wallet getting more thoroughly searched and the second wallet found,
despite the relative ease with which a mugger could do this. I'm sure it
has happened, probably many times, but point is there is rarely time for
contemplation in a shakedown, and most perpetrators will take things at
face value and be satisfied with getting something. And searching a
physical person's body is a hell of a lot simpler than cracking a
passphrase.

Moreover, there's no limit to the number of passphrases you can use. If you
were an atttacker, at what point would you stop, satisfied? After the
first, second, third, fourth wallet that you find/they admit to owning?
Going beyond two is already Bond-supervillain level implausible.

*Ben Kloester*

On 9 January 2018 at 06:37, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Mon, Jan 08, 2018 at 02:00:17PM +0100, Pavol Rusnak wrote:
> > On 08/01/18 13:45, Peter Todd wrote:
> > > Can you explain _exactly_ what scenario the "plausible deniability"
> feature
> > > refers to?
> >
> >
> > https://doc.satoshilabs.com/trezor-user/advanced_settings.
> html#multi-passphrase-encryption-hidden-wallets
>
> This sounds very dangerous. As Gregory Maxwell pointed out, the key
> derivation
> function is weak enough that passphrases could be easily brute forced, at
> which
> point the bad guys have cryptographic proof that you tried to lie to them
> and
> cover up funds.
>
>
> What model of human memory are you assuming here? What specifically are you
> assuming is easy to remember, and hard to remember? What psychology
> research
> backs up your assumptions?
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

[-- Attachment #2: Type: text/html, Size: 4324 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 820 bytes --]

On Mon, Jan 08, 2018 at 02:00:17PM +0100, Pavol Rusnak wrote:
> On 08/01/18 13:45, Peter Todd wrote:
> > Can you explain _exactly_ what scenario the "plausible deniability" feature
> > refers to?
> 
> 
> https://doc.satoshilabs.com/trezor-user/advanced_settings.html#multi-passphrase-encryption-hidden-wallets

This sounds very dangerous. As Gregory Maxwell pointed out, the key derivation
function is weak enough that passphrases could be easily brute forced, at which
point the bad guys have cryptographic proof that you tried to lie to them and
cover up funds.


What model of human memory are you assuming here? What specifically are you
assuming is easy to remember, and hard to remember? What psychology research
backs up your assumptions?

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Pavol Rusnak]

[-- Attachment #1.1: Type: text/plain, Size: 324 bytes --]

On 08/01/18 13:45, Peter Todd wrote:
> Can you explain _exactly_ what scenario the "plausible deniability" feature
> refers to?


https://doc.satoshilabs.com/trezor-user/advanced_settings.html#multi-passphrase-encryption-hidden-wallets


-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
CTO, SatoshiLabs


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 591 bytes --]

On Mon, Jan 08, 2018 at 01:39:20PM +0100, Pavol Rusnak via bitcoin-dev wrote:
> > 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.

Can you explain _exactly_ what scenario the "plausible deniability" feature
refers to?

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [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

Re: [bitcoin-dev] Satoshilabs secret shared private key scheme

[nullius]

[-- Attachment #1: Type: text/plain, Size: 785 bytes --]

On 2018-01-08 at 04:22:43 +0000 Gregory Maxwell <greg@xiph.org> wrote:
>I'm happy to see that there is no obvious way to abuse this one as a 
>brainwallet scheme!

BIP 39 was designed to make brainwallets secure!  If a user generates a 
weakling 12-word mnemonic from 16 tiny octets of entropy drawn off the 
non-artistic /dev/urandom, then protects its seed with a creative 
passphrase haiku about the power of human stupidity, then the result 
will have a 128-bit security level.  PROVE ME WRONG.

-- 
nullius@nym.zone | PGP ECC: 0xC2E91CD74A4C57A105F6C21B5A00591B2F307E0C
BIP 39 tool in progress, currently growing brainw^H^H^H^H^Hpassphrase 
support to help poor /dev/urandom: https://github.com/nym-zone/easyseed
Bitcoin: bc1qcash96s5jqppzsp8hy8swkggf7f6agex98an7h

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

[bitcoin-dev] Satoshilabs secret shared private key scheme

[Gregory Maxwell]

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!