7 ms·

Abusing SHA-1 collisions for Chromium updates

183 points by lelf 7y ago

ktta 7y ago
Relevant thread: https://twitter.com/stdlib/status/1136629930060636162 https://twitter.com/stdlib/status/1136629930060636162
- obituary_latte 7y ago
  O/T but anyone else have problems with mobile.twitter on iOS? It never seems to work for me - just times out. Both WiFi and cellular. 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.
  - jen729w 7y ago
    I often get the old generic “an error occurred” nonsense. I’m not signed in. Tin-foil-hat-me wonders if I’d see it as much if I were...
  - EvilTerran 7y ago
    I have a similar problem on my firefox-on-android: when I load a mobile.twitter link, it usually pinwheels for a bit, then throws up an error - either "you're rate limited" or just "something went wrong" (or, occasionally, it just pinwheels forever); then, regardless of which way it failed, loading the page a second time almost always works - but only if I do a proper reload from the browser UI, the in-page "try again" button doesn't help. 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.
    - ikeboy 7y ago
      It's a referer header issue. Caused by the mitigation in https://blog.twitter.com/engineering/en_us/topics/insights/2018/twitter_silhouette.html https://blog.twitter.com/engineering/en_us/topics/insights/2...
  - ikeboy 7y ago
    Typically need to reload. Twitter needs to recognize the referer header which doesn't work properly on some platforms, if you reload from Twitter the header is fine. See https://blog.twitter.com/engineering/en_us/topics/insights/2018/twitter_silhouette.html https://blog.twitter.com/engineering/en_us/topics/insights/2...
rurban 7y ago
This is would I would call a hack. Finally a real hack in the wild after many years!
Scaevolus 7y ago
If I'm understanding this glorious hack correctly, this allows Nix to determine if Chrome has an update available: 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 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-official/chromium-74.0.3729.169.tar.xz 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/ed8f3b5fa3cebfc3662ad5fff098567616220cf8 https://github.com/NixOS/nixpkgs/commit/ed8f3b5fa3cebfc3662a...
- tomsmeding 7y ago
  The cheap way to return more complex data than a boolean is to return more booleans -- i.e. split the version number up in bits and return them one by one. Not saying you should do this though :p
  - WorldMaker 7y ago
    This is funny because it is more the opposite case: they wanted the simplicity of returning a Boolean but the system doesn't allow that in this particular part of the pipeline. So they built a much more complex data structure to implement that simple Boolean.
- Kenji 7y ago
  Allowing broken hashes makes the entire system insecure. If you use broken hashes for security, you might as well not use hashes at all. The entire point of a hash is that collisions are pretty much impossible to generate.
tus87 7y ago
God tell me they check len(bytes) as well..
tomsmeding 7y ago
Summary by _max_bo_ in the twitter thread (https://twitter.com/stdlib/status/1136629930060636162 https://twitter.com/stdlib/status/1136629930060636162) linked elsewhere: > 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.
- mbo 7y ago
  Hey that's actually me :) I think there's better explanations elsewhere in that thread (and this one as well). It a was vastly simplified description for a non-technical friend of mine that I replied to.
craigds 7y ago
Why would Chrome return non-deterministic bytes for a versioned release?
- idle_zealot 7y ago
  A/B testing?
- vbezhenar 7y ago
  So they could return special build for people targeted by NSA and nobody would be surprised that their download is different.
userbinator 7y ago
Although collisions have been found for both SHA1 and MD5 (and the latter are much easier to generate), as far as I know it's still extremely difficult to generate a file with a given hash ("preimage attack")... I wonder if that property might make it useful for some things, since generating collisions even for MD5 is still much more time-consuming than verifying them, and generating a colliding pair means that finding another block with the same hash is still near-impossible.
- tialaramex 7y ago
  > as far as I know it's still extremely difficult to generate a file with a given hash 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.
grhmc 7y ago
Something I think is a bit misunderstood here is what this is for, and why it was made. 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. [0] https://github.com/aszlig/shellfuck/blob/master/bf.sh https://github.com/aszlig/shellfuck/blob/master/bf.sh
ga-vu 7y ago
This doesn't actually look like a SHA-1 collision attack, tbh

183 points by lelf 7y ago

ktta 7y ago

Relevant thread: https://twitter.com/stdlib/status/1136629930060636162 https://twitter.com/stdlib/status/1136629930060636162

obituary_latte 7y ago
O/T but anyone else have problems with mobile.twitter on iOS? It never seems to work for me - just times out. Both WiFi and cellular. 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.
- jen729w 7y ago
  I often get the old generic “an error occurred” nonsense. I’m not signed in. Tin-foil-hat-me wonders if I’d see it as much if I were...
- EvilTerran 7y ago
  I have a similar problem on my firefox-on-android: when I load a mobile.twitter link, it usually pinwheels for a bit, then throws up an error - either "you're rate limited" or just "something went wrong" (or, occasionally, it just pinwheels forever); then, regardless of which way it failed, loading the page a second time almost always works - but only if I do a proper reload from the browser UI, the in-page "try again" button doesn't help. 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.
  - ikeboy 7y ago
    It's a referer header issue. Caused by the mitigation in https://blog.twitter.com/engineering/en_us/topics/insights/2018/twitter_silhouette.html https://blog.twitter.com/engineering/en_us/topics/insights/2...
- ikeboy 7y ago
  Typically need to reload. Twitter needs to recognize the referer header which doesn't work properly on some platforms, if you reload from Twitter the header is fine. See https://blog.twitter.com/engineering/en_us/topics/insights/2018/twitter_silhouette.html https://blog.twitter.com/engineering/en_us/topics/insights/2...

rurban 7y ago

This is would I would call a hack. Finally a real hack in the wild after many years!

Scaevolus 7y ago

If I'm understanding this glorious hack correctly, this allows Nix to determine if Chrome has an update available: 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 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-official/chromium-74.0.3729.169.tar.xz 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/ed8f3b5fa3cebfc3662ad5fff098567616220cf8 https://github.com/NixOS/nixpkgs/commit/ed8f3b5fa3cebfc3662a...

tomsmeding 7y ago
The cheap way to return more complex data than a boolean is to return more booleans -- i.e. split the version number up in bits and return them one by one. Not saying you should do this though :p
- WorldMaker 7y ago
  This is funny because it is more the opposite case: they wanted the simplicity of returning a Boolean but the system doesn't allow that in this particular part of the pipeline. So they built a much more complex data structure to implement that simple Boolean.
Kenji 7y ago
Allowing broken hashes makes the entire system insecure. If you use broken hashes for security, you might as well not use hashes at all. The entire point of a hash is that collisions are pretty much impossible to generate.

tus87 7y ago

God tell me they check len(bytes) as well..

tomsmeding 7y ago

Summary by _max_bo_ in the twitter thread (https://twitter.com/stdlib/status/1136629930060636162 https://twitter.com/stdlib/status/1136629930060636162) linked elsewhere: > 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.

mbo 7y ago
Hey that's actually me :) I think there's better explanations elsewhere in that thread (and this one as well). It a was vastly simplified description for a non-technical friend of mine that I replied to.

craigds 7y ago

Why would Chrome return non-deterministic bytes for a versioned release?

idle_zealot 7y ago
A/B testing?
vbezhenar 7y ago
So they could return special build for people targeted by NSA and nobody would be surprised that their download is different.

userbinator 7y ago

Although collisions have been found for both SHA1 and MD5 (and the latter are much easier to generate), as far as I know it's still extremely difficult to generate a file with a given hash ("preimage attack")... I wonder if that property might make it useful for some things, since generating collisions even for MD5 is still much more time-consuming than verifying them, and generating a colliding pair means that finding another block with the same hash is still near-impossible.

tialaramex 7y ago
> as far as I know it's still extremely difficult to generate a file with a given hash 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.

grhmc 7y ago

Something I think is a bit misunderstood here is what this is for, and why it was made. 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. [0] https://github.com/aszlig/shellfuck/blob/master/bf.sh https://github.com/aszlig/shellfuck/blob/master/bf.sh

ga-vu 7y ago

This doesn't actually look like a SHA-1 collision attack, tbh