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; 22+ 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] 22+ messages in thread

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  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
  1 sibling, 0 replies; 22+ messages in thread
From: nullius @ 2018-01-08  6:33 UTC (permalink / raw)
  To: Gregory Maxwell, Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  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
                     ` (2 more replies)
  1 sibling, 3 replies; 22+ messages in thread
From: Pavol Rusnak @ 2018-01-08 12:39 UTC (permalink / raw)
  To: Gregory Maxwell, Bitcoin Protocol Discussion

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


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 12:39 ` Pavol Rusnak
@ 2018-01-08 12:45   ` Peter Todd
  2018-01-08 13:00     ` Pavol Rusnak
  2018-01-08 23:47   ` Gregory Maxwell
  2018-01-09 16:20   ` Russell O'Connor
  2 siblings, 1 reply; 22+ messages in thread
From: Peter Todd @ 2018-01-08 12:45 UTC (permalink / raw)
  To: Pavol Rusnak, Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 12:45   ` Peter Todd
@ 2018-01-08 13:00     ` Pavol Rusnak
  2018-01-08 19:37       ` Peter Todd
  0 siblings, 1 reply; 22+ messages in thread
From: Pavol Rusnak @ 2018-01-08 13:00 UTC (permalink / raw)
  To: Peter Todd, Bitcoin Protocol Discussion


[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 13:00     ` Pavol Rusnak
@ 2018-01-08 19:37       ` Peter Todd
  2018-01-08 22:26         ` Ben Kloester
  0 siblings, 1 reply; 22+ messages in thread
From: Peter Todd @ 2018-01-08 19:37 UTC (permalink / raw)
  To: Pavol Rusnak; +Cc: Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 19:37       ` Peter Todd
@ 2018-01-08 22:26         ` Ben Kloester
  2018-01-09  0:37           ` Peter Todd
  0 siblings, 1 reply; 22+ messages in thread
From: Ben Kloester @ 2018-01-08 22:26 UTC (permalink / raw)
  To: Peter Todd, Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 12:39 ` Pavol Rusnak
  2018-01-08 12:45   ` Peter Todd
@ 2018-01-08 23:47   ` Gregory Maxwell
  2018-01-09  0:40     ` Rhavar
  2018-01-09 15:12     ` [bitcoin-dev] Satoshilabs secret shared private key scheme Pavol Rusnak
  2018-01-09 16:20   ` Russell O'Connor
  2 siblings, 2 replies; 22+ messages in thread
From: Gregory Maxwell @ 2018-01-08 23:47 UTC (permalink / raw)
  To: Pavol Rusnak; +Cc: Bitcoin Protocol Discussion

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.


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 22:26         ` Ben Kloester
@ 2018-01-09  0:37           ` Peter Todd
  0 siblings, 0 replies; 22+ messages in thread
From: Peter Todd @ 2018-01-09  0:37 UTC (permalink / raw)
  To: Ben Kloester; +Cc: Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 23:47   ` Gregory Maxwell
@ 2018-01-09  0:40     ` Rhavar
  2018-01-09  1:13       ` Peter Todd
  2018-01-09 15:12     ` [bitcoin-dev] Satoshilabs secret shared private key scheme Pavol Rusnak
  1 sibling, 1 reply; 22+ messages in thread
From: Rhavar @ 2018-01-09  0:40 UTC (permalink / raw)
  To: Gregory Maxwell; +Cc: Bitcoin Protocol Discussion

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
>


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  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>
  0 siblings, 2 replies; 22+ messages in thread
From: Peter Todd @ 2018-01-09  1:13 UTC (permalink / raw)
  To: Rhavar, Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-09  1:13       ` Peter Todd
@ 2018-01-09 12:44         ` jens
       [not found]         ` <274aad5c-4573-2fdd-f8b0-c6c2d662ab7c@gibsonic.org>
  1 sibling, 0 replies; 22+ messages in thread
From: jens @ 2018-01-09 12:44 UTC (permalink / raw)
  To: Peter Todd, Bitcoin Protocol Discussion, Rhavar

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 23:47   ` Gregory Maxwell
  2018-01-09  0:40     ` Rhavar
@ 2018-01-09 15:12     ` Pavol Rusnak
  2018-01-10 20:28       ` Pavol Rusnak
  1 sibling, 1 reply; 22+ messages in thread
From: Pavol Rusnak @ 2018-01-09 15:12 UTC (permalink / raw)
  To: Gregory Maxwell; +Cc: Bitcoin Protocol Discussion

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


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-08 12:39 ` Pavol Rusnak
  2018-01-08 12:45   ` Peter Todd
  2018-01-08 23:47   ` Gregory Maxwell
@ 2018-01-09 16:20   ` Russell O'Connor
  2 siblings, 0 replies; 22+ messages in thread
From: Russell O'Connor @ 2018-01-09 16:20 UTC (permalink / raw)
  To: Pavol Rusnak, Bitcoin Protocol Discussion

[-- 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 --]

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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  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
  0 siblings, 1 reply; 22+ messages in thread
From: Pavol Rusnak @ 2018-01-10 20:28 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion, Gregory Maxwell

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


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-10 20:28       ` Pavol Rusnak
@ 2018-01-10 23:47         ` Gregory Maxwell
  2018-01-11  9:55           ` Pavol Rusnak
  0 siblings, 1 reply; 22+ messages in thread
From: Gregory Maxwell @ 2018-01-10 23:47 UTC (permalink / raw)
  To: Pavol Rusnak; +Cc: Bitcoin Protocol Discussion

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


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
  2018-01-10 23:47         ` Gregory Maxwell
@ 2018-01-11  9:55           ` Pavol Rusnak
  0 siblings, 0 replies; 22+ messages in thread
From: Pavol Rusnak @ 2018-01-11  9:55 UTC (permalink / raw)
  To: Gregory Maxwell; +Cc: Bitcoin Protocol Discussion

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


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

* Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
       [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
  0 siblings, 1 reply; 22+ messages in thread
From: Peter Todd @ 2018-01-12  9:50 UTC (permalink / raw)
  To: Perry Gibson; +Cc: Bitcoin Protocol Discussion

[-- 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 --]

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

* [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme)
  2018-01-12  9:50           ` Peter Todd
@ 2018-01-12 11:06             ` nullius
  2018-01-13  2:11               ` Damian Williamson
  0 siblings, 1 reply; 22+ messages in thread
From: nullius @ 2018-01-12 11:06 UTC (permalink / raw)
  To: Peter Todd, Bitcoin Protocol Discussion

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

On 2018-01-12 at 09:50:58 +0000, Peter Todd <pete@petertodd.org> wrote:
>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:  [...quote...]

I despise the term “plausible deniability”; and that’s really the wrong 
term to use in this discussion.

“Plausible deniability” is a transparent excuse for explaining away an 
indisputable fact which arouses suspicion—when you got some serious 
’splain’ to do.  This is usually used in the context of some pseudolegal 
argument about introducing “reasonable doubt”, or even making “probable 
cause” a wee bit less probable.

“Why yes, officer:  I was seen carrying an axe down the street near the 
site of an axe murder, at approximately the time of said axe murder.  
But I do have a fireplace; so it is plausible that I was simply out 
gathering wood.”

I rather suspect the concept of “plausible deniability” of having been 
invented by a detective or agent provocateur.  There are few concepts 
more useful for helping suspects shoot themselves in the foot, or 
frankly, for entrapping people.

One of the worst examples I have seen is in discussions of Monero, 
whereby I’ve seen proponents claim that even under the worst known 
active attacks, their mix scheme reduces transaction linking to a 
maximum of 20–40% probability.  “That’s not good enough to convince a 
jury!”  No, but it is certainly adequate for investigators to identify 
you as a person of interest.  Then, your (mis)deeds can be subjected to 
powerful confirmation attacks based on other data; blockchains do not 
exist in isolation.  I usually stay out of such discussions; for I have 
no interest in helping the sorts of people whose greatest concern in 
life is what story to foist on a jury.

In the context of devices such as Trezor, what is needed is not 
“plausible deniability”, but rather the ability to obviate any need to 
deny anything at all.  I must repeat, information does not exist in 
isolation.

If you are publicly known to be deepy involved in Bitcoin, then nobody 
will believe that your one-and-only wallet contains only 0.01 BTC.  
That’s not even “plausible”.  But if you have overall privacy practices 
which leave nobody knowing or suspecting that you have any Bitcoin at 
all, then there is nothing to “deny”; and should a Trezor with 
(supposedly) 0.01 BTC be found in your possession, that’s much better 
than “plausible”.  It’s completely unremarkable.

Whereas if you are known or believed to own large amounts of BTC, a 
realistic bad guy’s response to your “decoy” wallet could be, “I don’t 
believe you; and it costs me nothing to keep beating you with rubber 
hose until you tell me the *real* password.”

It could be worse, too.  In a kidnapping scenario, the bad guys could 
say, “I don’t believe you.  Hey, I also read Trezor’s website about 
‘plausible deniability’.  Now, I will maim your kid for life just to 
test whether you told me the *real* password.  And if you still don’t 
tell me the real password after you see that little Johnny can no longer 
walk, then I will kill him.”

The worst part is that you have no means of proving that you really 
*did* give the real password.  Indeed, it can be proved if you’re lying 
by finding a password which reveals a hidden wallet—but *you* have no 
means of affirmatively proving that you are telling the truth!  If the 
bad guys overestimated your riches (or if they’re in a bad mood), then 
little Johnny is dead either way.

In a legalistic scenario, if “authorities” believe you have 1000 BTC and 
you only reveal a password for 0.01 BTC, the likely response will not be 
to let you go.  Rather, “You will now sit in jail until you tell the 
*real* password.”  And again:  You have no means of proving that you did 
give the real password!

“Plausible deniability” schemes can backfire quite badly.

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

What about data obtained via the network?  I don’t *only* refer to 
dragnet surveillance.  See for but one e.g., Goldfelder, et al., “When 
the cookie meets the blockchain:  Privacy risks of web payments via 
cryptocurrencies” https://arxiv.org/abs/1708.04748  Your identity can be 
tied to your wallet all sorts of ways, any of which could be used to 
prove that you have more Bitcoin than you’re revealing.  Do you know 
what databases of cross-correlated analysis data customs agents have 
immediate access to nowadays—or will, tomorrow?  I don’t.

In the scenario under discussion, that may not immediately prove “beyond 
a reasonable doubt” that you lied specifically about your Trezor.  But 
it could give plenty of cause to keep you locked up in a small room 
while your hard drive is examined for evidence that Trezor apps handled 
*addresses already known to be linked to you*.  Why even bother with 
bruteforce?  Low-hanging fruit abound.

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

-- 
nullius@nym.zone | PGP ECC: 0xC2E91CD74A4C57A105F6C21B5A00591B2F307E0C
Bitcoin: bc1qcash96s5jqppzsp8hy8swkggf7f6agex98an7h | (Segwit nested:
3NULL3ZCUXr7RDLxXeLPDMZDZYxuaYkCnG)  (PGP RSA: 0x36EBB4AB699A10EE)
“‘If you’re not doing anything wrong, you have nothing to hide.’
No!  Because I do nothing wrong, I have nothing to show.” — nullius

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

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

* Re: [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme)
  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
  0 siblings, 1 reply; 22+ messages in thread
From: Damian Williamson @ 2018-01-13  2:11 UTC (permalink / raw)
  To: nullius, Bitcoin Protocol Discussion

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

The same problems exist for users of whole disk encrypted operating systems. Once the device (or, the initial password authentication) is found, the adversary knows that there is something to see. The objective of plausible deniability is to present some acceptable (plausible) alternative while keeping the actual hidden (denied).


If the adversary does not believe you, you do indeed risk everything.


Regards,

Damian Williamson

________________________________
From: bitcoin-dev-bounces@lists.linuxfoundation.org <bitcoin-dev-bounces@lists.linuxfoundation.org> on behalf of nullius via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Sent: Friday, 12 January 2018 10:06:33 PM
To: Peter Todd; Bitcoin Protocol Discussion
Subject: [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme)

On 2018-01-12 at 09:50:58 +0000, Peter Todd <pete@petertodd.org> wrote:
>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:  [...quote...]

I despise the term “plausible deniability”; and that’s really the wrong
term to use in this discussion.

“Plausible deniability” is a transparent excuse for explaining away an
indisputable fact which arouses suspicion—when you got some serious
’splain’ to do.  This is usually used in the context of some pseudolegal
argument about introducing “reasonable doubt”, or even making “probable
cause” a wee bit less probable.

“Why yes, officer:  I was seen carrying an axe down the street near the
site of an axe murder, at approximately the time of said axe murder.
But I do have a fireplace; so it is plausible that I was simply out
gathering wood.”

I rather suspect the concept of “plausible deniability” of having been
invented by a detective or agent provocateur.  There are few concepts
more useful for helping suspects shoot themselves in the foot, or
frankly, for entrapping people.

One of the worst examples I have seen is in discussions of Monero,
whereby I’ve seen proponents claim that even under the worst known
active attacks, their mix scheme reduces transaction linking to a
maximum of 20–40% probability.  “That’s not good enough to convince a
jury!”  No, but it is certainly adequate for investigators to identify
you as a person of interest.  Then, your (mis)deeds can be subjected to
powerful confirmation attacks based on other data; blockchains do not
exist in isolation.  I usually stay out of such discussions; for I have
no interest in helping the sorts of people whose greatest concern in
life is what story to foist on a jury.

In the context of devices such as Trezor, what is needed is not
“plausible deniability”, but rather the ability to obviate any need to
deny anything at all.  I must repeat, information does not exist in
isolation.

If you are publicly known to be deepy involved in Bitcoin, then nobody
will believe that your one-and-only wallet contains only 0.01 BTC.
That’s not even “plausible”.  But if you have overall privacy practices
which leave nobody knowing or suspecting that you have any Bitcoin at
all, then there is nothing to “deny”; and should a Trezor with
(supposedly) 0.01 BTC be found in your possession, that’s much better
than “plausible”.  It’s completely unremarkable.

Whereas if you are known or believed to own large amounts of BTC, a
realistic bad guy’s response to your “decoy” wallet could be, “I don’t
believe you; and it costs me nothing to keep beating you with rubber
hose until you tell me the *real* password.”

It could be worse, too.  In a kidnapping scenario, the bad guys could
say, “I don’t believe you.  Hey, I also read Trezor’s website about
‘plausible deniability’.  Now, I will maim your kid for life just to
test whether you told me the *real* password.  And if you still don’t
tell me the real password after you see that little Johnny can no longer
walk, then I will kill him.”

The worst part is that you have no means of proving that you really
*did* give the real password.  Indeed, it can be proved if you’re lying
by finding a password which reveals a hidden wallet—but *you* have no
means of affirmatively proving that you are telling the truth!  If the
bad guys overestimated your riches (or if they’re in a bad mood), then
little Johnny is dead either way.

In a legalistic scenario, if “authorities” believe you have 1000 BTC and
you only reveal a password for 0.01 BTC, the likely response will not be
to let you go.  Rather, “You will now sit in jail until you tell the
*real* password.”  And again:  You have no means of proving that you did
give the real password!

“Plausible deniability” schemes can backfire quite badly.

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

What about data obtained via the network?  I don’t *only* refer to
dragnet surveillance.  See for but one e.g., Goldfelder, et al., “When
the cookie meets the blockchain:  Privacy risks of web payments via
cryptocurrencies” https://arxiv.org/abs/1708.04748  Your identity can be
tied to your wallet all sorts of ways, any of which could be used to
prove that you have more Bitcoin than you’re revealing.  Do you know
what databases of cross-correlated analysis data customs agents have
immediate access to nowadays—or will, tomorrow?  I don’t.

In the scenario under discussion, that may not immediately prove “beyond
a reasonable doubt” that you lied specifically about your Trezor.  But
it could give plenty of cause to keep you locked up in a small room
while your hard drive is examined for evidence that Trezor apps handled
*addresses already known to be linked to you*.  Why even bother with
bruteforce?  Low-hanging fruit abound.

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

--
nullius@nym.zone | PGP ECC: 0xC2E91CD74A4C57A105F6C21B5A00591B2F307E0C
Bitcoin: bc1qcash96s5jqppzsp8hy8swkggf7f6agex98an7h | (Segwit nested:
3NULL3ZCUXr7RDLxXeLPDMZDZYxuaYkCnG)  (PGP RSA: 0x36EBB4AB699A10EE)
“‘If you’re not doing anything wrong, you have nothing to hide.’
No!  Because I do nothing wrong, I have nothing to show.” — nullius

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

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

* Re: [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme)
  2018-01-13  2:11               ` Damian Williamson
@ 2018-01-13  3:44                 ` nullius
  2018-01-13  6:11                   ` Peter Todd
  0 siblings, 1 reply; 22+ messages in thread
From: nullius @ 2018-01-13  3:44 UTC (permalink / raw)
  To: Damian Williamson, bitcoin-dev

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

Preface:  As a longstanding policy, whenever I buy a new hard disk or 
decommission an old one, I immediately `dd` it from start to end with a 
pseudorandom byte stream.  The result is indistinguishable from my disk 
encryption setup, which leaves no apparent on-disk headers.  I don’t do 
this for “plausibility” reasons, but rather, 0. to assure that 
immediately upon use, any sectors written with disk encryption cannot be 
distinguished from unwritten sectors, and 1. to make things overall more 
fun for potential cryptanalysts.  I do realize the small problem that I 
can’t affirmatively prove any particular disk in my possession to *not* 
contain decryptable data; and many of them don’t!

(I think that next, I may start writing my disks with headers for LUKS, 
which I do not use...)

Whereupon, I challenge plausible deniability designers to `dd` a 6TB 
disk with pseudorandom bytes, then try walking it across the U.S. border 
until it gets searched.  What could possibly go wrong?  Should you be 
ordered to decrypt it, the disk *could* be *plausibly* filled with 
pseudorandom bytes; and you would not be committing the crime of lying 
to an officer, when you truly state that in fact, it *is* filled with 
pseudorandom bytes.

Please, I want to see this “plausible deniability” theory in action.  
You owe it to your users to test the theory empirically, in 
circumstances in which users have here reported applying it.

Now, in reply:

On 2018-01-13 at 02:11:08 +0000, Damian Williamson 
<willtech@live.com.au> wrote:
>The same problems exist for users of whole disk encrypted operating 
>systems. Once the device (or, the initial password authentication) is 
>found, the adversary knows that there is something to see.

Or PGP.  Or in a broader sense, Tor.  Or in the physical world, a 
high-security safe bolted to your floor.  Security systems attract 
attention.  Smart people develop appropriate threat models, keep their 
security systems confidential where it is practical to do so (don’t brag 
about your high-security safe), and work to increase the popularity of 
network security systems (PGP, HTTPS, Tor...) to reduce how much they 
stand out.

In the context of this discussion, it does help that Bitcoin is becoming 
popular.  It would help much more if Trezors and similar devices were as 
commonplace as iGadgets.  But when considering the potential threats to 
any specific individual, the only “plausibility” shield is to not seem 
like someone who is likely to have *much*.  Of course, this is not a 
problem specific to Bitcoin.  Depending on the threat, the same danger 
applies to owning a substantial amount of gold, cash, or even money in a 
bank.

>The objective of plausible deniability is to present some acceptable 
>(plausible) alternative while keeping the actual hidden (denied).
>
>If the adversary does not believe you, you do indeed risk everything.

And therein lies the trick.  Unsophisticated adversaries such as common 
criminals may be fooled, or may not care if they can quickly grab 
*something* of value and run away.  But if your threat model may 
potentially include any adversaries possessed of both brains and 
patience, “plausible deniability” solves nothing.  Such an adversary 
will not likely be satisfied with the standard of “plausibility”.  More 
likely, the prevailing standard will be:  “I wasn’t born yesterday, and 
I *know* that you are hiding something.”

>[snip extended prior quotations]

-- 
nullius@nym.zone | PGP ECC: 0xC2E91CD74A4C57A105F6C21B5A00591B2F307E0C
Bitcoin: bc1qcash96s5jqppzsp8hy8swkggf7f6agex98an7h | (Segwit nested:
3NULL3ZCUXr7RDLxXeLPDMZDZYxuaYkCnG)  (PGP RSA: 0x36EBB4AB699A10EE)
“‘If you’re not doing anything wrong, you have nothing to hide.’
No!  Because I do nothing wrong, I have nothing to show.” — nullius

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

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

* Re: [bitcoin-dev] Plausible Deniability (Re: Satoshilabs secret shared private key scheme)
  2018-01-13  3:44                 ` nullius
@ 2018-01-13  6:11                   ` Peter Todd
  0 siblings, 0 replies; 22+ messages in thread
From: Peter Todd @ 2018-01-13  6:11 UTC (permalink / raw)
  To: nullius, Bitcoin Protocol Discussion

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

On Sat, Jan 13, 2018 at 03:44:03AM +0000, nullius via bitcoin-dev wrote:
> (I think that next, I may start writing my disks with headers for LUKS,
> which I do not use...)
> 
> Whereupon, I challenge plausible deniability designers to `dd` a 6TB disk
> with pseudorandom bytes, then try walking it across the U.S. border until it
> gets searched.  What could possibly go wrong?  Should you be ordered to
> decrypt it, the disk *could* be *plausibly* filled with pseudorandom bytes;
> and you would not be committing the crime of lying to an officer, when you
> truly state that in fact, it *is* filled with pseudorandom bytes.

It's very common for disks to be filled with pseudorandom data; this is not
suspicious at all. For example:

1) An encrypted partition that is filled, and later reformatted, will be left
full of random bytes. Even if you give border security your passphrase, the
unused space in the encrypted partition will be random data. (an exception
being most - but not all! - SSD's where TRIM has been used)

2) Modern drives (SSD and HD) often implement fast secure erasure with
encryption, which means that the actual data stored to disk or FLASH is
*always* encrypted. If such a drive is wiped, the encryption keys are replaced,
which means whatever data was stored becomes random noise (the encrypted data
is usually not authenticated). This also means that such drives can arrive from
the factory filled with random noise.

3) Software disk encryption schemes have the same property: reformatting
results in a drive filled with random noise.

The latter is particularly interesting with LUKS, as you can do all kinds of
things like erase the drive with luksErase, while keeping a backup of the LUKS
header elsewhere.

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

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

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

end of thread, other threads:[~2018-01-13  6:11 UTC | newest]

Thread overview: 22+ 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

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