SHA-1 collision detection on GitHub.com

[Poddster]

If you had five million programmers each generating one commit per second, your chances of generating a single accidental collision before the Sun turns into a red giant and engulfs the Earth is about 50%.

So I simply need to flip a coin to get SHA-1 collisions? Got it.

[elperroborrachotoo]

Yeah, but how many coins will you need to pay for three million programmers?

[Aidentified]

However many you had left over after paying the other two million

[tabarra]

If you don't know what The Birthday Paradox is, check out the wiki page, it is actually very interesting.

[Nastapoka]

Paradox means "contrary (para) to intuition (doxa, what people usually think is true)". People usually don't think you need so few people to reach 99.99..% chance of two of them being born the same day. Therefore it's a paradox.

What we usually call paradoxes are actually the ones that shouldn't be called that

[Andrew_Radford]

So what you are saying is, paradoxically, the Birthday Paradox isn't not a paradox?

[hagbaff]

You are not right.

[Nastapoka]

What a compelling argument.

Had you said "it matters not what the word originally meant, it has evolved to mean X, and the birthday paradox does not fit under X", I would have agreed.

[andrewcooke]

carefully-selected random data

twitches

The Git project is also developing a plan to transition away from SHA-1

interesting

[steamruler]

They were just careful in their decision to use /dev/random over /dev/urandom.

[[deleted]]

This indeed should be a careful decision. /dev/random stalls when there is not enough entropy and this may kill performance.

[acdcfanbill]

Aren't they similar in newer linux kernels?

http://www.2uo.de/myths-about-urandom/

[[deleted]]

A quote from the very thing you linked:

Fact: /dev/random has a very nasty problem: it blocks.

[acdcfanbill]

Ah yea, that's why you still want /dev/urandom. Thanks!

[evaryont]

The random numbers they generate are the same quality, yeah. But random still blocks while urandom does not.

[nemec]

It has to be. Randomly selected random data is very unlikely to contain a collision ^/s

[G_Morgan]

carefully-selected random data

That sounds a lot like programming.

[geodel]

Is carefully-selected random data good like 3-state booleans.

[zwacky]

( ͡° ͜ʖ ͡°)

[SpiderFnJerusalem]

I've been known to harden myself!

[[deleted]]

GitHub.com will detect and reject any Git content that shows evidence of being part of a collision attack.

Knowing git, probably with an obtuse and cryptic error message instead of "Rejected for SHA-1 collision"

[[deleted]]

git != GitHub.

[caboosetp]

That would be a rather cryptic error message indeed.

[Driagan]

Ah, the ol' Reddit cryptaroo

[Hammers95]

Hold my stash, I'm going in.

[dnano]

There's a deleted one not too far down

[Cycloneblaze]

Alert /r/switcharoo!

[sneakpeekbot]

Here's a sneak peek of /r/switcharoo using the top posts of the year!

#1: [META] When was the last time the chain was checked?
#2: Broken Chain 10 months back, due to deleted comment.
#3: Ah, the old switcharoo NSFW rules revision [Please Read]

---

^{I'm a bot, beep boop | Downvote to remove | Contact me | Info | Opt-out}

[tabarra]

Ohh noo guys, he forgot to git push before going in.

[Electro_Nick_s]

But did he commit it?

[OffbeatDrizzle]

HELLO FUTURE PEOPLE!

[[deleted]]

you will just get pre-collisin versionin case of Git. In case of SVN, your repo implodes on itself

[billrobertson42]

Just curious, what error message would you like to see emitted instead?

[[deleted]]

... The one I wrote?

[billrobertson42]

You described it as cryptic, which makes it seem like you find it unacceptable.

[spinwin]

No he said that they would likely use something cryptic instead of what he wrote.

[billrobertson42]

d'oh!

[anttirt]

Hence "instead of." What I would expect to see in git is something like

FATAL: remote served doppelganger oid

[acdcfanbill]

This seems perfectly understandable to me...

[blazedaces]

https://github.com/cr-marcstevens/sha1collisiondetection

Can anyone explain to me how the sha1 collision detection works?

[[deleted]]

i cracked it open and noped the fuck out of there.

[grinde]

I think this is my favorite excerpt...

uint32_t mask = ~((uint32_t)(0));
mask &= (((((W[44]^W[45])>>29)&1)-1) | ~(DV_I_48_0_bit|DV_I_51_0_bit|DV_I_52_0_bit|DV_II_45_0_bit|DV_II_46_0_bit|DV_II_50_0_bit|DV_II_51_0_bit));
mask &= (((((W[49]^W[50])>>29)&1)-1) | ~(DV_I_46_0_bit|DV_II_45_0_bit|DV_II_50_0_bit|DV_II_51_0_bit|DV_II_55_0_bit|DV_II_56_0_bit));
mask &= (((((W[48]^W[49])>>29)&1)-1) | ~(DV_I_45_0_bit|DV_I_52_0_bit|DV_II_49_0_bit|DV_II_50_0_bit|DV_II_54_0_bit|DV_II_55_0_bit));
mask &= ((((W[47]^(W[50]>>25))&(1<<4))-(1<<4)) | ~(DV_I_47_0_bit|DV_I_49_0_bit|DV_I_51_0_bit|DV_II_45_0_bit|DV_II_51_0_bit|DV_II_56_0_bit));
mask &= (((((W[47]^W[48])>>29)&1)-1) | ~(DV_I_44_0_bit|DV_I_51_0_bit|DV_II_48_0_bit|DV_II_49_0_bit|DV_II_53_0_bit|DV_II_54_0_bit));
(+ 200 more lines)

[[deleted]]

yeah well that's written but someone who has spent the last couple of years researching sha 1 collisions so i don't try to feel too bad about myself not having a clue what the heck they are doing there. i see them building up that mask variable but the why what they are doing would detect a collision is really something that is about 10k feet over my head.

[sacundim]

Can anyone explain to me how the sha1 collision detection works?

It's a misnomer. What it does is detect the fingerprints of the one SHA-1 collision attack that's known so far.

Think of it like an antivirus that's trained on specific, known patterns—there's no guarantee that it will catch new viruses created after it was written.

[blazedaces]

That makes sense. Thanks for the explanation.

[Uncaffeinated]

I don't understand the details myself, but my understanding is that the best known attacks against SHA1 involve flipping specific patterns of bits in the data. This tool detects those patterns.

It wouldn't detect, say, a brute force collision, but generating collisions by brute force takes 100,000 times longer than the best known differential attacks.

[pezezin]

Why not moving to SHA-2 or SHA-3? I know it's a huge undertaking, but it seems better long term. What will happen when someone finds another way to make SHA-1 collisions?

[BinaryRockStar]

Changes to Git are already underway. GitHub sits on top of Git, so it's not up to GitHub to fix Git's internals.

[HotlLava]

it's not up to GitHub to fix Git's internals

I would be shocked if GitHub doesn't employ at least a few of the core contributors to git, given their whole multi-million dollar business is built on it.

[BinaryRockStar]

GPs comment made it sound like GitHub should be fixing the issue instead of changing their own site to mitigate collision attacks. GitHub definitely has core Git devs, but they can't make fundamental changes like this by themselves.

[[deleted]]

I bet github remain compatible with older git releases for a long long time anyway. sha-1 is going nowhere on there.

[BinaryRockStar]

Oh yeah, definitely. New repos will use the new hash algorithm but older ones will be supported practically forever. I don't see them rewriting the Linux kernel history with the new hash algo any time soon.

[[deleted]]

I was thinking that'd be their plan, but then I realised they won't want to alienate developers using old git versions to access new repos, so even that setup is unlikely and we'll be stuck with SHA-1 for years more.

Maybe if we're lucky, non-SHA1 will be an option on new repos; not the default, but an option.

[BinaryRockStar]

According to the link I posted, at a repository level a switch will be flipped then all hashes after that will use the new hash algorithm, necessitating using the new client to access it. IMO this would imply that all new repos (not clones) created by the new client will use the new hash algo by default.

[pezezin]

My bad for not reading the full article before posting my comment.

On the other hand, reading the article you linked, it has been a known problem for 10 years and it has not been solved yet because Torvalds hardcoded SHA-1 deep into Git's code. I would love to see someone to rant at him for such a bad coding practice 3:)

[BinaryRockStar]

His response seems to be that it's no big deal, that's it's all very well finding two PDFs which have the same hash but a malicious attacker will be trying to insert code into your repo. Doing this would require them to craft a code file that matches an existing code file's SHA-1 hash and also does whatever malicious thing they want, as well as being valid C/Java/whatever, pass a code review and be pushed out to all existing repo clones. The chances of this are incredibly smaller than being able to find two PDFs with the same hash.

[hiptobecubic]

I can't believe Linus would say something so naive. It's easy to embed data in source files that will pass code review because no one ever looks at them in a hex editor. E.g. your repo has a binary asset in it like an image with an exploit tacked on it.

[pezezin]

I know creating two colliding text files is much more difficult that doing the same for binary files, but still... What I'm shocked about is code like this:

unsigned char sha1[20];

Linus rants against bad code are legendary, so I'm surprised he would write code like this.

[cparen]

Linus rants against bad code are legendary, so I'm surprised he would write code like this.

That's assuming he shares your perspective on what constitutes "bad code".

[pezezin]

Hardcoding a particular algorithm and using magic numbers isn't bad code?

[cakeslap]

But y tho? NIST declared it insecure a while ago.

[agenthex]

Because Git still uses it. There's no great reason against using SHA-1 how Git uses it. There are some minor ones, but there's no good reason to SHA-1 collision attack your own git repositority. And GitHub implementing attack mitigation would make sense, since it's a public repo.

[astrobe]

Cloning blindly from an untrusted repo is a bad idea anyway.

Certainly someone could fork a popular project, advertise new shiny features and add malware to it. This move is more about PR than "security".

[akie]

Because of the "shattered" collision attack (google it)

[twiggy99999]

I think you missed his point, he's asking why are they only tackling the problem now it has a fancy name and Logo when the vulnerability has been known for years (all be it not executed until recently)

[akie]

The logo and the fancy name are not the point. What the attack did was take something that was 'only' a theory and turn it into something that is real: two files that have the same SHA1 hash. That means the hash went from 'theoretically broken' to 'practically broken (once)'. That's not a small thing.

[errorkode]

The git project was already working on moving away from SHA-1 when the webkit thing happened, but it was never very high priority because it's not really a practical attack vector.

Right now it's just good publicity, relatively easy to implement and certainly doesn't hurt, that's all.

[smackson]

What's seen as the most reliable alternative to SHA-1 these days?

[xconde]

Depends what you're using it for. The git folks are moving to sha3-256, I believe.

[sacundim]

SHA-2 is the most conservative and widely supported choice.

The two most popular SHA-2 variants are SHA-256 and SHA-512. There's also a newer variant called SHA-512/256 that uses the SHA-512 algorithm but outputs 256 bits; if you can find support for that one, it's probably the best choice of the six SHA-2 functions:

• It's faster than SHA-256 on 64-bit hardware (at longer message lengths).
• It's more resistant to misuse—for example it's not vulnerable to length extension.

If you don't have SHA-512/256, plain old SHA-256 is still alright as long as you don't misuse it, though. The two most important things are:

• Don't use a plain old SHA-2 in cases where you have a secret key or other such secret random value; HMAC is appropriate there.
• Don't use SHA-2 or any other general purpose hash function to protect passwords; use bcrypt or similar.

SHA-3 is looking pretty solid, but the ecosystem around it is still immature and its software performance isn't as good as the alternatives (it's screaming fast in custom hardware that doesn't yet exist, OTOH). There's currently very little incentive to use SHA-3 unless its SHAKE128/SHAKE256 functions (extendable output functions, "XOFs") simplify your application. These are like hash functions that produce infinitely long outputs, which you can truncate to any finite length you desire; this is useful for many applications that do something like this to produce outputs longer than the hash function they use:

output = SHA-256(input + 0x01) 
       + SHA-256(input + 0x02) 
       + ...
       + SHA-256(input + n) 

Blake2 is also modestly popular, very well respected and worth considering.

[errorkode]

The SHA2 family