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

41–50 of 369 posts

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

#41

Post by basilgohar »

rustybolt wrote: post #32
martpie wrote: post #29

Earlier quoted context omitted.

You can see their emails at the bottom: those are universities/research institutes domains. You can be sure _they_ did not actually spend that themselves.

I'm just amazed that they were willing to take the risk that there was a bug in the code and they wouldn't find a collision.

It was a sound premise to investigate. EFF spent much more to demonstrate the weakness of DES decades ago, and it highlighted the need for stronger crypto and the fact that nation states would be more than able to break commonly-used crypto at the time.

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

#42

Post by pjc50 »

umvi wrote: post #20

Is "a Shambles" British or something? I've always heard it as "in Shambles"

Yes; in addition to the other comments, there is also the shambles: https://en.wikipedia.org/wiki/The_Shambles

(nowadays devoid of mead products but a nice picturesque place to visit if you can stand crowds. Try the bookshop)

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

#43

Post by bjornsing »

> We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1. In particular, HMAC-SHA-1 seems relatively safe, and preimage resistance (aka ability to invert the hash function) of SHA-1 remains unbroken as of today.

Nice to see this bit of intellectual honesty. Would be even nicer if they had explained what that means in terms of PGP keys.

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

#44

Post by emilfihlman »

>Can I try it out for myself? Since our attack on SHA-1 has pratical implications, in order to make sure proper countermeasures have been pushed we will wait for some time before releasing source code that allows to generate SHA-1 chosen-prefix collisions.

Sigh. Again with this idiocy. All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves.

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

#45

Post by whatshisface »

>A countermeasure has been implemented in commit edc36f5, included in GnuPG version 2.2.18 (released on the 25th of November 2019): SHA-1-based identity signatures created after 2019-01-19 are now considered invalid.

Since SHA-1 was always possible to break, and since NSA probably gets access to big computers and sophisticated techniques before researchers, why doesn't this invalidate every SHA-1 signature ever made and not just ones from last year?

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

#46

Post by toyg »

rkangel wrote: post #8
EGreg wrote: post #5

Earlier quoted context omitted.

It may, because now an attacker can replace code with arbitrary other valid code as long as developers are willing to ignore the long weird random comment at the end ;-) I’m gonna say many developers will not care but and many compilers will not care either. So yeah, Linus’ main deterrent reason (code won’t compile) doesn’t apply anymore. HOWEVER! 1. A chosen-prefix attack still needs to compute TWO suffixes m1 and m…

If you look in this 2017 ( https://marc.info/?l=git&m=148787047422954 ) email from Linux, he discusses how git also encodes length. That would mean that you need a collision of the same length and the right functionality, so you can't just append data.

Now that you can arbitrarily produce collisions, the second step is easy enough for a skilled and well-funded attacker.

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

#47

Post by CiPHPerCoder »

rustybolt wrote: post #32
martpie wrote: post #29

Earlier quoted context omitted.

You can see their emails at the bottom: those are universities/research institutes domains. You can be sure _they_ did not actually spend that themselves.

I'm just amazed that they were willing to take the risk that there was a bug in the code and they wouldn't find a collision.

This is cheap!

Breaking MD5 for the Flame malware probably set the NSA back millions when you sum the person-hours and CPU time together.

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

#48

Post by est31 »

runeks wrote: post #35
est31 wrote: post #23

Earlier quoted context omitted.

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shattered collision already: $ curl https://shattered.io/static/shattered-1.pdf | wc -c 422435 $ curl -s https://shattered.io/static/shattered-2.pdf | wc -c 422435 Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look…

The point is that the hashed data must follow a specific data format, and can’t just be arbitrary data. This means that the collision data MUST contain the length at some specific offset in the data, which makes it harder to find a collision. The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.

Yeah the data must start with a specific prefix, but can otherwise contain whatever it wants. Anyways, even the shattered attack, which this paper says costs 11k to execute today, had a pdf specific prefix (the shown part is the same in both files):

    $ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -n 512 -C 
    00000000  25 50 44 46 2d 31 2e 33  0a 25 e2 e3 cf d3 0a 0a  |%PDF-1.3.%......|
    00000010  0a 31 20 30 20 6f 62 6a  0a 3c 3c 2f 57 69 64 74  |.1 0 obj.>.st|
    00000090  72 65 61 6d 0a ff d8 ff  fe 00 24 53 48 41 2d 31  |ream......$SHA-1|
    000000a0  20 69 73 20 64 65 61 64  21 21 21 21 21 85 2f ec  | is dead!!!!!./.|
The shattered attack was about a so-called "identical prefix" collision, while the shambles paper's collision was a "chosen prefix" one. You can choose it in both cases, but in the "chosen prefix" one both colliding prefixes can be entirely different (and can be as long as you want btw, the attack doesn't cost more if the prefix is 4 KB vs 4 GB), while in the "identical prefix" case it has to be identical.

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

#49

Post by simias »

School-Cotton wrote: post #40
cpach wrote: post #24

Earlier quoted context omitted.

AFAICT ”a shambles” is correct usage. See https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/

Downvoted. There's no ISO standard for English, since language is a social phenomenon. "Correct" language is whatever the community of speakers uses in practice, not what someone claims is correct in a blog post (or even a book).

And the linked article showed you that, in practice, "a shambles" is perfectly correct English. It is therefore correct in a descriptivist sense.

Beyond that prefixing your comment by "downvoted" is frankly silly and only serves to derail the conversation IMO.

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

#50

Post by DarkWiiPlayer »

toyg wrote: post #34
est31 wrote: post #23

Earlier quoted context omitted.

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shattered collision already: $ curl https://shattered.io/static/shattered-1.pdf | wc -c 422435 $ curl -s https://shattered.io/static/shattered-2.pdf | wc -c 422435 Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look…

Yeah, that quote doesn't exactly make me confident about Linus's understanding of this particular issue.

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.
Post reply on HN