News for hackers. Stuff that matters.

A comment on Announcing the first SHA-1 collision. Parent comment

Re:Announcing the first SHA-1 collision by jeeceebees on Thursday February 23, 2017 @10:56PM (#13720833)
Wouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions?

Why does the pigeonhole principle hold?

[ Parent | on HN ]
Re:Announcing the first SHA-1 collision by glitch003 on Thursday February 23, 2017 @11:02PM (#13720879)
Yes, this is correct. It's a really simple principle, and I think an explanation can help you understand :)

Suppose you have 3 holes, and 4 pigeons, and you stuff the pigeons into holes. There must be 1 hole with at least 2 pigeons, right?

The same is true with hash functions. If you're hashing data down to a fixed length, like say 256-bits with sha-256, and the data is longer than 256 bits, there must be a collision somewhere.

[ Parent | on HN ]
Re:Announcing the first SHA-1 collision by userbinator on Thursday February 23, 2017 @11:05PM (#13720892)
Wouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions?

Yes, they do. Finding them is the hard part.

[ Parent | on HN ]
Re:Announcing the first SHA-1 collision by clarkcox3 on Friday February 24, 2017 @04:34PM (#13728128)
Yes; by definition using something with X possible values to represent something with Y possible values will always have collisions if X < Y.
[ Parent | on HN ]