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

501–510 of 524 posts

Re: Announcing the first SHA-1 collision

#501

Post by susam »

lisper wrote: post #403
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…

It's instructive to diff the hexdumps of the two files. It's surprisingly small.

It is small indeed.

    $ diff -u

Re: Announcing the first SHA-1 collision

#502

Post by Aissen »

bbarn wrote: post #229
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?

I don't think that's how averages work. But it's true that relying on the birthday paradox, you can reduce the average. I was just trying to compute the "cloud" cost of 110 GPUs for 1 year (or the equivalent for a day, assuming this is embarrassingly parallel).

Re: Announcing the first SHA-1 collision

#503

Post by yAnonymous »

inetknght wrote: post #162
yAnonymous wrote: post #136

Earlier quoted context omitted.

>This will mess up torrent sharing websites in a hurry. I doubt it. Should this ever become a problem, it would be trivial to change the hashing algorithm. Not worth the effort.

How do you propose to ensure backwards compatibility with the millions of torrents already produced?

Depends on the implementation, which I'm not familiar with, but there are definitely ways to handle that.

Re: Announcing the first SHA-1 collision

#504

Post by Aissen »

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.

I found my mistake g2.8xlarge have 4 GPUs each, so it cuts the cost by 4 (~626k per collision). p2.16xlarge have 16 GPUs (~867k per collision). Exact model of GPU not taken into account, so this could vary widely.

Re: Announcing the first SHA-1 collision

#505

Post by acjohnson55 »

benaiah wrote: post #465
digikata wrote: post #462

Earlier quoted context omitted.

So if one were hashing data or a document format that also contained a bit of self-referential integrity data, e.g. the end of the data has a CRC of the rest of the block, or maybe a cryptographic signature using some other hash, wouldn't that further constrain the search space? Then not only would one need to back out the random bits needed to complete the SHA-1 collision, it would also have to satisfy a some other…

> The best thing would be if one could prove a mathmatically incompatible set of counter functions where data colliding in the hash of one function would prevent the other function from validating correctly. I'm a rank amateur, so this is completely outside of my wheelhouse, but this sounds suspect. I don't think you can make hash collision impossible, even with multiple functions, unless the combined hashes contain…

Right. But there are properties that can be proven about a given hash function that give us more faith that no collision can be efficiently found: https://en.m.wikipedia.org/wiki/Security_of_cryptographic_ha...

Re: Announcing the first SHA-1 collision

#506

Post by Pigo »

tripzilch wrote: post #480
Pigo wrote: post #206

Earlier quoted context omitted.

I really don't see why anyone would go through all this trouble when you can still just put Star_Wars_XIII.exe out there and get 10k downloads.

Because the 10k people that would fall for such a trick (and I don't doubt there's at least 10k of them), are most probably already part of at least 23 other botnets.

I never thought about that potential complication.

Re: Announcing the first SHA-1 collision

#507

Post by [deleted] »

mike_hearn wrote: post #330
xyzzyz wrote: post #315

Earlier quoted context omitted.

You are thinking about this in a wrong way. It is in fact true that being able to generate collisions allows you to break SSL. What you do is this: generate two certificates with colliding hashes, one for google.com, the other for your own domain. Verisign will gladly sign the second one, since you own the domain, but since the hashes match, you can also use the same signature for the first one. Now you can impersona…

Moreover, how quickly we forget! An intelligence agency did in fact carry out such an attack on code signing certificates using an MD5 collision as part of the FLAME malware.

[deleted]

Re: Announcing the first SHA-1 collision

#508

Post by hueving »

digikata wrote: post #474
nneonneo wrote: post #466

Earlier quoted context omitted.

It's a good thought, but if the functions have bounded-length outputs (as with all major hash functions), then your combined hash value is still a bounded length. A collision must therefore exist because there are many more potential messages than potential hash values. If your functions produce unbounded-length hashes, then you may as well just be compressing your input to guarantee there are no collisions in your "…

True - I suppose the hash function just ends up being the convolution of say an interior CRC and some exterior hash function. That gives us low to zero chance of something mathematically provable. But perhaps some arrangement of functions forces an attacker to scramble the inputs in more drastic ways such that the original data must be altered by more than a handful bytes it could perhaps raise the difficulty on a pr…

But to make a strong cryptographic hash, you don't want predictability based on inputs. If you end up with some kind of pattern where getting the same output values requires modifying huge ranges of bytes, that lets attackers reason about inputs that generated a hash.

Re: Announcing the first SHA-1 collision

#510

Post by spiznnx »

nneonneo wrote: post #469
CGamesPlay wrote: post #444

Earlier quoted context omitted.

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

The notion of "document security" is a common desire in business and legal contexts. PDFs are a standard representation of documents, whereas JPGs are less common (TIFF might count since it's a somewhat common scanned document format, but I digress). Subverting the most popular document format, one which even provides built-in support for digital signatures is probably much more interesting than subverting the JPG fo…

I wonder if this is the 'standard' thing to do when you have a broken hash function. I took a introductory course in computer security a year ago and we had to create MD5 hash-colliding documents for homework[0].

[0] https://courses.engr.illinois.edu/cs461/sp2015/static/proj1.... (see part 4)

Post reply on HN