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

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

Post reply on HN
Print view View original

271–280 of 369 posts

Re: The first chosen-prefix collision for SHA-1

#271

Post by xoa »

rakoo wrote: post #223
baddox wrote: post #198

Earlier quoted context omitted.

> Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. When has that happened? Public key cryptography and symmetric key cryptography are still doing fine as far as I'm aware, and the latter doesn't even seem to be vulnerable to quantum computing. Moreover, SHA-1 has been considered insecure for, what, at least 10 years? The fact that a cryptographic ha…

"Public/symmetric key cryptography" is just the name of the practice, of course it's doing fine. What's not doing fine is picking a particular set of ciphers/hash functions/signature scheme and expecting to not fail in 40 years.

Incorrect, particular sets of ciphers are themselves doing just fine. There is no hint of well studied symmetric-key algorithms (like AES, which is in fact now over 20 years old) with long known sufficient key lengths "failing" (in terms of cold ciphertext being cracked) in 40 years, or 400 years for that matter. Even with a fully scalable general quantum computer, the best known improvement is Grover's Algorithm, which results in roughly a quadratic improvement (so a 128-bit key cracked in 2^64 iterations, 256-bit in 2^128, etc). This obviously is trivially defeated by doubling the key length, and AES-256 has been available from the beginning and has been becoming more standard for a while as well.

Now, there are various kinds of hot attacks, such as side channel leaks, that always present a serious challenge in many threat scenarios. And it's certainly possible to have bad implementations of a solid algorithm. But for AES implementations are very mature, and side channel attacks do not apply to data at rest. So in the context of "will my encrypted ciphertext with all my deepest secrets [sitting on a drive/in the cloud/wherever] be crackable in 40 years" no, symmetric-key crypto with 256-bit keys is dependable at this point.

A false sense of defeatism is itself plenty dangerous to security.

Re: The first chosen-prefix collision for SHA-1

#272

Post by tptacek »

nneonneo wrote: post #259

So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some pseudorandom data C1, C2 such that SHA1(P1+C1) = SHA1(P2+C2). The length extension property of SHA1 (and MD5) means that now SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X. A similar attack (which requires only a few hours on modest hardware nowadays) has been known…

Squeamish Osssifrage's answer to this Crypto Stack Exchange question does a predictably excellent job of putting these attacks in context.

https://crypto.stackexchange.com/questions/60640/does-shatte...

Re: The first chosen-prefix collision for SHA-1

#273

Post by LennyWhiteJr »

RcouF1uZ4gsC wrote: post #161

Does this affect Git? I believe it uses SHA-1 for commits. Is it possible to use this attack to add malicious code to a git repository without changing the hashes for the commits?

Potentially. GitHub at least already started collision detection after Shattered was published.

https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Re: The first chosen-prefix collision for SHA-1

#274

Post by tptacek »

staticassertion wrote: post #187
espadrine wrote: post #99

Earlier quoted context omitted.

Cryptographers rely on precise definitions to make their assessments. In particular, a primitive makes a number of useful promises. Any achievement that describes a way in which a promise is not kept makes that primitive broken , regardless of whether that achievement is theoretical or practical. (They often talk about “theoretically broken” or “practically broken” to distinguish whether it was actually done.) > it's…

Is SHA1 not still faster than 256/512? And Blake2 barely faster? I suspect with some hardware SHA1 is still going to beat all of those out - am I wrong? I would love to learn more.

https://bench.cr.yp.to/results-hash.html

Regardless, no competent designer is going to use SHA1.

Re: The first chosen-prefix collision for SHA-1

#275

Post by RickHull »

nneonneo wrote: post #259

So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some pseudorandom data C1, C2 such that SHA1(P1+C1) = SHA1(P2+C2). The length extension property of SHA1 (and MD5) means that now SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X. A similar attack (which requires only a few hours on modest hardware nowadays) has been known…

Actually, the website does cover this in the '''Q&A''' section:

> What is a chosen-prefix collision?

> A classical collision (or identical-prefix collision) for a hash function H is simply two messages M and M’ that lead to the same hash output: H(M) = H(M’). Even though this security notion is fundamental in cryptography, exploiting a classical collision for attacks in practice is difficult.

> A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation.

> With such an ability, the attacker can obtain a collision even though prefixes can be chosen arbitrarily (and thus potentially contain some meaningful information). This is particularly impactful when the hash function is used in a digital signature scheme, one of the most common usage of a hash function.

Re: The first chosen-prefix collision for SHA-1

#276

Post by CiPHPerCoder »

p1mrx wrote: post #242
SAI_Peregrinus wrote: post #220

Earlier quoted context omitted.

Because 224 bits is considered the minimum safe output length for a general purpose hash function. So they'd be drop-in replacements but still wouldn't be safe. Safer than MD5/SHA1, but not actually safe. So rather than push off getting people to make things actually safe by providing a footgun NIST just didn't do that.

> 224 bits is considered the minimum safe output length for a general purpose hash function. Considered by whom?

Truncating a hash function to 224 bits put it at the 112-bit security level, which is roughly equivalent to 2048-bit RSA under today's understanding of the costs of distributed cracking attacks.

There are a lot of standards organizations all over the world with various recommendations. https://www.keylength.com collates quite a few of them. Pick the one most closely relevant for your jurisdiction.

Most of them recommend 2048-bit RSA as their minimum for asymmetric security, and AES-128 / SHA-256 as their minimum for symmetric security. This is a [112, 128]-bit security lower bound.

Truncating a hash to 160 bits yields 80-bit security, which is insufficient. 128 bits (64-bit security) is out of the question.

Re: The first chosen-prefix collision for SHA-1

#277

Post by biggestdecision »

jVinc wrote: post #262

So how would someone go about gaining more than 45k USD in profit from a single case of using the chosen-prefix collision? Not being candid here, I am honestly curious here. I'd guess that even in situations where you somehow get a signed e-mail sent off spoofing a CEO saying "Please pay these guys 50k$" the actual payout seems unlikely and that puts the attacker 45k in the red. But maybe there are some obvious avenu…

At the current time this is much more likely to be abused for political/intelligence reasons, than for profitable criminal reasons. Sneaking a malicious commit with the same signature into a git repository for example.

Re: The first chosen-prefix collision for SHA-1

#278

Post by toyg »

shrimpx wrote: post #245
toppy wrote: post #192

Earlier quoted context omitted.

This biblical prophecy from Luke 12,3 is solo true: " What you have said in the dark will be heard in the daylight, and what you have whispered in the ear in the inner rooms will be proclaimed from the roofs."

I wonder what the intended meaning is. I presume it has to do with a presumed eventual urge to confess.

It’s basically “don’t try to get fresh with God”. Which conveniently translates into a call to humility and honesty towards its earthly representatives.

Re: The first chosen-prefix collision for SHA-1

#279

Post by WorldMaker »

CobrastanJorji wrote: post #205
WorldMaker wrote: post #170

Earlier quoted context omitted.

There's an MC Frontalot song called "Secrets from the Future" and the refrain is "You can't hide secrets from the future." It's something of a useful mantra to remind oneself that if "the future" is a part of your threat model, yes your encryption likely isn't enough because on a long enough timescale it is likely "the future" will crack it. As with any other security issue, the question is "what is your threat model…

The point about archeologists is a good one because it speaks to motive. In general, we should be very supportive of the efforts of distant historians who want to understand what humanity used to be like. We should not WANT to hide secrets from a sufficiently far future. I can't think of any secret that deserves to be hidden from them for any reason besides perhaps modesty.

Relatedly, that is a part of why I love the term "cryptoarcheology" in general, as a reminder that digital spaces will need archeologists too.

There's it's somewhat shortened form "cryptarch", generally more used as a title ("cryptoarcheologist"), which was used in places in the Quantum Thief trilogy of books and is most probably already burned into your brain if you have played any of the Destiny series of videogames (and I presume was heavily influenced by Quantum Thief).

Re: The first chosen-prefix collision for SHA-1

#280

Post by staticassertion »

tptacek wrote: post #274
staticassertion wrote: post #187

Earlier quoted context omitted.

Is SHA1 not still faster than 256/512? And Blake2 barely faster? I suspect with some hardware SHA1 is still going to beat all of those out - am I wrong? I would love to learn more.

https://bench.cr.yp.to/results-hash.html Regardless, no competent designer is going to use SHA1.

Thank you, that's an excellent chart.
Post reply on HN