Is there any difference between md5 and sha1 in this situation?

Question

It is known that

1.    if   ( md5(a)   == md5(b)   )
2.    then ( md5(a.z) == md5(b.z) )
3.    but  ( md5(z.a) != md5(z.b) )

where the dots concatenate the strings.

EDIT ---

Here you can find a and b:
http://www.mscs.dal.ca/~selinger/md5collision/

Check these links:
hexpaste.com/qzNCBRYb/1 - this is a.md5(a)."kutykurutty"
hexpaste.com/mSXMl13A/1 - this is b.md5(b)."kutykurutty"

They share the same md5 hash, yet they are different. But you can call these strings a' and b', because they have the same md5.

--- EDIT

What happens in the second row if we change all the md5 to sha1? So:

1.    if   ( sha1(c)   == sha1(d)   )
2.    then ( sha1(c.z) ?= sha1(d.z) )

I couldn't find two different strings with same sha1, that's why I'm asking this. Are there any other interesting "rules" about sha1?

Answer 1

The first statement will only hold true for very specific z specifically computed for given a and b. It is true that you can generate an MD5 collision, but this is not trivial - some computational effort is required and certainly you can't expect that any z will do.

Currently SHA-1 is believed to be cryptographically secure which means noone has come up with a way to generate SHA-1 collisions. It doesn't mean that it is really secure and collision generation is not possible - maybe there is a yet uncovered vulnerability. Even if there is a vulnerability it's highly unlikely that the same strings will at the same time form both an MD5 and a SHA-1 collision.

Answer 2

Sha1 isn't as easily cracked as md5, but they did find some vulnerabilities in it back in '05 I believe.

Answer 3

SHA1 will behave exactly like MD5 in this scenario.

The only two references I have found are the following -

1. http://www.iaik.tugraz.at/content/research/krypto/sha1/MeaningfulCollisions.php
2. http://www.schneier.com/blog/archives/2005/02/sha1_broken.html#c1654 (See comment by David Schwartz)

From the IAIK website -

Note that for colliding SHA-1 message pairs (as for all other hash functions following a similar design principle) it is always possible to append suffixes to both messages as long as they are the same.

I don't think anybody has found two colliding strings for SHA1, so this is mostly an academic discussion. But from what I understand, when a collision is discovered, it should be possible to create several other collisions by using this property.

Answer 4

Your example is wrong in my opinion. Let me show you why:

md5(a) == md5(b)

When both hashes are the same, the corresponding strings have to be same (this could be collisions, but it's not important in my thesis), so we'll have:

a = b

When you now concatenate both strings with a string z, you will have a.z = b.z and their md5-hashes will be the same, because they have the same string-input

md5(a.z) == md5(b.z)

and the md5-hash will a third time be equals while both string inputs are the same

md5(z.a) == md5(z.b)

---

And this is true for md5 and every other hashing algorithm while they have to be deterministic and side effect free.

---

So your example will only make sense when z is a special string which will result in an collision. And therefore the behaviour of md5 and sha1 will exactly be the same: The collision-string appended will result in a collision, but prepended will be different hashes (but there's a really really really low probability you find a collision-string which will be prependend and appended result in an collision, but none example has been yet found in reality) You only didn't find thwo different string with same sha1 because collisions are harder to find as explained by the people before me.