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

491–500 of 524 posts

Re: Announcing the first SHA-1 collision

#491

Post by userbinator »

It's interesting to note that when the first MD5 collisions were discovered a bit over a decade ago, they were computed by hand calculation. Next came the collision generators like HashClash/fastcoll (remember these?) which could generate colliding MD5 blocks within a few seconds on hardware of the time. I wonder how long it will be before the same can be done for SHA-1, because it seems here that they "simply" spent a large amount of computing power to generate the collision, but I'm hopeful that will be reduced very soon.

As for what I think in general about it: I'm not concerned, worried, or even scared about the effects. If anything, inelegance of brute-force aside, I think there's something very beautiful and awe-inspiring in this discovery, like solving a puzzle or maths conjecture that has remained unsolved for many years.

I remember when I first heard about MD5 and hash functions in general, and thinking "it's completely deterministic. The operations don't look like they would be irreversible. There's just so many of them. It's only a matter of time before someone figures it out." Then, years later, it happened. It's an interesting feeling, especially since I used to crack softwares' registration key schemes which often resembled hash functions, and "reversing" the algorithms (basically a preimage attack) was simply a matter of time and careful thought.

There's still no practical preimage for MD5, but given enough time and interest... although I will vaguely guess that finding SHA-256 collisions probably has a higher priority to those interested.

Re: Announcing the first SHA-1 collision

#492

Post by glitch003 »

jeeceebees wrote: post #490
versteegen wrote: post #485

Earlier quoted context omitted.

You are correct: by the pigeonhole principle, if the sum of the lengths of all the hashes/checksums is less than the length of the checksummed data, then collisions exist. (A detail: If checksums are included into the input of other checksums, their length doesn't count towards the amount of checksummed data, because they are not free to vary.)

Wouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions? Why does the pigeonhole principle hold?

Yes, this is correct. It's a really simple principle, and I think an explanation can help you understand :)

Suppose you have 3 holes, and 4 pigeons, and you stuff the pigeons into holes. There must be 1 hole with at least 2 pigeons, right?

The same is true with hash functions. If you're hashing data down to a fixed length, like say 256-bits with sha-256, and the data is longer than 256 bits, there must be a collision somewhere.

Re: Announcing the first SHA-1 collision

#494

Post by userbinator »

jeeceebees wrote: post #490
versteegen wrote: post #485

Earlier quoted context omitted.

You are correct: by the pigeonhole principle, if the sum of the lengths of all the hashes/checksums is less than the length of the checksummed data, then collisions exist. (A detail: If checksums are included into the input of other checksums, their length doesn't count towards the amount of checksummed data, because they are not free to vary.)

Wouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions? Why does the pigeonhole principle hold?

Wouldn't this imply that all hash functions (other than one-to-one mappings) must have collisions?

Yes, they do. Finding them is the hard part.

Re: Announcing the first SHA-1 collision

#495

Post by kevinnk »

dingo_bat wrote: post #488

> Hash functions compress large amounts of data into a small message digest. My understanding of crypto concepts is very limited, but isn't this inaccurate? Hash functions do not compress anything. They have an image too which says " SHA-1 compressions performed". Seems weird to see basic mistakes in a research disclosure.

https://en.m.wikipedia.org/wiki/One-way_compression_function

Cryptographic compression is not related to data compression.

Re: Announcing the first SHA-1 collision

#496

Post by ClayFerguson »

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…

Yeah, I think it's actually trivial to purposefully create two sets of data that hash into the same hash value. If this weren't the case then it would be the equivalent of data compression. If you are TRYING to cause a hash collision and successfully do that's trivial. Not even worthy of emailing your mom about. This entire post is not worthy of any attention.

Re: Announcing the first SHA-1 collision

#497

Post by ClayFerguson »

It's trivially easy and unimportant to purposefully create two sets of data that hash into the same hash value. The value of any hashing function is only from the statistical efficiencies arising from the fact that RANDOM data will have astronomically low probability of collision. Purposefully creating collisions is merely a nonsensical time-wasting pursuit. But hey, it got you noticed on HackerNews. Mission accomplished.

Re: Announcing the first SHA-1 collision

#499

Post by schoen »

WatchDog wrote: post #486
schoen wrote: post #477

Earlier quoted context omitted.

My intuition about this would be about hashes with "hidden state" that is neither reflected in nor reconstructible from the digest. For example, suppose the hash has a 1024-bit internal state and a 256-bit digest. Then two inputs that have a hash collision have the same digest but only about 2¯⁷⁶⁸ probability of having the same internal state, so if you continue to extend them, subsequent hashes will be different. I…

That makes sense, are there common hash algorithms that use different sized internal-state/digest?

Apparently it's a general architectural proposal.

https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...

Maybe I should consult a textbook (or a cryptographer) to understand more.

My intuition is that Merkle and Damgård may have thought that you get the greatest efficiency (or "bang for your buck") in some sense by simply outputting a digest that is as long as the internal state, since for some properties related to the intrinsic strength of the hash you would prefer that the digest be long. However, Lucks was apparently explicitly concerned about length extension and wanted to have some hidden state in order to prevent such phenomena, and hence proposed deliberately engineering it in.

But I'm not sure if that accurately presents the reason why the internal state and digest lengths have typically been the same in the past.

Edit: https://en.wikipedia.org/wiki/Comparison_of_cryptographic_ha... lists the internal state size alongside the output digest size. According to this chart, these functions have the same output and internal state lengths: MD4, MD5, RIPEMD and variants, SHA-0, SHA-1, Tiger-192, GOST, HAVAL-256, SHA-256, SHA-512, WHIRLPOOL.

These functions have a larger (hidden) internal state: RadioGatún, Tiger-160, Tiger-128, HAVAL-224, HAVAL-192, HAVAL-160, HAVAL-128, SHA-224, MD2, SHA-384, SHA-512/224, SHA-512/256, BLAKE2 variants, SHA-3 and all its variants, and PANAMA.

Sometimes the larger internal state is achieved simply by deliberately truncating (limiting the length of) the output hash, so the end user (and attackers) don't know the full original output hash and hence can't deduce the full original internal state.

I didn't know about this distinction before, although I once heard someone mention it in connection with BLAKE and SHA-3 candidates.

Re: Announcing the first SHA-1 collision

#500

Post by nurettin »

"as google, we spent two years to research a way of generating sha-1 collisions and made quintillions of computations to generate an example" <- not very convincing or practical. It's like those japanese animes where the nerdy kid boasts about having computed your every move.
Post reply on HN