Bitcoin Forum
June 21, 2018, 10:47:43 AM
 News: Latest stable version of Bitcoin Core: 0.16.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Reverse Hash  (Read 2438 times)
Peter Lambert
Hero Member

Offline

Activity: 756
Merit: 500

It's all fun and games until somebody loses an eye

 May 25, 2011, 12:38:06 AM

I admit I know little about cryptography, could somebody help me out with this question?

Why can't you just do a reverse hash to solve the next block?

If you pick a number below the difficulty, take the other inputs that go into the mining function, and run it backwards, wouldn't you get a random number, then report that as the solution for the next block and claim the reward?

I feel like I am either missing something big, or this would be an easy way to exploit the system?

Thanks for the help!

-Peter-

Use CoinBR to trade bitcoin stocks: CoinBR.com

The best place for betting with bitcoin: BitBet.us
1529578063
Hero Member

Offline

Posts: 1529578063

Ignore
 1529578063

1529578063
 Report to moderator
The World's Betting Exchange

Bet with play money. Win real Bitcoin. 5BTC Prize Fund for World Cup 2018.

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1529578063
Hero Member

Offline

Posts: 1529578063

Ignore
 1529578063

1529578063
 Report to moderator
1529578063
Hero Member

Offline

Posts: 1529578063

Ignore
 1529578063

1529578063
 Report to moderator
arturh
Member

Offline

Activity: 60
Merit: 10

 May 25, 2011, 12:41:47 AM

A hash is a one-way function.
Sukrim
Legendary

Offline

Activity: 2380
Merit: 1002

 May 25, 2011, 12:51:08 AM

Think of a hash as a much more complicated sum of digits:

1337 --> 14

I now can easily verify that 1+3+3+7 = 14

However, I can NOT say if this 14 is derived from 95, 1733, 842, 7700000 or any other number that happens to have a sum of digits equaling 14.

https://www.coinlend.org <-- automated lending at various exchanges. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
w128
Newbie

Offline

Activity: 14
Merit: 0

 May 25, 2011, 01:09:25 AM

Think of a hash as a much more complicated sum of digits:

1337 --> 14

I now can easily verify that 1+3+3+7 = 14

However, I can NOT say if this 14 is derived from 95, 1733, 842, 7700000 or any other number that happens to have a sum of digits equaling 14.

Awesome explanation.
mewantsbitcoins
Full Member

Offline

Activity: 126
Merit: 100

 May 25, 2011, 01:11:50 AM

Oh, man there's much easier way to think about it.

You stick your penis into a woman - nine months later out comes a baby. You say to a woman - come on, have some mercy, take this evil creature and give me back my semen. But the woman says NO!

Same way with computers. You stick a string into a GPU/CPU and out comes a hash. You please and beg - Oh, merciful and all powerful GPU/CPU, take this hash and give me my data back, but GPU/CPU says NO!

So be careful when you stick things into other things
Alex Beckenham
Full Member

Offline

Activity: 154
Merit: 100

 May 25, 2011, 01:13:50 AM

Oh, man there's much easier way to think about it.

You stick your penis into a woman - nine months later out comes a baby. You say to a woman - come on, have some mercy, take this evil creature and give me back my semen. But the woman says NO!

Same way with computers. You stick a string into a GPU/CPU and out comes a hash. You please and beg - Oh, merciful and all powerful GPU/CPU, take this hash and give me my data back, but GPU/CPU says NO!

So be careful when you stick things into other things

Awesome explanation.

drmoo
Newbie

Offline

Activity: 13
Merit: 0

 May 25, 2011, 01:19:52 AM

We need to go deeper.
Steve
Hero Member

Offline

Activity: 868
Merit: 1000

 May 25, 2011, 01:20:07 AM

Think of a hash as a much more complicated sum of digits:

1337 --> 14

I now can easily verify that 1+3+3+7 = 14

However, I can NOT say if this 14 is derived from 95, 1733, 842, 7700000 or any other number that happens to have a sum of digits equaling 14.

Adding to this, an important property of secure hashes is that it's very difficult (nearly impossible) to derive the data that produced the hash from the hash (or to find other data that produces the same hash...a collision).  In this simple example it is trivial to find sets of numbers that sum to 14.  Also, due to the high improbability of finding a collision, one can use a hash to verify content (i.e. if you ask someone for the data corresponding with hash "14", and they delivered 1337, you can be confident that 1337 is in fact the correct data...of course, with this trivial example, you can't because collisions are plentiful...so you can't really be sure in this example that 1337 is the correct data or if it's really 95 or 1733 or something else that would sum up to 14).

(gasteve on IRC) Does your website accept cash? https://bitpay.com
Sawzall
Full Member

Offline

Activity: 140
Merit: 100

 May 25, 2011, 01:23:41 AM

We need to go deeper.
No, that's when all the trouble started.
againey
Newbie

Offline

Activity: 9
Merit: 0

 May 25, 2011, 03:52:20 AM

Think of a hash as a much more complicated sum of digits:

1337 --> 14

I now can easily verify that 1+3+3+7 = 14

However, I can NOT say if this 14 is derived from 95, 1733, 842, 7700000 or any other number that happens to have a sum of digits equaling 14.

That's entirely true, and is relevant for most applications of cryptographic hash functions.  But in this case, we have that nonce value that is completely open to us, and we're only trying to find any one hash among a huge number of acceptable hashes.

For a simplistic example, consider our hash function to be the sum of digits as above, but keep taking the sum of digits until only one digit remains.  1337 -> 14 -> 5, 983542 -> 31 -> 4, 183954235098345 -> 69 -> 15 -> 6.

Now say that we want to get a hash that is 9; that is, we're setting the difficulty such that only roughly one in nine streams of digits will be accepted.  We then take some content that is known, add a couple of nonce digits to the beginning of the known stream of digits, and generate the hash to find out if it is accepted.  That's the essence of the current process used by miners.  For the given hash function and difficulty, we'd need to perform on average 9 hashes with random 2-digit nonces before finding a match.

But Peter proposes the following:  Let's assume that our hash is 9, since in the end that's what it'll have to be anyway.  Now say we're trying to hash ??8645, where ?? are the two nonce digits.  We can reverse this in the following manner:  We know that the given digits add up to 23, which will then add up to 5.  We can then see that we're 4 short, so if our two nonce digits contributed four more, we'd have our hash.  So we choose our nonce to be 13 and end up with 138645 -> 27 -> 9.  We've found a nonce that produces an acceptable hash in roughly the time it takes to do just a single hash, rather than having to do on average 9 hashes.  (Even in this case it's probably more complicated than the specific example I picked, but I'm still pretty sure it would be proportional to the time complexity of a single hash, and would be independent of the difficulty intended by limiting the range of acceptable hashes.)

Given the much higher rarities of randomly finding an acceptable hash in the current Bitcoin mining environment, if that could be reduced down to anything even remotely close to being proportional to the time it takes to perform a single hash, that would completely ruin the whole point.  But offhand I don't know if it's actually feasible, given modern day cryptographically strong hash algorithms, to take an assumed hash and a mostly known stream of content, and then reverse the process to find out what the small unknown bit of content needs to be to "solve the equation".  Seeing as how the process is substantially different from what is typically considered within the field of cryptography however, I wouldn't be surprised if the Bitcoin situation provides significantly weaker security than is currently presumed.
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 May 25, 2011, 04:24:49 AM

If you change any single bit of the input to a modern cryptographic hash, nearly 50% of the output bits (on average) will change.  This is by design, and also the hashing systems that lack this property are in the trash bin of history.

If a reverse attack on SHA is found, we can switch to a new hash.  If a general reverse attack is found, all of cryptography is screwed.