Deterministic wallets and sharing private keys

[thanke]

The clients that offer type-2 deterministic wallets (like electrum and armory) should advise their users that sharing any private key from the derived chain (not the master private key, of course) MUST be avoided. Such a sharing of a private key could happen for example by funding your MtGox account with the "Redeem private key" option.

The deterministic wallet suggested in the thread https://bitcointalk.org/index.php?topic=19137.0 is this computation of the key chains:
Publickey(type,n) = Master_public_key + H(n|S|type)*point
Privatekey(type,n) = Master_private_key + H(n|S|type)

The use scenario is that a "hot" machine (connected to the internet and potentially vulnerable) generates a chain of public keys, and for that purpose stores both the master public key and the seed S. In a reasonable threat model both values become available to an attacker. Since the serial numbers n and the type can be guessed, a single leaked private key will leak the master private key as well by a simple substraction in a the finite field underlying secp256k1.

Users should be advised that ANY private key from the generated key chain is to be secured with the same security level as the master private key.

This seems to affect both electrum and armory implementations of deterministic wallets.

Can someone please crosspost this to https://bitcointalk.org/index.php?topic=19137.0 (I can't due to newbie rules, sorry never bothered posting anything despite using bitcoin for years).

[Stephen Gornick]

Can someone please crosspost this to https://bitcointalk.org/index.php?topic=19137.0 (I can't due to newbie rules, sorry never bothered posting anything despite using bitcoin for years).

An update on the wiki article would be good too:

 - http://en.bitcoin.it/wiki/Deterministic_Wallet

[ThomasV]

The clients that offer type-2 deterministic wallets (like electrum and armory) should advise their users that sharing any private key from the derived chain (not the master private key, of course) MUST be avoided. Such a sharing of a private key could happen for example by funding your MtGox account with the "Redeem private key" option.

You are right.
A private key should never be shared, and the idea of "redeeming" a private key is silly; the only sensible way to transfer value is to create a transaction.
You are right to point out that this is even worse with deterministic wallets.

I was planning to add a warning in Electrum, against web sites such as brainwallet.org; I guess we should extend that warning, against "redeem private key" features.

[EhVedadoOAnonimato]

Let me see if I got the tl;dr version correctly.

With the master public key and a single, non-master private key as inputs, it's possible to calculate the master private key. Is that correct?

[thanke]

With the master public key and a single, non-master private key as inputs, it's possible to calculate the master private key. Is that correct?

Correct. Well, to be precise, you also need the seed S (besides the master public key and a single, non-master private key). Electrum uses the master public key itself as the seed, while Armory uses what it calls a chaincode. However, this doesn't make a difference because for practical purposes, i.e. in order to be able to generate the chain of public keys, both the master public key and the seed will be stored together on the same machine.

A private key should never be shared, and the idea of "redeeming" a private key is silly; the only sensible way to transfer value is to create a transaction.

Yes, any best-practice document should reflect this. More so since deterministic wallets are already in widespread use.

[ThomasV]

Correct. Well, to be precise, you also need the seed S (besides the master public key and a single, non-master private key). Electrum uses the master public key itself as the seed, while Armory uses what it calls a chaincode. However, this doesn't make a difference because for practical purposes, i.e. in order to be able to generate the chain of public keys, both the master public key and the seed will be stored together on the same machine.

what you write is correct, but for Electrum users, the word "seed" refers to a secret number used to derive their master private key.
what you call "seed" here is Electrum's master public key.
I am just writing this in case users who are familiar with Electrum find it confusing. :-)

[casascius]

...the idea of "redeeming" a private key is silly; the only sensible way to transfer value is to create a transaction.

Why is this silly?

It sounds to me almost like saying "using any phone but the iPhone to make phone calls is silly".  It says something without actually saying anything.

Do you mean that the phrase "redeeming a private key" is a silly way to describe conveying a private key as a means of transferring bitcoins, or just that you believe that people ought never to transfer value by conveying the private keys encumbering it?

[ThomasV]

...the idea of "redeeming" a private key is silly; the only sensible way to transfer value is to create a transaction.

Why is this silly?

It sounds to me almost like saying "using any phone but the iPhone to make phone calls is silly".

Do you mean that the phrase "redeeming a private key" is a silly way to describe conveying a private key as a means of transferring bitcoins, or just that you believe that people ought never to transfer value by conveying the private keys encumbering it?

the latter. people should not transfer value by communicating a private key to a stranger.

[casascius]

the latter.

Now that it's clear... why is this silly?

As now clarified:

the latter. people should not transfer value by communicating a private key to a stranger.

By the same broad logic, people shouldn't use checks.  Anyone could write a bad check, or put a stop payment on a good one until cashed.

Narrowing it a bit, using checks is sensible when the parties have trust or recourse.  Is the same not true for conveying private keys?  Conveying private keys allows people to transact in Bitcoin units in the immediate absence of power, internet, and/or properly configured hardware, an ability taken for granted with fiat cash/checks and a feature the common populace is going to expect from any currency meant to replace it.

[ThomasV]

the latter.

Now that it's clear... why is this silly?

As now clarified:

the latter. people should not transfer value by communicating a private key to a stranger.

By the same broad logic, people shouldn't use checks.  Anyone could write a bad check, or put a stop payment on a good one until cashed.

Narrowing it a bit, using checks is sensible when the parties have trust or recourse.  Is the same not true for conveying private keys?  Conveying private keys allows people to transact in Bitcoin units in the immediate absence of power, internet, and/or properly configured hardware, an ability taken for granted with fiat cash/checks and a feature the common populace is going to expect from any currency meant to replace it.

You might be very well organized and aware of the risks, so that after you "redeem" one of your private keys at mtgox, you will also remove that key from your wallet, or otherwise mark it as "not secret anymore", so that you will never reuse the corresponding address to receive coins...

However, you cannot expect other people to have the same level of organisation, discipline and awareness as you have. It is a bad practice to share private keys, and I do not think we should encourage this.

[casascius]

You might be very well organized and aware of the risks, so that after you "redeem" one of your private keys at mtgox, you will also remove that key from your wallet, or otherwise mark it as "not secret anymore", so that you will never reuse the corresponding address to receive coins...

That's just it...  ideally, the key I redeemed would be a paper wallet that exists nowhere other than on the piece of paper itself, so these steps are unnecessary and self-performing just by virtue of how the wallet came to be.  People are going to use paper wallets regardless because they are secure in practice and super easy to manage.

It's worth pointing out that people who keep their bitcoins on paper wallets aren't losing them, and the people who are keeping them in hotwallets (or in cold wallets but mismanaging their backups) are losing them left and right.  The practical benefit to using paper wallets clearly outweighs the theoretical benefits of discouraging or forbidding the importation of private keys.

If the security of an Electrum wallet is compromised by people using its deterministic keys to make paper wallets or to give away to counterparties, then Electrum may do well to offer a path of least resistance and make it easy to generate/print throwaway (non-deterministic) public keys for giveaway purposes, that never get saved in the wallet.  This way, those who have the opinion that "it's not silly" aren't going to compromise their whole Electrum wallet by accidentally giving away the means to compute their seed.  Likewise, it should prefer to "sweep" private keys instead of "importing" them, maximizing the ability for a user to capture funds from a paper wallet without unknowingly being exposed to theft after they thought they were safe following a successful import.

[thanke]

As now clarified:

the latter. people should not transfer value by communicating a private key to a stranger.

By the same broad logic, people shouldn't use checks.  Anyone could write a bad check, or put a stop payment on a good one until cashed.

Not sure if this analogy is fitting: checks are a risk for the accepting party, not for the undersignee/payer, while conveying private keys can be a risk for the payer if he doesn't know what he is doing (i.e. happens to use keys from a deterministic wallet).

Narrowing it a bit, using checks is sensible when the parties have trust or recourse.  Is the same not true for conveying private keys?  Conveying private keys allows people to transact in Bitcoin units in the immediate absence of power, internet, and/or properly configured hardware, an ability taken for granted with fiat cash/checks and a feature the common populace is going to expect from any currency meant to replace it.

What do you mean by "absence of properly configured hardware"? If you have in mind that you want to pay a stranger over the internet and have no trusted computer/operating system at hand then none of the two options is sensible, neither typing the private key from your paper wallet into a browser nor starting a bitcoin client on this OS.

A separate issue: redeeming a private key doesn't allow for change.

[thanke]

That's just it...  ideally, the key I redeemed would be a paper wallet that exists nowhere other than on the piece of paper itself, so these steps are unnecessary and self-performing just by virtue of how the wallet came to be.  People are going to use paper wallets regardless because they are secure in practice and super easy to manage.

For paper wallets you either need a safe (not easy to manage) or the paper keys have to be one part of a 2-of-2 multisig output. Otherwise, I wouldn't feel secure with them except for tiny amounts.

It's worth pointing out that people who keep their bitcoins on paper wallets aren't losing them, and the people who are keeping them in hotwallets (or in cold wallets but mismanaging their backups) are losing them left and right.  The practical benefit to using paper wallets clearly outweighs the theoretical benefits of discouraging or forbidding the importation of private keys.

Correct, but it was not the point to discourage importation of private keys (from paper wallets for example). The point was just to discourage the average user from conveying private keys to strangers. I don't see the benefit of conveying a private key from your paper wallet to someone else over importing that private key into your client and conducting a regular transaction. Instead, a regular transaction has two added benefits: 1) proof of payment if you pay to a signed URI, 2) possibility of change.

In the absence of power or internet I agree with you and think your coins are the way to go.

If the security of an Electrum wallet is compromised by people using its deterministic keys to make paper wallets or to give away to counterparties, then Electrum may do well to offer a path of least resistance and make it easy to generate/print throwaway (non-deterministic) public keys for giveaway purposes, that never get saved in the wallet.  This way, those who have the opinion that "it's not silly" aren't going to compromise their whole Electrum wallet by accidentally giving away the means to compute their seed.

Keys for paper wallets doesn't necessarily have to be non-deterministic, type-1 deterministic wallets are fine. The risk is only with type-2 deterministic wallets.

Likewise, it should prefer to "sweep" private keys instead of "importing" them, maximizing the ability for a user to capture funds from a paper wallet without unknowingly being exposed to theft after they thought they were safe following a successful import.

"Sweep" means import and transfer to another address?

[casascius]

As now clarified:

the latter. people should not transfer value by communicating a private key to a stranger.

By the same broad logic, people shouldn't use checks.  Anyone could write a bad check, or put a stop payment on a good one until cashed.

Not sure if this analogy is fitting: checks are a risk for the accepting party, not for the undersignee/payer, while conveying private keys can be a risk for the payer if he doesn't know what he is doing (i.e. happens to use keys from a deterministic wallet).

Sure, it fits.  This would be like giving away checks that are really transaction slips that have your online banking login and password pre-printed on them because they support some neat new payment feature the bank came out with, where the bank has decided they mean for you write the check and scan it with your own computer to move the funds to the payee.  Rather than the bank saying "the old way of checking is stupid", they should continue to offer paper checks that don't have this "feature" since even in the age of electronic money, there are still good use cases for writing checks.

Narrowing it a bit, using checks is sensible when the parties have trust or recourse.  Is the same not true for conveying private keys?  Conveying private keys allows people to transact in Bitcoin units in the immediate absence of power, internet, and/or properly configured hardware, an ability taken for granted with fiat cash/checks and a feature the common populace is going to expect from any currency meant to replace it.

What do you mean by "absence of properly configured hardware"? If you have in mind that you want to pay a stranger over the internet and have no trusted computer/operating system at hand then none of the two options is sensible, neither typing in the private key from your paper wallet nor starting a bitcoin client on this OS.

A separate issue: redeeming a private key doesn't allow for change.

I mean two people bumbling around trying to transfer bitcoins from one to the other but can't because one or the other party just got a new cellphone or needs to download the last 5000 blocks of the blockchain and is several minutes away from having a working bitcoin wallet to the point that transferring digital bitcoins is impractical.

Redeeming a private key does allow for change: either returned on the same note or on another note or a new note (when the payee can print one, such as a pos retail terminal).  It presents a risk that the change could be stolen, but it is a risk that can be mitigated just by printing small denomination notes.

[thanke]

Correct. Well, to be precise, you also need the seed S (besides the master public key and a single, non-master private key). Electrum uses the master public key itself as the seed, while Armory uses what it calls a chaincode. However, this doesn't make a difference because for practical purposes, i.e. in order to be able to generate the chain of public keys, both the master public key and the seed will be stored together on the same machine.

what you write is correct, but for Electrum users, the word "seed" refers to a secret number used to derive their master private key.
what you call "seed" here is Electrum's master public key.
I am just writing this in case users who are familiar with Electrum find it confusing. :-)

Yes, by "seed" I was referring its meaning in gmaxwell's original post, which is different what Electrum calls its seed.

Here is a specific suggestion for Electrum: I want to take k pieces of paper, divide the wallet seed into n parts and write on each piece of paper m of the n parts. The pieces of paper will be stored in different locations, so that someone needs access to several locations simultaneously in order to recover the wallet seed. Now, the seed being 128bit long, simply dividing into n shorter parts doesn't work even for n=2 because 64bit is not secure enough against brute force attacks. Each part should be 128bit as well. Maybe Electrum can print out n seeds, 128bit each, which XORed together give the wallet's seed?

[ThomasV]

Here is a specific suggestion for Electrum: I want to take k pieces of paper, divide the wallet seed into n parts and write on each piece of paper m of the n parts. The pieces of paper will be stored in different locations, so that someone needs access to several locations simultaneously in order to recover the wallet seed. Now, the seed being 128bit long, simply dividing into n shorter parts doesn't work even for n=2 because 64bit is not secure enough against brute force attacks. Each part should be 128bit as well. Maybe Electrum can print out n seeds, 128bit each, which XORed together give the wallet's seed?

if you are geeky enough to want to do that, then I guess you can do it using the command line.
I don't want the GUI to include complicated options that only a minority of users will understand.

[casascius]

One way to allow key import that would have a convenient side effect: encourage the use of "minikeys" (30-character hash-based keys) for paper wallet and bitcoin voucher applications, and discourage the use of the full 51-character private key code.

In doing so, you will be selectively discouraging the use of private keys that could have come from a deterministic wallet, because it won't be possible to make a 30-character minikey that also was derived from a deterministic wallet.  It benefits the user with a shorter code, so the change is attractive.

Minikeys are already supported by pretty much anything that accepts private keys (other than the Satoshi client) simply because of my use of them in my coins.  If there was a consensus that paper wallet generators should default to generating minikeys, I bet it could be made into the de facto standard way to do a paper wallet.

[thanke]

One way to allow key import that would have a convenient side effect: encourage the use of "minikeys" (30-character hash-based keys) for paper wallet and bitcoin voucher applications, and discourage the use of the full 51-character private key code.

Agree, great idea. Very clean distinguishment for the user.

In doing so, you will be selectively discouraging the use of private keys that could have come from a deterministic wallet, because it won't be possible to make a 30-character minikey that also was derived from a deterministic wallet.

It won't be possible to make a 30-character minikey that also was derived from a deterministic type 2 wallet as we were discussing it. However, it's still possible to generate the minikeys deterministically by a PRNG from some seed. This may be even advisable, you could have minikeys on paper flying around in your various purses and still have the seed to all of them somewhere in a safe.

[casascius]

Yes that is what I mean, type 2.  I don't mean to suggest they can't be generated deterministically at all