Live data from Hacker News

A SHA-1 chosen-prefix collision attack

zdnet.com

41–50 of 75 posts

Re: A SHA-1 chosen-prefix collision attack

#41

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.

Is there any reason not to just use SHA-3? It sounds like it's a real swiss army knife to hear the authors talk about it.

Right now it has worse library support, worse hardware support, and isn't analysed as thouroughly as SHA512/SHA256. Also SHA-3 seems to be fighting with Blake2 for popularity, it's not immediatly clear to me that SHA-3 will be popular in 10 years (a point for usage in API design etc).

But those are temporary problems that might not even matter to you.

Re: A SHA-1 chosen-prefix collision attack

#42
post #19

Earlier quoted context omitted.

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…

Yup, the pigeonhole principle really defines a hard limit on compression, in that it is impossible to compress (make smaller) ALL files. The way compression algorithms get around that, is by abusing the fact that we rarely want to send around arbitrary data, real world data has lots of redundancy in it, so we can make algorithms where real world data gets mapped into compressed files smaller then they are (by finding…

Often rendered as the pithy phrase "A compression algorithm is actually an expansion algorithm with some interesting failure cases."

Re: A SHA-1 chosen-prefix collision attack

#43

“Everyone should switch to (in order of preference): • BLAKE2b / BLAKE2s • SHA-512/256 • …” You know, SHA-512/256 was a terrible name. For someone who’s not a cryptographer, it’s way too easy to confuse the single algorithm SHA-512/256, which resists length extension attacks, with the pair of algorithms SHA-512 / SHA-256, which do not.

"truncated sha512" would be a much better way to talk about it.

Re: A SHA-1 chosen-prefix collision attack

#44

“Everyone should switch to (in order of preference): • BLAKE2b / BLAKE2s • SHA-512/256 • …” You know, SHA-512/256 was a terrible name. For someone who’s not a cryptographer, it’s way too easy to confuse the single algorithm SHA-512/256, which resists length extension attacks, with the pair of algorithms SHA-512 / SHA-256, which do not.

Damn, I knew this and I'd forgotten it. Thanks for pointing it out.

that just goes to show how bad the name is. It doesn't trick you until before you learn, but it keeps on giving!

Re: A SHA-1 chosen-prefix collision attack

#45
post #8

Earlier quoted context omitted.

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.

Do you know why it's said to be last-resort in the article?

Catalin was quoting me in the article, so it's only fair that I elaborate here.

There are four common flavors of the SHA2 family you're likely to run into:

  - SHA-224
  - SHA-256
  - SHA-384
  - SHA-512
And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail)

  - SHA-512/256
  - SHA-512/224
These latter two don't have nearly the cross-platform support as the first four.

For example, in PHP, hash('sha256', 'some text') worked since PHP 5.1.2 (without PECL), but hash('sha512/256', 'some text') didn't work until PHP 7.1.0 (which is only a few years old).

See for yourself: https://3v4l.org/A1dZc

As a typical software developer, you might see SHA-{magic/numbers} and probably discover from Google/StackOverflow/etc. that they're in the SHA2 family and that the SHA2 family is secure, and then reason that whatever you're doing must also be also secure.

But there's a problem.

SHA-256 and SHA-512 (not the truncated varieties) are known to be vulnerable to length extension attacks. This is only a problem if you're using these hash functions in a vulnerable way. (Which isn't as uncommon as you'd think in homebrew crypto.)

If you're using HMAC, length extension attacks are a moot point. There's a reason 'tptacek always recommends HMAC for symmetric authentication.

SHA-224, SHA-384, SHA-512/224, and SHA-512/256 are not vulnerable to length extension attacks.

BLAKE2 is not vulnerable to length-extension attacks. It's also at least as secure as SHA2, but faster than MD5. SHA3 is at least as secure as BLAKE2, but is significantly slower in software.

Thus, the recommendations are:

  - BLAKE2
    for speed and security
  
  - SHA-512/256
    if you want speed, length-extension attack resistance, and arbitrary standards compliance
  
  - SHA3-256
    if you care more about security and what the FIPS authors think than speed
  
  - SHA-384 
    if you're concerned about backwards compatibility but don't want to accidentally cause
    junior developers that poorly mimic your designs to introduce LEAs into their code
  
  - Any other SHA-2 family hash function 
    if you're not interested in all of this nuance and want something
    guaranteed to be secure for the next few years that is widely implemented
Of course, there should be a huge asterisk with this list: If you're not a crypto expert, you shouldn't be making this decision. Just stop using SHA1.

It's also worth noting that Marc Stevens-- hash function breaker extraordinaire-- disagrees with my recommendation because BLAKE2 isn't a {NIST,FIPS,ISO,whateverStandardsBodyYouTrust}-approved hash function, and for better or worse, believes strongly in reinforcing public trust in standards organizations. https://twitter.com/realhashbreaker/status/11283816001468948...

He has a point in general, but in this specific case, I think BLAKE2 is going to become the de jure SHA2 successor at least until SHA3 hardware acceleration becomes ubiquitous.

Also, standards bodies have a nasty habit of digging in their heels on their mistakes, instead of issuing new guidance in response to research. See also: WPA3 and Dragonfly vs SPAKE2-EE or OPAQUE.

For a higher-level example, look at the failures baked into the JOSE standards (JWT, etc.) versus PASETO.

Fun fact: If you take JOSE and replace JSON with CBOR, without fixing any of the protocol security problems, you get COSE... which reared its ugly head in W3C's WebAuthn standard. Bad standards never die.

Until we get a standards committee that isn't garbage, I don't entirely agree with Marc's appeal to faith here.

While NIST et al. certainly do a better job at deciding on primitives than self-styled post-2010 cypherpunks (y'know, the ones that try to cascade a bunch of ciphers together in case one is broken but then use CRC32 for mixing files into the encryption key?), their failure to correct (let alone learn from) their mistakes and update recommendations in a timely manner is a problem that can't be dealt with through blind adherence to whatever they publish.

Re: A SHA-1 chosen-prefix collision attack

#46
post #8

Earlier quoted context omitted.

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.

Do you know why it's said to be last-resort in the article?

SHA-512/256 is the second resort, and it’s the 512 bit variant of SHA-2 truncated to 256 bits (SHA-384 is similar). Generally any SHA followed by a relatively large number is actually a variant of SHA-2.

Re: A SHA-1 chosen-prefix collision attack

#47

Earlier quoted context omitted.

Do you know why it's said to be last-resort in the article?

Catalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have n…

Ahh so it's because of length extension attacks. Thanks!

Re: A SHA-1 chosen-prefix collision attack

#48

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.

Is there any reason not to just use SHA-3? It sounds like it's a real swiss army knife to hear the authors talk about it.

There are reasons to prefer other functions, but none of those are disqualifying marks on SHA-3.

If you have SHA-3 available, just use it. Everything listed in that article is secure today and will probably be secure 10 years from now.

Re: A SHA-1 chosen-prefix collision attack

#49

Earlier quoted context omitted.

Do you know why it's said to be last-resort in the article?

Catalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have n…

What do you mean by "at least as secure"?

They are different algorithms, so I don't see how their security can be provably related.

Re: A SHA-1 chosen-prefix collision attack

#50
post #49

Earlier quoted context omitted.

Catalin was quoting me in the article, so it's only fair that I elaborate here. There are four common flavors of the SHA2 family you're likely to run into: - SHA-224 - SHA-256 - SHA-384 - SHA-512 And then there are two more variants of "truncated SHA-512" (except they also use different initialization vectors than SHA-512, which is kind of an important detail) - SHA-512/256 - SHA-512/224 These latter two don't have n…

What do you mean by "at least as secure"? They are different algorithms, so I don't see how their security can be provably related.

Saying "BLAKE2 is at least as secure as SHA-256" is saying that:

1. The best known attacks against SHA-256 have a cost of 2^i for some value of i.

2. The best known attacks against BLAKE2 have a cost of 2^j for some value of j.

3. j >= i

Post reply on HN