Topic: Reverse Hash (Read 2575 times)

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.

I wouldn't worry about it.

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.

No, that's when all the trouble started.

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

We need to go deeper.

Awesome explanation.

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.

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.

A hash is a one-way function.

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-