Re^3: MD5 - what's the alternative

[BrowserUk]

No. I haven't missed the point.

I'm not sure where you got the quoted word "panic" from, but it wasn't any of my posts.

How certain can I be that the message has not been altered in transit?

1. If the message you recieved is protected by PKC, then if the PKC is secure, so is the message.
2. How did you receive the md5?

   If it came inside the PK encrypted message, and the encyption is any good, how could the bad guys know it?

Let's just assume for a moment that you received your "trusted md5" via secure means. How would the bad guys know what is was in order to create a message that hashed to that same MD5?

If the MD5 was not transmitted to you by secure means, then it's an aweful lot easier to alter both the message and the md5.

... he can pad a modified (or completely different) version of the message such that it hashes to the original checksum, ...

This is completely wrong! The attack consists of altering bits of bytes of the original message to produce a duplicate message.

The results will be the same length as the original, with a few bits altered.

1. The attacker does not get to choose which bits of which bytes get altered.
2. He does not get to choose what they get altered too.
3. The process is purely matehmatical.

Hence, if the message is plain text, it will show obvious signs of tampering. Wrong letters in words, accented characters that don't fit. It will probably look as though it has suffered from corruption in transit with a few bits having been dropped or switched. Chances are that the intent of the original message would be almost intact.

What the attacker cannot do, is change it to something specific.

The "weakness" in the md5 digital (not cryptographic) signature , certainly does not allow the attacker to "pad a modified (or completely different) version of the message such that it hashes to the original checksum".

If the message is binary, either compressed, encrypted or both, the effect of the bits changed by the mathematical manipulations, will likely render an executable unrunnable; a compressed file undecompressible; and an encrypted file undecryptable. These format being more more sensitive to random bit corruption than plain text.

Nowhere, in any of the publically available material that I have been able to access over the last couple of days does is suggest (or even hint) that it is possible to replace one message with another of entirely different meaning and then coerse it to produce the original md5. And I believe I've read everything available to read.

Your suggestion that this is possible, shows a distinct lack of understanding of the processes involved.

Please read the (rather extended) thread starting at 386470 and if your still convinced that I have missed the point then /msg me and we can continue this offline.

[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.