Topic: Why hash functions are safe? (Read 277 times)

Feel free to make changes if needed, it is not some strictly copyrighted content (you can use it anywhere and do anything with that), and it is not some message from Satoshi, that should be set in stone and preserved as it is. All it describes is just my experience with hash functions, but I think it can be a good introduction for someone who wants to get familiar with that. MediaWiki can show history, so all changes will be visible anyway.

Edit: Many people think that hash functions are one-way, so that it is only possible to start from some Initialization Vector, get some data, and reach some Exit Hash as an output. People often don't expect that hash functions could be executed backwards, and that property can sometimes be useful. It is inevitable, because as long as you have a bijective operation, you can always reverse it. The only "irreversibility" is that we cannot generate data, from Initialization Vector and Exit Hash alone, that's the "one-way" we care about, and that's the only part that makes it truly "one-way".

Here is some example, so people can see in practice, how it is possible to execute hash function backwards (again, my example is based on SHA-1, but you can use the same trick on SHA-256, and some other hash functions). First, we start from IV of all zeroes, and use a message of all zeroes. Everything is zero on our input, let's see how it looks like:
Now, we can clearly see, why k-constants are so important. Without them (or with them set to zero), we would reach all zeroes everywhere. Many people stop there and think that we cannot go backwards. They are wrong, we can try to set the Exit Hash to all zeroes, set the last 16 w-values to zeroes, and go backwards. Let's try it:
We did everything backwards, and we reached some IV. Let's see, how it would look like, if we execute it forward again:
As we can see, for a given message (zeroes everywhere), we've got some IV, that will pass through all of that, without changing our hash. Nice trick, isn't it? Fortunately, it is still far away from breaking anything, but it can be used as a proof that backward computations in hash functions are possible.

It has been done.

You don't have to wait to the end. Modulo is also used inside (for example: all additions are modulo 2^32), but modulo alone is not what makes it irreversible. If you think that adding the initialization vector to the last round is the key, then I can tell you it is not, because if there is only one block, then you know its value, and you can compute backwards the value of the last round (see: meet in the middle attack). For example, if you want to break all 80 rounds, I can tell you it would look like this:
If there would be only modulo 2^32, then it would be quite easy to break it. If you would add rotations into that, then it is harder, but still possible. The key is to use many operations: Addition, Rotation, Xor, also known as ARX model. That's what makes it messy. But this ARX model is used only in some hash functions, like SHA-1 and SHA-2, there are other hash functions using different approaches. In the context of Bitcoin, we have SHA-256, so this ARX model is also used here.

Another important fact is that f-functions can be considered "if-function", "xor-function", and "majority-function", here is why:
During addition, when we execute simple "a+b" operation (modulo 2^32), it can be expressed as a combination of f2 and f3 functions. First, f2 is used to xor both numbers and get the result, then f3 is used to get the number we need to add. So, in fact, our addition can be expressed as a chain of functions, where we first execute f2(0,getBit(a,0),getBit(b,0)), and then we use f3(0,getBit(a,0),getBit(b,0)) to get the first argument for the next operation. It can quickly turn into a complete mess, like this:
Then, it will quickly turn out that getBit(c,31) depends on all other bits from "a" and "b".

Edit:
No problem, feel free to copy my posts and use anywhere you want.

Edit:

Every hash function can be broken. But if you dig deeper, you will quickly see, how many dependencies there are between internal values in hash functions. Then, you will quickly realize that even if breaking single rounds is easy, going further is a nightmare, and everything quickly turns into a spaghetti of dependencies, where every bit can change every other bit, and you are unable to trace that, or even store expressions in more expanded form to reduce it. Many times, there is a combination of things, and then it is hard to reduce it, when you have "rolK(rolN(something&(someValue|anotherValue))+rolM(somethingElse^anotherThing))". So that's how I found an answer to the question "why it is safe" (and also I learned many things about the internal construction of hash functions, but well, I am still not an expert, I only tried to get some confirmation that this model is "safe enough for me").

Nice post. I think that I should preserve it on the Bitcoin Wiki before it gets buried in history.

I would like to repost this verbatim on the Wiki (after I locate my password, which is inside LastPass somewhere), if you approve of that.
Edit: Of course, I will include author info and a link back.

I can't find it in your post, but hash functions attempt to be one-way because they use the modulo operation after completing other operations on the input values.

In the past, hash functions have been broken. Unless you have some proof that a hash function cannot be broken, there is always the risk that a cryptographer (or some other researcher) will break it in the future. 

Many people wonder, why hash functions are safe. How it is possible to achieve one-direction function? In this topic, I will show you, how I tried to attack SHA-1, and what does it mean, in the context of other hash functions.

The first thing we need to know, is the message construction. Imagine a binary string, that consists of zeroes and ones, like this: "10111010000". There are 11 bits, so it is not byte-aligned. It does not matter in the context of hash functions, because they can handle that easily. To create a hashed message, you need to append "1", and then append the right number of zeroes (it depends on the size of the message). In the end, it is needed to have 512-bit blocks, one or more of them. Also, it is needed to have 64 bits to specify the size of the message. That means, our message size can vary from 0 to 2^64-1. So, we have: size(message)+size(one)+size(paddingZeroes)+size(messageSize). And that size should be always divisible by 512 without any remainder. So, to make things fit, we only need to adjust the size of padding zeroes.

To make things simple, here I assume that there is always only one 512-bit block. In real-life scenarios, there are many of them, it depends on the size of the message. But one block is enough to show everything I need.

First, we start by using predefined and fixed initialization vector. In case of SHA-1, it is defined as:
We can clearly see that it is "nothing up my sleeve number", so we can assume that it was not chosen in a special way for hash function creator to make this hash function weaker.

Then, we split our 512-bit block into 32-bit chunks. In my code, I use a simple array of uint32 values, and I use this format to display it:
That means, if our message is empty, we have this block:
As we can see, there is empty message, a single "1", padding zeroes, and the size of the message (in bits) in the last 64 bits (equal to zero). So we have just 0x80000000, followed by 0x00000000. SHA-1 of that is:
If we have some binary string mentioned earlier, "10111010000", it looks like this:
And its SHA-1 is:
It is unusual to hash some binary string that is not byte-aligned, but as we can see, it is perfectly defined in hash functions like SHA-1, and we can do that if needed. Also we can notice that it is all about hashing some particular 512-bit block. If we have a chain of blocks, we can quickly notice, that the last one has the most restrictions, because it has to contain the last chunk of the message (if any), the one bit, some padding zeroes, and the size of the whole message.

So, the whole core of the hash function is just hashing a single chunk. We can think about hashing in this way:
Then, the whole hash function is just about transforming some initialization vector into some result hash. We can remember about that to understand, how it is possible to create length-extension attack, just by taking all previous blocks as a message, append single "1", add padding zeroes, and the new message size. We can quickly notice that to extend any message, it is not even needed to know the content! But let's go back to our single block.

The first step is to expand our message. We have 16 values, 32-bit each, but there are 80 rounds in SHA-1. That means, those values should be extended. The first 16 chunks are the same, but the next ones are created by a simple loop, with xoring and rotations:
That means, we use chunks from w[­0] to w[­15] as a base, and use that to create values from w[­16] to w[­79]. For example:
So, to get our "w-values", we have to just xor some other "w-values", and then rotate left the whole result. The final result depends on our message, for example:
As we can see, even for such simple message, it is a mess. We can skip left rotation, then we will get SHA-0, and just by looking at those w-values, we could quickly see, why this rotation was added.

The next step is transforming the initial hash function, round-by-round, chunk-by-chunk. So, we start from our initialization vector, and apply every chunk to each round, until we will get the final message. If we print that to the screen, we could see something like this:

The 81th round is just my idea, because there are only 80 rounds, but in the last step, the initialization vector is added to the message, and I want to also trace that. In practice, when there is more than one 512-bit block, the result of this "81th round" is passed as an initialization vector to the next 512-bit block.

Breaking all 80 rounds is hard. But to show why, it is needed to dig deeper into the details of how each round is processed. To make things simple, first we start from breaking the first 16 rounds. To do that, we can start by understanding, how the first round is calculated.
It is easy to notice that many values are repeated. The reason is that the new a-value is a combination of all previous chunks, the c-value is just the previous b-value, that is rotated left by 30 bits (or rotate right by 2 bits, to make things easier, I only use left rotations), and all other values are just passed into the next position. By digging deeper into a-value, we can see this:
So far, we know a[­i], we can rotate it to the left by 5 bits, we know e[­i], we know w[­i]. Our f-value is just a function that takes (b,c,d) values, and return some result out of it. There are three f-functions, f1, f2, and f3. In SHA-1, our f-functions are strictly connected with our k-values. They are changed every 20 rounds.
Using exactly those k-values is very important. They are square roots of some small numbers, we can calculate for example (5a827998^2,5a827999^2,5a82799a^2), and see what would happen. These constants are needed, because without them, if the initial hash is zero, and the message is zero, the result would be also zero, and that could make the whole hash function very weak. So, as we now know, how our a-value is calculated, we can try to just calculate it for the first round, maybe we will notice something interesting.
As we can see, our a[­1] can be simply expressed as a constant value, added into w[­0]. But it is so simple only in the first stage. We can try to form similar equations for later rounds, and we will quickly see, that our a[­15] depends on all values from w[­0] to w[­15], and we cannot reduce it that easily.

However, breaking the first 16 rounds is easy, because if we can set our block to any values we want (that is true if our hashed block is not the last one), then we can set our w-values to anything we want. So, let's try to reach all zeroes, just by putting the right values in the right places:
Let's check the first 17 rounds:
Nice result, isn't it? That's why if we reduce our hash function to only the first 16 rounds, we can attack in many ways, and get any hashes we want. It can be useful if we wonder "what happens if this hash function will be no longer preimage-resistant". We can just modify the source code, and replace some secure hash function with the same hash function, but with reduced number of rounds. That will make it very weak, and then we can attack in many ways, and test "what could happen".

When it comes to breaking next rounds, it gets harder and harder. To break 17th round, we need to set w[­16] into some value we want. But we cannot control w[­16] directly. We have values from w[­0] to w[­15] in our message, all other values are derived from that. So, we have to dig deeper and see, how w[­16] is constructed:
Nice, we have only four dependencies. So, our break17 attack is not that hard to mount. For example, let's try to change w[­13] into something else:
Then we have this:
Now we can notice, how things are connected. Fortunately, we can fix it by changing w[­14] and w[­15] accordingly.
It is better, but there is another problem:
As we can see, our hash after 16 rounds is almost right. Almost, because our attack to w[­13] changed also c[­16] to be 0x40000000, instead of 0x00000000. We can fix it by changing w[­12].
It's better, but we are still not there:
So, now 0x40000000 moved into d[­16]. Maybe we could move it further, outside e[­16], just by using some lower value? Let's try w[­10].
Now we got it:
As we can see, we have successful collision in 16th round, zero hash reached again. One important thing is that 17th round is left unchanged, no matter what value we will put diagonally:
That means we reached collisions on 17th round, with preimage on 16th round. This property can be useful later, but for now, to reach break17, we can try to modify e[­16]. So, our preimage would look like this:
First, we can start with w[­16], because we cannot control it directly, we have only values from w[­0] to w[­15] in our message.
Then, we can notice that:
Almost there, because then we can use rol2 on that, and we will get all values:
So, our rounds should look like this:
Then, we can derive w-values from that:
Let's check the first 18 rounds:
We got it. But then, doing break18, break19, etc. is getting harder and harder, because we have more and more dependencies. But there is more: if we want to explore some properties, we can try to reduce the number of bits. By looking at SHA-256 and SHA-512, we can clearly see that they are similar. Also, SHA-256 construction is quite similar to SHA-1, if it comes to attacks described above.

When it comes to reduction, we can for example use SHA-1 reduced from 160 to 80 bits, simply by using 16-bit values. If we use 8-bit values, it becomes really convenient, because then we have 40-bit hash function, and we can explore some properties further. Then, we can try to bruteforce some bits, and see that for some rounds, there are no preimages. When it comes to executing hash function twice, we can then see, how it works, and that no 40-bit value hashed again can give us some desired value in some rounds.