Bitcoin Forum

hey folks...

So i'm trying to send 1 BTC from a cold wallet following these instructions:


    [Online PC] Go to the send tab and make a transaction. Instead of sending it, Electrum will detect a seedless wallet and query for a location to save the transaction. Select your USB-Key.
    [Offline PC] Go to Settings -> Import/Export -> "Load raw transaction". Select your transaction from the USB-Key. It will detect it's not signed and will prompt you to do so now. Fill in your password and sign the    transaction. Save the new, signed, transaction to your USB-Key.
    [Online PC] Go to Settings -> Import/Export -> "Load raw transaction". Select the signed transaction and it will ask you if you want to broadcast it.


However, when I create the unsigned transaction for 1 BTC, I see 2 outputs,
one for 1 BTC, and another for 40.003 BTC.  Why is this happening?

I didnt send it yet, i dont want to send 40 coins!

Bitcoin works on the concept of inputs and output.  The inputs of a tx reference the unspent outputs of a prior tx.  You can't spend "part" of an output.  

So if you have an unspent output (of a previous tx) with a value of 41.003 BTC then that becomes your input.  If you want to "spend" 1 BTC, the only way to do so is to create a tx which has two ouputs, 1 BTC to the receiver and 40.003 BTC back to yourself.  The address of the 40.003 BTC output should be an address in your wallet.

To add to the above post:

The second address where the 40 BTC is going should be under the Change tab on your Receive menu.

Click the arrow next to "Change" and the first or second address that shows up should be the address the 40 BTC is trying to be sent to.

Edit: Here's my way of thinking about it.

Every transaction you receive is a single bill. Like in USD we have $1, $5, $10, $20... etc.. but in Bitcoin, your "bills" are the transactions you receive.

ie. if you receive 123 BTC in one transaction to your one address... you should have a sinlge 123BTC bill to use.

When you try to spend ANY money at all... you only have a 123BTC bill, so you have to make change. In America someone would give you back 4 $1 bills if you bought a 1 dollar thing with a $5 bill.

In bitcoin you have to send YOURSELF the change. so your client makes 2 outputs. 1 to your sender for the amount, and 1 to yourself for the remainder (change) minus the miner fee you chose.

thanks guys... yeah i was aware of the input and output idea, but did NOT see the address on the my
wallet, so i was quite weirded out...

expanding the change tab reveals that address now.

THANK YOU BOTH!

follow-up question:

The several different receiving addresses in the wallet all have their own inputs and outputs right?
Will Electrum let me choose which address I want to create the transaction from?

Although I can choose which address to receive to, I don't see how to choose which one I
want to send from.  What am I missing?

Right click on any address on the receive tab.

Click freeze

Now Electrum will not use any outputs on that address.

This can be utilized to control which outputs get used.

As far as using multiple inputs on the same address, electrum is currently first in first out.

You use them in the order you got them... not the most efficient way, but hopefully the logic will be fixed down the line.

thanks again.  very interesting.  slowly but surely mastering electrum.
 

It's nowhere close to 41 BTC, but my precious BTCs are in an offline electrum wallet. It's great to be able to send funds to it and manage public keys without having to worry about my seed being stolen.

Good luck!

ya its very cool.

i still would like to more about this: https://bitcointalk.org/index.php?topic=516834.0

perhaps i would need to dive into the source code to better understand how the
electrum seed relates to the private keys. 

as an early adopter, I also think I should review the source code as well to ensure
backdoors aren't placed into electrum (someone's gotta do that right?)

Another way to send from a certain address or addresses is to right click and "send from".  You can do this by selecting multiple addresses at once and using "send from".

Trust me, there are a lot of people who have verified the current build, and are religiously watching each commit to the master git.

Also, if you open up /lib/account.py and start following from the module "get_private_key" under the class OldAccount, you'll find out how it works.

Oh, and to get your mnemonic seed to the actual hexadecimal seed (the one used for "get_private_key") you use the mndecode module in /lib/mnemonic.py

btw, there's a step that involves SHA256 hashing 100,000 times in a row (using a for loop) sooooo trying to verify it by hand is going to take a while. If you want to write your own script to verify it though, the above modules should point you in the right direction.

Thx burdell.

Why do they hash 100,000 times? 

Because the person who made it decided it should be that way.

I didn't make it, so I don't know... but I do know that BIP32 (the official Bitcoin Improvement Protocol that was created based on Electrum's method) hashes 200,000 times... so I guess they thought 100,000 wasn't enough?

Maybe Thomas could ring in with the reason why it must be 100,000 times and not 2 times or 100 times.

It is called key stretching. 
https://en.wikipedia.org/wiki/Key_stretching


More iterations is better, it raises the cost of a brute force attack.  The Bitcoin-Core wallet does something similar to provide brute force resistance for wallet passphrase.

So key stretching is part of bitcoin core....but then, why would it need to be part of electrum if an attacker was trying to brute force keys directly on the block chain?  Or was developed first in electrum ?

In the past you could enter your own seed to create an electrum wallet. Since human beings are not very good at producing random numbers these human generated seeds afforded poor security. To alleviate that they introduced key stretching. There is a whole sticky about this here:

https://bitcointalk.org/index.php?topic=153990.0

Now most people are  using the computer generated seed that electrum creates on startup. That has 128 bits of entropy. But the key stretching is still applied to it. There is this thread where people are saying that key stretching reduces entropy:

https://bitcointalk.org/index.php?topic=330672.0

Is the above correct? Is it a bad idea to use key stretching on computer generated random seeds?

Wait, so simply brute forcing a priv key uses 256 bits, or 160 bits?

Interesting thread the one you just posted.  If true, we shouldn't be doing this way, but what is difference between key stretching electrum seed vs key stretching in bitcoin core.  Both would lose entropy and have the convergence problem.

256 bit ECDSA keys have 128 bits of key strength.  It requires 2^128 operations to brute force the privKey from the PubKey.  This assumes the PubKey is known.  If it isn't the an attacker would need to attempt a hash collision against the PubKeyHash, looking for any privKey which produces the same PubKeyHash.  That would require on average 2^160 operations.  Yes the PubKeyHash is oversized.  Bitcoin would have similar security (when PubKey is known) is the PubKeyHash was only 128 bits (i.e. RIPEMD-128 or XOR the left and right 128 bit sequence of SHA-256).

As for key stretching reducing entropy is depends on how it is implemented.  I haven't looked at Electrum source code but PBKDF2 was created to remove the entropy loss associated with PBKDF1.

But each of those 2^128 (or 2^160) "operations" would actually be 100,000 rounds of hashing if I understand correctly.

The electrum code appears to be doing a loop on the hash , but each iteration it is concatenating the output with the original seed. I don't know if this pbkdf2 (doesn't sound like it) but maybe that solves any entropy loss issue.  Most probably it would, because on the last iteration you would still have all the entropy of the original seed, but you still have all those loops,to get through. Clever.



    @classmethod
    def stretch_key(self,seed):
        oldseed = seed
        for i in range(100000):
            seed = hashlib.sha256(seed + oldseed).digest()
        return string_to_number( seed )

It isn't standard PBKDF2 but it is injecting entropy back into the process.  Generally I think it is a good idea to stick with standards but it doesn't appear to be broken.  IIRC it is a good idea to also include the iteration count as part of the input for each round of the hash function, although I can't remember the rationale for that decision.


Yup that is the whole point.  Imagine you have a GPU rig (8 GPUs) which can hash 1 billion passwords per second. Using a key derivation function with 100,000 iterations chops that raw throughput to 10K passwords attempts per second.  Another way to look at, is assume the attacker has sufficient hardware to brute force your single hashed password in 1 minute.  The same password requiring 100K iterations would take take 100,000 minutes (or ~70 days).

Usually in a key derivative function salt is also used to prevent a pre-computation attack, but as I understand it the seed in electrum is purely random thus not subject a a precomputation attack.  If starting from a non-random source (i.e. Bitcoin QT wallet passphrase) a random salt should be used (it can be stored plaintext in the wallet).

I get it... However, bitcoin already has key stretching.  Why stretch again in electrum (unless we are simply trying increase the 12 word seed entropy from 128 bits up to 160)?

edit: actually i dont think it would increase the entropy, just add more stretching, since the seed has less entropy than a 160 bit "normal" priv key

hmmm......  ??? lol

I'd just like to add that from 2.0 they'll be using PBKDF2. It's a standard that lots of wallets will support:

https://github.com/spesmilo/electrum/blob/41f9da1559f838fd191eb936359b911635010d2a/lib/bitcoin.py#L67

https://github.com/trezor/python-mnemonic/blob/master/mnemonic/mnemonic.py#L103

Really? 

How the heck is that supposed to work if I'm trying to import my seed into a new version and its hashed differently?

It supports old seeds. See the oldwallet class.


Electrum does key stretching because it allows you to enter your own seed which may be a human generated one. Because it has no way of knowing whether a seed is human generated or computer generated is stretches them all.

I am not sure what you mean by bitcoin does key stretching. If you are referring to bitcoin core software then it does key stretching for the wallet passphrase. That's all. It has nothing to do with the public blockchain or other wallets like electrum.

I was told this,...gotcha....thx for clarifying.

Ok, thanks all for information.  I'm more than satisfied that I
understand how electrum handles the keys and that it's
secure.

Bitcoin the protocol does not use key stretching.

Bitcoin-core "the client" uses key stretching to harden to the WALLET DECRYPTION PASSPHRASE against brute force attack.  Nothing more.   Electrum doesn't copy that code from bitcoin-core wallet so it isn't key stretching "again".



Private keys only have 128 bit key strength.  Not 160 bit and not 256 bit.

I see.  So then, it would be even harder to brute force an private key from the electrum seed dictionary because of the key stretching versus trying to do it "directly".

Correct?

If the seed is random then it would be more difficult to brute force the seed.  If the seed is not random then it would depend on what entropy the seed has.   100K iterations is ~2^16 so the stretching adds 16 bits of key strength.  Then again if the seed is "password123" then stretching or not the resulting entropy is too low to be considered secure.

In either case brute forcing the seed would allow you to gain access to all the private keys, where as brute forcing a single private key only gives you access to that key.  It is generally speaking academic if the seed has sufficient entropy because keys with 128 bit key strength are considered beyond brute force anyways.

Key stretching is used to provide brute force resistance to keys that otherwise would have less than 128 bit key strength.  As an example consider a passphrase which has 74 bits of entropy.  It may be possible to brute force that.  Through key hardening you can add 16 bits of key strength making it the equivalent of a 90 bit random symmetric key which today is beyond brute force for all but maybe the largest nation states.   It turns a moderately weak key int one that is nearly unbreakable.   On the other hand "password123" has 0 bits of entropy (it is on lists of know passwords) and thus even with key hardening would be quickly compromised.

Very good.

Yes, I was referring to the 1626 word dictionary  , 1626^12 is slightly
more than 128 bits of entropy.

Mostly academic, as you say.

It might be conceivable that out of dumb luck, you get the first
2 words alphabetically on the list (a 1 in 2.6 million chance), and if a brute-force
attack was done starting in alphabetical order,
you would then only have a 1626^10 key strength, which is about
107 bits of entry.

We all know how people here like to argue about how fast computers
could be in the future, etc... 107 bits starts to creep down a bit (no pun intended),
so its nice to know that the key stretching puts it right back squarely into
unfeasible to brute-force territory.

And there's no need to regenerate your electrum seed simply because the
first word starts with an "A".

I think it is good to understand these things to give people confidence in Electrum.
Helps me sleep at night anyway :)