Author

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

vjudeu

copper member

Activity: 903

Merit: 2248

Quote

No changes have been made to the original except for superficial formatting adjustments.

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:

Code:

 0   00000000 00000000 00000000 00000000 00000000
 1   5a827999 00000000 00000000 00000000 00000000
 2   aad1acc4 5a827999 00000000 00000000 00000000
 3   b4b8122e aad1acc4 56a09e66 00000000 00000000
 4   f4054bb3 b4b8122e 2ab46b31 56a09e66 00000000
 5   3ddc7e77 f4054bb3 ad2e048b 2ab46b31 56a09e66
 6   1b670769 3ddc7e77 fd0152ec ad2e048b 2ab46b31
 7   af3a24d9 1b670769 cf771f9d fd0152ec ad2e048b
 8   de5c70e6 af3a24d9 46d9c1da cf771f9d fd0152ec
 9   696f053c de5c70e6 6bce8936 46d9c1da cf771f9d
10   a2a7c201 696f053c b7971c39 6bce8936 46d9c1da
11   19dc07e1 a2a7c201 1a5bc14f b7971c39 6bce8936
12   18e5db2b 19dc07e1 68a9f080 1a5bc14f b7971c39
13   3960bbc3 18e5db2b 467701f8 68a9f080 1a5bc14f
14   0162d4f7 3960bbc3 c63976ca 467701f8 68a9f080
15   35be3bf3 0162d4f7 ce582ef0 c63976ca 467701f8
16   1f1a20ef 35be3bf3 c058b53d ce582ef0 c63976ca
17   ce584377 1f1a20ef cd6f8efc c058b53d ce582ef0
18   c12dad7e ce584377 c7c6883b cd6f8efc c058b53d
19   07f86b69 c12dad7e f39610dd c7c6883b cd6f8efc
20   eec57612 07f86b69 b04b6b5f f39610dd c7c6883b
21   53744724 eec57612 41fe1ada b04b6b5f f39610dd
22   f068e89f 53744724 bbb15d84 41fe1ada b04b6b5f
23   d57d6b78 f068e89f 14dd11c9 bbb15d84 41fe1ada
24   bf8a1a67 d57d6b78 fc1a3a27 14dd11c9 bbb15d84
25   5988d6b2 bf8a1a67 355f5ade fc1a3a27 14dd11c9
26   2ba14e53 5988d6b2 efe28699 355f5ade fc1a3a27
27   6252fb22 2ba14e53 966235ac efe28699 355f5ade
28   40baa831 6252fb22 cae85394 966235ac efe28699
29   b4ea157c 40baa831 9894bec8 cae85394 966235ac
30   b5451650 b4ea157c 502eaa0c 9894bec8 cae85394
31   5eb50b03 b5451650 2d3a855f 502eaa0c 9894bec8
32   a66143d7 5eb50b03 2d514594 2d3a855f 502eaa0c
33   ea0fdc69 a66143d7 d7ad42c0 2d514594 2d3a855f
34   3aad42c0 ea0fdc69 e99850f5 d7ad42c0 2d514594
35   c60e5798 3aad42c0 7a83f71a e99850f5 d7ad42c0
36   b20906a8 c60e5798 0eab50b0 7a83f71a e99850f5
37   4bba01de b20906a8 318395e6 0eab50b0 7a83f71a
38   edbfe282 4bba01de 2c8241aa 318395e6 0eab50b0
39   8c3d6240 edbfe282 92ee8077 2c8241aa 318395e6
40   7bdcecf7 8c3d6240 bb6ff8a0 92ee8077 2c8241aa
41   d1ab7dd5 7bdcecf7 230f5890 bb6ff8a0 92ee8077
42   92c9f0bd d1ab7dd5 def73b3d 230f5890 bb6ff8a0
43   777946c3 92c9f0bd 746adf75 def73b3d 230f5890
44   783fe917 777946c3 64b27c2f 746adf75 def73b3d
45   ea8a796f 783fe917 ddde51b0 64b27c2f 746adf75
46   d1944385 ea8a796f de0ffa45 ddde51b0 64b27c2f
47   04e5232a d1944385 faa29e5b de0ffa45 ddde51b0
48   e4254e11 04e5232a 746510e1 faa29e5b de0ffa45
49   66ba8bc8 e4254e11 813948ca 746510e1 faa29e5b
50   45351d04 66ba8bc8 79095384 813948ca 746510e1
51   0b5dba0d 45351d04 19aea2f2 79095384 813948ca
52   d5395acb 0b5dba0d 114d4741 19aea2f2 79095384
53   c89e0c1b d5395acb 42d76e83 114d4741 19aea2f2
54   0de9320a c89e0c1b f54e56b2 42d76e83 114d4741
55   1e6d93f1 0de9320a f2278306 f54e56b2 42d76e83
56   9514bb84 1e6d93f1 837a4c82 f2278306 f54e56b2
57   b97107a2 9514bb84 479b64fc 837a4c82 f2278306
58   367ea0bd b97107a2 25452ee1 479b64fc 837a4c82
59   07bb47e4 367ea0bd ae5c41e8 25452ee1 479b64fc
60   f47c3f41 07bb47e4 4d9fa82f ae5c41e8 25452ee1
61   63a88718 f47c3f41 01eed1f9 4d9fa82f ae5c41e8
62   a5dd2d61 63a88718 7d1f0fd0 01eed1f9 4d9fa82f
63   f3016f6a a5dd2d61 18ea21c6 7d1f0fd0 01eed1f9
64   eca784a4 f3016f6a 69774b58 18ea21c6 7d1f0fd0
65   5f0e6c37 eca784a4 bcc05bda 69774b58 18ea21c6
66   fe2afead 5f0e6c37 3b29e129 bcc05bda 69774b58
67   d221b9b1 fe2afead d7c39b0d 3b29e129 bcc05bda
68   de1ad873 d221b9b1 7f8abfab d7c39b0d 3b29e129
69   43504e91 de1ad873 74886e6c 7f8abfab d7c39b0d
70   e14838bf 43504e91 f786b61c 74886e6c 7f8abfab
71   3353305e e14838bf 50d413a4 f786b61c 74886e6c
72   ef6bd90f 3353305e f8520e2f 50d413a4 f786b61c
73   4b39c7c4 ef6bd90f 8cd4cc17 f8520e2f 50d413a4
74   1e5ce93a 4b39c7c4 fbdaf643 8cd4cc17 f8520e2f
75   ca89f4d8 1e5ce93a 12ce71f1 fbdaf643 8cd4cc17
76   9fbe978e ca89f4d8 87973a4e 12ce71f1 fbdaf643
77   1de16953 9fbe978e 32a27d36 87973a4e 12ce71f1
78   c3ea2f20 1de16953 a7efa5e3 32a27d36 87973a4e
79   57ec91c2 c3ea2f20 c7785a54 a7efa5e3 32a27d36
80   9e1547ed 57ec91c2 30fa8bc8 c7785a54 a7efa5e3
81   9e1547ed 57ec91c2 30fa8bc8 c7785a54 a7efa5e3

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:

Code:

80   00000000 00000000 00000000 00000000 00000000
79   00000000 00000000 00000000 00000000 359d3e2a
78   00000000 00000000 00000000 359d3e2a 00000000
77   00000000 00000000 359d3e2a 00000000 00000000
76   00000000 d674f8a8 00000000 00000000 5f284582
75   d674f8a8 00000000 00000000 5f284582 07d5e38e
74   00000000 00000000 5f284582 07d5e38e b31490c6
73   00000000 7ca11609 07d5e38e b31490c6 6d3cd8e9
72   7ca11609 1f578e38 b31490c6 6d3cd8e9 dffab6e4
71   1f578e38 cc52431a 6d3cd8e9 dffab6e4 48b86019
70   cc52431a b4f363a5 dffab6e4 48b86019 a6fab3b1
69   b4f363a5 7feadb93 48b86019 a6fab3b1 d1db0453
68   7feadb93 22e18065 a6fab3b1 d1db0453 9774f7d9
67   22e18065 9beacec6 d1db0453 9774f7d9 7c12cfcd
66   9beacec6 476c114f 9774f7d9 7c12cfcd 2f1abc61
65   476c114f 5dd3df66 7c12cfcd 2f1abc61 d52a363e
64   5dd3df66 f04b3f35 2f1abc61 d52a363e b811ad44
63   f04b3f35 bc6af184 d52a363e b811ad44 b8b7cbd4
62   bc6af184 54a8d8fb b811ad44 b8b7cbd4 447b8e5d
61   54a8d8fb e046b512 b8b7cbd4 447b8e5d 40621fa9
60   e046b512 e2df2f52 447b8e5d 40621fa9 9aa8b623
59   e2df2f52 11ee3975 40621fa9 9aa8b623 e45aceb9
58   11ee3975 01887ea5 9aa8b623 e45aceb9 95734533
57   01887ea5 6aa2d88e e45aceb9 95734533 6d4fdb3e
56   6aa2d88e 916b3ae7 95734533 6d4fdb3e 88a654c5
55   916b3ae7 55cd14ce 6d4fdb3e 88a654c5 605069f2
54   55cd14ce b53f6cf9 88a654c5 605069f2 a8767750
53   b53f6cf9 22995316 605069f2 a8767750 fe73456a
52   22995316 8141a7c9 a8767750 fe73456a 2a85e611
51   8141a7c9 a1d9dd42 fe73456a 2a85e611 c076d7c8
50   a1d9dd42 f9cd15ab 2a85e611 c076d7c8 ce246b10
49   f9cd15ab aa179844 c076d7c8 ce246b10 0ee48fa7
48   aa179844 01db5f23 ce246b10 0ee48fa7 18da0117
47   01db5f23 3891ac43 0ee48fa7 18da0117 c6bf6a01
46   3891ac43 3b923e9c 18da0117 c6bf6a01 45efefcb
45   3b923e9c 6368045c c6bf6a01 45efefcb ef3ead97
44   6368045c 1afda807 45efefcb ef3ead97 ef7648ad
43   1afda807 17bfbf2d ef3ead97 ef7648ad 855898f0
42   17bfbf2d bcfab65f ef7648ad 855898f0 e66f6c8c
41   bcfab65f bdd922b7 855898f0 e66f6c8c 43f40da6
40   bdd922b7 156263c2 e66f6c8c 43f40da6 2b543506
39   156263c2 99bdb233 43f40da6 2b543506 b1953441
38   99bdb233 0fd03699 2b543506 b1953441 d9c0f9d0
37   0fd03699 ad50d418 b1953441 d9c0f9d0 6bd7d9e8
36   ad50d418 c654d106 d9c0f9d0 6bd7d9e8 8297d6a5
35   c654d106 6703e743 6bd7d9e8 8297d6a5 e598df91
34   6703e743 af5f67a1 8297d6a5 e598df91 aead8e64
33   af5f67a1 0a5f5a96 e598df91 aead8e64 cad2fc0a
32   0a5f5a96 96637e47 aead8e64 cad2fc0a 027e1d16
31   96637e47 bab63992 cad2fc0a 027e1d16 5cfacd75
30   bab63992 2b4bf02b 027e1d16 5cfacd75 5af34007
29   2b4bf02b 09f87458 5cfacd75 5af34007 d26c4f62
28   09f87458 73eb35d5 5af34007 d26c4f62 81ef3ed9
27   73eb35d5 6bcd001d d26c4f62 81ef3ed9 e5695c63
26   6bcd001d 49b13d8b 81ef3ed9 e5695c63 5e39e756
25   49b13d8b 07bcfb66 e5695c63 5e39e756 09df22c0
24   07bcfb66 95a5718f 5e39e756 09df22c0 20f43111
23   95a5718f 78e79d59 09df22c0 20f43111 92684f4b
22   78e79d59 277c8b00 20f43111 92684f4b 73f6e565
21   277c8b00 83d0c444 92684f4b 73f6e565 b82de34a
20   83d0c444 49a13d2e 73f6e565 b82de34a bc0fdbce
19   49a13d2e cfdb9595 b82de34a bc0fdbce 3d18d998
18   cfdb9595 e0b78d2a bc0fdbce 3d18d998 369c3742
17   e0b78d2a f03f6f3a 3d18d998 369c3742 27cf1d48
16   f03f6f3a f4636660 369c3742 27cf1d48 46baeceb
15   f4636660 da70dd08 27cf1d48 46baeceb 0285eb98
14   da70dd08 9f3c7520 46baeceb 0285eb98 450b5cf4
13   9f3c7520 1aebb3ad 0285eb98 450b5cf4 50ddcf84
12   1aebb3ad 0a17ae60 450b5cf4 50ddcf84 96783800
11   0a17ae60 142d73d1 50ddcf84 96783800 eb162293
10   142d73d1 43773e11 96783800 eb162293 7f768223
 9   43773e11 59e0e002 eb162293 7f768223 dbad15ed
 8   59e0e002 ac588a4f 7f768223 dbad15ed 2ce32c8a
 7   ac588a4f fdda088d dbad15ed 2ce32c8a 9aa3f7e5
 6   fdda088d 6eb457b7 2ce32c8a 9aa3f7e5 d9f15a35
 5   6eb457b7 b38cb228 9aa3f7e5 d9f15a35 f1da9dd2
 4   b38cb228 6a8fdf96 d9f15a35 f1da9dd2 c8ca3eb4
 3   6a8fdf96 67c568d7 f1da9dd2 c8ca3eb4 1d4426d0
 2   67c568d7 c76a774b c8ca3eb4 1d4426d0 3f121481
 1   c76a774b 2328fad3 1d4426d0 3f121481 02e1def6
 0   2328fad3 75109b40 3f121481 02e1def6 cfd74e98

We did everything backwards, and we reached some IV. Let's see, how it would look like, if we execute it forward again:

Code:

 0   2328fad3 75109b40 3f121481 02e1def6 cfd74e98
 1   c76a774b 2328fad3 1d4426d0 3f121481 02e1def6
 2   67c568d7 c76a774b c8ca3eb4 1d4426d0 3f121481
 3   6a8fdf96 67c568d7 f1da9dd2 c8ca3eb4 1d4426d0
 4   b38cb228 6a8fdf96 d9f15a35 f1da9dd2 c8ca3eb4
 5   6eb457b7 b38cb228 9aa3f7e5 d9f15a35 f1da9dd2
 6   fdda088d 6eb457b7 2ce32c8a 9aa3f7e5 d9f15a35
 7   ac588a4f fdda088d dbad15ed 2ce32c8a 9aa3f7e5
 8   59e0e002 ac588a4f 7f768223 dbad15ed 2ce32c8a
 9   43773e11 59e0e002 eb162293 7f768223 dbad15ed
10   142d73d1 43773e11 96783800 eb162293 7f768223
11   0a17ae60 142d73d1 50ddcf84 96783800 eb162293
12   1aebb3ad 0a17ae60 450b5cf4 50ddcf84 96783800
13   9f3c7520 1aebb3ad 0285eb98 450b5cf4 50ddcf84
14   da70dd08 9f3c7520 46baeceb 0285eb98 450b5cf4
15   f4636660 da70dd08 27cf1d48 46baeceb 0285eb98
16   f03f6f3a f4636660 369c3742 27cf1d48 46baeceb
17   e0b78d2a f03f6f3a 3d18d998 369c3742 27cf1d48
18   cfdb9595 e0b78d2a bc0fdbce 3d18d998 369c3742
19   49a13d2e cfdb9595 b82de34a bc0fdbce 3d18d998
20   83d0c444 49a13d2e 73f6e565 b82de34a bc0fdbce
21   277c8b00 83d0c444 92684f4b 73f6e565 b82de34a
22   78e79d59 277c8b00 20f43111 92684f4b 73f6e565
23   95a5718f 78e79d59 09df22c0 20f43111 92684f4b
24   07bcfb66 95a5718f 5e39e756 09df22c0 20f43111
25   49b13d8b 07bcfb66 e5695c63 5e39e756 09df22c0
26   6bcd001d 49b13d8b 81ef3ed9 e5695c63 5e39e756
27   73eb35d5 6bcd001d d26c4f62 81ef3ed9 e5695c63
28   09f87458 73eb35d5 5af34007 d26c4f62 81ef3ed9
29   2b4bf02b 09f87458 5cfacd75 5af34007 d26c4f62
30   bab63992 2b4bf02b 027e1d16 5cfacd75 5af34007
31   96637e47 bab63992 cad2fc0a 027e1d16 5cfacd75
32   0a5f5a96 96637e47 aead8e64 cad2fc0a 027e1d16
33   af5f67a1 0a5f5a96 e598df91 aead8e64 cad2fc0a
34   6703e743 af5f67a1 8297d6a5 e598df91 aead8e64
35   c654d106 6703e743 6bd7d9e8 8297d6a5 e598df91
36   ad50d418 c654d106 d9c0f9d0 6bd7d9e8 8297d6a5
37   0fd03699 ad50d418 b1953441 d9c0f9d0 6bd7d9e8
38   99bdb233 0fd03699 2b543506 b1953441 d9c0f9d0
39   156263c2 99bdb233 43f40da6 2b543506 b1953441
40   bdd922b7 156263c2 e66f6c8c 43f40da6 2b543506
41   bcfab65f bdd922b7 855898f0 e66f6c8c 43f40da6
42   17bfbf2d bcfab65f ef7648ad 855898f0 e66f6c8c
43   1afda807 17bfbf2d ef3ead97 ef7648ad 855898f0
44   6368045c 1afda807 45efefcb ef3ead97 ef7648ad
45   3b923e9c 6368045c c6bf6a01 45efefcb ef3ead97
46   3891ac43 3b923e9c 18da0117 c6bf6a01 45efefcb
47   01db5f23 3891ac43 0ee48fa7 18da0117 c6bf6a01
48   aa179844 01db5f23 ce246b10 0ee48fa7 18da0117
49   f9cd15ab aa179844 c076d7c8 ce246b10 0ee48fa7
50   a1d9dd42 f9cd15ab 2a85e611 c076d7c8 ce246b10
51   8141a7c9 a1d9dd42 fe73456a 2a85e611 c076d7c8
52   22995316 8141a7c9 a8767750 fe73456a 2a85e611
53   b53f6cf9 22995316 605069f2 a8767750 fe73456a
54   55cd14ce b53f6cf9 88a654c5 605069f2 a8767750
55   916b3ae7 55cd14ce 6d4fdb3e 88a654c5 605069f2
56   6aa2d88e 916b3ae7 95734533 6d4fdb3e 88a654c5
57   01887ea5 6aa2d88e e45aceb9 95734533 6d4fdb3e
58   11ee3975 01887ea5 9aa8b623 e45aceb9 95734533
59   e2df2f52 11ee3975 40621fa9 9aa8b623 e45aceb9
60   e046b512 e2df2f52 447b8e5d 40621fa9 9aa8b623
61   54a8d8fb e046b512 b8b7cbd4 447b8e5d 40621fa9
62   bc6af184 54a8d8fb b811ad44 b8b7cbd4 447b8e5d
63   f04b3f35 bc6af184 d52a363e b811ad44 b8b7cbd4
64   5dd3df66 f04b3f35 2f1abc61 d52a363e b811ad44
65   476c114f 5dd3df66 7c12cfcd 2f1abc61 d52a363e
66   9beacec6 476c114f 9774f7d9 7c12cfcd 2f1abc61
67   22e18065 9beacec6 d1db0453 9774f7d9 7c12cfcd
68   7feadb93 22e18065 a6fab3b1 d1db0453 9774f7d9
69   b4f363a5 7feadb93 48b86019 a6fab3b1 d1db0453
70   cc52431a b4f363a5 dffab6e4 48b86019 a6fab3b1
71   1f578e38 cc52431a 6d3cd8e9 dffab6e4 48b86019
72   7ca11609 1f578e38 b31490c6 6d3cd8e9 dffab6e4
73   00000000 7ca11609 07d5e38e b31490c6 6d3cd8e9
74   00000000 00000000 5f284582 07d5e38e b31490c6
75   d674f8a8 00000000 00000000 5f284582 07d5e38e
76   00000000 d674f8a8 00000000 00000000 5f284582
77   00000000 00000000 359d3e2a 00000000 00000000
78   00000000 00000000 00000000 359d3e2a 00000000
79   00000000 00000000 00000000 00000000 359d3e2a
80   00000000 00000000 00000000 00000000 00000000
81   2328fad3 75109b40 3f121481 02e1def6 cfd74e98

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.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: vjudeu on June 11, 2022, 11:08:16 PM

Quote

if you approve of that

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

It has been done.

vjudeu

copper member

Activity: 903

Merit: 2248

Quote

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.

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:

Code:

 0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1   ........ 67452301 7bf36ae2 98badcfe 10325476
 2   ........ ........ 59d148c0 7bf36ae2 98badcfe
 3   ........ ........ ........ 59d148c0 7bf36ae2
 4   ........ ........ ........ ........ 59d148c0
 5   ........ ........ ........ ........ ........
-------------------------------------------------
75   ........ ........ ........ ........ ........
76   f0b47840 ........ ........ ........ ........
77   bf36ae2b f0b47840 ........ ........ ........
78   9d148c09 bf36ae2b 3c2d1e10 ........ ........
79   10325477 9d148c09 efcdab8a 3c2d1e10 ........
80   98badcff 10325477 67452302 efcdab8a 3c2d1e10
81   00000000 00000000 00000000 00000000 00000000

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:

Code:

f1=b?c:d (if b, then c, else d)
f2=b^c^d (xor on all)
f3=(b&c)|(b&d)|(c&d) (2-of-3 from b,c,d should be true to make the whole thing true, a "majority")

+---+---+---+----+----+----+
| b | c | d | f1 | f2 | f3 |
+---+---+---+----+----+----+
| 0 | 0 | 0 |  0 |  0 |  0 |
| 0 | 0 | 1 |  1 |  1 |  0 |
| 0 | 1 | 0 |  0 |  1 |  0 |
| 0 | 1 | 1 |  1 |  0 |  1 |
| 1 | 0 | 0 |  0 |  1 |  0 |
| 1 | 0 | 1 |  0 |  0 |  1 |
| 1 | 1 | 0 |  1 |  0 |  1 |
| 1 | 1 | 1 |  1 |  1 |  1 |
+---+---+---+----+----+----+

f1=01010011=bcd_function(0x53)
f2=01101001=bcd_function(0x69)
f3=00010111=bcd_function(0x17)

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:

Code:

modulo(uint32(a)+uint32(b),2^32)=uint32(c)
getBit(c,0)=f2(0,getBit(a,0),getBit(b,0))
getBit(carry,0)=f3(0,getBit(a,0),getBit(b,0))
getBit(c,1)=f2(getBit(carry,0),getBit(a,1),getBit(b,1))
getBit(carry,1)=f3(getBit(carry,0),getBit(a,1),getBit(b,1))
...
getBit(c,30)=f2(getBit(carry,29),getBit(a,30),getBit(b,30))
getBit(carry,30)=f3(getBit(carry,29),getBit(a,30),getBit(b,30))
getBit(c,31)=f2(getBit(carry,30),getBit(a,31),getBit(b,31))
bitDroppedByModulo=f3(getBit(carry,30),getBit(a,31),getBit(b,31))

Then, it will quickly turn out that getBit(c,31) depends on all other bits from "a" and "b".

Edit:

Quote

if you approve of that

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

Edit:

Quote

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.

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").

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

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.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

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.

vjudeu

copper member

Activity: 903

Merit: 2248

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

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]

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

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

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

And its SHA-1 is:

Code:

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:

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

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

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

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

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

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

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]

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

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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.