January 30, 2012 at 23:36
Collisions in 512-bit MD5 blocks
Dutch researcher Marc Stevens has unveiled details of a successful attack on MD5 ( PDF ) and laid out a C ++ program to look for collisions within a single 512-bit data block.
Program for Windows
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 problem can be solved in hours. The author says that the program is easy to parallelize.
The classical methods for detecting collisions in MD5 have been published since 2004, some of them required a minimum complexity of up to 2 10 , that is, they could be carried out in a second on a regular home PC, but in practice these methods were of little importance, because the classical methods focused only on the search different documents that have the same hashes (identical-prefix collision attacks). These are the so-called collisions of the second kind.
A special type of attack on hash functions is chosen-prefix type attacks.when the attacker takes two random documents and can show which bits need to be changed in one document to get the required 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 held in 2007, the complexity of the search for a collision was about 2 to 50 calls to MD5Compress function. Since then, the algorithms have accelerated to 2,339 calls, and in 2009 a group of researchers demonstrated chosen-prefix collisions, requiring only 596 bits and with a computational complexity of 2 53.2calls. After that, the weakness of MD5 became obvious to everyone, and even fake Certification Authority level certificates were made using this method.
As Mark Stevens explains, in 2010, Chinese researchers first demonstrated identical-prefix collisions 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 "competition". 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 discovered techniquestunneling . According to Stevens, the complexity of collision search in one 512-bit block according to its algorithm is estimated at 2 49.81 calls to the MD5Compress function.
Program for Windows
Sources will appear here soon .
Collision Example
Message 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
Message 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
008ee33a9d58b51cfeb425b0959121c9SHA1 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 problem can be solved in hours. The author says that the program is easy to parallelize.
The classical methods for detecting collisions in MD5 have been published since 2004, some of them required a minimum complexity of up to 2 10 , that is, they could be carried out in a second on a regular home PC, but in practice these methods were of little importance, because the classical methods focused only on the search different documents that have the same hashes (identical-prefix collision attacks). These are the so-called collisions of the second kind.
A special type of attack on hash functions is chosen-prefix type attacks.when the attacker takes two random documents and can show which bits need to be changed in one document to get the required 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 held in 2007, the complexity of the search for a collision was about 2 to 50 calls to MD5Compress function. Since then, the algorithms have accelerated to 2,339 calls, and in 2009 a group of researchers demonstrated chosen-prefix collisions, requiring only 596 bits and with a computational complexity of 2 53.2calls. After that, the weakness of MD5 became obvious to everyone, and even fake Certification Authority level certificates were made using this method.
As Mark Stevens explains, in 2010, Chinese researchers first demonstrated identical-prefix collisions 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 "competition". 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 discovered techniquestunneling . According to Stevens, the complexity of collision search in one 512-bit block according to its algorithm is estimated at 2 49.81 calls to the MD5Compress function.