[How Electrum Works] Why you should be careful with your private keys.

[dabura667]

Hi all,

In another thread, it seemed that not many people are aware (even though there is a warning message when you export a private key from a seeded address) of the (MPK + privkey_n = Master Private Key (mpk)) quirk.

I'm here to explain it.

First, some clarification.

Your seed is not your Master Private Key. Your seed is "stretched" out 100,000 times by hashing it against itself and subsequent hashes. The final hash that arises from this process is your "Master Private Key" or Extended Private Key. This is the private key to your Master Public Key.

Now that you understand this, here's some basic ECC math:

For a private-public keypair d = private, P = Public, the formula that calculates the public key from the private key is P = dG... where G is the "generator point" on the curve that Bitcoin uses for Elliptic Curve calculations. All keypairs in Bitcoin use the same Generator point G.

This relationship of P = dG is important to understand how the attack takes place.


First let's learn about Electrum's address derivation.

Well, the address derivation formula works something like this:

1. We first create an "s" which is = Hash( n:c:MPK ) where n = the index number of the address (0 = first address, 1 = second address, etc.) and c = Change addresses or not. (1 = change, 0 = regular) and MPK = your master public key.
2. Then we take that hash, use it as a private key against the generator point to get a public key R = sG
3. Then we take the master public key and add it to the sequence public key. This gives us a 3rd public key without needing to know its private key or the master private key, we will call this P_n = d_nG

Notice how nowhere in that process did I use the master private key or the private key to P_n.

Now, how do I spend bitcoins for the address at P_n?

1. I stretch the seed 100,000 times to get the Master private key.
2. Since P_n = MPK + R... we can also write the equation as d_nG = mpkG + sG.... G cancels out to get d_n = mpk + s
3. We add the master private key to the Sequence "s" (and mod by the curve order) to get d_n... with this, we can sign for the address at P_n

......

Ok, now that we understand what's going on, how are we vulnerable?

First, what does the attacker need?

1. Your Master Public Key.
2. Any one of the private keys from an individual address derived from your Master Public(/private) Key.

How do they attack you?

I know 100% that your MPK is correct, I know 100% that the private key I obtained is from that MPK's address. Normally people don't use a lot of addresses on Electrum, so even if we don't know the sequence number, we could try about 100 times and most likely find the right sequence.

Here's what I do:
1. I calculate the Bitcoin address from your private key, public key is X.
2. I attempt to guess, let's say I get it right that your number was Hash( 0:0:MPK ). Because I know your MPK and I guessed the index of your private key, I now have the sequence secret.
3. I created the public key for the sequence secret, and add it to your Master Public Key. If the end result is X, I have correctly found the sequence secret. If not, just keep guessing, its fast.
4. As we said before, private key derivation is d₀ = mpk + s... so we change it around to mpk = s - d₀
5. We know the sequence secret now, and the Bitcoin address private key. we subtract the private key from the sequence secret, modding by the curve order, we get the master private key.
6. Just in case, check if MPK = mpk * G. If it does, now you can solve any sequence address's private key.


So everyone, please treat every single individual private key on your seed's wallet as carefully as you would treat your seed.


BIP32 has the same problem, however, it also has something called "hardened keys." Which are supposed to break the chain (so you can only derive it one way) but at the expense of utility. (You won't be able to derive deeper chains from that child)


That being said. Electrum's offline signing ability and its lightweight client make it my favorite Bitcoin client to date. Just be sure to educate yourself. The same can be said with anything in life, especially Bitcoin related things, but it always helps to learn.


I hope this helps prevent theft. Please take care of your private keys.

Thank you.

[1715038312]

1715038312

[1715038312]

1715038312

[jonald_fyookball]

Thanks Debura.

Btw, 10,000 or 100,000?

[JonCD]

Thanks for the explanation.

I've seen you mention this topic many times around here lately, so it's great to finally be able to be able to quantify why this occurs.

I feel like keys simply should never be exported because of this, why would anyone ever want to take this risk?

[jonald_fyookball]

Thanks for the explanation.

I've seen you mention this topic many times around here lately, so it's great to finally be able to be able to quantify why this occurs.

I feel like keys simply should never be exported because of this, why would anyone ever want to take this risk?

The only valid reason I can think of, would be to do an off chain transaction.  But in that case, it should be the only coins in the electrum wallet, and therefore, why not simply give someone the seed?

[dabura667]

Thanks Debura.

Btw, 10,000 or 100,000?

https://github.com/spesmilo/electrum/blob/master/lib/account.py#L148

Nice catch. Fixed the OP.

[AussieHash]

http://bitcoinmagazine.com/8396/deterministic-wallets-advantages-flaw/

Vitalik Buterin
7 months ago
> you can get all of the other private keys in the same sequence. That is not a vulnerability, that is the way it is *supposed* to work. In fact, that is the whole point!

No, that is very much a vulnerability. Here's the idea. Suppose I make a root master private key, then hand my master public key to my accountant, and then create three child keys - one for department A, one for department X, and one for myself. Intuitively, this setup should be safe. Department A should not be able to compute the keys of department X or myself, and indeed they can't. Also, the accountant should not be able to get any private keys. However, if the accountant and department X collude, they can steal everything. This is very counterintuitive, and this is very bad.

[JonCD]

There is one clever way in which this might be bypassed: making three hierarchical BIP32 wallets, with every address being a 2-of-3 multisignature address between the three wallets down some particular child key derivation path. Then, an auditor can have one of the three master public keys, and search the blockchain for transactions whose script contains public keys generated from that master public key. The solution is complex, not supported by any existing client, and far from perfect, but something like it seems to be the only way to get around the issue.
-Vitalik Buterin

What do you guys think of this solution? How feasible is this?

[jonald_fyookball]

There is one clever way in which this might be bypassed: making three hierarchical BIP32 wallets, with every address being a 2-of-3 multisignature address between the three wallets down some particular child key derivation path. Then, an auditor can have one of the three master public keys, and search the blockchain for transactions whose script contains public keys generated from that master public key. The solution is complex, not supported by any existing client, and far from perfect, but something like it seems to be the only way to get around the issue.
-Vitalik Buterin

What do you guys think of this solution? How feasible is this?

Solution to what?  Trying to combine deterministic wallets with multisig?  Why would you even need to do that?

[JonCD]

The solution to a more secure internal control structure, so you can leverage the utility of the master public key.

[jonald_fyookball]

The solution to a more secure internal control structure, so you can leverage the utility of the master public key.

There's nothing wrong with how electrum does it.  He's talking about some convoluted scenario that doesn't have any real life application as far as I'm concerned.

[dabura667]

The solution to a more secure internal control structure, so you can leverage the utility of the master public key.

There's nothing wrong with how electrum does it.  He's talking about some convoluted scenario that doesn't have any real life application as far as I'm concerned.

Actually, the "solution" that JonCD was talking about was more geared towards BIP32.

Electrum (in its current 1.9.8 version) would not be able to generate the 3 separate key chains for a deterministic 2of3 P2SH chain wallet.


However, the method JonCD describes is actually what ThomasV is implementing into Electrum 2.0 right as we speak. (in fact current git HEAD already has 2 of 3 and 2 of 2 BIP32 deterministic chains already.)

The idea is that since your bitcoins are not attributed to any 1 specific master public key and master private key, even if you exported one of the private keys and someone calculated your master private key, they would still need one more master private key, AND they would need all three master public keys (so that they could create the redeemscripts)...

It adds a level of obfuscation that protects the user. Not to mention that if your wallet is 2 of 3, you probably won't be exporting keys anyways.

In general, if you want to have exportable private keys in BIP32, you must use hardened keys. The downside to this is that you will not be able to generate those public keys from a Master Public Key. (hardened keys do not have a master public key, which is how they are hardened) But they will still be attached to your chain, so recoverable from seed.

[jonald_fyookball]

I was referring to the quote from Vitalik. I don't see the point to implement a complex scheme like that just to allow an auditor to search the blockchain when you could set up a watch only wallet.  Doesn't make sense, maybe I'm missing something.

[dabura667]

I was referring to the quote from Vitalik. I don't see the point to implement a complex scheme like that just to allow an auditor to search the blockchain when you could set up a watch only wallet.  Doesn't make sense, maybe I'm missing something.

The idea is that if you give the auditor the watch only wallet, he could conspire with one of the holders of the private keys below it to create the master private key and run away with all the money.

M = master public key
m = master private key

m/ = CEO holds it

M/ = Auditor holds it. With it, they can view all company funds, but not spend.

m/m₁ = Department A head holds it, and can generate further chains with it.
m/m₂ = Department B head holds it, and can generate further chains with it.
m/m₃ = Department C head holds it, and can generate further chains with it.

combining M/ with m/m_x would give me m/ ... so an auditor would have to conspire with one corrupt department head to run away with the company's entire finances.


With the solution provided says that the CEO would make

m₁/
m₂/
m₃/

Then

Dept A:
m₁/m₁
m₂/m₁
m₃/m₁

Dept B:
m₁/m₂
m₂/m₂
m₃/m₂

Dept C:
m₁/m₃
m₂/m₃
m₃/m₃

Each dept using the three public keys generated by those chains to generate deterministic 2of3 chains.

The Auditor would ONLY receive:

M₁/

Then they could check the blockchain for redeemscripts that included
M₁/M₁
M₁/M₂
M₁/M₃

Then they would know how much money each department SPENT without being able to collude to get 2 private keys.

Downside: They could only find SPENT funds, as the redeemscript is only revealed on the blockchain when funds are spent from the multi-sig address.

imo, the best way to do an audit for business would be to use a dual-key Stealth Address, and give the scan_privkey to the auditor... but this is a topic slightly unrelated to BIP32.

You could set up so your company's stealth addresses are generate on a per-department basis, but that all scan_keypairs are generated by a separate BIP32 chain.

Give that master private key to the auditor, as that keypair is only used to generate shared secrets to discover funds, not to spend it.

[jonald_fyookball]

What about create 1000 receive and change addresses and not give public key to auditor ?

[JonCD]

I was referring to the quote from Vitalik. I don't see the point to implement a complex scheme like that just to allow an auditor to search the blockchain when you could set up a watch only wallet.  Doesn't make sense, maybe I'm missing something.

Right so there is a weakness in the internal control structure if a department head, who controls a single private key related to the funds of his department, colludes with the auditor, who holds the master public key.

The idea is that if you give the auditor the watch only wallet, he could conspire with one of the holders of the private keys below it to create the master private key and run away with all the money.

M = master public key
m = master private key

m/ = CEO holds it

M/ = Auditor holds it. With it, they can view all company funds, but not spend.

m/m₁ = Department A head holds it, and can generate further chains with it.
m/m₂ = Department B head holds it, and can generate further chains with it.
m/m₃ = Department C head holds it, and can generate further chains with it.

combining M/ with m/m_x would give me m/ ... so an auditor would have to conspire with one corrupt department head to run away with the company's entire finances.


With the solution provided says that the CEO would make

m₁/
m₂/
m₃/

Then

Dept A:
m₁/m₁
m₂/m₁
m₃/m₁

Dept B:
m₁/m₂
m₂/m₂
m₃/m₂

Dept C:
m₁/m₃
m₂/m₃
m₃/m₃

Each dept using the three public keys generated by those chains to generate deterministic 2of3 chains.

The Auditor would ONLY receive:

M₁/

Then they could check the blockchain for redeemscripts that included
M₁/M₁
M₁/M₂
M₁/M₃

Then they would know how much money each department SPENT without being able to collude to get 2 private keys.

Downside: They could only find SPENT funds, as the redeemscript is only revealed on the blockchain when funds are spent from the multi-sig address.

imo, the best way to do an audit for business would be to use a dual-key Stealth Address, and give the scan_privkey to the auditor... but this is a topic slightly unrelated to BIP32.

You could set up so your company's stealth addresses are generate on a per-department basis, but that all scan_keypairs are generated by a separate BIP32 chain.

Give that master private key to the auditor, as that keypair is only used to generate shared secrets to discover funds, not to spend it.

Great explanation. Finding what was spent is useful for transaction reconciliations, although a lot of what auditors do is reconciliation of balances as well, so not having that ability is definitely a pretty big downside.

I am not too familiar with stealth addresses yet, I am reading up on this.

[JonCD]

What about create 1000 receive and change addresses and not give public key to auditor ?

I suppose you could do this. As long as the accounts all balanced with the keys provided.

The problem with this is the current structure of the client. You can easily obtain the Master Public Key from it without having to input your encryption password. The MPK is required in order to create a watch-only wallet. So the level of safety a watch-only wallet could provide would be completely eliminated, as any wallet you created would become a hot wallet.

In the scenario provided, where single private keys are given to department heads, it would require the Master Public Key be treated with the same level of attention and security as you would a private key. And it's not.. it's a public key. I feel like it is intended to be made public, so you can leverage it for services like watch-only service providers and POS systems. So having to treat it like a private key would mitigate it's usefulness.

[arorts]

I'm in a sort of a crisis.

What's the best way to obtain the private keys of a "Receiving" address that appears in Electrum after creating a seedless/watch-only wallet with a Master Public Key.
In addition to knowing that address I also know the following data generated in an Armory wallet with the same MPK:

 a) Root chain
 b) public key/address
 c) and its private key

 I have a bit of BTC that I had sent to that receiving address and can't take it out  

Please advise!

Thanks,

[jonald_fyookball]

I'm in a sort of a crisis.

What's the best way to obtain the private keys of a "Receiving" address that appears in Electrum after creating a seedless/watch-only wallet with a Master Public Key.
In addition to knowing that address I also know the following data generated in an Armory wallet with the same MPK:

 a) Root chain
 b) public key/address
 c) and its private key

 I have a bit of BTC that I had sent to that receiving address and can't take it out  

Please advise!

Thanks,

can you just create an offline transaction and sign it to move the funds out of that address?

better than to be exporting private keys, as private key+ MPK can expose your whole wallet.  not sure why you're mixing electrum and armory???sounds like a mess.

[arorts]

I'm in a sort of a crisis.

What's the best way to obtain the private keys of a "Receiving" address that appears in Electrum after creating a seedless/watch-only wallet with a Master Public Key.
In addition to knowing that address I also know the following data generated in an Armory wallet with the same MPK:

 a) Root chain
 b) public key/address
 c) and its private key

 I have a bit of BTC that I had sent to that receiving address and can't take it out  

Please advise!

Thanks,

can you just create an offline transaction and sign it to move the funds out of that address?

better than to be exporting private keys, as private key+ MPK can expose your whole wallet.  not sure why you're mixing electrum and armory???sounds like a mess.

Thanks for the feedback.
I did attempt to do that first but Armory simply doesn't understand the transaction format created by Electrum in their latest version and if you ask why Armory, it's  because it has excellent security measures that I absolutely love. Why not Armory in my online wallet, too? I don't like to download a never-ending file that needs my PC to be online all the time. So it was absolute the perfect combination.

Anyway...that was just a dummy account so I don't mind importing the private key to my online wallet as long as I quickly move the btc out of it. However, if I try to import the Armory private key (which belongs to a different address than the one I have my coins at), Electrum shows an import error regardless of whether I provide it in Base58 or the other format. Now why would that happen when I'm using exactly the same MPK (I concatenated Armory's PublicX and PublicY and entered them into Electrum) ?

Is importing any private key of my offline wallet into Electrum the only solution?

Is there any way I could add the Electrum "receiving" address into Armory without asking me its private key? At least I could connect it online to get the blockchain and move out the btc quickly.

[jonald_fyookball]

I'm in a sort of a crisis.

What's the best way to obtain the private keys of a "Receiving" address that appears in Electrum after creating a seedless/watch-only wallet with a Master Public Key.
In addition to knowing that address I also know the following data generated in an Armory wallet with the same MPK:

 a) Root chain
 b) public key/address
 c) and its private key

 I have a bit of BTC that I had sent to that receiving address and can't take it out  

Please advise!

Thanks,

can you just create an offline transaction and sign it to move the funds out of that address?

better than to be exporting private keys, as private key+ MPK can expose your whole wallet.  not sure why you're mixing electrum and armory???sounds like a mess.

Thanks for the feedback.
I did attempt to do that first but Armory simply doesn't understand the transaction format created by Electrum in their latest version and if you ask why Armory, it's  because it has excellent security measures that I absolutely love. Why not Armory in my online wallet, too? I don't like to download a never-ending file that needs my PC to be online all the time. So it was absolute the perfect combination.

Anyway...that was just a dummy account so I don't mind importing the private key to my online wallet as long as I quickly move the btc out of it. However, if I try to import the Armory private key (which belongs to a different address than the one I have my coins at), Electrum shows an import error regardless of whether I provide it in Base58 or the other format. Now why would that happen when I'm using exactly the same MPK (I concatenated Armory's PublicX and PublicY and entered them into Electrum) ?

Is importing any private key of my offline wallet into Electrum the only solution?

Is there any way I could add the Electrum "receiving" address into Armory without asking me its private key? At least I could connect it online to get the blockchain and move out the btc quickly.

You're really mixing 2 different systems, (which sounds like it doesn't really work)
but, it sounds like you really want to be using Armory but still want that
one address out of your electrum wallet.

If so, then I assume you can import the address into Armory.

Go to your offline electrum wallet and you can export the private
key from the address.

Does that work for you?