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

61–70 of 369 posts

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

#61

Post by est31 »

DarkWiiPlayer wrote: post #50
toyg wrote: post #34

Earlier quoted context omitted.

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.

> 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
    of the original message.  The padded message is then processed by the
    SHA-1 as n 512-bit blocks.
Now, storing the length as a prefix does give you advantages: you can't mount a length extension attack, which limits your ability to exploit one shattered attack, e.g. the pdfs released by google, for different files/types of files. But it doesn't make mounting a novel shattered attack "much harder" as Linus claims.

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

#62

Post by fireflash38 »

CiPHPerCoder wrote: post #15
ebg13 wrote: post #7

Quick question about the "What should I do" section. It says " use instead SHA-256 ". Isn't SHA-512 both better and faster on modern hardware?

SHA-256 and SHA-512 are both in the same family (SHA-2). Latacora says to use SHA-2. If you can get away with it, SHA-512/256 instead of SHA-256. But they're all SHA-2 family hash functions. https://latacora.micro.blog/2018/04/03/cryptographic-right-a... No need to bikeshed this. But if you must: SHA-512/256 > SHA-384 > SHA-512 = SHA-256 If you're wondering, "Why is SHA-384 better than SHA-512 and SHA-256?" the answe…

I read the blog, but it doesn't really expand on why SHA224/384 aren't vulnerable to that attack, can you explain (or link to some place that does?)

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

#63

Post by bjornsing »

bjornsing wrote: post #53
groovybits wrote: post #10

Earlier quoted context omitted.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

> you have to be able to also edit the size field in the header.” As I read the OP [1] a chosen-prefix collision attack such as this allows you to “edit the size field in the header”. Or am I missing something? 1. “A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is the…

A few emails forward in the thread Linus explains though why we don’t need to worry much about this attack in practice: https://marc.info/?l=git&m=148787287624049&w=2

This argument sounds sound to me.

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

#64

Post by claudiawerner »

pjc50 wrote: post #42
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)

I live in York and I haven't actually gone into any shops in the Shambles...

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

#65

Post by _notreallyme_ »

bjornsing wrote: post #43

> 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.

It means if someone you want to impersonate uses the Web Of Trust, i.e. their key is signed by other people whose keys have been signed the same way, you can generate a GPG key for which all of these signatures are still valid.

For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts.

This would defeat an adversary "paranoid" enough to check a key signature, but not paranoid enough to obtain a clear explaination/confirmation of why the key changed...

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

#66

Post by Boulth »

whatshisface wrote: post #45

> 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…

Actually it's even worse than that: signature creation time is added by the signer so it's totally under control of the attacker. IMHO all SHA-1 based signatures should be ignored.

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

#67

Post by CydeWeys »

rustybolt wrote: post #28
oppositelock wrote: post #25

Earlier quoted context omitted.

That's dirt cheap for a government actor, and we can be sure that the big governments have been doing this sort of attack for years.

It's a lot of money for an academic researcher.

Is it? Multi-million grants are common in academia. A lot of research is expensive. When I worked in a lab the materials alone for a single day's experiment would frequently run into the thousands. E.g. the total human RNA samples we used cost many thousands of dollars per milligram. Admittedly this is a different field, but it's still academia.

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

#68

Post by School-Cotton »

simias wrote: post #49
School-Cotton wrote: post #40

Earlier quoted context omitted.

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.

"a shambles" is not used (or quite rarely used) in North America, in my experience. Which was what the OP was asking about.

You are of course right that "a shambles" is perfectly fine British English, but that's beside the point.

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

#69

Post by colanderman »

CiPHPerCoder wrote: post #15
ebg13 wrote: post #7

Quick question about the "What should I do" section. It says " use instead SHA-256 ". Isn't SHA-512 both better and faster on modern hardware?

SHA-256 and SHA-512 are both in the same family (SHA-2). Latacora says to use SHA-2. If you can get away with it, SHA-512/256 instead of SHA-256. But they're all SHA-2 family hash functions. https://latacora.micro.blog/2018/04/03/cryptographic-right-a... No need to bikeshed this. But if you must: SHA-512/256 > SHA-384 > SHA-512 = SHA-256 If you're wondering, "Why is SHA-384 better than SHA-512 and SHA-256?" the answe…

I'm super confused. Are SHA-256 and SHA256 different, and if so, why in the world would this be considered a sane naming scheme?

If not, I completely do not understand the inequation you wrote, which seemingly lists SHA-256 (and -512) multiple times.

Post reply on HN