Collisions in 512-bit MD5 blocks
Dutch researcher Marc Stevens (Marc Stevens) revealed the details of a successful attack on MD5 ( PDF ) and laid out a C ++ program to search for collisions within a single 512-bit data block.
Windows program
Sources will appear here soon.
Collision Example
SHA1 hashes for these messages:
On the Core2 Q9550 processor, a collision was found in three weeks. According to Mark Stevens, the estimated time is about five weeks. It is possible that when using CUDA on the GPU, this task can be solved in hours. The author says that the program is easily parallelized.
Classical methods for collision detection in MD5 have been published since 2004, some of them required a minimum complexity of up to 2 10 , that is, they could be performed per second on an ordinary home PC, but in practice these methods had little value, because classical methods are focused only on search identical documents that have identical hashes (identical-prefix collision attacks). These are the so-called collisions of the second kind.
')
A special type of hash attack is a chosen-prefix attack , when an attacker takes two random documents and can show which bits need to be changed in one document in order to get the desired hash function. These are collisions of the first kind: for a given message M it becomes possible to select another message N for which H (N) = H (M). This type of attack on MD5 was first carried out in 2007, the complexity of collision search was about 2 50 calls to the MD5Compress function. Since then, the algorithms have accelerated to 2 39 calls, and in 2009 a group of researchers demonstrated chosen-prefix collisions, requiring only 596 bits and 2 53.2 calls with a computational complexity. After that, the weakness of MD5 became obvious to everyone, and even fake certificates of the level of Certication Authority were started using this method.
As Mark Stevens explains, in 2010, Chinese researchers for the first time demonstrated collisions like identical-prefix for single 512-bit MD5 blocks, but they did not provide details of their algorithm “for security reasons”. Instead, they announced a kind of competition among cryptographers to repeat this attack for MD5. The work of Mark Stevens claims to win this “contest”. The attack is based on a new collision search algorithm, based on a small number of options in the first round of hash calculation (MD5 works in four rounds), and the Mark Stevens method uses previously detected tunneling techniques. According to Stevens, the complexity of finding a collision in a single 512-bit block according to his algorithm is estimated at 2 49.81 calls to the MD5Compress function.
Windows program
Sources will appear here soon.
Collision Example
Post 1
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3d c0 78 3e 7b 95 18
af bf a2 [00] a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1 [55] 5d 83 60 fb 5f 07 fe a2
Post 2
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3d c0 78 3e 7b 95 18
af bf a2 [02] a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1 [d5] 5d 83 60 fb 5f 07 fe a2
MD5 common hash
008ee33a9d58b51cfeb425b0959121c9 SHA1 hashes for these messages:
> sha1sum message1.bin message2.bin c6b384c4968b28812b676b49d40c09f8af4ed4cc message1.bin c728d8d93091e9c7b87b43d9e33829379231d7ca message2.bin
On the Core2 Q9550 processor, a collision was found in three weeks. According to Mark Stevens, the estimated time is about five weeks. It is possible that when using CUDA on the GPU, this task can be solved in hours. The author says that the program is easily parallelized.
Classical methods for collision detection in MD5 have been published since 2004, some of them required a minimum complexity of up to 2 10 , that is, they could be performed per second on an ordinary home PC, but in practice these methods had little value, because classical methods are focused only on search identical documents that have identical hashes (identical-prefix collision attacks). These are the so-called collisions of the second kind.
')
A special type of hash attack is a chosen-prefix attack , when an attacker takes two random documents and can show which bits need to be changed in one document in order to get the desired hash function. These are collisions of the first kind: for a given message M it becomes possible to select another message N for which H (N) = H (M). This type of attack on MD5 was first carried out in 2007, the complexity of collision search was about 2 50 calls to the MD5Compress function. Since then, the algorithms have accelerated to 2 39 calls, and in 2009 a group of researchers demonstrated chosen-prefix collisions, requiring only 596 bits and 2 53.2 calls with a computational complexity. After that, the weakness of MD5 became obvious to everyone, and even fake certificates of the level of Certication Authority were started using this method.
As Mark Stevens explains, in 2010, Chinese researchers for the first time demonstrated collisions like identical-prefix for single 512-bit MD5 blocks, but they did not provide details of their algorithm “for security reasons”. Instead, they announced a kind of competition among cryptographers to repeat this attack for MD5. The work of Mark Stevens claims to win this “contest”. The attack is based on a new collision search algorithm, based on a small number of options in the first round of hash calculation (MD5 works in four rounds), and the Mark Stevens method uses previously detected tunneling techniques. According to Stevens, the complexity of finding a collision in a single 512-bit block according to his algorithm is estimated at 2 49.81 calls to the MD5Compress function.
Source: https://habr.com/ru/post/137316/
All Articles