Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Possible Duplicate:
Collision rate for different hash algorithms

Many hashing algorithms seem to have fixed-length message digest as output.

If I compute the md5 hash of two strings:

>>> hashlib.md5("This is a really really long text string to make a hash out of").hexdigest()
'2916991b5ebba69ab38a84a0a72b4176'

>>> hashlib.md5("Short").hexdigest()
'30bb747c98bccdd11b3f89e644c4d0ad'

I get an output that is 32 characters long for each, even though there is a significant difference in the lengths of the inputs. Is it theoretically possible that I could come up with two (or more) completely different inputs that generate the same output, since there are infinite possibilities for an input and only a finite number of characters to work with for the output?

If yes, what is the likelihood of finding another input that would generate the same output?

share|improve this question

marked as duplicate by Rory Alsop Jul 2 '12 at 22:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
The real trick isn't finding a collision, it is finding a collision that maps to a data that is actually useful, and wouldn't be immediately recognized as crap. Which isn't impossible, particularly for MD5(). en.wikipedia.org/wiki/Collision_attack en.wikipedia.org/wiki/MD5#Collision_vulnerabilities –  Zoredache Jul 2 '12 at 22:38
1  
I think this question is entirely covered by the existing one - which covers collision rates. –  Rory Alsop Jul 2 '12 at 22:38

1 Answer 1

up vote 2 down vote accepted

Is it theoretically possible that I could come up with two (or more) completely different inputs that generate the same output, since there are infinite possibilities for an input and only a finite number of characters to work with for the output?

Yes, its theoretically possible. But hash functions are so designed to make it practically difficult. When I say practically difficult, I mean it will take immense compute cycles (which translates to money and time) to compute a collision.

If yes, what is the likelihood of finding another input that would generate the same output?

This depends on the hash functions. The property is called Collision Resistance

To depict via an example, lets construct a hash function which hashes numbers into a resulting smaller address-space [0, 9]. Our simple hash function is hash(X) = X mod 10. Hence

hash(10)   = 0
hash(1864) = 4

This is a valid hash function but has very poor collision resistance. For example, hash of 24 and 1284 is the same. If you are relying on the hash(4 in this case) for the integrity of the message, a attacker can safely replace the message 24 to 1284 which hashes to the same value. This particular attack is called a Preimage attack Preimage collision resistance is a prime property of any hash function.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.