Announcing the first SHA-1 collision • Hacker News Board

Re: Announcing the first SHA-1 collision

#221

Post by jakeogh » Thu, Feb 23, 2017, 3:16 PM UTC

stordoff wrote: post #163

prefect42 wrote: post #58

Earlier quoted context omitted.

71 device years, on an p2.16xlarge instance, I think the NSA could certainly come up with something way moar better in a shorter timeframe, assuming they haven't already done so.

> The time needed for a homogeneous cluster to produce the collision would then have been of 114 K20-years, 95 K40-years or 71 K80-years If I'm reading that correctly, 852 (71 * 12) K80 cards gets that down to a month, which sounds well within the reach of NSA et al. Even getting it down to a day (71 * 12 * 30=25,560 cards) seems feasible. Assuming $10k per card ($5k launch price + doubled to account for supporting h…

Any serious effort I assume would use ASIC's.

Re: Announcing the first SHA-1 collision

#222

Post by kuschkufan » Thu, Feb 23, 2017, 3:16 PM UTC

cesarb wrote: post #119

On a quick scroll of the comments, I haven't seen this posted so far: http://valerieaurora.org/hash.html We're at the "First collision found" stage, where the programmer reaction is "Gather around a co-worker's computer, comparing the colliding inputs and running the hash function on them", and the non-expert reaction is "Explain why a simple collision attack is still useless, it's really the second pre-image attack…

Love this page. Someone should remind her to update the table for sha1 now.

Re: Announcing the first SHA-1 collision

#223

Post by koolba » Thu, Feb 23, 2017, 3:18 PM UTC

jakeogh wrote: post #217

koolba wrote: post #214

Earlier quoted context omitted.

> On the other hand it's useful for denial of service. If you want to disrupt a swarm feeding it bad data is 'good enough'. No you can't do that either. Again, this is not a preimage attack: https://en.wikipedia.org/wiki/Preimage_attack That means you can't use this to match an arbitrary SHA-1. That means you can't use it to generate bad parts of a larger file. What you're describing is already possible by having cli…

Thanks, so it can gen 2 same size colliding chunks, but it can not take an arb chunk and generate a collision for it. Right?

Yes that's my understanding of it. In the PDF example on the site, the file format allows enough tweaking to the raw data without impacting the content to make it feasible.

Re: Announcing the first SHA-1 collision

#224

Post by amichal » Thu, Feb 23, 2017, 3:18 PM UTC

Linked http://shattered.io/ has two PDFs that render differently as examples. They indeed have same SHA-1 and are even the same size.

  $ls -l sha*.pdf 
  -rw-r--r--@ 1 amichal  staff  422435 Feb 23 10:01 shattered-1.pdf
  -rw-r--r--@ 1 amichal  staff  422435 Feb 23 10:14 shattered-2.pdf
  $shasum -a 1 sha*.pdf
  38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
  38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

Of course other hashes are different:

  $shasum -a 256 sha*.pdf

  2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  shattered-1.pdf
  d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  shattered-2.pdf 

  $md5 sha*.pdf
  
  MD5 (shattered-1.pdf) = ee4aa52b139d925f8d8884402b0a750c
  MD5 (shattered-2.pdf) = 5bd9d8cabc46041579a311230539b8d1

Re: Announcing the first SHA-1 collision

#225

Post by sp332 » Thu, Feb 23, 2017, 3:19 PM UTC

Aissen wrote: post #169

sp332 wrote: post #129

Earlier quoted context omitted.

If you find a collision for the smallest piece, you don't need to find collisions for any higher nodes on the Merkle tree because you'll just be hashing the same values as the legit version.

Then this smallest piece must also change the file type to an executable, and contain a meaningful payload.

Well, you could put most of the payload in other parts of the file. People probably wouldn't notice if they didn't go looking. And the small part could exploit a popular codec instead of being an executable itself.

Re: Announcing the first SHA-1 collision

#226

Post by stiaje » Thu, Feb 23, 2017, 3:20 PM UTC

sah2ed wrote: post #164

> "Today, 10 years after of SHA-1 was first introduced, ..." That part from the original article seems to be missing something?

It must be supposed to say 10 years after first known collision of SHA-1 or something.

Re: Announcing the first SHA-1 collision

#227

Post by rakoo » Thu, Feb 23, 2017, 3:23 PM UTC

koolba wrote: post #69

anilgulecha wrote: post #59

Earlier quoted context omitted.

Create 2 torrents with the same hash. Release one into the wild. Wait. Infect.

Torrents have a tree of hashes for the parts. That allows validating pieces without the entire file (which is also validated at the end). Probabilistically, the hashes of the parts would not match even if the top level hash matched.

It's technically true to speak of a tree, but it's less misleading to say it's a list

Re: Announcing the first SHA-1 collision

#228

Post by ratstew » Thu, Feb 23, 2017, 3:24 PM UTC

I got a chuckle out of the binary diff. :)

http://i.imgur.com/OmFHELl.png

Re: Announcing the first SHA-1 collision

#229

Post by bbarn » Thu, Feb 23, 2017, 3:24 PM UTC

Aissen wrote: post #196

Anyone good enough in AWS pricing can reproduce the $100k pricing for one collision ? Using EC2 g2.xlarge instances I'm more at $2.8M.

This would still be just an average, right? Isn't it 0$ to $2.8M depending on luck?

Re: Announcing the first SHA-1 collision

#230

Post by x1798DE » Thu, Feb 23, 2017, 3:24 PM UTC

sangnoir wrote: post #137

jgrahamc wrote: post #95

How am I going to explain this to my wife? Actually a serious question. How do we communicate something like this to the general public?

> How am I going to explain this to my wife? Someone has discovered a computational equivalent of bypassing tamper-proof seals, but only a specific brand of seals (SHA1) which is very currently popular. Other types of seals still work fine. This means we can no longer trust if the cake from the baker hasn't been tampered with even though the packaging it comes in has an intact SHA1 seal, we should therefore demand th…

Er, if I'm following your metaphor correctly, you seem to be implying that if I create something and "seal" it, then send it along, that you can no longer trust it because someone may have tampered with it. That is not an accurate assessment of this vulnerability. The attacker needs to construct both the "good" and the "bad" document in order for this to work.

In non-technical terms I guess it's more like getting a document notarized with an embossed stamp or something, and this vulnerability is something that allows you to create a special document where you can get the stamp to apply to two documents at the same time (maybe one of them could be a document accepting $100 inheritence, and the hidden one is a document signing over the title of your house).

It's a bit hard to explain why this matters because most people have no non-technical equivalent of the sort of thing that this would matter for, because people use fuzzy social proofs where forgery isn't out of the question anyway (even notarized documents don't really have any indication of the contents of the document, as far as I can tell).