Discussion:
Satoshilabs secret shared private key scheme
(too old to reply)
Gregory Maxwell via bitcoin-dev
2018-01-08 04:22:43 UTC
Permalink
Raw Message
On Sun, Jan 7, 2018 at 3:16 PM, Pavol Rusnak via bitcoin-dev
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!
Pavol Rusnak via bitcoin-dev
2018-01-08 12:39:20 UTC
Permalink
Raw Message
Post by Gregory Maxwell via bitcoin-dev
https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Hey Gregory!

Thanks for looking into the scheme. I appreciate your time!
Post by Gregory Maxwell via bitcoin-dev
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?
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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".
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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
Peter Todd via bitcoin-dev
2018-01-08 12:45:06 UTC
Permalink
Raw Message
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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
Pavol Rusnak via bitcoin-dev
2018-01-08 13:00:17 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
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
Peter Todd via bitcoin-dev
2018-01-08 19:37:14 UTC
Permalink
Raw Message
Post by Pavol Rusnak via bitcoin-dev
Post by Peter Todd via bitcoin-dev
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
Ben Kloester via bitcoin-dev
2018-01-08 22:26:17 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
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 <
Post by Peter Todd via bitcoin-dev
Post by Pavol Rusnak via bitcoin-dev
Post by Peter Todd via bitcoin-dev
Can you explain _exactly_ what scenario the "plausible deniability"
feature
Post by Pavol Rusnak via bitcoin-dev
Post by Peter Todd via bitcoin-dev
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?
--
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Peter Todd via bitcoin-dev
2018-01-09 00:37:25 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
Post by Peter Todd via bitcoin-dev
This sounds very dangerous. As Gregory Maxwell pointed out, the key
derivation
Post by Peter Todd via bitcoin-dev
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
Gregory Maxwell via bitcoin-dev
2018-01-08 23:47:02 UTC
Permalink
Raw Message
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Hey Gregory!
Thanks for looking into the scheme. I appreciate your time!
Post by Gregory Maxwell via bitcoin-dev
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
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.
Post by Pavol Rusnak via bitcoin-dev
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?
Post by Pavol Rusnak via bitcoin-dev
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.
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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?
Post by Pavol Rusnak via bitcoin-dev
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.
Post by Pavol Rusnak via bitcoin-dev
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.
Rhavar via bitcoin-dev
2018-01-09 00:40:38 UTC
Permalink
Raw Message
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
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Hey Gregory!
Thanks for looking into the scheme. I appreciate your time!
Post by Gregory Maxwell via bitcoin-dev
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
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.
Post by Pavol Rusnak via bitcoin-dev
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?
Post by Pavol Rusnak via bitcoin-dev
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.
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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?
Post by Pavol Rusnak via bitcoin-dev
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.
Post by Pavol Rusnak via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Peter Todd via bitcoin-dev
2018-01-09 01:13:35 UTC
Permalink
Raw Message
Post by Rhavar via bitcoin-dev
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
jens via bitcoin-dev
2018-01-09 12:44:56 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
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?
Post by Peter Todd via bitcoin-dev
Post by Rhavar via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Peter Todd via bitcoin-dev
2018-01-12 09:50:58 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
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
nullius via bitcoin-dev
2018-01-12 11:06:33 UTC
Permalink
Raw Message
Post by Peter Todd via bitcoin-dev
Post by jens via bitcoin-dev
Post by Peter Todd via bitcoin-dev
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.
Post by Peter Todd via bitcoin-dev
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.
Post by Peter Todd via bitcoin-dev
1) https://blog.trezor.io/hide-your-trezor-wallets-with-multiple-passphrases-f2e0834026eb
--
***@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
nullius via bitcoin-dev
2018-01-13 03:44:03 UTC
Permalink
Raw Message
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
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]
--
***@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
Peter Todd via bitcoin-dev
2018-01-13 06:11:12 UTC
Permalink
Raw Message
Post by nullius via bitcoin-dev
(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
Pavol Rusnak via bitcoin-dev
2018-01-09 15:12:58 UTC
Permalink
Raw Message
Post by Gregory Maxwell via bitcoin-dev
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
Pavol Rusnak via bitcoin-dev
2018-01-10 20:28:10 UTC
Permalink
Raw Message
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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
Gregory Maxwell via bitcoin-dev
2018-01-10 23:47:23 UTC
Permalink
Raw Message
Post by Pavol Rusnak via bitcoin-dev
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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
Post by Pavol Rusnak via bitcoin-dev
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...)
Pavol Rusnak via bitcoin-dev
2018-01-11 09:55:08 UTC
Permalink
Raw Message
Post by Gregory Maxwell via bitcoin-dev
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
Russell O'Connor via bitcoin-dev
2018-01-09 16:20:20 UTC
Permalink
Raw Message
On Mon, Jan 8, 2018 at 7:39 AM, Pavol Rusnak via bitcoin-dev <
Post by Pavol Rusnak via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Pavol Rusnak via bitcoin-dev
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.
nullius via bitcoin-dev
2018-01-08 06:33:44 UTC
Permalink
Raw Message
Post by Gregory Maxwell via bitcoin-dev
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.
--
***@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
Loading...