Bitcoin Forum
April 13, 2021, 12:48:01 AM *
News: Latest Bitcoin Core release: 0.21.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Key stretching weakness  (Read 3326 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.
1618274881
Hero Member
*
Offline Offline

Posts: 1618274881

View Profile Personal Message (Offline)

Ignore
1618274881
Reply with quote  #2

1618274881
Report to moderator
1618274881
Hero Member
*
Offline Offline

Posts: 1618274881

View Profile Personal Message (Offline)

Ignore
1618274881
Reply with quote  #2

1618274881
Report to moderator
1618274881
Hero Member
*
Offline Offline

Posts: 1618274881

View Profile Personal Message (Offline)

Ignore
1618274881
Reply with quote  #2

1618274881
Report to moderator
ThomasV
Moderator
Legendary
*
Offline Offline

Activity: 1894
Merit: 1075



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: 1001



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: 1001



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
Last edit: November 12, 2013, 09:34:48 AM by Revalin
 #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:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!