Bitcoin Forum
December 14, 2017, 11:47:49 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Isn't the output of SHA256 *slightly* too big to use for a private key?  (Read 4262 times)
chriswilmer
Legendary
*
Offline Offline

Activity: 1008


View Profile WWW
October 09, 2013, 07:02:01 PM
 #1

If the order of the elliptic curve in Bitcoin is some number slightly less than 2^256, then why is it OK to use the SHA256 hash of some input as a private key? My (steadily growing) understanding of ECDSA is that the private key must be some integer between 1 and the order of the curve, which is :

Code:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Sorry if this has been asked 1000 times already...
1513295269
Hero Member
*
Offline Offline

Posts: 1513295269

View Profile Personal Message (Offline)

Ignore
1513295269
Reply with quote  #2

1513295269
Report to moderator
1513295269
Hero Member
*
Offline Offline

Posts: 1513295269

View Profile Personal Message (Offline)

Ignore
1513295269
Reply with quote  #2

1513295269
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
BurtW
Legendary
*
Offline Offline

Activity: 2114

All paid signature campaigns should be banned.


View Profile WWW
October 09, 2013, 07:05:34 PM
 #2

If the output of the SHA256 is greater than n it will just "wrap around" and work.

Although, now that I think about it, if the output of your SHA256 was exactly n that would probably cause a problem.

But then, the probablity of the output of the SHA256 being exactly n is 1 / 2256

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
plaprade
Newbie
*
Offline Offline

Activity: 12



View Profile
October 09, 2013, 07:08:12 PM
 #3

If the order of the elliptic curve in Bitcoin is some number slightly less than 2^256, then why is it OK to use the SHA256 hash of some input as a private key? My (steadily growing) understanding of ECDSA is that the private key must be some integer between 1 and the order of the curve, which is :

Code:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Sorry if this has been asked 1000 times already...

Valid private keys are integers between 1 and n-1. If you get an integer >= n when hashing some secret, then that integer is an invalid private key. It would be a mistake to reduce that integer modulo n as it would introduce a bias towards lower values. The probability of that happening is relatively low however.
plaprade
Newbie
*
Offline Offline

Activity: 12



View Profile
October 09, 2013, 07:14:35 PM
 #4

If the output of the SHA256 is greater than n it will just "wrap around" and work.

Although, now that I think about it, if the output of your SHA256 was exactly n that would probably cause a problem.

But then, the probablity of the output of the SHA256 being exactly n is 1 / 2256

You should not "wrap around" or reduce your integer modulo n.

If your integer is == 0 or or >= n, then you should discard it completely and generate a new private key using a new secret. Otherwise you would be introducing a bias towards lower-valued private keys.
BurtW
Legendary
*
Offline Offline

Activity: 2114

All paid signature campaigns should be banned.


View Profile WWW
October 09, 2013, 07:17:51 PM
 #5

So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
October 09, 2013, 07:24:05 PM
 #6

So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.
chriswilmer
Legendary
*
Offline Offline

Activity: 1008


View Profile WWW
October 09, 2013, 07:37:17 PM
 #7

So, do brainwallet.org or any of the other brainwallet sites reject pass phrases that happen to hash above n?

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.


I realize that this is very improbable... but for my own understanding of how Bitcoin works, I am interested to know what happens if you generate a private key integer that is greater than n...

I actually implemented my own (very inefficient) version of the ECDSA algorithm, so I know that you can pick a private key outside of the range and the algorithm could still function just fine (by wrapping around)... but is this what the default Bitcoin behavior is?

BurtW
Legendary
*
Offline Offline

Activity: 2114

All paid signature campaigns should be banned.


View Profile WWW
October 09, 2013, 08:02:46 PM
 #8

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.

Actually (2256 - n) / 2256 = 1 - n / 2256, which is very close to zero.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560



View Profile WWW
October 10, 2013, 03:43:42 AM
 #9

Quote
but is this what the default Bitcoin behavior is?
What do you mean by "default Bitcoin"?  You mean Bitcoin-QT?  Bitcoin-QT picks a random integer in the appropriate range; it doesn't use SHA-256.  So, it doesn't have this problem.  Brainwallets use SHA-256.  HD wallets use HMAC_SHA512.  Are you referring to any of those in particular?

The correct response, if using SHA-256 to generate a key, is to reject the key and try again.

As pointed out though, it's all moot when writing an application.  When writing a standard you'd want to get details like this right.  But during implementation this isn't important, because the code you write to check for it will never trigger.

chriswilmer
Legendary
*
Offline Offline

Activity: 1008


View Profile WWW
October 10, 2013, 03:48:01 AM
 #10

Quote
but is this what the default Bitcoin behavior is?
What do you mean by "default Bitcoin"?  You mean Bitcoin-QT?  Bitcoin-QT picks a random integer in the appropriate range; it doesn't use SHA-256.  So, it doesn't have this problem.  Brainwallets use SHA-256.  HD wallets use HMAC_SHA512.  Are you referring to any of those in particular?

The correct response, if using SHA-256 to generate a key, is to reject the key and try again.

As pointed out though, it's all moot when writing an application.  When writing a standard you'd want to get details like this right.  But during implementation this isn't important, because the code you write to check for it will never trigger.

Gotcha. Thanks.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 10, 2013, 04:52:04 AM
 #11

You are more likely to introduce a bug in handling the special case than the chance of handler being called even once in the entire lifetime of your application.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2366



View Profile
October 10, 2013, 05:23:29 AM
 #12

You are more likely to introduce a bug in handling the special case than the chance of handler being called even once in the entire lifetime of your application.
It's quite easy to test the retry, simply change the comparison criteria. To do less creates a certificational weakness which reduces the signature security below 128 bits. The level of testing required to adequately address isn't substantial compared to _everything else_ about the process, as there are many other mistakes you could make which would readily leak the private key but leave the software apparently working correctly.

Bitcoin will not be compromised
J35st3r
Full Member
***
Offline Offline

Activity: 196



View Profile
October 12, 2013, 07:50:35 AM
 #13

Sorry if this has been asked 1000 times already...

And its actually pretty close to the subject of the very first question I asked on this forum ...

bitaddress.org lets you input a hexadecimal private key, and trying some different values (including all FFFF and all 0000) I thought I'd found a collision. It actually turned out that all 0000 broke the (bitaddress.org) algorithm and just returned the same key as the previous try. But further playing confirmed that the key values do wrap around at the n value (at least in the sense of generating the same public key value, and hence address, from the private key). This is also the case with the  version of the ECDSA algorithm used by pywallet. As for bitcoin-qt, I'll leave it to the developers to comment as I haven't got my head around that code yet.

Oh, and some advice. Don't use SHA256 for your brainwallet. Far too many crooks generating rainbow tables and sweeping transactions. If you must, then at the very least use some sort of salt to make their job harder.

1Jest66T6Jw1gSVpvYpYLXR6qgnch6QYU1 NumberOfTheBeast ... go on, give it a try Grin
chriswilmer
Legendary
*
Offline Offline

Activity: 1008


View Profile WWW
October 14, 2013, 01:07:54 AM
 #14

Sorry if this has been asked 1000 times already...

And its actually pretty close to the subject of the very first question I asked on this forum ...

bitaddress.org lets you input a hexadecimal private key, and trying some different values (including all FFFF and all 0000) I thought I'd found a collision. It actually turned out that all 0000 broke the (bitaddress.org) algorithm and just returned the same key as the previous try. But further playing confirmed that the key values do wrap around at the n value (at least in the sense of generating the same public key value, and hence address, from the private key). This is also the case with the  version of the ECDSA algorithm used by pywallet. As for bitcoin-qt, I'll leave it to the developers to comment as I haven't got my head around that code yet.

Oh, and some advice. Don't use SHA256 for your brainwallet. Far too many crooks generating rainbow tables and sweeping transactions. If you must, then at the very least use some sort of salt to make their job harder.

Thanks for the reply and the advice.

It's interesting what semi-technical users are interested in. I think there are many users that don't really want to know how ECDSA works, but they do want to know what a "valid" private key is. Not too many places say that it is any integer from 1 to n-1 and specify the n value (and what's worse, I found a few places that mentioned that SHA256 output is a valid key, which is wrong... and probability has nothing to do with it if it leads a user to think that "all FFFF values" typed manually is valid).
b!z
Legendary
*
Offline Offline

Activity: 1568



View Profile
October 15, 2013, 06:51:13 AM
 #15

Sorry if this has been asked 1000 times already...

And its actually pretty close to the subject of the very first question I asked on this forum ...

bitaddress.org lets you input a hexadecimal private key, and trying some different values (including all FFFF and all 0000) I thought I'd found a collision. It actually turned out that all 0000 broke the (bitaddress.org) algorithm and just returned the same key as the previous try. But further playing confirmed that the key values do wrap around at the n value (at least in the sense of generating the same public key value, and hence address, from the private key). This is also the case with the  version of the ECDSA algorithm used by pywallet. As for bitcoin-qt, I'll leave it to the developers to comment as I haven't got my head around that code yet.

Oh, and some advice. Don't use SHA256 for your brainwallet. Far too many crooks generating rainbow tables and sweeping transactions. If you must, then at the very least use some sort of salt to make their job harder.

I did read a very interesting thread before, where it was shown brainwallets with common passphrases like "password" and "love" had transactions sweeped out of them quickly. Using a salt definitely would make the security better.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2366



View Profile
October 15, 2013, 07:05:46 AM
 #16

I did read a very interesting thread before, where it was shown brainwallets with common passphrases like "password" and "love" had transactions sweeped out of them quickly.
"brainwallets" far more elaborate than those (e.g. ones with 60+ character inputs) have been compromised. Humans are not an acceptable source of randomness.

Quote
Using a salt definitely would make the security better.
If the salt is large enough to provide adequate security you can just use the password to encrypt the salt instead, and then you don't have the key management nightmare of a password which can never really be changed.

Bitcoin will not be compromised
Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2016



View Profile WWW
October 15, 2013, 09:47:19 AM
 #17

The probability to hash above n is 1/2^128, so it should be considered practically impossible to achieve.

Actually (2256 - n) / 2256 = 1 - n / 2256, which is very close to zero.
Looks like n ~ 2^256 - 2^128, so this comes up as 1/2^128 as Sergio said.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
October 15, 2013, 04:34:10 PM
 #18

A frustrating anecdote:  the Crypto++ library does not wrap around values greater than N (and it rightfully shouldn't).  Instead, it just segfaults.  I know this because in testing address importing, I frequently use strings like "\xaa"*32 for the private keys.  One day I used "\xff'*32 without realizing I was picking an invalid private key, which led to like a full day of tracking down this devastating "bug" which was really just developer stupidity. 

In practice, if your "random number generator" leads to a private key that is out of range, it's more likely a bad RNG or a malicious result than it is that you just got "unlucky".  With even a mediocre RNG, this isn't an issue.

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
chriswilmer
Legendary
*
Offline Offline

Activity: 1008


View Profile WWW
October 15, 2013, 05:32:34 PM
 #19

A frustrating anecdote:  the Crypto++ library does not wrap around values greater than N (and it rightfully shouldn't).  Instead, it just segfaults.  I know this because in testing address importing, I frequently use strings like "\xaa"*32 for the private keys.  One day I used "\xff'*32 without realizing I was picking an invalid private key, which led to like a full day of tracking down this devastating "bug" which was really just developer stupidity. 

In practice, if your "random number generator" leads to a private key that is out of range, it's more likely a bad RNG or a malicious result than it is that you just got "unlucky".  With even a mediocre RNG, this isn't an issue.

Interesting!
blub
Member
**
Offline Offline

Activity: 88


View Profile
October 15, 2013, 08:55:00 PM
 #20

if the private key must not be 0 how comes the address Armory generates from a all 0 private key has a balance? bug in armory?
https://blockchain.info/de/address/16QaFeudRUt8NYy2yzjm3BMvG4xBbAsBFM

btw, transaction relayed buy 0.0.0.0?

Pages: [1] 2 »  All
  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!