The main question is, even if we manage to reverse a hash to get back an input, how can we know the input is our original input, I think I asked this once before, but the answer wasn't what I expected, if we don't have access to the original input, which is the case in every hash function out there, not having/knowing the input. We can never truly reverse the output to an input knowing whether it's the same original input or not.
This is because of collisions, they exist for a reason and I think it's what makes hash functions secure, for example if you take a sha256 hash of an uncompressed Bitcoin public key, can you guarantee that if we manage to reverse the output, we could get the same uncompressed public key back? You can't, because even if you get an actual collision as the result of your reversal, there is no way of knowing whether the result is our original "unknown" input. Unless you check all possible candidates aka every single possible collision, how many would that be for sha256?
However if you can figure that out by working on more blocks and correctly guess the original input, then we are screwed.
Now I'm a bit confused, our math ph.D talks about energy efficient computing when he mentions "reversible computers", which has something to do with erasing and writing bits of information, are they related?
Topic: Reversible computations - page 2. (Read 354 times)
Let's start from some quotes, because that's what I started with, before creating this topic.
The first thing to note is that I already demonstrated a practical example, to show exactly, how to execute some hash function backwards: https://bitcointalksearch.org/topic/m.60342783
Also, I repeated that again in some other topics, for example here: https://bitcointalksearch.org/topic/m.62397317
So, let's talk more about "mostly reversible components". What they are, how they are defined, how to use them, and so on. Because I started my journey from SHA-1, I will use that in my examples, but a lot of things can be also applied to SHA-256, or other hash functions. The most important thing is the internal construction of a particular hash function: if it is identical for two different hash functions, then guess what: similar attacks can be performed on both, which I also demonstrated by attacking the first 16 rounds of SHA-256, exactly in the same way, as I did it for SHA-1: https://bitcointalksearch.org/topic/hardened-sha-1-vs-weakened-sha-256-how-to-test-them-5467882
The main keyword that helps a lot is called "ARX". Which is an abbreviation of "Addition, Rotation and Xor". Those three operations, combined together, can be used to make new hash functions, and reach certain properties. In case of SHA-1 and SHA-256, they both use that ARX model. Which also means, if you can think about any successful attack for ARX, then you can use that on both SHA-1, and SHA-256.
So, let's dig deeper, and explain, what I promised, step by step. First, we can take Addition. If we work with integers, we all know that addition can be reversed by using subtraction. Those two operations are connected. If you have "a+b=c", then you can also go back, and write it as "a=c-b". Which means, if you start from "a", combine it with "b", and reach "c" as a result, then you can obviously throw away your "b", and claim that your operation is "irreversible". But this is not the case!
So, how to write the same thing in a reversible way? Well, the answer is quite simple: you can just save your "b", instead of throwing it away. Which means, if you write "(a,b)" as your input, instead of just writing "a", and "c" as your output, then it is perfectly reversible operation. Then, you can take subtraction, pass "(c,b)" as your input, and reach "a" as your output.
Also, the best news is that using modulo, for example modulo 2^32, which is used in both SHA-1 and SHA-256, is not going to change anything. Addition modulo 2^32 can be simply reversed by using subtraction modulo 2^32. Other operations are also reversible. If you take Rotations, then left rotation by 30 bits can be reversed, if you just apply left rotation by 2 bits. Because left rotation by 32 bits is just a "do nothing" operation, so you can easily complete it. With Xor, it is even easier, because you can just Xor again by the same value, and you are done.
Quote
Now, how do we build collision resistant and efficient cryptographic hash functions? That is right. We use mostly reversible components or at least components that can be made (mostly) reversible with a moderate computational overhead.
Many people cannot understand it, especially the last sentence about "mostly reversible components". Which means, they repeat like a parrot that "hash functions can be executed only in one direction". They think that hash functions are "irreversible", which means, they treat it like a black box, and they think, that whatever gets in, then never can get out, or get in another direction. This is only partially true, and I will try to show you, why.The first thing to note is that I already demonstrated a practical example, to show exactly, how to execute some hash function backwards: https://bitcointalksearch.org/topic/m.60342783
Also, I repeated that again in some other topics, for example here: https://bitcointalksearch.org/topic/m.62397317
So, let's talk more about "mostly reversible components". What they are, how they are defined, how to use them, and so on. Because I started my journey from SHA-1, I will use that in my examples, but a lot of things can be also applied to SHA-256, or other hash functions. The most important thing is the internal construction of a particular hash function: if it is identical for two different hash functions, then guess what: similar attacks can be performed on both, which I also demonstrated by attacking the first 16 rounds of SHA-256, exactly in the same way, as I did it for SHA-1: https://bitcointalksearch.org/topic/hardened-sha-1-vs-weakened-sha-256-how-to-test-them-5467882
The main keyword that helps a lot is called "ARX". Which is an abbreviation of "Addition, Rotation and Xor". Those three operations, combined together, can be used to make new hash functions, and reach certain properties. In case of SHA-1 and SHA-256, they both use that ARX model. Which also means, if you can think about any successful attack for ARX, then you can use that on both SHA-1, and SHA-256.
So, let's dig deeper, and explain, what I promised, step by step. First, we can take Addition. If we work with integers, we all know that addition can be reversed by using subtraction. Those two operations are connected. If you have "a+b=c", then you can also go back, and write it as "a=c-b". Which means, if you start from "a", combine it with "b", and reach "c" as a result, then you can obviously throw away your "b", and claim that your operation is "irreversible". But this is not the case!
So, how to write the same thing in a reversible way? Well, the answer is quite simple: you can just save your "b", instead of throwing it away. Which means, if you write "(a,b)" as your input, instead of just writing "a", and "c" as your output, then it is perfectly reversible operation. Then, you can take subtraction, pass "(c,b)" as your input, and reach "a" as your output.
Also, the best news is that using modulo, for example modulo 2^32, which is used in both SHA-1 and SHA-256, is not going to change anything. Addition modulo 2^32 can be simply reversed by using subtraction modulo 2^32. Other operations are also reversible. If you take Rotations, then left rotation by 30 bits can be reversed, if you just apply left rotation by 2 bits. Because left rotation by 32 bits is just a "do nothing" operation, so you can easily complete it. With Xor, it is even easier, because you can just Xor again by the same value, and you are done.
Jump to: