Can you Jerry-Rig your Rig?

[bcpokey]

Well fair enough. Grue gave a good link on a general concept to explain why it wouldn't really work, so all is well and good. Especially since SHA-2 is superior to SHA-1.

[the joint]

What's the relationship between the input and the output?  Isn't there some kind of determination of a certain output given by a certain input?  Will a given input always produce the same output?  My apologies, I don't quite get it. 

this isn't elementary algebra

hmmm... i'm not quite sure about that. our maths prof always goes like "as you've known since grade 9 ..." when talking about some shit you never heard before. for people like him it probably is elementary algebra.

Exactly.  I'm good at philosophical thinking, which makes me a quick learner.  And I'm sure coding has its analogues which will help make it easier to understand (for example, language -- syntax, grammar, content).  But the different terminology results in the same type of problem I would have trying to go to Mexico and understand what they're talking about, even if it's about everyday stuff.  Even if this was elementary algebra, no hablo Espanol de techno-nerdo (mas o menos).

[grue]

Yes, cause I'm fucking smart.  And I'm currently playing DDR for cardio which is why I'm postponing wikisearch    

https://secure.wikimedia.org/wikipedia/en/wiki/Sha-1#SHA-1_pseudocode

find the inverse function for me, mmkay?

edit:
whoops, didnt know you posted before me . ignore this post

[the joint]

And I will, but you do realize that a person (me) with virtually no programming experience (except for coding an RPG in Qbasic when I was 12) will have a very hard time understanding that WIKI stuff which makes reference to things I've never heard of?  I'm not sure why you can't figure out a way to tell your computer to get around the problem.  Like, if you know what a given output needs to be, why cant you figure out what the input needs to be?  It is based on an algorithm after all.  Your computer isn't just guessing values 'randomly,' since randomness is another word for causation (caused by randomness).  Why can't you use the algorithm to determine what the relationship is between inputs and outputs such that you can determine why a certain input gives the output that it does?  My guess is that when TiagoTiago says "you can't know what effect a change in the input will have in the output," he really means "it's INFEASIBLE to try to know what effect a change in the input will have in the output."  It's gotta be possible.

With a hash function there is no discernible pattern between the input and the output.  Hash functions were made complicated on purpose.  The only way to find out what the output for any given input is, is to run the function on it and see what comes out.  By design, even a minor change to the input always results in a drastic change to the output.

The algorithm cannot be done in reverse.  Google it, find the implementation, and you'll see why.  Too many steps "throw away" bits of intermediate information along the way - information you would need to do the algorithm in reverse.  This is done repeatedly during each hash, and is intentional.

There isn't a way to get the input from an output - except by guessing inputs by trial and error and calculating the output and seeing if it matches the desired result.  

Finally.  Thanks, bro.  You're a bro.  That's you.

[anty]

There's a fundamental problem when you try to reverse hashing functions:
Due to the bit-shifting you lose information. Information you need to guess when you want to reverse it, creating loads of possibilities.

Bit-shifting work like this: You got the initial bits, e.g.
01010101
now you shift to the right by, lets say 4 bits it fill it with 0s:
00000101
You just lost 4 bits of information. You now have to guess the lost 4 bits to reverse the operation: 2^4=16 possible variations.

It could be one of these:
01011111
01011110
01011101
01011100
01011000
01011001
01011010
01011011
01010000
01010001
01010010
01010011
01010111
01010110
01010101
01010100

But a hashing function doesn't consist of one bit-shifting operation but multiple iterations, based on each other. And of course it's based on more than 8 bits.
In between these shift operations the hashing functions performs some other operations, like multiplications, to get rid of the 0s we just added.

So basically at each operation you want to reverse you have another operation that it's based on which also leads to more guessing and so on.
Work, that you can only verify to be correct after you've checked each guessed version until you hit the right one. So basically you are better off just guessing inputs until you hit the right one.

Disclaimer: I'm basing this on my knowledge of the MD5 hashing algorithm, but SHA-2 uses shift operations, too.

[the joint]

There's a fundamental problem when you try to reverse hashing functions:
Due to the bit-shifting you lose information. Information you need to guess when you want to reverse it, creating loads of possibilities.

Bit-shifting work like this: You got the initial bits, e.g.
01010101
now you shift to the right by, lets say 4 bits it fill it with 0s:
00000101
You just lost 4 bits of information. You now have to guess the lost 4 bits to reverse the operation: 2^4=16 possible variations.

It could be one of these:
01011111
01011110
01011101
01011100
01011000
01011001
01011010
01011011
01010000
01010001
01010010
01010011
01010111
01010110
01010101
01010100

But a hashing function doesn't consist of one bit-shifting operation but multiple iterations, based on each other. And of course it's based on more than 8 bits.
In between these shift operations the hashing functions performs some other operations, like multiplications, to get rid of the 0s we just added.

So basically at each operation you want to reverse you have another operation that it's based on which also leads to more guessing and so on.
Work, that you can only verify to be correct after you've checked each guessed version until you hit the right one. So basically you are better off just guessing inputs until you hit the right one.

Disclaimer: I'm basing this on my knowledge of the MD5 hashing algorithm, but SHA-2 uses shift operations, too.

Also helpful.  Thank you!

[DrHaribo]

Here's how it works:

http://en.wikipedia.org/wiki/Sha-256

There may be a shortcut hidden in there, but noone's found it yet. 

[zard_cz]

I see a bit of confusion here about what is actually going on.

True, the hash-function is not reversible in sense that you can not know for certain what the input was. This is a problem in general if we were to get a document from a signature but in our case we have the majority of the input already and we are modifying only a small part to get difference in the hashes (as hash by itself is the same for the same input, we need to vary a bit of it).

It is theoretically possible to calculate an input for a hash of our choosing, the problem here is that the reverse hash function is so computationally complex at the moment that it is not even remotely feasible to perform it.

This is true for the general state of encryption and if that assumption is broken (which it may, you never know), we will have many more pressing issues to worry about than easy bitcoin generation.


The problem illustration commonly use is to imagine a multiplication of two very very large primes. Forward step is fine, we can multiply very large numbers relatively easily. The problem comes when we want to reverse the operation - at the moment there is no efficient way get these two primes back from the product.


Does that make sense/helps?