Topic: Seeing output of 40 BTC when i'm trying to send 1 coin (Read 1785 times)

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

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.

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?

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

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.

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?

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

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

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

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 )

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.

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.

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://bitcointalksearch.org/topic/why-you-cannot-enter-an-arbitrary-seed-in-electrum-153990

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://bitcointalksearch.org/topic/key-stretching-weakness-330672

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

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 ?

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.

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.

Thx burdell.

Why do they hash 100,000 times? 

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.

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