Re^4: MD5 - what's the alternative

[Aristotle]

You missed the point again. Here's how cryptographic signatures work:

Alice has a pair of keys. The encryption key is secret, the decryption key is published.

Alice wants to send a message to Bob such that Bob can be sure the message has not been altered in transit.

To that end, she encrypts a hash of her message with her secret encryption key, attaches the encrypted hash to the message, and sends them both together to Bob, over the same channel. She does not need to encrypt her message. Bob can use Alice's published decryption key to decrypt the hash to verify the message against it, and can be sure that the message has not been tampered with..

If Eve intercepts the message, she cannot send Bob an altered message with a new hash, because it would have to be encrypted using Alice's secret.

Therefore, even though the message has been sent in the clear over an insecure channel, Bob can trust it as much as he trusts Alice's published key.

But if Eve can feasibly find a collision in the hash function, she doesn't have to know Alice's key; she can just pad the altered message such that it matches the hash previously calculated and encrypted by Alice. Bob can no longer trust the message any more than he could without the addition of the hash.

[BrowserUk]

Okay. Here's an open challenge to all crypto-analysts everywhere.

Modify the following text

The quick brown fox jumps over the laxy dog f67fcc68ecf72971a7bd012e3a47d0ac

such that it will verify by the following perl program:

#! perl -slw
use strict;
use Digest::MD5 qw[ md5_hex ];

my $challenge = 
'The quick brown fox jumps over the laxy dog f67fcc68ecf72971a7bd012e3
+a47d0ac';

my( $text, $sig ) = $ARGV[ 0 ] =~ m[(^.*)\s(.{32})$];

die 'Cheat! The text has to be different'
    if $ARGV[ 0 ] eq $challenge;

die 'Bad luck'
    if  md5_hex( $ARGV[ 0 ] ) ne '7b79a6f61178415a63fc5e7b76d64a1f'
    or md5_hex( $text ) ne $sig;
    
print "You won yourself a meal on BrowserUk" ;

print 'Make sure your passport is valid'
    if $ARGV[ 0 ] =~ m[lazy];
    
__END__

anytime in my remaining lifetime, and I'll stand them a meal at their favorite restuarant.

Pad or truncate the message as necessary, but correct my typo and I'll stand them a meal at my favorite restuarant.

And pick up the tab for getting them to and from it.

[Aristotle]

Guess what? Not a lifetime, just 8 hours on a 1.6 GHz machine, according to More Hash Function Attacks.

There's a reason the cryptographers started making waves about MD5 being weak when the first and so innocuous seeming collision conditions were found.

[BrowserUk]

I didn't read it all, but that article is still referring to the fact that it is possible to find two pieces of text that have the same md5. That was always known to be possible.

My challenge still stands.