Isn't the output of SHA256 *slightly* too big to use for a private key?

[chriswilmer]

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

[1714000169]

1714000169

[1714000169]

1714000169

[1714000169]

1714000169

[1714000169]

1714000169

[BurtW]

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 / 2²⁵⁶. 

[plaprade]

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]

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 / 2²⁵⁶. 

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]

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

[Sergio_Demian_Lerner]

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]

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]

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

Actually (2²⁵⁶ - n) / 2²⁵⁶ = 1 - n / 2²⁵⁶, which is very close to zero.

[fpgaminer]

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]

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]

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.

[gmaxwell]

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.

[J35st3r]

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.

[chriswilmer]

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]

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]

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.

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.

[Meni Rosenfeld]

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

Actually (2²⁵⁶ - n) / 2²⁵⁶ = 1 - n / 2²⁵⁶, which is very close to zero.

Looks like n ~ 2^256 - 2^128, so this comes up as 1/2^128 as Sergio said.

[etotheipi]

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.

[chriswilmer]

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]

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?