Forums: Md5 Hacked "hash Collision" - Forums

The excitement began Thursday with an announcement that French computer scientist Antoine Joux had uncovered a flaw in a popular algorithm called MD5, often used with digital signatures. Then four Chinese researchers released a paper that reported a way to circumvent MD5 and other algorithms.

While their results are preliminary, these discoveries could eventually make it easier for intruders to insert undetectable back doors into computer code or to forge an electronic signature--unless a different, more secure algorithm is used.

A third announcement, which was even more anticipated, took place Tuesday evening at the Crypto 2004 conference in Santa Barbara, Calif. The other papers also were presented at the conference.

Eli Biham and Rafi Chen, researchers at the Technion institute in Israel, originally were scheduled to present a paper identifying ways to assail the security in the SHA-0 "Secure Hash Algorithm," which was known to have imperfections. In a presentation Tuesday evening, however, Biham reported some early work toward identifying vulnerabilities in the SHA-1 algorithm, which is believed to be secure.

Biham's presentation was very preliminary, but it could call into question the long-term future of the wildly popular SHA-1 algorithm and spur researchers to identify alternatives.

Currently considered the gold standard of its class of algorithms, SHA-1 is embedded in popular programs like PGP and SSL. It is certified by the National Institute of Standards and Technology and is the only signing algorithm approved for use in the U.S. government's Digital Signature Standard. SHA-1 yields a 160-bit output, which is longer than MD5's 128-bit output and is considered more secure.

Jim Hughes, general chairman of the Crypto 2004 conference, said Tuesday morning that the news was sufficiently important that he was organizing the first Webcast in the conference's 24-year history. "There are three significant rump session papers on hash collisions that will be presented," including an update on Joux's findings, Hughes said in a message to a cryptography-related mailing list.

Unique fingerprints
"If you could find two contracts that hash out to the same signature, you could replace one with the other and in a court of law there would be at least an ambiguity about which one is valid," Hughes, a senior fellow at StorageTek, said in a telephone interview. "That's a very significant possibility."

The MD5 and SHA-1 algorithms are known to computer scientists as hash functions. They take all kinds of input, from an e-mail message to an operating-system kernel, and generate what's supposed to be a unique fingerprint. Changing even one letter in the input file results in a completely different fingerprint.

Security applications rely on these fingerprints being unique. But if a malicious attacker could generate the same fingerprint with a different input stream, the cloned fingerprint--known as a hash collision--would certify that software with a back door is safe to download and execute. It would help a crook who wanted to falsely sign an e-mail instructing that someone's bank account be emptied.

Because researchers have long known that no practical encryption algorithm can be completely secure, they attempt to design ones that take an inordinately long time to generate duplicate fingerprints. SHA-1 is regarded as secure because it is not possible to knowingly generate hash collisions using existing techniques.

The SHA-1 algorithm relies on a computer executing a routine 80 times in an attempt to create a unique fingerprint. Biham said that he had been been able to duplicate the fingerprint for 36 of those 80 rounds.

If vulnerabilities similar to those identified in SHA-0 are eventually discovered in SHA-1, that would mean that attempts to forge a fingerprint would be accelerated by about 500 million times--putting it within theoretical reach of a network of fast PCs.

The weakness in the MD5 algorithm may be the more immediate threat. The open-source Apache Web server product uses MD5 hashes to assure the public that source code on dozens of mirror sites is not modified and is safe to run. So does Sun Microsystems' Solaris Fingerprint Database, which the company says can "verify that a true file in an official binary distribution is being used, and not an altered version that compromises system security."

MD5's flaws that have been identified in the past few days mean that an attacker can generate one hash collision in a few hours on a standard PC. To write a specific back door and cloak it with the same hash collision may be much more time intensive.

Still, Hughes said that programmers should start moving away from MD5. "Right now the algorithm has been shown to be weak," he said. "Before useful (attacks) can be done, it's time to migrate away from it."

This is a good update to know about. I was planning on looking at security monitoring solution that utilized MD5 as a value add to their product. Looks like it is not anymore.

Still lots of people reply on MD5 for hashing and fingerprinting of files. Until there is a standard set out by the "3" digit guys, they will still use it for their forensic investigations.

expect a mass migration from md5 and within the next year, a whole slew of utilities to come out that exploit this vuln in hash computation.

its crazy, i actually had a dream about the demise of md5 a while back (sad i know)

lmao, i posted rumours about this 10 months ago...but no one believed me!

my source was a blackhat cracker with some chinese friends

im still waiting for some proof of concept code!

A POC would be interesting to check out indeed. I'm sure there'd be plenty to keep you reading for awhile in there.

K, here's your POC:

md5.pl

#!/usr/bin/perl -w

use strict;
use Digest::MD5 qw(md5_hex);

# Create a stream of bytes from hex.
my $bytes1 = map {chr(hex($_))} qw(
  d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
  2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89
  55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a
  08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b
  d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
  dd 53 e2 b4 87 da 03 fd 02 39 63 06 d2 48 cd a0
  e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 a8 0d 1e
  c6 98 21 bc b6 a8 83 93 96 f9 65 2b 6f f7 2a 70
);

# Create a second stream of bytes from hex.
my $bytes2 = map {chr(hex($_))} qw(
  d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
  2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89
  55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a
  08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b
  d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
  dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0
  e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e
  c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70
);

# Print MD5 hashes
print md5_hex($bytes1), "\n";
print md5_hex($bytes2), "\n";

two md5 hashes, different source, same results.

If you can't see the differences then let me reprint them here:
d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89
55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a
08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b
d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
dd 53 e2 b4 87 da 03 fd 02 39 63 06 d2 48 cd a0
e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 a8 0d 1e
c6 98 21 bc b6 a8 83 93 96 f9 65 2b 6f f7 2a 70

d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89
55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a
08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b
d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0
e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e
c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70

Blimey, hows that work ?

76dc611d6ebaafc66cc0879c71b5db5c
76dc611d6ebaafc66cc0879c71b5db5c

both come out to that for the lazy amongst you.