Key stretching weakness

[Revalin]

I found a small weakness in Electrum's key stretching algorithm: The seed-key is only hashed twice.  This allows rejecting most passphrases before stretching.  It's good for about 8 bits worth of security.

I have sample code here:  https://bitcointalk.org/index.php?topic=85495.msg3546401#msg3546401

[1715316619]

1715316619

[ThomasV]

I found a small weakness in Electrum's key stretching algorithm: The seed-key is only hashed twice.  This allows rejecting most passphrases before stretching.  It's good for about 8 bits worth of security.

I have sample code here:  https://bitcointalk.org/index.php?topic=85495.msg3546401#msg3546401

Electrum's key stretching is not intended to protect the seed against someone having an encrypted seed and bruteforcing AES.
It is there only to make the seed a bit stronger, in case a user uses a custom seed instead of the 128 bits of entropy provided by the software.

more info here: http://stackoverflow.com/questions/11965095/is-it-possible-to-harden-aes-encryption-against-brute-force-attack

[Revalin]

Thanks for the clarification.  It's working as designed, then.  Why not stretch the wallet key, though?

[deepceleron]

I found a small weakness in Electrum's key stretching algorithm: The seed-key is only hashed twice.

You should not be hashing anything multiple rounds that needs to maintain entropy. As 256 bits of possible input do not map to a full 256 bits of output (for every two inputs that have a duplicate hash there must be a non-possible hash), repeated hashing reduces entropy further. "Infinity" rounds of hashing may even converge on a vastly reduced output set, but mathematical proof would be a challenge.

[Revalin]

You should not be hashing anything multiple rounds that needs to maintain entropy.

SHA256 probably isn't a random oracle, but the entropy loss is small.  Typical passphrases have far less than 256 bits of entropy.  Given those criteria, I think key stretching is beneficial.

Let's say you're right, though, and we shouldn't waste entropy by hashing.  Then why is the seed hashed before generating the keys?

[deepceleron]

You should not be hashing anything multiple rounds that needs to maintain entropy.

SHA256 probably isn't a random oracle, but the entropy loss is small.

If it was a random oracle, the entropy loss would be 36%.

I retort, and say why isn't everything done with cryptographically strong random numbers? Because we must let people be stupid?

[Revalin]

I retort, and say why isn't everything done with cryptographically strong random numbers? Because we must let people be stupid?

That's a reasonable opinion, but you're missing my point: Electrum does hash the seed to generate keypairs.  Why is it done for one case but not the other?