Bitcoin Forum

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 :


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

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

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.

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.

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?

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

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.

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.

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

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.

"brainwallets" far more elaborate than those (e.g. ones with 60+ character inputs) have been compromised. Humans are not an acceptable source of randomness.

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.

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

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!

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?

The reason that particular Bitcoin address has a balance is that someone sent it bitcoins. You can send money to any Bitcoin address provided it numerically has a hash160 and valid checksum. You can even send if the address was just made up and there is no private key that can spend the money (https://blockchain.info/address/1BitcoinEaterAddressDontSendf59kuE).

The reason that particular Bitcoin address still has a balance is that it was created with an invalid private key; it cannot be spent with the private key 0x000̅0. If client software uses the raw output of a 256 bit hash or allows any user-input key without checking validity, it is basically allowing people to lose their money. Even if the chance is extremely low, not checking the RNG or brainwallet hash for valid range is irresponsible.

so basically there are ripemd Hashes with  no corresponding private key?
So the probabilty of an addres collision is greater than the often cited 1/2^160?
Is there any information about how many hashes have no corresponding private keys?

On average every Bitcoin address has about 2^(256-160)= 2⁹⁶ possible key pairs.

It would be very interesting to prove or disprove the following:

Every possible valid Bitcoin address has at least one corresponding valid key pair.

If ripemd160 works the way we think it does, every possible address has many, many private keys. The fortunate snag is that it would take longer than the lifetime of the universe to find one, if you started looking with today's technology (no quantum computer, no computronium the size of galaxies, no violations of the laws of thermodynamics, etc.). So what you're really asking is, how many (used?) addresses are there where the private (or public) key is not known? That's merely a reflection of our state of knowledge, and therefore a much less interesting question.

Elliptic curves form a group under point addition. As such they have an additive identity, which is the point at infinity. 0 * G is the identity of this group.

Thanks!  ([re]learn something new every day)

So I corrected my post above and have a new question/comment regarding these posts:  

So if the private key 0 give us the Zero point on the curve Zero = 0 * G then 16QaFeudRUt8NYy2yzjm3BMvG4xBbAsBFM is just the Bitcoin address calculated from the Zero point.

BUT, there are many other valid points that will hash to the same address, therefore:


is not true.  Besides the private key 0 there are many other valid private keys that will produce the address 16QaFeudRUt8NYy2yzjm3BMvG4xBbAsBFM, right?  

Yes, we think. Any such proof would depend on the properties of ripemd160(sha256), which are not themselves proven. But that's a mostly academic point.

I'll point out that I understand EC on real numbers better than on a finite field. I'm not sure exactly how the point at infinity would be represented and how it applies to our situation.

It's just treated as a special case. There is no representation other than "it is the zero point"

It's like if you had an object that could be a number between 1 and 10 or a car. Your programming logic would be:

If a == "a car" { print "there is a car" }
else
 if a < 5 { something }
 if a < 10 {something else}