Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

CRC32 has hash collisions for the inputs "plumless" and "buckeroo". What's the smallest data length for collisions in MD4, MD5, SHA-1, and the recently accepted SHA-3 (Keccak)? We know that lim_len n->infty p(collision) = 1.0, but I'm curious how large your data has to be before a particular hash algorithm actually experiences a collisions.

Can MD4 collide on blocks less than 100 byes? 1000? 10^10? 10^20? ...

share|improve this question

closed as off topic by rschwieb, Matt N., Thomas, sdcvvc, Jason DeVito Oct 13 '12 at 3:06

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

up vote 1 down vote accepted

The range of MD4 is 128 bits or 16 bytes. That means that it necessarily collides on inputs of length 17 bytes or less. Heuristically, we expect it to collide on inputs of length 9 bytes or less (assuming it approximates a random function).

share|improve this answer
    
Thanks! I was curious because a lot of people are saying that rsync is sufficiently accurate, but I'm starting to think that hash-based syncing is quite risky. –  mcandre Oct 3 '12 at 22:26
    
The probability of collision is rather small. If you generate, say, $2^{50}$ random hashes, then it is very unlikely that there will be any collisions. –  Yuval Filmus Oct 4 '12 at 2:40
    
True, p() is small. But for a given colliding piece of data, hash-based sync software will be unable to sync it. –  mcandre Oct 4 '12 at 12:59
    
Hash-based sync software is an engineering solution - it works and it's efficient. The only other solution is to compare a (losslessly) compressed version of the complete files, or a complete overhaul of the system. –  Yuval Filmus Oct 13 '12 at 18:14

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