Why Hash Functions Are Safe

From Bitcoin Wiki
Revision as of 15:32, 12 June 2022 by NotATether (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

This document was originally posted at 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:

67452301 efcdab89 98badcfe 10325476 c3d2e1f0

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:

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]

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

80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

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:

da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

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

ba100000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 0000000b

And its SHA-1 is:

be5abcb4 16303cb7 3459305d e9ef9055 16be628d

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:

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

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:

w[i]=rol(w[i-16]^w[i-14]^w[i-8]^w[i-3])

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:

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

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:

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

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:

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

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.

0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0

1   1fb498b3 67452301 7bf36ae2 98badcfe 10325476

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:

a[i+1]=rol5(a[i])+f[i]+e[i]+k[i]+w[i]

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.

  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

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.

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]

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:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667

Let's check the first 17 rounds:

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

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:

w[16]=rol(w[0]^w[2]^w[8]^w[13])

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:

604b674d 994f32f3 90cf3e87 cfb8d2c5 4bac3da7 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8668 a57d8667 a57d8667

Then we have this:

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

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

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8668 a57d8647 a57d8667

It is better, but there is another problem:

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

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

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8668 a57d8647 a57d8667 a57d8667

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

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

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

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8668 a57d8647
a57d8667 a57d8667 657d8667 657d8667

Now we got it:

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

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:

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

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:

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

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.

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

Then, we can notice that:

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

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

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

So, our rounds should look like this:

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

Then, we can derive w-values from that:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 b750d1b2
6b141d05 a57d8667 a57d8667 e108b395

Let's check the first 18 rounds:

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

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.