Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SHA-1 'fully and practically broken' by new collision (2020)

duo.com

Post reply on HN
Print view View original

21–30 of 210 posts

Re: SHA-1 'fully and practically broken' by new collision (2020)

#21

Post by akomtu »

fwip wrote: post #14
motohagiography wrote: post #13

Earlier quoted context omitted.

I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#22

Post by __s »

ganzuul wrote: post #19
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Natural data is easily identifiable.

That's because natural data has low entropy

But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are

ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize

It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward

edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev

Re: SHA-1 'fully and practically broken' by new collision (2020)

#24

Post by dTal »

ganzuul wrote: post #19
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Natural data is easily identifiable.

Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#25

Post by cletus »

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it.

I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)?

It just seems like such a massive and foreseeable oversight that's going to cause pain for some time to come for really no reason at all.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#26

Post by AnimalMuppet »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

Can you create an intentional collision, and also have the counterfeit have compilable code? (Or, in other circumstances, intelligible English text?)

Re: SHA-1 'fully and practically broken' by new collision (2020)

#27

Post by hyperpape »

akomtu wrote: post #21
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.

Ignoring punctuation, capitalization and spaces, you have

(26 ^ 1024) / (2 ^ 160) ascii texts, which is too large for python to do the division.

Thinking harder, that's:

>>> (13 * (160)) * (26 ** (1024 - 160)) 586015382205826960727672544401463871212215837535709025412643135464856100047507808667927549205890681326798481562717865671371914861707033271010401105757243098374422354323280335989456977123883814519788789676409601028611595593846201622073508573113400508407626532918150795408521721900638322896979964584478287370459866751451622413984067802115006844002721198098126119299044037305285971873899685570443731713584345786693414215895940310733413089663439828136700053588516077484775302179979357918243214847406310224703621807862576801557249657421436718532619781248154845297450962161296162654285951879462181582579086975207170674079727507724939279192338763731562331681240184746490930657625088527012496974579965412172847315257089070105214466289197177909463176672954181773739345690793807307314187284671422149249630372138364687234076394633405015375177710973043617082884089261346079718819448519032937091364439564690325014717871376537803759701695837030040255807318892621674241958398030180530294671920834183657715967728968579955163053146309746677182369005157209730333605691785063279407829717681098919238400049142795696195708090541066855775773950462556018168019660329830112434789524857886670766484791538540247307849949305926757172442880517278313785940979709167536140659937329357336156000509320395656047604973761134700992358740522602445520136787846575269569119611476145342798153931437530464566322510167663230985347176517861376

If you restrict it to words, assume that there's only 1000 words in the English language, averaging 5 letters each, you get:

(1000 ^ 200) / (2 ^ 160) which becomes:

>>> (500 ** 160) * (1000 ** 40) 684227765783602085411977335590779360976690401306892466678255997993062052092705371819647552911192178726196289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

There will be massive numbers of realistic texts that match any given hash.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#28

Post by alerighi »

cletus wrote: post #25

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying abo…

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine.

Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the reasons git was created was speed for large project like the Linux kernel) for no real purpose. If you want to change the algorithm, given that you will break compatibility with all existing repositories, tools, and clients, you make a fork of git because you are changing too much.

I don't see why migrating to SHA-256. The collisions are still very unlikely to generate accidentally, and sure, if you want to do damage to a repository you can create one on purpose, as you can as well commit some hooks that contains malware, or alter the git history in any way you want, so what's the point?

Re: SHA-1 'fully and practically broken' by new collision (2020)

#29

Post by [deleted] »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

[deleted]

Re: SHA-1 'fully and practically broken' by new collision (2020)

#30

Post by dTal »

akomtu wrote: post #21
fwip wrote: post #14

Earlier quoted context omitted.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.

The pigeonhole principle forbids it, since the hash itself is an ASCII message under 1KB long. Even within your message constraints, the message can contain contain any possible hash, and more besides. Therefore there are more valid messages than hashes.
Post reply on HN