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

A SHA-1 chosen-prefix collision attack

zdnet.com

Post reply on HN
Print view View original

11–20 of 75 posts

Re: A SHA-1 chosen-prefix collision attack

#11

Post by pslam »

arkadiyt wrote: post #9

Their attacks are based on previous chosen-prefix work from Marc Stevens, who tweeted this about the attack [1]: "Their $100K figure is based on as-of-yet undisclosed improvements. History shows many claims of low-cost SHA-1 attacks that have not stood up to peer review. I am very sceptical that their attack costs in total less than the $110K building block (SHAttered) that they use." [1]: https://twitter.com/realhas…

Marc Stevens quotes $500K, which is very much still a threat (even an order of magnitude more would be). Plenty of organizations would be willing to spend that much pocket change on a single attack.

The game-changer is it's chosen-prefix. A vendor can produce a pair of entirely different binaries with the same hash, but most importantly, they look and behave sane except for the last few blocks of the file. This is easily hidden, especially if the binary is encrypted.

It's not a stretch of the imagination to see how, for example, an IP camera vendor could do exactly this. Yes, it requires a nefarious/complicit vendor, or an insider who can pull this off undetected (not everyone has a fully automated build/release pipeline).

So it changes the threat model. SHAtter was waived by many because the threat model didn't convincingly apply to them. Example: git. That analysis needs to be repeated.

(All this assuming the attack described in the paper is correct and practical in real world implementation)

Re: A SHA-1 chosen-prefix collision attack

#12

Post by Someone1234 »

chrisseaton wrote: post #10
zdw wrote: post #7

From the paper, this doesn't seem to be able to create a collision while retaining the same length of input data. It seems that checking both the hash and input length would be a very cheap way of identifying attempts at hash collisions.

If you're going to modify your code to add an extra check you might as well just switch to another algorithm entirely.

A lot of existing schemes already check both.

The above comment didn't mention modification explicitly and could be read as talking about the level of threat this poses.

Re: A SHA-1 chosen-prefix collision attack

#13

Post by blurbleblurble »

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the right one.

I don't know how feasible this actually is, but it made for an interesting sci-fi thought.

edit: Thanks for all of the enlightening replies!

Re: A SHA-1 chosen-prefix collision attack

#15

Post by paulddraper »

blurbleblurble wrote: post #13

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the r…

The problem is that is a huge number of strings that becomes a hash.

Each SHA-256 hash has 2^(8 * 1024 - 256) = 10^2389 possible 1KB inputs.

So...perhaps it could be done, but the quantum computer would have programmed with a very good selection criteria.

Re: A SHA-1 chosen-prefix collision attack

#16

Post by CiPHPerCoder »

blurbleblurble wrote: post #13

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the r…

IIRC the best quantum attack against SHA256 clocked in at about 2^85 cost. It's still not practical for most modern hash functions.

Re: A SHA-1 chosen-prefix collision attack

#17

Post by yardstick »

zdw wrote: post #7

From the paper, this doesn't seem to be able to create a collision while retaining the same length of input data. It seems that checking both the hash and input length would be a very cheap way of identifying attempts at hash collisions.

This is one reason why HMAC-SHA1 is still safe.

Re: A SHA-1 chosen-prefix collision attack

#18

Post by JeremyBanks »

optimiz3 wrote: post #8
CiPHPerCoder wrote: post #5

Earlier quoted context omitted.

Nope. SHA-2 (known to developers as SHA224, SHA256, SHA384, and SHA512) was the replacement for SHA-1. SHA-3 was created as an insurance policy in case the SHA-2 family was broken too. So far, it hasn't been. We won't need a SHA-4 any time soon. SHA-2 is fine, BLAKE2 is fine (and faster), SHA-3 is fine.

Also, SHA-2 underpins Bitcoin; it's the ultimate billion dollar pot of gold. SHA-2 is perhaps the most exhaustively researched (both publicly and privately) cryptographic hash because of this.

deleted

Re: A SHA-1 chosen-prefix collision attack

#19

Post by stouset »

paulddraper wrote: post #15
blurbleblurble wrote: post #13

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the r…

The problem is that is a huge number of strings that becomes a hash. Each SHA-256 hash has 2^(8 * 1024 - 256) = 10^2389 possible 1KB inputs. So...perhaps it could be done, but the quantum computer would have programmed with a very good selection criteria.

No, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. You start your “decompression” process and read in a 0. What input produced that bit? Literally fifty percent of all possible strings would produce that same output. Without more information, you cannot choose between them. And the information needed to choose correctly is exactly the same amount of information in the original input.

https://en.m.wikipedia.org/wiki/Pigeonhole_principle

Re: A SHA-1 chosen-prefix collision attack

#20

Post by jhpriestley »

blurbleblurble wrote: post #13

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the r…

There are infinitely many strings that produce a given hash. Infinitely many of them will also produce a secondary hash that you check against. There is no general-purpose scheme to compress arbitrary data, regardless of available computational power, because if you can compress all length-N plaintext strings then you must end up with at least 2^N distinct compressed strings which will take on average at least N bits of storage.
Post reply on HN