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

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

Post reply on HN
Print view View original

171–180 of 369 posts

Re: The first chosen-prefix collision for SHA-1

#171

Post by mehrdadn »

saurik wrote: post #108
tambourine_man wrote: post #76

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in t…

FWIW, a lot of very smart people seem to think that we actually do have symmetric encryption in a state where it "works" and is "understood" and that AES is unlikely to be "broken". What we don't really feel so great about is asymmetric encryption, but at least that feels like something P != NP might imply can be done... hashing algorithms just have this problem where if you glance at the information theory you would…

> something P != NP might imply can be done... hashing algorithms just have this problem where if you glance at the information theory you would have guessed they couldn't be possible until someone shows you one that seems to work

I'm confused what you mean by this? Why does the info theory suggest hashing wouldn't be possible? Also, you can easily derive a secure hash function from a secure symmetric cipher and vice-versa, so why would one seem to be possible but not the other?

Re: The first chosen-prefix collision for SHA-1

#172

Post by pathseeker »

saalweachter wrote: post #144
flatiron wrote: post #135

Earlier quoted context omitted.

yeah my thoughts about git are similar. look at the two messages they have an an example: Key is part of a collision! It's a trap!yE'NsbK#ދW]{1gKmCx's/vr| -pJO_,1$)uB1qXv#U)9ESU;p~0G:Y ݕbBIjFra눰3&t'lB_!h5M([,˴QMK#|o5pv|i,+yYpݍD7_Rf\'GUZ, ϵdvAYAugV=Lk8_E 2 +nolBtxXoQt&+?Y3LP:'Qt(,ۛuԪWJm:A"M6 and Practical SHA-1 chosen-prefix collision!'lka}vbI3,·W]Ǟ+gK}Cxs/v&r| }-hRJO_ rO̳;bzC ,1&uRP-MXrU3aO;pr0:sY'2 l&r7#(A{oNyCJ_W,8…

Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.

Depends on if the chosen prefix attack allows the content to appear arbitrarily in the middle of the byte stream like that.

Re: The first chosen-prefix collision for SHA-1

#173

Post by flatiron »

saalweachter wrote: post #144
flatiron wrote: post #135

Earlier quoted context omitted.

yeah my thoughts about git are similar. look at the two messages they have an an example: Key is part of a collision! It's a trap!yE'NsbK#ދW]{1gKmCx's/vr| -pJO_,1$)uB1qXv#U)9ESU;p~0G:Y ݕbBIjFra눰3&t'lB_!h5M([,˴QMK#|o5pv|i,+yYpݍD7_Rf\'GUZ, ϵdvAYAugV=Lk8_E 2 +nolBtxXoQt&+?Y3LP:'Qt(,ۛuԪWJm:A"M6 and Practical SHA-1 chosen-prefix collision!'lka}vbI3,·W]Ǟ+gK}Cxs/v&r| }-hRJO_ rO̳;bzC ,1&uRP-MXrU3aO;pr0:sY'2 l&r7#(A{oNyCJ_W,8…

Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.

anyone checking diffs would notice that, or working on the file, etc. it wouldn't survive long

Re: The first chosen-prefix collision for SHA-1

#174

Post by pathseeker »

LeonM wrote: post #4
0x0 wrote: post #2

Q: Does this make it even more urgent for git to move to a different hash?

A: (from the article) SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Attacks only get better over time, and the goal of the cryptanalysis effort is to warn users so that they can deprecate algorithms before the attacks get practical. We actually expect our attack to cost just a couple thousand USD in a few years.

That's not a relevant answer. Git's use-case is very specific and it's quite possible that this attack won't be relevant. It needs analysis.

>no good reason to use this hash function in modern security software

This argument conveniently ignores the cost to switching existing software (i.e. it's completely detached from reality).

Re: The first chosen-prefix collision for SHA-1

#175

Post by munk-a »

FactolSarin wrote: post #121
jlokier wrote: post #102

Just a curiosity, since people are talking about Git still using SHA-1 (despite work on SHA-256 since 2017). I see that Git doesn't actually use SHA-1 any more, it uses "hardened SHA-1": https://stackoverflow.com/questions/10434326/hash-collision-...

How would an attack on a git repo work? You create a repo with identical hashes but different content and next time the user clones from scratch they get your modified version?

If you could push up a commit that computed to the same hash of the last tagged release in a repo... I'm not certain, the tag might end up referencing the new object? Certain versions of git (i.e. maybe git for windows) may also react in different manners.

In theory you might get people building software packages for distros to build your malicious version, you may also just temporarily shut down the ability for anyone to check out the version (basically denial of service for making?) but the time window would be weird.

Re: The first chosen-prefix collision for SHA-1

#176

Post by tialaramex »

rst wrote: post #118
jlokier wrote: post #102

Just a curiosity, since people are talking about Git still using SHA-1 (despite work on SHA-256 since 2017). I see that Git doesn't actually use SHA-1 any more, it uses "hardened SHA-1": https://stackoverflow.com/questions/10434326/hash-collision-...

Well, according to that reference, it's hardened against a specific, previously known attack. Do you have any information on whether that also protects against the different, new attack which was just published?

Not so much the specific attack, as the broad class of attacks. I think this new work is in that same broad class but I am not a mathematician.

The idea in Marc Stevens' anti-collision work is that some inputs are "disturbance vectors" which do unusual things to the SHA-1 internals, and we want to detect those and handle that case specially since there is almost no chance of that happening by accident. It has a list of such vectors found during his research.

This paper doesn't talk about "disturbance vectors" but it does discuss ideas like "Boomerangs" which I think ends up being similar - I just don't understand the mathematics enough to know whether that means "the same" or not.

Re: The first chosen-prefix collision for SHA-1

#177

Post by saalweachter »

flatiron wrote: post #173
saalweachter wrote: post #144

Earlier quoted context omitted.

Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.

anyone checking diffs would notice that, or working on the file, etc. it wouldn't survive long

Hmmm, does the garbage string actually have to survive long?

If there's a followup CL to "delete a garbage string that accidentally made it into the repo", which doesn't actually fix whatever else was added, would that get you anywhere?

Re: The first chosen-prefix collision for SHA-1

#178

Post by magicalhippo »

est31 wrote: post #61
DarkWiiPlayer wrote: post #50

Earlier quoted context omitted.

It's not about it being the same length, but the length of the data being part of the hashed data, which, Linus assumes, will likely make it more difficult to find a collision. He even says at the beginning that he hasn't had a look at the attack yet and is just making an assumption.

> It's not about it being the same length, but the length of the data being part of the hashed data As I tried to point out, the length is already part of what the SHA-1 function hashes: https://tools.ietf.org/html/rfc3174#section-4 As a summary, a "1" followed by m "0"s followed by a 64- bit integer are appended to the end of the message to produce a padded message of length 512 * n. The 64-bit integer is the length…

> But it doesn't make mounting a novel shattered attack "much harder" as Linus claims.

From what I understood the core of Linus' argument[1] is that it's very hard to make a "bad" variant of the code which has the same length _and_ the same hash while still looking like sane code. For random data files, sure those are more at risk.

[1]: https://marc.info/?l=git&m=148787287624049&w=2

Re: The first chosen-prefix collision for SHA-1

#179

Post by Izmaki »

tambourine_man wrote: post #76

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in t…

No, the bridge collapsed because it was never touched again after initial deployment, for 10 years. How are buildings doing in Chernobyl? Don’t neglect your data, if you want to keep it safe always. :P
Post reply on HN