The first chosen-prefix collision for SHA-1 • Hacker News Board

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

#281

Post by femto113 » Tue, Jan 07, 2020, 9:34 PM UTC

noja wrote: post #241

femto113 wrote: post #231

Earlier quoted context omitted.

Concatenating two hashes is an algorithm. Mathematically concatenating two 128 bit hashes is not any stronger than a single 256 bit hash (and is likely weaker), but if it’s all you have (or all you can afford to compute) two weak hashes is definitely much better than one.

Why is concatenating two 128 bit hashes (each with a different algorithm) not stronger than a single-algorithm 256 bit hash?

One reason is that it is theoretically possible to use memory instead of computation to attack the combined hashes by pre-generating a large number of collisions under one algorithm and then simply checking those using the other one, which means you don't need to do both algorithms for every check. Can't say for sure if that works out cheaper in terms of money but if the memory is available it could definitely save a lot of time.

Another reason is that for any given hash its theoretical maximum strength against any attack will be less than or equal to its bit length, but the practical strength always trends lower over time as attacks are found, and having two algorithms to attack increases the chances of finding flaws.

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

#282

Post by dickjocke » Tue, Jan 07, 2020, 9:41 PM UTC

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…

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda).

I just don't understand what danger being able to pad two documents to make them collide poses?

edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature provided. Assuming the attacker is able to send me the wrong library via a MITM attack, how can this prefix collision work? It seems that the original library AND the original signature on the library's website have not been altered, so their efforts to use this and make them match are impossible. And it seems like if they can alter the signature on the website and stuff, then all bets are off--why not just send the malicious library at that point?

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

#283

Post by ReidZB » Tue, Jan 07, 2020, 9:43 PM UTC

tptacek wrote: post #272

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...

Agreed. It's a great loss to the community that they have decided to step away from Stack Exchange: https://crypto.meta.stackexchange.com/questions/1361/im-leav...

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

#284

Post by nneonneo » Tue, Jan 07, 2020, 9:46 PM UTC

RickHull wrote: post #275

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 collis…

The confusing thing is that the team behind SHAttered did choose a prefix - they just had to choose a common prefix rather than two different prefixes (choosing a common prefix simply changes the initial state used by SHA-1). So I'm hoping that my post clarifies this point a bit.

The SHAttered attack (classical collision) can be used in practice - for example, my project https://github.com/nneonneo/sha1collider exploits their collision to turn any two PDFs into documents with identical SHA-1 hashes.

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

#285

Post by DaiPlusPlus » Tue, Jan 07, 2020, 9:47 PM UTC

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…

Bitcoin uses SHA-256, but I wouldn’t put it past some of the devs of some of the Altcoins and Shitcoins to use SHA-1 for either - or both of - their Proof-of-Work or Blockchain integrity hashing algorithms.

So if I understand today’s news correctly, you could use this to break blockchain integrity and offer-up alternative “valid” historical blocks (but not cheat at proof-of-work). You would still need to convince a quorum of network nodes to use your fake historical blocks - I imagine this might be doable on lesser-used coins that still have some trades - you could probably combine this with a few pump-and-dump trades too (without costing you anything as the coins you pump would be stolen).

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

#286

Post by femto113 » Tue, Jan 07, 2020, 9:51 PM UTC

dickjocke wrote: post #282

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…

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature prov…

It’s a step on the same path that led to being able to spoof a CA for MD5 signed certs.

https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-c...

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

#287

Post by nneonneo » Tue, Jan 07, 2020, 9:53 PM UTC

dickjocke wrote: post #282

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…

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature prov…

Suppose your system uses SHA-1 hashes for codesigning verification (e.g. to load a system driver). I create an innocent-looking device driver and convince a signing authority to sign it. However, secretly I've created a malicious driver (e.g. a rootkit) which collides with my innocent one. Now, I can load the malicious one on your machine - which the signing authority has never seen - using the signing certificate of the legitimate one.

This might sound far-fetched; after all, you'd need to convince a signing authority to sign the code. But this is pretty much exactly how Apple's Gatekeeper verification works: your software is submitted to them, and they do some security checks and notarize your bundle (https://developer.apple.com/developer-id/), and I'm sure there's many more such examples out there.

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

#288

Post by ThePowerOfFuet » Tue, Jan 07, 2020, 9:53 PM UTC

femto113 wrote: post #286

dickjocke wrote: post #282

Earlier quoted context omitted.

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature prov…

It’s a step on the same path that led to being able to spoof a CA for MD5 signed certs. https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-c...

Please don't feed the cancer which is AMP.

https://techcrunch.com/2008/12/30/md5-collision-creates-rogu...

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

#289

Post by Kalium » Tue, Jan 07, 2020, 9:54 PM UTC

dickjocke wrote: post #282

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…

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature prov…

The core of it is that it means a malicious document will pass the check of authenticity when you are using the genuine signature. Someone could tamper with a mirror infect you that way. Absolutely no tampering with the signature would be required, which is what makes this dangerous. Basically, it can be used to send to entirely fake data that you can't tell is fake.

Or someone could say that you have your legally binding signature attached to a contract with hash ABC, but then present a different contract with hash ABC but very different terms.

Those are the end state. This is a major step closer to that end state. Neither of those scenarios are the case today, but they're now close enough that it's a matter of time. And likely not a lot of time.

Time to abandon SHA1.

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

#290

Post by ReidZB » Tue, Jan 07, 2020, 9:55 PM UTC

xoa wrote: post #271

rakoo wrote: post #223

Earlier quoted context omitted.

"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, wh…

DES is a good example here: it was designed ~45 years ago and it's still theoretically surprisingly strong when you compare it with other areas of cryptography. By that, I mean it's held up very well to cryptanalysis that attempts to find faster-than-brute-force techniques, with the best attack taking 2^43 time (vs. the 2^56 brute-force time).

To be clear, 2^56 is trivially brute-force-able today, but that can be mitigated with constructs like 3DES, which are still (barely) secure despite being based on a 45-year-old cipher.

(So no one mistakes my intent, there are many reasons to prefer AES over DES. I just wanted to provide it as an example, especially since it happened to line up with the 40-year timeframe.)