is sha256 for a private key really secure?

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: deepceleron on March 25, 2013, 02:02:53 PM

A function that turns a dataset into a truly random but repeatable signature is called a random oracle. No real function can implement a true random oracle. Here is a paper showing how certain cryptography functions must fail when their reliance on a random oracle is replaced with a hash function: http://eprint.iacr.org/1998/011.pdf

Here is a previous forum conversation on the reduction of entropy by hash functions.

TL;DR: SHA256 may reduce the time required for a brute force attack on ECDSA from the heat death of the universe x 100 to the heat death of the universe x 50.

Makes sense. Thanks for the links, and education.

deepceleron

legendary

Activity: 1512

Merit: 1036

Quote from: DannyHamilton on March 25, 2013, 01:51:54 PM

Quote from: theymos on March 25, 2013, 01:21:50 PM

The output of SHA-256 is less random than random data.

Interesting. Is this something that has been proven, or is it just a common assumption? I had assumed that given random data as an input the output would be equally random.

Quote from: theymos on March 25, 2013, 01:21:50 PM

Also, there are almost certainly fewer than 2³² distinct possible outputs given 32-bit input.

Which appears to be a "Yes" to my question of "Is this statement based on the possibility that the output SHA-256 may not be evenly distributed between 0 and 2²⁵⁶?"

Again, I'm curious, has this been proven, or is it just a common assumption?

A function that turns a dataset into a truly random but repeatable signature is called a random oracle. No real function can implement a true random oracle. Here is a paper showing how certain cryptography functions must fail when their reliance on a random oracle is replaced with a hash function: http://eprint.iacr.org/1998/011.pdf

Here is a previous forum conversation on the reduction of entropy by hash functions.

TL;DR: SHA256 may reduce the time required for a brute force attack on ECDSA from the heat death of the universe x 100 to the heat death of the universe x 50.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: MysteryMiner on March 25, 2013, 01:55:28 PM

To increase paranoia - can You trust the random number generator of the computer in first place?

No. This is why I choose all my private keys by flipping a perfectly balanced coin onto a perfectly flat surface that has been placed perfectly perpendicular to the local force of gravity. I flip the coin exactly 260 times writing down 0 for heads and 1 for tails. I ignore the first 4 digits (in case I somehow subconciously affected the early tosses), and use the resulting 256 bit number as my private key.

Grin

MysteryMiner

legendary

Activity: 1512

Merit: 1049

Death to enemies!

For few thousand USD worth of coins the SHA-256 output is secure enough. I would not worry about it. I would think more about securing the single private key from loss in accident or theft by someone than by it's randomness. I feel confident enough to store any amount of coins in wallet generated by original Satoshi client. I never heard about coins being stolen by guessing private key due to RNG or hash function weakness, all theft happened due to trivial security breach.

To increase paranoia - can You trust the random number generator of the computer in first place?

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: theymos on March 25, 2013, 01:21:50 PM

The output of SHA-256 is less random than random data.

Interesting. Is this something that has been proven, or is it just a common assumption? I had assumed that given random data as an input the output would be equally random.

Quote from: theymos on March 25, 2013, 01:21:50 PM

Also, there are almost certainly fewer than 2³² distinct possible outputs given 32-bit input.

Which appears to be a "Yes" to my question of "Is this statement based on the possibility that the output SHA-256 may not be evenly distributed between 0 and 2²⁵⁶?"

Again, I'm curious, has this been proven, or is it just a common assumption?

theymos

administrator

Activity: 5222

Merit: 13032

Quote from: DannyHamilton on March 25, 2013, 12:56:04 PM

Is this statement based on the possibility that the output SHA-256 may not be evenly distributed?

The output of SHA-256 is less random than random data. Also, there are almost certainly fewer than 2³² distinct possible outputs given 32-bit input.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: theymos on March 25, 2013, 12:07:46 PM

It's probably fine, though it'd be a little more secure to just use the random data as a private key directly.

Is this statement based on the possibility that the output SHA-256 may not be evenly distributed?

theymos

administrator

Activity: 5222

Merit: 13032

It's probably fine, though it'd be a little more secure to just use the random data as a private key directly.

xDan

hero member

Activity: 688

Merit: 500

ヽ( ㅇㅅㅇ)ﾉ ~!!

thanks guys, that's cleared it up Cool

melvster

sr. member

Activity: 350

Merit: 250

SHA3 was released last year, so if SHA256 has an exploit many systems will switch

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: deepceleron on March 25, 2013, 05:58:37 AM

I should caution anyone else that SHA256 hashing doesn't magically make things more secure . . .

Yes. I stated that passing an already sufficiently secure private key through SHA-256 wouldn't make it any more secure than it was to start with, however I failed to point out (as you have) that passing an insufficiently secure seed through SHA-256 also wouldn't make it significantly more secure than it was to start with.

SHA-256 is a reasonable way to take something that already has more than 256 bits of entropy and convert it into a 256 bit number that can potentially be used as a private key.

deepceleron

legendary

Activity: 1512

Merit: 1036

I should caution anyone else that SHA256 hashing doesn't magically make things more secure, one must generate at least as much true randomness and entropy as a 256 bit number can hold, or your Bitcoin address will be weaker than one created by Bitcoin itself. If your bitcoin address is 16ga2uqnF1NqpAuQeeg7sTCAdtDUwDyJav, for example, it won't take a whole bunch of work for someone to find that you used a really stupid private key.

Also, SHA256 can create a value invalid as an ECDSA private key, "Specifically, any 256-bit number between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 is a valid private key."

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: xDan on March 24, 2013, 05:57:35 PM

- snip -
But now I realise maybe it would have been more secure to just generate a purely random private key without involving sha256 algorithm.
- snip -

SHA-256 is used throughout bitcoin (transactionID, merkle root, one step in creating a bitcoin address, mining, etc). If SHA-256 isn't secure, then it really won't matter much what process you use for creating your private key since people will lose faith in bitcoin itself.

In other words, it was probably an unnecessary step, but it shouldn't have increased your risk at all.

grue

legendary

Activity: 2058

Merit: 1452

sha's output is already "random".

xDan

hero member

Activity: 688

Merit: 500

ヽ( ㅇㅅㅇ)ﾉ ~!!

hey

I used bitaddress.org offline to generate a cold storage private key. However, instead of using their key generation, because I wasn't sure I trusted javascript for randomness (maybe I'm wrong there, but anyway..), I used their sha256 brainwallet option, with a very long string generated by the command:

openssl rand -base64 500

plus some random characters typed on the keyboard.

But now I realise maybe it would have been more secure to just generate a purely random private key without involving sha256 algorithm.

Thoughts?

I think the answer is obvious and that this is secure, but was hoping someone with actual knowledge of this sort of thing could confirm it, before I go sending my bitcoins across... I don't really know anything about brute forcing or whether these hash functions would ever be broken.

I already went through the whole process of doing this on a Linux live CD with no net connection and it was a pain, so don't wanna do this again unless it's necessary... Though if there's any hint of insecurity in my process I would.

Topic: is sha256 for a private key really secure? (Read 2854 times)