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

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

#331

Post by perl4ever » Wed, Jan 08, 2020, 2:39 AM UTC

jodrellblank wrote: post #216

gist wrote: post #204

Earlier quoted context omitted.

The way I see it, this is what is bad: > We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all. What the…

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.

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

#332

Post by lightedman » Wed, Jan 08, 2020, 2:41 AM UTC

gowld wrote: post #311

ReidZB wrote: post #283

Earlier quoted context omitted.

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

* that the owners of Stack Exchange drove them and others away.

Yup, that's pretty much what happened in reading that posted link, so why you're being downvoted I don't know.

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

#333

Post by perl4ever » Wed, Jan 08, 2020, 2:41 AM UTC

mlyle wrote: post #227

knorker wrote: post #186

Earlier quoted context omitted.

Yes, but for the specific concerns listed it should not be a problem. That is, if you upload to dropbox and check the sha1 when it comes back, yes you did get the same data back. And your data can't be stolen by a hash-to-data oracle either, unless the evil attacker constructed your secret data for you. So it depends on your threat model. Yes there are practical concerns, but not the ones listed.

I disagree. Deduplicating filesystems often depend on hash equivalency meaning data equivalency. They may or may not have modes to validate all data before deduplication, but these suck for performance and are often turned off. E.g. I make two things that hash to the same thing. One is a contract where I'm obligated to pay back a loan. Another is some meaningless document. I give them to a counterparty who puts them…

The filesystem removes a document, but you can't expect it will be the right one more than 50% of the time.

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

#334

Post by microtherion » Wed, Jan 08, 2020, 2:47 AM UTC

comicjk wrote: post #101

tambourine_man wrote: post #76

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in t…

Bridge engineers don't have to fear the progress of science working against them, but computer security is not alone here. Consider designing body armor or military aircraft and hoping that the state of the art will stay the same! An adversary who can use the progress of science against you is always dangerous. Computer security has been rather lucky so far: the asymmetry between hashing and cracking a hash, for exam…

> Consider designing body armor or military aircraft and hoping that the state of the art will stay the same!

This was particularly a problem for castles vs. the progress of artillery, because those were supposed to have a rather long lifetime.

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

#335

Post by mlyle » Wed, Jan 08, 2020, 3:20 AM UTC

perl4ever wrote: post #333

mlyle wrote: post #227

Earlier quoted context omitted.

I disagree. Deduplicating filesystems often depend on hash equivalency meaning data equivalency. They may or may not have modes to validate all data before deduplication, but these suck for performance and are often turned off. E.g. I make two things that hash to the same thing. One is a contract where I'm obligated to pay back a loan. Another is some meaningless document. I give them to a counterparty who puts them…

The filesystem removes a document, but you can't expect it will be the right one more than 50% of the time.

An attacker may be able to control the way it happens.

It may be repeatable to always remove the first or the last. If it's online dedup, it'll always be the last.

Or the attacker can provide many copies of the document you want to still have a copy of, and one copy in the middle of the one that should be vanished.

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

#336

Post by Thorrez » Wed, Jan 08, 2020, 3:45 AM UTC

upofadown wrote: post #149

newscracker wrote: post #133

General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox…

SHA1 isn't broken for hashes.

What does "for hashes" mean? For a hash table? Of course it's fine for a hash table (but probably too slow). Hash tables don't need collision resistance. If you need collision resistance then SHA-1 is broken.

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

#337

Post by userbinator » Wed, Jan 08, 2020, 3:45 AM 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…

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.

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

#338

Post by userbinator » Wed, Jan 08, 2020, 4:00 AM UTC

tgsovlerkhgsel wrote: post #329

ReidZB wrote: post #290

Earlier quoted context omitted.

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

> 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 if I spent enough, but doing so would still not be "trivial".

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

#339

Post by Thorrez » Wed, Jan 08, 2020, 4:09 AM UTC

mzs wrote: post #316

joeyh wrote: post #301

Earlier quoted context omitted.

Hardened sha1 does detect this new attack. Easy to test: Check their pair of files into a git repo and see that they have different checksums, while sha1sum(1) generates the same for both.

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 just so happen to produce the same outputs 99.99999999999...% of the time).[1]

https://stackoverflow.com/questions/10434326/hash-collision-...

There's essentially no chance that the string "foo\n" fell into that tiny probability of difference. The reason there's a difference is because before git hashes something, git will do various processing to it (maybe appending and prepending various things) and those things broke the carefully created collision. But a chosen-prefix attack might mean those various things can be accounted for, and a collision could still be found.

So we need to directly run hardened SHA1 on the data, which I believe is located at https://github.com/cr-marcstevens/sha1collisiondetection

As seen in https://github.com/git/git/blob/master/sha1dc_git.c

So I tested that one:

    $ sha1collisiondetection-master/bin/sha1dcsum bar baz messageA messageB shattered-1.pdf shattered-2.pdf
    f1d2d2f924e986ac86fdf7b36c94bcdf32beec15  bar
    f1d2d2f924e986ac86fdf7b36c94bcdf32beec15  baz
    4f3d9be4a472c4dae83c6314aa6c36a064c1fd14 *coll* messageA
    9ed5d77a4f48be1dbf3e9e15650733eb850897f2 *coll* messageB
    16e96b70000dd1e7c85b8368ee197754400e58ec *coll* shattered-1.pdf
    e1761773e6a35916d99f891b77663e6405313587 *coll* shattered-2.pdf

So it does protect against the new attack.

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

#340

Post by tialaramex » Wed, Jan 08, 2020, 4:10 AM UTC

NieDzejkob wrote: post #268

Boulth wrote: post #66

Earlier quoted context omitted.

Actually it's even worse than that: signature creation time is added by the signer so it's totally under control of the attacker. IMHO all SHA-1 based signatures should be ignored.

In this case, signature creation time isn't under control of the attacker. The attack scenario being considered is that Mallory can convince Alice to sign a key K1, provided by Mallory, such that it looks like Alice signed K2. The party creating the signature is honest here.

The problem is that the dates are part of the document being signed.

Rather than keys, Alice will typically sign a document (e.g. an X.509 to-be-signed certificate)

Mallory creates two documents, the legitimate seeming document A (a to-be-signed certificate Alice willingly signs) and document B (the content of which is controlled by Mallory to an extent depending on the details of the collision). In document A I'm sure Alice will insist on the date being roughly correct so you'd detect that. But Alice never sees document B, she isn't aware it exists, so it can specify any date, including one chosen not to set off alarms.

For the Web PKI we were triply safe because:

1. We told Alice (the public CAs) never to sign anything at all with the dangerous algorithm after a set date. So long as Mallory wasn't able to develop and use a collision before that date and Alice did as she was told‡ this would be safe in perpetuity.

2. We already had a countermeasure in the documents, very early in each Web PKI X.509 certificate is the Serial Number, if you look at yours you'll notice it's a crazy huge number and seemingly not "serial" in any sense. It's random. Can't do a chosen prefix collision attack if you can't choose the prefix.

3. Since no more new documents were being signed clients in the Web PKI were able to stop recognising these signatures thus permanently ensuring the attack was impossible within about 18 months.

‡ A very small number of exceptions were explicitly granted, and a similarly small number of exceptional cases occurred for which no permission was asked. All investigated to everybody's satisfaction. As you may see if you poke around in the demo documents from this article, a collision document may not jump out as problematic from a crowd but it certainly isn't so innocuous as to survive careful scrutiny, and with such a small number of exceptions to look at this scrutiny was possible in a way it never would be for the wider Web PKI.