NotATether: Created page with "This document was originally posted at [https://bitcointalk.org/index.php?topic=5402178.0 Why hash functions are safe?] on Bitcointalk and is reposted here for preservation. N..."

2022-06-12T15:32:08Z

Created page with "This document was originally posted at [https://bitcointalk.org/index.php?topic=5402178.0 Why hash functions are safe?] on Bitcointalk and is reposted here for preservation. N..."

New page

This document was originally posted at [https://bitcointalk.org/index.php?topic=5402178.0 Why hash functions are safe?] on Bitcointalk and is reposted here for preservation. No changes have been made to the original except for superficial formatting adjustments.

--------------

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:

<code>67452301 efcdab89 98badcfe 10325476 c3d2e1f0</code>

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:

<code>w[ 0] w[ 1] w[ 2] w[ 3] 
w[ 4] w[ 5] w[ 6] w[ 7] 
w[ 8] w[ 9] w[10] w[11] 
w[12] w[13] w[14] w[15] </code>

That means, if our message is empty, we have this block:

<code>80000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 </code>

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:

<code>da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709</code>

If we have some binary string mentioned earlier, "10111010000", it looks like this:

<code>ba100000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 0000000b </code>

And its SHA-1 is:

<code>be5abcb4 16303cb7 3459305d e9ef9055 16be628d</code>

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:

<code>initialization vector: 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 
message: 80000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
result hash: da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709 </code>

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:

<code>w[i]=rol(w[i-16]^w[i-14]^w[i-8]^w[i-3])</code>

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:

<code>w[16]=rol(w[ 0]^w[ 2]^w[ 8]^w[13]) 
w[17]=rol(w[ 1]^w[ 3]^w[ 9]^w[14]) 
w[18]=rol(w[ 2]^w[ 4]^w[10]^w[15]) 
... 
w[77]=rol(w[61]^w[63]^w[69]^w[74]) 
w[78]=rol(w[62]^w[64]^w[70]^w[75]) 
w[79]=rol(w[63]^w[65]^w[71]^w[76]) </code>

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:

<code>ba100000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 0000000b 
74200001 00000000 00000016 e8400002 
00000000 0000002c d0800005 00000016 
e840005a a100000b 00000000 000000b0 
42000017 0000004e 49400169 84000014 
38c00007 000002c0 08000005 a1000133 
250005a5 100000e2 a100000b 00000b58 
8100017f 000004e0 94001694 40000164 
5c800076 00002c58 21000003 b10013f5 
63805a4b 00000e21 10000182 2500b5fd 
b10017f3 00004cc0 48016914 0000177c 
ed0002c0 1002c562 b1000039 10013403 
b905a5c9 0000e6a8 35000ebe 100b5ec2 
3d017f43 0004e000 00169114 100164fa 
8000765c 002c5800 00000321 0013f501 
c25a4b74 000e2480 100183ca 84b5fa4b 
1817f356 004cc740 1969112f 1017712a </code>

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:

<code> i a[i] b[i] c[i] d[i] e[i] 
~------------------------------------------------- 
0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 
1 1fb498b3 67452301 7bf36ae2 98badcfe 10325476 
2 5d43e370 1fb498b3 59d148c0 7bf36ae2 98badcfe 
3 158d2f62 5d43e370 c7ed262c 59d148c0 7bf36ae2 
4 cdecfb5d 158d2f62 1750f8dc c7ed262c 59d148c0 
5 4953565e cdecfb5d 85634bd8 1750f8dc c7ed262c 
6 e44ab766 4953565e 737b3ed7 85634bd8 1750f8dc 
7 c09d7f27 e44ab766 9254d597 737b3ed7 85634bd8 
8 87074800 c09d7f27 b912add9 9254d597 737b3ed7 
9 41376611 87074800 f0275fc9 b912add9 9254d597 
10 cbdbff31 41376611 21c1d200 f0275fc9 b912add9 
11 40166973 cbdbff31 504dd984 21c1d200 f0275fc9 
12 adc0e0ca 40166973 72f6ffcc 504dd984 21c1d200 
13 84c05eb2 adc0e0ca d0059a5c 72f6ffcc 504dd984 
14 1512c8b9 84c05eb2 ab703832 d0059a5c 72f6ffcc 
15 40182905 1512c8b9 a13017ac ab703832 d0059a5c 
16 d8fd6547 40182905 4544b22e a13017ac ab703832 
17 06bf9173 d8fd6547 50060a41 4544b22e a13017ac 
18 28a9520e 06bf9173 f63f5951 50060a41 4544b22e 
19 0b3088dd 28a9520e c1afe45c f63f5951 50060a41 
20 e758e8da 0b3088dd 8a2a5483 c1afe45c f63f5951 
21 90eb9850 e758e8da 42cc2237 8a2a5483 c1afe45c 
22 7dbb787d 90eb9850 b9d63a36 42cc2237 8a2a5483 
23 1c64d028 7dbb787d 243ae614 b9d63a36 42cc2237 
24 1e97b73a 1c64d028 5f6ede1f 243ae614 b9d63a36 
25 62d7f53f 1e97b73a 0719340a 5f6ede1f 243ae614 
26 34f3d6d8 62d7f53f 87a5edce 0719340a 5f6ede1f 
27 4f2ed1c1 34f3d6d8 d8b5fd4f 87a5edce 0719340a 
28 c7b11e2d 4f2ed1c1 0d3cf5b6 d8b5fd4f 87a5edce 
29 874b786f c7b11e2d 53cbb470 0d3cf5b6 d8b5fd4f 
30 ca4556cb 874b786f 71ec478b 53cbb470 0d3cf5b6 
31 6a2e466e ca4556cb e1d2de1b 71ec478b 53cbb470 
32 62ea3d59 6a2e466e f29155b2 e1d2de1b 71ec478b 
33 b77bac25 62ea3d59 9a8b919b f29155b2 e1d2de1b 
34 4b1347e2 b77bac25 58ba8f56 9a8b919b f29155b2 
35 391ef0c4 4b1347e2 6ddeeb09 58ba8f56 9a8b919b 
36 abbab988 391ef0c4 92c4d1f8 6ddeeb09 58ba8f56 
37 04f07669 abbab988 0e47bc31 92c4d1f8 6ddeeb09 
38 b201788b 04f07669 2aeeae62 0e47bc31 92c4d1f8 
39 62273351 b201788b 413c1d9a 2aeeae62 0e47bc31 
40 9bdbdd71 62273351 ec805e22 413c1d9a 2aeeae62 
41 95aa398b 9bdbdd71 5889ccd4 ec805e22 413c1d9a 
42 5e28e858 95aa398b 66f6f75c 5889ccd4 ec805e22 
43 95642485 5e28e858 e56a8e62 66f6f75c 5889ccd4 
44 fa950aba 95642485 178a3a16 e56a8e62 66f6f75c 
45 de1e3a01 fa950aba 65590921 178a3a16 e56a8e62 
46 afe695ab de1e3a01 bea542ae 65590921 178a3a16 
47 a195ba90 afe695ab 77878e80 bea542ae 65590921 
48 e6d39f43 a195ba90 ebf9a56a 77878e80 bea542ae 
49 0bca9922 e6d39f43 28656ea4 ebf9a56a 77878e80 
50 6ae826ff 0bca9922 f9b4e7d0 28656ea4 ebf9a56a 
51 01ff3253 6ae826ff 82f2a648 f9b4e7d0 28656ea4 
52 e2581ce0 01ff3253 daba09bf 82f2a648 f9b4e7d0 
53 56ce73ab e2581ce0 c07fcc94 daba09bf 82f2a648 
54 ae56e542 56ce73ab 38960738 c07fcc94 daba09bf 
55 8590c0e8 ae56e542 d5b39cea 38960738 c07fcc94 
56 be4a4bea 8590c0e8 ab95b950 d5b39cea 38960738 
57 168ce0bb be4a4bea 2164303a ab95b950 d5b39cea 
58 e1afab22 168ce0bb af9292fa 2164303a ab95b950 
59 982bcbca e1afab22 c5a3382e af9292fa 2164303a 
60 9b9d2913 982bcbca b86beac8 c5a3382e af9292fa 
61 d37db937 9b9d2913 a60af2f2 b86beac8 c5a3382e 
62 85b9d227 d37db937 e6e74a44 a60af2f2 b86beac8 
63 cd98fbb7 85b9d227 f4df6e4d e6e74a44 a60af2f2 
64 bb0f226f cd98fbb7 e16e7489 f4df6e4d e6e74a44 
65 eb59446c bb0f226f f3663eed e16e7489 f4df6e4d 
66 d37225cb eb59446c eec3c89b f3663eed e16e7489 
67 111341f3 d37225cb 3ad6511b eec3c89b f3663eed 
68 e79afbf0 111341f3 f4dc8972 3ad6511b eec3c89b 
69 8ba00627 e79afbf0 c444d07c f4dc8972 3ad6511b 
70 503c7ae0 8ba00627 39e6befc c444d07c f4dc8972 
71 3cd517f9 503c7ae0 e2e80189 39e6befc c444d07c 
72 b47ddf0e 3cd517f9 140f1eb8 e2e80189 39e6befc 
73 5e3a0780 b47ddf0e 4f3545fe 140f1eb8 e2e80189 
74 63db37b2 5e3a0780 ad1f77c3 4f3545fe 140f1eb8 
75 15e98d17 63db37b2 178e81e0 ad1f77c3 4f3545fe 
76 b0149467 15e98d17 98f6cdec 178e81e0 ad1f77c3 
77 14b7106a b0149467 c57a6345 98f6cdec 178e81e0 
78 666b8bc6 14b7106a ec052519 c57a6345 98f6cdec 
79 6e9d9f84 666b8bc6 852dc41a ec052519 c57a6345 
80 72f480ed 6e9d9f84 999ae2f1 852dc41a ec052519 
81 da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709</code>

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.

<code> 0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
1 1fb498b3 67452301 7bf36ae2 98badcfe 10325476</code>

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:

<code>a[i+1]=rol5(a[i])+f[i]+e[i]+k[i]+w[i]</code>

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.

<code> round k[i] f[i] 
~----------------------------------------------------------------- 
0...19 5a827999 f1(b=b[i],c=c[i],d=d[i])=(b&c)|((~b)&d) 
20...39 6ed9eba1 f2(b=b[i],c=c[i],d=d[i])=b^c^d 
40...59 8f1bbcdc f3(b=b[i],c=c[i],d=d[i])=(b&c)|(b&d)|(c&d) 
60...79 ca62c1d6 f4=f2(b=b[i],c=c[i],d=d[i])=b^c^d </code>

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.

<code>a[i+1]=rol5(a[i])+f[i]+e[i]+k[i]+w[i] 
a[1]=rol5(a[0])+f[0]+e[0]+k[0]+w[0] 
a[0]=67452301 
f[0]=f1(b[0],c[0],d[0]) 
f[0]=f1(efcdab89,98badcfe,10325476) 
f[0]=98badcfe 
e[0]=c3d2e1f0 
k[0]=5a827999 
a[1]=rol5(67452301)+98badcfe+c3d2e1f0+5a827999+w[0] 
rol5(67452301)=e8a4602c 
a[1]=9fb498b3+w[0] </code>

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:

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5 
4bac3da7 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8667 a57d8667 </code>

Let's check the first 17 rounds:

<code> 0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 
1 00000000 67452301 7bf36ae2 98badcfe 10325476 
2 00000000 00000000 59d148c0 7bf36ae2 98badcfe 
3 00000000 00000000 00000000 59d148c0 7bf36ae2 
4 00000000 00000000 00000000 00000000 59d148c0 
5 00000000 00000000 00000000 00000000 00000000 
6 00000000 00000000 00000000 00000000 00000000 
7 00000000 00000000 00000000 00000000 00000000 
8 00000000 00000000 00000000 00000000 00000000 
9 00000000 00000000 00000000 00000000 00000000 
10 00000000 00000000 00000000 00000000 00000000 
11 00000000 00000000 00000000 00000000 00000000 
12 00000000 00000000 00000000 00000000 00000000 
13 00000000 00000000 00000000 00000000 00000000 
14 00000000 00000000 00000000 00000000 00000000 
15 00000000 00000000 00000000 00000000 00000000 
16 00000000 00000000 00000000 00000000 00000000 
17 3b8b2d2e 00000000 00000000 00000000 00000000 </code>

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:

<code>w[16]=rol(w[0]^w[2]^w[8]^w[13])</code>

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:

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8668 a57d8667 a57d8667</code>

Then we have this:

<code>13 00000000 00000000 00000000 00000000 00000000 
14 00000001 00000000 00000000 00000000 00000000 
15 00000020 00000001 00000000 00000000 00000000 
16 00000400 00000020 40000000 00000000 00000000 
17 3b8bad24 00000400 00000008 40000000 00000000 </code>

Now we can notice, how things are connected. Fortunately, we can fix it by changing w[14] and w[15] accordingly.

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5 
4bac3da7 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8668 a57d8647 a57d8667 </code>

It is better, but there is another problem:

<code>13 00000000 00000000 00000000 00000000 00000000 
14 00000001 00000000 00000000 00000000 00000000 
15 00000000 00000001 00000000 00000000 00000000 
16 00000000 00000000 40000000 00000000 00000000 
17 3b8b2d24 00000000 00000000 40000000 00000000 </code>

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

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5 
4bac3da7 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8667 a57d8667 
a57d8668 a57d8647 a57d8667 a57d8667 </code>

It's better, but we are still not there:

<code>12 00000000 00000000 00000000 00000000 00000000 
13 00000001 00000000 00000000 00000000 00000000 
14 00000000 00000001 00000000 00000000 00000000 
15 00000000 00000000 40000000 00000000 00000000 
16 00000000 00000000 00000000 40000000 00000000 
17 7b8b2d6e 00000000 00000000 00000000 40000000 </code>

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

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5 
4bac3da7 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8668 a57d8647 
a57d8667 a57d8667 657d8667 657d8667 </code>

Now we got it:

<code>10 00000000 00000000 00000000 00000000 00000000 
11 00000001 00000000 00000000 00000000 00000000 
12 00000000 00000001 00000000 00000000 00000000 
13 00000000 00000000 40000000 00000000 00000000 
14 00000000 00000000 00000000 40000000 00000000 
15 00000000 00000000 00000000 00000000 40000000 
16 00000000 00000000 00000000 00000000 00000000 
17 3b8b2d2e 00000000 00000000 00000000 00000000 </code>

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:

<code>10 00000000 00000000 00000000 00000000 00000000 
11 ........ 00000000 00000000 00000000 00000000 
12 00000000 ........ 00000000 00000000 00000000 
13 00000000 00000000 ........ 00000000 00000000 
14 00000000 00000000 00000000 ........ 00000000 
15 00000000 00000000 00000000 00000000 ........ 
16 00000000 00000000 00000000 00000000 00000000 
17 3b8b2d2e 00000000 00000000 00000000 00000000 </code>

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:

<code>11 00000000 00000000 00000000 00000000 00000000 
12 ........ 00000000 00000000 00000000 00000000 
13 00000000 ........ 00000000 00000000 00000000 
14 00000000 00000000 ........ 00000000 00000000 
15 00000000 00000000 00000000 ........ 00000000 
16 00000000 00000000 00000000 00000000 ........ 
17 00000000 00000000 00000000 00000000 00000000 </code>

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.

<code>w[16]=rol(w[0]^w[2]^w[8]^w[13]) 
w[0]=604b674d 
w[2]=90cf3e87 
w[8]=a57d8667 
w[13]=a57d8667 
w[16]=e108b395 </code>

Then, we can notice that:

<code>a[17]=rol5(a[16])+f[16]+e[16]+k[16]+w[16] 
a[17]=00000000 
a[16]=00000000 
f[16]=00000000 
k[16]=5a827999 
w[16]=e108b395 
00000000=00000000+00000000+e[16]+5a827999+e108b395 
e[16]=c474d2d2 </code>

Almost there, because then we can use rol2 on that, and we will get all values:

<code>a[12]=rol2(c474d2d2)=11d34b4b 
b[13]=rol2(c474d2d2)=11d34b4b 
c[14]=c474d2d2 
d[15]=c474d2d2 
e[16]=c474d2d2 </code>

So, our rounds should look like this:

<code>11 00000000 00000000 00000000 00000000 00000000 
12 11d34b4b 00000000 00000000 00000000 00000000 
13 00000000 11d34b4b 00000000 00000000 00000000 
14 00000000 00000000 c474d2d2 00000000 00000000 
15 00000000 00000000 00000000 c474d2d2 00000000 
16 00000000 00000000 00000000 00000000 c474d2d2 
17 00000000 00000000 00000000 00000000 00000000 </code>

Then, we can derive w-values from that:

<code>604b674d 994f32f3 90cf3e87 cfb8d2c5 
4bac3da7 a57d8667 a57d8667 a57d8667 
a57d8667 a57d8667 a57d8667 b750d1b2 
6b141d05 a57d8667 a57d8667 e108b395 </code>

Let's check the first 18 rounds:

<code> 0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 
1 00000000 67452301 7bf36ae2 98badcfe 10325476 
2 00000000 00000000 59d148c0 7bf36ae2 98badcfe 
3 00000000 00000000 00000000 59d148c0 7bf36ae2 
4 00000000 00000000 00000000 00000000 59d148c0 
5 00000000 00000000 00000000 00000000 00000000 
6 00000000 00000000 00000000 00000000 00000000 
7 00000000 00000000 00000000 00000000 00000000 
8 00000000 00000000 00000000 00000000 00000000 
9 00000000 00000000 00000000 00000000 00000000 
10 00000000 00000000 00000000 00000000 00000000 
11 00000000 00000000 00000000 00000000 00000000 
12 11d34b4b 00000000 00000000 00000000 00000000 
13 00000000 11d34b4b 00000000 00000000 00000000 
14 00000000 00000000 c474d2d2 00000000 00000000 
15 00000000 00000000 00000000 c474d2d2 00000000 
16 00000000 00000000 00000000 00000000 c474d2d2 
17 00000000 00000000 00000000 00000000 00000000 
18 08723a05 00000000 00000000 00000000 00000000 </code>

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.

Why Hash Functions Are Safe - Revision history

NotATether: Created page with "This document was originally posted at [https://bitcointalk.org/index.php?topic=5402178.0 Why hash functions are safe?] on Bitcointalk and is reposted here for preservation. N..."