Hacker News Reader

Comment by byteCoder | Hacker News Reader

Following the tradition of sports, I propose that commit id e83c5163316f89bfbde7d9ab23ca2e25604af290 be officially retired.

View on HN

Done. Don't ask me how I did it, but you will never see that hash come up again naturally during your lifetime.

it is SHA-1 though, might still be broken during our liftime

Which is why he added the caveat "naturally".

Given that the only way to reuse it is to duplicate the tree and commit metadata exactly, or find an sha1 collision, I think it's pretty safe. :)

I wonder if there are any git sha1 collisions out there in aggregate, say across all of github. Would they even notice if there were?

>I wonder if there are any git sha1 collisions out there in aggregate, say across all of github.

Despite the incredibly high number of all commits there must be, I think the chance of a collision is still very unlikely. 2^160 is a pretty big number.

The number of inputs before a likely collision is more on the order of 2^80. Which is still pretty large.

True, the birthday paradox definitely makes it a lot more likely, but as you say the odds should still be too low.

This is comparable to the number of atoms in the universe. Pretty large! We will never see an accidental collision.

Not quite, atoms in the universe is in the range of 10^80, which is a bit less than 2^266.

On the other hand, 2^80 is "only" approx. 1.2 * 10^24. Still, good luck colliding with that without big effort.

There's a table in http://en.wikipedia.org/wiki/Birthday_attack which gives some numbers, but it's missing the 160-bit entry. Nevertheless, even the number of 128 bits hashes required for a random collision are extremely high.

In hindsight, it's good that git didn't choose MD5, since collisions for MD5 can be generated almost trivially now. However, the decreasing security of SHA-1 could be a concern for the future.

I don't think commit hash was ever intended to be cryptographically secure. It's just a unique identifier.

> Source control management systems such as Git and Mercurial use SHA-1 not for security but for ensuring that the data has not changed due to accidental corruption. Linus Torvalds has said about Git: "If you have disk corruption, if you have DRAM corruption, if you have any kind of problems at all, Git will notice them. It's not a question of if, it's a guarantee. You can have people who try to be malicious. They won't succeed. [...] Nobody has been able to break SHA-1, but the point is the SHA-1, as far as Git is concerned, isn't even a security feature. It's purely a consistency check. The security parts are elsewhere, so a lot of people assume that since Git uses SHA-1 and SHA-1 is used for cryptographically secure stuff, they think that, OK, it's a huge security feature. It has nothing at all to do with security, it's just the best hash you can get.

http://en.wikipedia.org/wiki/SHA-1#Data_integrity

Too bad he didn't use SHA-256 though. It had been available for three years at that moment.

According to the Wikipedia entry[0], "No actual collisions have yet been produced", github or otherwise. The NSA might have produced them, but publicly non have been found, and it's not for lack of trying.

[0] http://en.wikipedia.org/wiki/SHA-1

I take that statement to imply "on purpose", or as part of an attack. You can't know whether there's a coincidental collision anywhere in github unless you bother to look. But I do understand that it's still extremely improbable.

In a thousand years, a git sha-1 collision is going to cause a lot of trouble.

Every commit id is pretty much automatically retired. The odds of collisions in our lifetime are pretty small.

Or am I over-thinking it?

Yeah, I'm pretty sure it was a joke.

I was under the impression that git hashes are generated based on the contents in a commit. If that's true you cannot retire them. They're not random.

While that is true, part of the contents that is hashed is the time of commit. Therefore if you (somehow...) managed to get that hash, you could just reset and commit again. Or amend.

In any case, I believe he was joking. The odds of a sha1 collision are very very low.

Very low indeed. Chance of SHA1 collision is of the order of 2^52. One person explained it this way: Chance of everyone currently on Earth winning a jackpot in their lifetime is actually higher than a single random SHA1 collision. It should be actually mind boggling how many of the software systems and algorithms rely on hashes and them being not collided.

I think it is 2^61 now, the paper that once showed the 2^52 attack has removed the claims.

Reply on news.ycombinator.com