Abusing SHA-1 collisions for Chromium updates
github.com
github.com
1) Nix network access is only allowed for things where you guarantee the hashes of what's output. This is generally used to do things like "download http://example.com/release-1.2.tar.xz, it will have SHA1 93f3025c7802a1a11e4f16186089b583ef1095b8"
2) There are known pairs of strings that have equivalent SHA1 hashes.
3) To determine if a fetch would succeed in a "pure" way, write a network-accessing function that will return a "true" or "false" string with identical hashes, then you can use that (supposedly deterministic) string to return a (nondeterministic!) True or False to the caller.
4) This is used to run a command like `curl -s -L -f -I https://commondatastorage.googleapis.com/chromium-browser-of... `. If the command succeeds, we know we can use this version of the browser to update.
I don't know how it reads the channel version data without running into the same determinism issues.
Here's the latest update to the hack, moving from MD5 to SHA1: https://github.com/NixOS/nixpkgs/commit/ed8f3b5fa3cebfc3662a...
Second pre-image attacks aren't possible (a theoretical pre-image attack exists for MD5 with difficulty just marginally better than brute force, this is a further good reason to stop using MD5 but isn't an immediate problem). So only the person who made file X1 could have produced file X2 with the same MD5() or SHA1(), since they could have produced both with a deliberate collision, whereas anybody else would be obliged to create a second pre-image.
One of the great things about Nix is that it keeps packages honest about versioning; you can't sneak in an updated package with the same version number like is possible with other package systems that don't pin to hashes.
They would have to have set up the hash collision beforehand. It's no longer an 'innocent file'. It's nothing something you can decide to do at a later point.
I understand these things independently: 1) SHA1 collision weakness 2) Nix checking package SHA1 when updating packages 3) Chromium returning different SHA1 for each download
Seriously, what is this?
edit: I just read mbrock's comment above which explained it perfectly. Didn't realize it was testing the url to see if there was an actual update available, I thought it was doing the actual update.
While doing so, they found themselves needing some kind of "tryFetch" function that would return true or false depending on whether a certain URL is reachable.
But there's no such function in Nix. Why not? Because you're not really supposed to do stuff like that in the Nix paradigm which is all about determinism.
So... they really wanted to do it anyway, so they invented a clever hack, probably too clever.
What can you do in Nix? Well, you can make a package that downloads a certain URL and uses the downloaded result, provided that all the observable outputs of that package are deterministic. So after the package's build script runs, Nix verifies that the result matches a hash specified in the package definition. If the hash doesn't match, the package fails to evaluate.
So this hacker decided to make such a package that tries to download the Chrome update and results in the boolean information about whether the update was available. But the result needs to have the same hash in both cases. That's where a hash collision comes in handy.
So this hacky build script uses a couple of well-known PDF files that both have the same SHA1 hash. If the update exists, it gives PDF 1, otherwise it gives PDF 2.
The update script then depends on that hack package. It "installs" that package, and then checks whether it actually contains PDF 1 or PDF 2, and now it knows whether the Chrome update was available or not.
That's the part I always feel when looking at FP languages. They sound good on paper, examples are very tempting, but when reality kicks in to this pure, predictable, perfect world, it turns into a massive pain.
Generally speaking these sandbox determinism requirements in Nixpkgs/NixOS are not annoying, they are a crucial feature: you know what you get when you install something. But yeah, it is a constraint, and sometimes when you try to package some weird program where the Makefile does some arbitrary network operations, you might find it annoying -- and you can locally disable the sandbox -- but the whole Nix philosophy is that build scripts should be reproducible, so then you just have to fix it.
What the author of the script has done here, you’re supposed to do by writing code in some other language that generates a Nix manifest (or just by hand-rolling a Nix manifest.) And yet, the author here managed to get Nix to non-deterministically generate Nix.
Considered from the point of view of Nix’s goals, this is more an “exploit” than a truly-needed feature.
The person who wrote this (aszlig) is truly a hacker, contorting tools to do interesting things -- and indeed, you see his cleverness at work here.
This is an update script, which is run by hand, by a maintainer, to update the Nix expression for Chromium.
This script could have been written in Python, Bash, Perl, or PowerPoint for all it matters. Or even Brainfuck using aszlig's own brainfuck interpreter written in bash[0]. This script could be deleted today and make no difference to using Nix. It is not part of any running system.
This doesn't mean Nix is insecure or broken, and no abuse like this is used anywhere in the Nix package set.
> chrome wants things different. nix wants things to be the same, always. nixpkg programmer invokes horrifying incantation from the depths of hell to trick nix into thinking two different things are the same.
Edit: this is really strange. Tried opening in a new tab and as it was stuck loading (progress bar halted at about 1/4), I opened “view source” app I have installed. It showed empty html/head/body tags and upon closing, twitter loaded up immediately.
I figure something's timing out on the first attempt, but various bits get downloaded & cached before it fails, meaning the second try runs fast enough to not hit the same timeout.
See https://blog.twitter.com/engineering/en_us/topics/insights/2...
I think this might give a false impression, "still extremely difficult" here means that you'd need to do on average far more than 2^120 hash operations to do this. If you had a billion computers that could do this one billion times per second, and you did that for a billion seconds (ie several decades) you're still doing a billion times too few operations to have any significant chance of finding your pre-image.
However, because all Merkle–Damgård hashes (MD4, MD5, SHA-1, SHA-256, SHA-512) are subject to length extension, you don't need to generate new collisions you can just length-extend an existing one at leisure.
That is - take the | operator to be a string concatenation. At a high level if I know A, B such that MD5(A) = MD5(B) then I can trivially choose x and have MD5(A|x) = MD5(B|x) without doing any of the collision work again.
"Sponge" constructions like SHA3 don't do this. If somebody finds a way to make A, B such that SHA3(A) = SHA3(B) then almost certainly SHA3(A|x) is not equal to SHA3(B|x) for arbitrary values of x because the output from SHA3() is a summary ("squeezing out" the sponge) not the internal state itself.