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

Announcing the first SHA-1 collision

security.googleblog.com

Post reply on HN
Print view View original

451–460 of 524 posts

Re: Announcing the first SHA-1 collision

#451

Post by bobbyyankou »

detaro wrote: post #434
bobbyyankou wrote: post #428

Can someone help me understand what the major distinction is between this accomplishment (SHAttered) and the same team's The SHAppening (2015)? It looks like the did the same thing or something similar in 2^57.5 SHA1 calculations back then versus 2^63 SHA1 calculations this time.

SHAppening was a freestart collision, this is a "full" one. This stack overflow answer looks like a good description of freestart collisions: https://crypto.stackexchange.com/questions/29695/what-is-a-f... My attempt at TL;DR: SHA-1 works on blocks, and each block is processed and it's data "mixed" with a previous intermediate result based on the previous blocks (Merkle-Damgård construction). A freestart collision on…

Ah, cool. I didn't notice the distinction between freestart and full. Thanks for that link; it was very helpful.

Re: Announcing the first SHA-1 collision

#452

Post by manacit »

CGamesPlay wrote: post #444
nneonneo wrote: post #325

The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…

Great analysis. So why did Google choose to use PDFs instead of JPGs directly?

Because many automated systems/image hosting website (imgur, etc) will process JPEGs to optimize them, which I assume would no longer cause there to be a collision.

On the other hand, PDFs are almost universally sent as-is, increasing the risk of being able to 'fool' someone.

Re: Announcing the first SHA-1 collision

#453

Post by xapata »

andreyf wrote: post #415
bo1024 wrote: post #414

Earlier quoted context omitted.

> UPDATE: some people are raising the possibility of hashes where some values have 1 or 0 preimages, which makes second and first preimage attacks formally impossible. Yes, such hashes are possible (in fact trivial) to construct, but they are not cryptographically secure. One of the requirements for a cryptographically secure hash is that all possible hash values are (more or less) equally likely. True, but the main…

> in fact on average they have to have gazillions of pre-images each pretty sure "on average" they have at least a few gazillion orders of magnitude more than a few gazillion pre-images each ;)

You're saying the average of infinities is a gazillion gazillion?

For any hashcode, there are an infinite number of documents that would result in that hashcode.

Re: Announcing the first SHA-1 collision

#456

Post by HarrietJones »

nneonneo wrote: post #398
jwilk wrote: post #391

Earlier quoted context omitted.

Thanks! What tools did you use to analyse the JPEG?

I used Hachoir ( https://github.com/haypo/hachoir3 ), a Python library that I've contributed to. Hachoir disassembles files using a library of parsers, with the intent of describing the function of every single bit in the file. You can see the resulting disassemblies (rendered with the hachoir-wx GUI) here: http://imgur.com/a/F1cnV

I've just started disassembling a report file format. In python. This is going to be so useful. Thanks!!

Re: Announcing the first SHA-1 collision

#457

Post by aphextron »

gcp wrote: post #32
jasode wrote: post #16

>Nine quintillion computations; 6,500 years of CPU; 110 years of GPU Is there a rough calculation in terms of today's $$$ cost to implement the attack?

Say you want to replicate this in 1 month, you need 1320 GPUs for a month. They didn't specify which ones, but say at 1000 bucks per GPU, that's a 1.3M USD investment. And some pocket change for power etc. There isn't anything new about this result actually, Google just set aside the necessary resources to demonstrate it.

>There isn't anything new about this result actually, Google just set aside the necessary resources to demonstrate it.

I think that was the point. Google wanted to show that anyone with sufficient resources could easily pull this off.

Re: Announcing the first SHA-1 collision

#458

Post by lilyball »

ddlatham wrote: post #402
lilyball wrote: post #376

Earlier quoted context omitted.

If you can do a first-preimage attack, then just keep doing it until you get a distinct document. I'm not sure what sort of first-preimage attack you have in mind that is only capable of producing a single preimage for any hash.

Since the parent was claiming that first-preimage attacks were strictly more severe, which seems to be a theoretical claim for all possible first-preimage attacks, I was pointing out that doesn't necessarily hold. First-preimage attacks are not guaranteed a priori to be able to produce multiple distinct documents for a given hash.

I think the argument here is twofold:

1) If you have some first-preimage attack against a hash, that attack can probably be "continued" such that it produces multiple preimages.

2) Even if your attack can only ever produce one preimage, since there's an infinite number of documents that can produce the same hash, it's vanishingly unlikely that your attack will produce the exact preimage that you already have (note: this is assuming a cryptographically secure hash, where all outputs are equally likely). Therefore, even if you can only get one preimage, it's still almost certainly a second preimage.

Re: Announcing the first SHA-1 collision

#459

Post by cestith »

stcredzero wrote: post #425
makomk wrote: post #336

Earlier quoted context omitted.

Or, if you're really clever - and Ange Albertini is quite good at this kind of trick - you can design the PDF so that the different garbage in the middle causes the other, unchanged content to be interpreted differently in the two PDF files, possibly even designing it so that the intended contents of each PDF is treated as garbage and ignored entirely in the other PDF.

With many image formats, you can just concatenate whatever you want at the end of the file, and the OS and programs will obliviously read and copy the whole file, while the image libraries will happily ignore the extra data.

And then you put PHP tags in that content at the end, and change the .htaccess file to process *.jpeg as PHP scripts, and your webshell looks benign until someone has that in mind looking through the account.

Re: Announcing the first SHA-1 collision

#460

Post by Lord_Yoda »

pfg wrote: post #372
Lord_Yoda wrote: post #364

As I consumer how do I identify sites which are vulnerable? What should I do to protect my data?

Recent versions of Chrome will show a warning if you try to browse to a site that uses a SHA-1 certificate. Mozilla is doing the same thing as of Firefox 51, but they're enabling this gradually to measure impact. Microsoft has an update ready to disable SHA-1 support in their browsers - I think it was delayed a few days ago due to some issues (not sure if they were related to disabling SHA-1). You can use [1] to test…

Thanks!
Post reply on HN