Bitcoin Forum
September 23, 2018, 03:43:41 AM *
News: ♦♦ New info! Bitcoin Core users absolutely must upgrade to previously-announced 0.16.3 [Torrent]. All Bitcoin users should temporarily trust confirmations slightly less. More info.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Key stretching weakness  (Read 3253 times)
Revalin
Hero Member
*****
Offline Offline

Activity: 728
Merit: 500


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
November 11, 2013, 07:51:19 AM
 #1

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

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1537674221
Hero Member
*
Offline Offline

Posts: 1537674221

View Profile Personal Message (Offline)

Ignore
1537674221
Reply with quote  #2

1537674221
Report to moderator
1537674221
Hero Member
*
Offline Offline

Posts: 1537674221

View Profile Personal Message (Offline)

Ignore
1537674221
Reply with quote  #2

1537674221
Report to moderator
ThomasV
Moderator
Legendary
*
Offline Offline

Activity: 1899
Merit: 1017



View Profile WWW
November 11, 2013, 10:52:13 AM
 #2

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

Electrum: the convenience of a web wallet, without the risks
Revalin
Hero Member
*****
Offline Offline

Activity: 728
Merit: 500


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
November 11, 2013, 06:37:40 PM
 #3

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

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
deepceleron
Legendary
*
Offline Offline

Activity: 1512
Merit: 1000



View Profile WWW
November 11, 2013, 06:52:38 PM
 #4

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
Hero Member
*****
Offline Offline

Activity: 728
Merit: 500


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
November 12, 2013, 04:03:26 AM
 #5

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?

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
deepceleron
Legendary
*
Offline Offline

Activity: 1512
Merit: 1000



View Profile WWW
November 12, 2013, 06:13:44 AM
 #6

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
Hero Member
*****
Offline Offline

Activity: 728
Merit: 500


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
November 12, 2013, 07:39:00 AM
 #7

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?

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!