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

chriswilmer

legendary

Activity: 1008

Merit: 1000

Quote from: Meni Rosenfeld on October 16, 2013, 05:44:49 PM

Quote from: BurtW on October 16, 2013, 05:12:14 PM

Quote from: Meni Rosenfeld on October 16, 2013, 04:36:24 PM

Quote from: BurtW on October 16, 2013, 03:36:17 PM

Within the context of Pub = Priv * G, what is Pub if Priv is zero? It looks to be undefined to me.

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:

Quote from: blub on October 15, 2013, 03:55:00 PM

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

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.

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}

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

Quote from: BurtW on October 16, 2013, 05:12:14 PM

Quote from: Meni Rosenfeld on October 16, 2013, 04:36:24 PM

Quote from: BurtW on October 16, 2013, 03:36:17 PM

Within the context of Pub = Priv * G, what is Pub if Priv is zero? It looks to be undefined to me.

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:

Quote from: blub on October 15, 2013, 03:55:00 PM

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

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.

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.

maaku

legendary

Activity: 905

Merit: 1012

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.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: Meni Rosenfeld on October 16, 2013, 04:36:24 PM

Quote from: BurtW on October 16, 2013, 03:36:17 PM

Within the context of Pub = Priv * G, what is Pub if Priv is zero? It looks to be undefined to me.

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:

Quote from: blub on October 15, 2013, 03:55:00 PM

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

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:

Quote from: blub on October 16, 2013, 03:31:46 PM

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?

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

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

Quote from: BurtW on October 16, 2013, 03:36:17 PM

Within the context of Pub = Priv * G, what is Pub if Priv is zero? It looks to be undefined to me.

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.

maaku

legendary

Activity: 905

Merit: 1012

Quote from: blub on October 16, 2013, 03:31:46 PM

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?

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.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

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.

blub

member

Activity: 88

Merit: 10

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?

deepceleron

legendary

Activity: 1512

Merit: 1036

Quote from: blub on October 15, 2013, 03:55:00 PM

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

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.

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.

blub

member

Activity: 88

Merit: 10

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?

chriswilmer

legendary

Activity: 1008

Merit: 1000

Quote from: etotheipi on October 15, 2013, 11:34:10 AM

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!

etotheipi

legendary

Activity: 1428

Merit: 1093

Core Armory Developer

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.

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

Quote from: BurtW on October 09, 2013, 03:02:46 PM

Quote from: Sergio_Demian_Lerner on October 09, 2013, 02:24:05 PM

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.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: b!z on October 15, 2013, 01:51:13 AM

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.

b!z

legendary

Activity: 1582

Merit: 1010

Quote from: J35st3r on October 12, 2013, 02:50:35 AM

Quote from: chriswilmer on October 09, 2013, 02:02:01 PM

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.

chriswilmer

legendary

Activity: 1008

Merit: 1000

Quote from: J35st3r on October 12, 2013, 02:50:35 AM

Quote from: chriswilmer on October 09, 2013, 02:02:01 PM

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

J35st3r

full member

Activity: 196

Merit: 100

Quote from: chriswilmer on October 09, 2013, 02:02:01 PM

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.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: maaku on October 09, 2013, 11:52:04 PM

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.

maaku

legendary

Activity: 905

Merit: 1012

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.

chriswilmer

legendary

Activity: 1008

Merit: 1000

Quote from: fpgaminer on October 09, 2013, 10:43:42 PM

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.

Topic: Isn't the output of SHA256 *slightly* too big to use for a private key? (Read 4437 times)

Topic: Isn't the output of SHA256 slightly too big to use for a private key? (Read 4437 times)