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

341–350 of 369 posts

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

#341

Post by p1mrx »

CiPHPerCoder wrote: post #276
p1mrx wrote: post #242

Earlier quoted context omitted.

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

"Cryptographic hash functions with output size of n bits usually have a collision resistance security level n/2 and preimage resistance level n."

Depending on what you're doing, "SHA-512/128" could have a 128-bit security level. But I guess it's safer to assume n/2 when making a general recommendation.

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

#342

Post by Thorrez »

pathseeker wrote: post #172
saalweachter wrote: post #144

Earlier quoted context omitted.

Isn't that like incredibly simple? Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.

Depends on if the chosen prefix attack allows the content to appear arbitrarily in the middle of the byte stream like that.

That's exactly what a chosen prefix attack means. You choose the arbitrary prefixes. Then the garbage is inserted. Then (due to SHA1's Merkle–Damgård construction) you append a postfix that's mostly arbitrary (but the same in both files).

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

#343

Post by Thorrez »

Skunkleton wrote: post #195
banana_giraffe wrote: post #75

Earlier quoted context omitted.

Like the two files on the linked page?

The two files on the linked page were both full of junk data. I suspect that those files being of the same length isn't the norm.

Why wouldn't it be the norm? If they're able to make files of the same length, other attackers can make files of the same length too.

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

#344

Post by Thorrez »

bjornsing wrote: post #63
bjornsing wrote: post #53

Earlier quoted context omitted.

> you have to be able to also edit the size field in the header.” As I read the OP [1] a chosen-prefix collision attack such as this allows you to “edit the size field in the header”. Or am I missing something? 1. “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 the…

A few emails forward in the thread Linus explains though why we don’t need to worry much about this attack in practice: https://marc.info/?l=git&m=148787287624049&w=2 This argument sounds sound to me.

His argument assumes the file is text and people read the entire thing. If either of those assumptions are false, then it's not safe.

People store things in git that aren't text. Therefore it's not safe.

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

#345

Post by jodrellblank »

perl4ever wrote: post #331
jodrellblank wrote: post #216

Earlier quoted context omitted.

The idea behind your complaint is " if we tell good people about risks, then bad people will know about them. If we keep them secret from good people, then bad people won't find out about them ". Or, " if we don't make a list of open doors, then bad people can't find which doors are open ". Which is .. not true. Bad people will already be making their own list of open doors, and sneaking through them without being no…

"Which is .. not true. Bad people will already be making their own list of open doors, and sneaking through them without being noticed, over and over again." But the vast majority of people do literally have front doors which cannot guard them from 1% of the possible attacks in the world, if they were targeted. Never mind the best ones in the world.

The internet brings a much bigger attack surface than local people who can reach a front door, and home users access the same openssh as companies do, but companies (can) afford stronger doors. "Most people's home doors can't withstand a hit from a sledgehammer" -> "we shouldn't talk about cryptographic weaknesses in case someone abuses them" is a stretch, the comparison does break down.

[1] is a fun YouTube video about physical pen testing; one example at 13:45 in the video, the presenter is walking home from a bar, walks up to a locked high street bank, spits a mouthful of beer through the gap in the doors, triggers the presence sensor on the inside which lets people out, and the door opens and lets him in.

[1] https://www.youtube.com/watch?v=rnmcRTnTNC8

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

#346

Post by smichel17 »

caspper69 wrote: post #266
SAI_Peregrinus wrote: post #211

Earlier quoted context omitted.

To be excessively pedantic you can encrypt securely (but slowly for the SHA series) with a hash function of sufficient capacity by running the hash function in CTR mode. You turn it into a stream cipher. Ideally you also MAC the ciphertext, nonce, and other associated data. That's is pretty easy with such a hash function (either use HMAC or a MAC mode of the hash function if supported). Salsa20 & ChaCha20 cores are h…

> To be excessively pedantic This is the best, most delicious, type of pedantry friend!

You're the best kind of pedantry friend!

(Just some more pedantry, friend.)

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

#347

Post by nneonneo »

userbinator wrote: post #337
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…

Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself AFAIK there's still no practical preimage attack for MD5, for which you can generate collisions in seconds on hardware that's a decade old, so it seems making a hash function collision resistant is in general quite a bit harder than making it resistant to preimage attacks.

To some extent that’s just a function of the brute-force search space: due to the birthday paradox a 128-bit hash like MD5 only requires testing around 2^64 hashes to find a collision. However, to find a preimage you would need to search through 2^128 possible messages.

Attacks generally improve on brute force by factors; for example, MD5 collision finding is some 2^40 times more efficient than 2^64 brute force, but being 2^40 times more efficient than 2^128 brute force for preimage finding is still well outside of anyone’s capabilities.

MD5 also appears to be unusually preimage-resistant; the best attack requires something like 2^123 operations which is really infeasible.

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

#348

Post by perl4ever »

jodrellblank wrote: post #345
perl4ever wrote: post #331

Earlier quoted context omitted.

"Which is .. not true. Bad people will already be making their own list of open doors, and sneaking through them without being noticed, over and over again." But the vast majority of people do literally have front doors which cannot guard them from 1% of the possible attacks in the world, if they were targeted. Never mind the best ones in the world.

The internet brings a much bigger attack surface than local people who can reach a front door, and home users access the same openssh as companies do, but companies (can) afford stronger doors. "Most people's home doors can't withstand a hit from a sledgehammer" -> "we shouldn't talk about cryptographic weaknesses in case someone abuses them" is a stretch, the comparison does break down. [1] is a fun YouTube video ab…

"The internet brings a much bigger attack surface than local people who can reach a front door"

"Local people", huh. My front door is visible to everyone on the internet, and I have no practical way to prevent that. Some obscure company went by with their mapping vehicle and...

Now, some people do live in big buildings where less is exposed to the outside, but millions don't.

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

#349

Post by mzs »

Thorrez wrote: post #339
mzs wrote: post #316

Earlier quoted context omitted.

checks-out, thanks $ mkdir sha1 $ cd sha1 $ curl -O https://sha-mbles.github.io/messageA ... $ curl -O https://sha-mbles.github.io/messageB ... $ echo foo > bar $ echo foo > baz $ openssl sha1 * SHA1(bar)= f1d2d2f924e986ac86fdf7b36c94bcdf32beec15 SHA1(baz)= f1d2d2f924e986ac86fdf7b36c94bcdf32beec15 SHA1(messageA)= 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 SHA1(messageB)= 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 $ git i…

No, you and joeyh are incorrect about the test (but correct about the result). As can be seen in the output, SHA1(bar)= f1d2d2f924e986ac86fdf7b36c94bcdf32beec15 but git_SHA1(bar) = 257cc5642cb1a054f08cc83f2d943e56fd3ebe99 . Why is there a difference? Not because of hardened SHA1. Hardened SHA1 essentially always produces identical outputs to SHA1 > git doesn't really use SHA-1 anymore, it uses Hardened-SHA-1 (they ju…

I really appreciate this, thanks!

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

#350

Post by ReidZB »

userbinator wrote: post #338
tgsovlerkhgsel wrote: post #329

Earlier quoted context omitted.

> trivially Having to rent thousands of dollars in GPU-hours or using specialized hardware doesn't sound "trivial" to me. Practical, yes. Accessible even to a layman with money to spare, yes. Trivial? Hell no.

It's funny to see how different the various people here have on the definition of "trivial". 10 years ago, I generated MD5 collisions in a few minutes with a tiny little executable I downloaded. That's what I call trivial. If I had some DES-encrypted files that I'd lost the key to, and they were important enough that I needed their contents, I would probably be happy that I could crack the key today and recover them…

Oh, sure, maybe trivial isn't the best word for it, but it's all relative (to me). $20k is remarkably cheap for a practical cryptographic attack compared to the rest of the field, and there's plenty of software to do it, and it's been done before (many times).

Apparently there's even a SaaS offering to do it for you in some cases (for staggeringly cheap, like $300), but I had no idea that existed when I wrote my comment.

Post reply on HN