undefined | Better HN

0 pointsJoshTriplett9y ago0 comments

> Is it a very difficult technical problem to switch, or just a problem of backward compatibility for existing repos (i.e., it would be expensive to change everything over)?

A bit of both. Git has an ongoing effort to replace everywhere in the source code that passes around SHA1s as fixed-size arrays of bytes with a data structure. That'll make it possible to replace the hash. But even with that work, git will still need to support reading and writing repositories in the existing format, and numerous interoperability measures.

0 comments

jordigh9y ago

Mercurial hasn't switched either for similar reasons, although the format did reserve space for a bigger hash (32 bytes over sha-1's 20 bytes) since 2006, less than a year into hg's existence.

glandium9y ago

Worth noting, though, that while mercurial local storage can accomodate larger hash digests, the exchange protocols don't.

andy_ppp9y ago

Linus suggested changing the hash algorithm doesn't need these changes, just take the first 160 bytes of a SHA2 or whatever and use that. The chances of collisions would still be less than SHA1.

JoshTriplettOP9y ago

You'd still have to do the second half of the work, namely building the interoperability and migration mechanisms.

Ericson23149y ago

That's the far larger half too.

glandium9y ago

... and policy. Because now you can have collisions between sha-1 and whatever else you pick.

Dylan168079y ago

Not yet you can't.

yuhong9y ago

Any 160-bit hash can generate a collision in 2^80 time though.

rspeer9y ago

I think the more important collision to worry about in 2^80 time is the Earth colliding with the Sun.

Our interstellar successors, if any, will probably have found something better than Git to use.

EDIT: I should be clear that I'm not making the usual silly claim that we don't need to worry about hashes being broken because they take forever to brute force. I'm saying that hashes will be broken, but not by brute forcing the entire hash space. A decade or so of cryptographic research will save you eons of compute time.

Dylan168079y ago

2^80 time is not as much as you think it is. The bitcoin network is currently calculating about 3 * 2^60 hashes per second. It can do 2^80 hashes in under a week.

The 2^80 space cost of doing a birthday attack is a lot more notable, but it's not unfeasible either. Yearly hard drive production is somewhere around 2^70 bytes. You're not pulling that attack off in the year 2017 but a big budget you could get probably get there in a few decades.

1 more reply

j / k navigate · click thread line to collapse

0 comments

jordigh9y ago

Mercurial hasn't switched either for similar reasons, although the format did reserve space for a bigger hash (32 bytes over sha-1's 20 bytes) since 2006, less than a year into hg's existence.

glandium9y ago

Worth noting, though, that while mercurial local storage can accomodate larger hash digests, the exchange protocols don't.

andy_ppp9y ago

Linus suggested changing the hash algorithm doesn't need these changes, just take the first 160 bytes of a SHA2 or whatever and use that. The chances of collisions would still be less than SHA1.

JoshTriplettOP9y ago

You'd still have to do the second half of the work, namely building the interoperability and migration mechanisms.

Ericson23149y ago

That's the far larger half too.

glandium9y ago

... and policy. Because now you can have collisions between sha-1 and whatever else you pick.

Dylan168079y ago

Not yet you can't.

yuhong9y ago

Any 160-bit hash can generate a collision in 2^80 time though.

rspeer9y ago

I think the more important collision to worry about in 2^80 time is the Earth colliding with the Sun.

Our interstellar successors, if any, will probably have found something better than Git to use.

Dylan168079y ago

2^80 time is not as much as you think it is. The bitcoin network is currently calculating about 3 * 2^60 hashes per second. It can do 2^80 hashes in under a week.

1 more reply

j / k navigate · click thread line to collapse