bcpokey


July 13, 2011, 11:10:40 PM 

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 SHA2 is superior to SHA1.







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



the joint
Legendary
Offline
Activity: 1806


July 13, 2011, 11:15:53 PM 

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 technonerdo (mas o menos).





the joint
Legendary
Offline
Activity: 1806


July 13, 2011, 11:17:29 PM 

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


July 13, 2011, 11:27:32 PM 

There's a fundamental problem when you try to reverse hashing functions: Due to the bitshifting you lose information. Information you need to guess when you want to reverse it, creating loads of possibilities.
Bitshifting 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 bitshifting 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 SHA2 uses shift operations, too.




the joint
Legendary
Offline
Activity: 1806


July 13, 2011, 11:34:25 PM 

There's a fundamental problem when you try to reverse hashing functions: Due to the bitshifting you lose information. Information you need to guess when you want to reverse it, creating loads of possibilities.
Bitshifting 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 bitshifting 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 SHA2 uses shift operations, too.
Also helpful. Thank you!





zard_cz
Newbie
Offline
Activity: 16


July 18, 2011, 11:28:19 AM 

I see a bit of confusion here about what is actually going on.
True, the hashfunction 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?




