7 ms·

So the big problem with Git and SHA1 is that in many cases you are giving full control to an untrusted third party over the sha1 hash of something. For example,

So the big problem with Git and SHA1 is that in many cases you are giving full control to an untrusted third party over the sha1 hash of something. For example, if you merge a binary file, it'd be quite easy for them to generate two different versions of the same file, with the same SHA1 digest, and then use the second version to cause problems in the future. You may also be able to modify a text file in the same way without getting noticed in review (I'm not up to speed on how advanced sha1 collision techniques are now). Similarly, the git commits you merge themselves could have that done - the actual git commit serialization gives you a fair bit of ability to append stuff to it that isn't shown in the UI. That wouldn't affect the signed git commits. But it's still dubious to have the ability to change old history in a checkout. Anyway, Git is apparently moving towards SHA256 support, so hopefully this problem will be fixed soon: https://lwn.net/Articles/823352/ https://lwn.net/Articles/823352/

thephyber 6y ago
> it'd be quite easy for them to generate two different versions of the same file Citation needed. When SHA1 was cracked, it cost $110k worth of cloud computing. And there was some restriction on the two files which matched checksums. IIRC it was like the Birthday Paradox — you don’t pick one and find another sharing the same match, but you generate billions of mutations of similar binaries and statistically two would have the same checksum. Not exactly easy, fast, cheap, or work with all use cases.
- cratermoon 6y ago
  It was $11K https://www.usenix.org/conference/usenixsecurity20/presentation/leurent https://www.usenix.org/conference/usenixsecurity20/presentat...
  - bawolff 6y ago
    That was a later attack, not the original. Attacks get cheaper with time.
- westurner 6y ago
  That nonce value could be ±\0 or 5,621,964,321e100; though for well-designed cryptographic hash functions it's far less likely that - at maximum difficulty - a low nonce value will result in a hash collision.
  - bawolff 6y ago
    ? How are nonces even involved in this?
    - westurner 6y ago
      Searching for the value to prepend or append that causes a hash collision is exactly the same as finding a nonce value at maximum difficulty (not less than the difficulty value, exactly equal to the target hash). Mutate and check.
      - bawolff 6y ago
        The term nonce has a broader meaning than how it is used in bitcoin. (Edit: i reworded this sentence from what i originally had) That said, no, finding a collision and finding a preimage are very different things, and well the collision attacks on sha1 will involve a lot of guessing and checking, they are not generic birthday or bruteforce attacks but rely on weaknesses in sha-1 to be practical. They also do not make preimage attacks practical.
        westurner 6y ago
        Brute forcing to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Write each and compare the cost/fitness/survival functions. If the hash function is reversible - as may be discovered through e.g. mutation and selection - that would help find hashes that are equal and maybe also less than. Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: it's not necessary to search the whole space for simple collisions and may not be necessary for preimages; we don't know and it's just a matter of time. "Collision attack" https://en.wikipedia.org/wiki/Collision_attack https://en.wikipedia.org/wiki/Collision_attack Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing
- bawolff 6y ago
  Later versions of the attack were much cheaper and also chosen prefix collisions which are much less restrictive in the requirements on the file.
- petertodd 6y ago
  > And there was some restriction on the two files which matched checksums. I know. That's why I mentioned the difference in difficulty between getting a collision in binary files and git commit objects themselves, and textual sourcecode.
zie 6y ago
'quite easy' is relative, and just because you can find some file that matches the hash, there is also a very high likelihood that the file will be useless. The chances of generating a USEFUL file(where useful means it does something, like compile, nefarious or not) and causes a SHA1 hash collision are very low... currently. So to get a nefarious file that puts in an exploit or something useful for an attacker AND causes a SHA1 collision is a very very high bar to meet, currently. Hopefully they replace SHA1 with SHA256/etc before the capability becomes feasible.
- pdpi 6y ago
  Sort of. This is really tricky to achieve with text files (where the padding necessary to make the hashes line up looks completely out of place), but many binary formats allow arbitrary padding — e.g. zip files have an index at the end. Inversely, png files have a header and ignore meaningless data at the end. Both can be padded with arbitrary data (and, indeed, you can cat a png and a zip together as a janky steganography system)
  - hnedeotes 6y ago
    I have thought about this in regards to Nix but as far as I could conceive, it seemed that: a) you can definitively generate content that will be hashed to the same value - this is a given since anything that compresses a source into a much shorter representation allows that by definition (lets ignore feasibility/time/cost) b) Making a) in a way that the contents are usable for a given purpose, doesn't introduce severe noticeable changes, and plays ball with the remaining stuff (OS, build chains, the context where it's included in, etc) seems to be the actual difficult part So my conclusion was at the time that in terms of feasibility it's probably easier to hack the chain itself replacing the hash. But again, if there's a master "hash" for whatever artefact is produced that relies on all those hashes it would also need to be replaced?
  - michaelt 6y ago
    For text files, tools for brute forcing a git commit hash [1] work by messing with the author and committer timestamps. Of course, that only gives you about 40 bits to play with (assuming the further you move the timestamp, the easier it is to detect) so it wouldn't be completely sufficient on its own. [1] https://github.com/DesWurstes/VanityCommit#alternatives https://github.com/DesWurstes/VanityCommit#alternatives
josefx 6y ago
> For example, if you merge a binary file, it'd be quite easy for them to generate two different versions of the same file, with the same SHA1 digest, and then use the second version to cause problems in the future. I think the last time I saw this come up the response was that git will just ignore your attempt to merge a new file if the checksum is the same. So you would have to compromise the repo server directly to replace it.

thephyber 6y ago

> it'd be quite easy for them to generate two different versions of the same file Citation needed. When SHA1 was cracked, it cost $110k worth of cloud computing. And there was some restriction on the two files which matched checksums. IIRC it was like the Birthday Paradox — you don’t pick one and find another sharing the same match, but you generate billions of mutations of similar binaries and statistically two would have the same checksum. Not exactly easy, fast, cheap, or work with all use cases.

cratermoon 6y ago
It was $11K https://www.usenix.org/conference/usenixsecurity20/presentation/leurent https://www.usenix.org/conference/usenixsecurity20/presentat...
- bawolff 6y ago
  That was a later attack, not the original. Attacks get cheaper with time.
westurner 6y ago
That nonce value could be ±\0 or 5,621,964,321e100; though for well-designed cryptographic hash functions it's far less likely that - at maximum difficulty - a low nonce value will result in a hash collision.
- bawolff 6y ago
  ? How are nonces even involved in this?
  - westurner 6y ago
    Searching for the value to prepend or append that causes a hash collision is exactly the same as finding a nonce value at maximum difficulty (not less than the difficulty value, exactly equal to the target hash). Mutate and check.
    - bawolff 6y ago
      The term nonce has a broader meaning than how it is used in bitcoin. (Edit: i reworded this sentence from what i originally had) That said, no, finding a collision and finding a preimage are very different things, and well the collision attacks on sha1 will involve a lot of guessing and checking, they are not generic birthday or bruteforce attacks but rely on weaknesses in sha-1 to be practical. They also do not make preimage attacks practical.
      - westurner 6y ago
        Brute forcing to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Write each and compare the cost/fitness/survival functions. If the hash function is reversible - as may be discovered through e.g. mutation and selection - that would help find hashes that are equal and maybe also less than. Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: it's not necessary to search the whole space for simple collisions and may not be necessary for preimages; we don't know and it's just a matter of time. "Collision attack" https://en.wikipedia.org/wiki/Collision_attack https://en.wikipedia.org/wiki/Collision_attack Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing
bawolff 6y ago
Later versions of the attack were much cheaper and also chosen prefix collisions which are much less restrictive in the requirements on the file.
petertodd 6y ago
> And there was some restriction on the two files which matched checksums. I know. That's why I mentioned the difference in difficulty between getting a collision in binary files and git commit objects themselves, and textual sourcecode.

zie 6y ago

'quite easy' is relative, and just because you can find some file that matches the hash, there is also a very high likelihood that the file will be useless. The chances of generating a USEFUL file(where useful means it does something, like compile, nefarious or not) and causes a SHA1 hash collision are very low... currently. So to get a nefarious file that puts in an exploit or something useful for an attacker AND causes a SHA1 collision is a very very high bar to meet, currently. Hopefully they replace SHA1 with SHA256/etc before the capability becomes feasible.

pdpi 6y ago
Sort of. This is really tricky to achieve with text files (where the padding necessary to make the hashes line up looks completely out of place), but many binary formats allow arbitrary padding — e.g. zip files have an index at the end. Inversely, png files have a header and ignore meaningless data at the end. Both can be padded with arbitrary data (and, indeed, you can cat a png and a zip together as a janky steganography system)
- hnedeotes 6y ago
  I have thought about this in regards to Nix but as far as I could conceive, it seemed that: a) you can definitively generate content that will be hashed to the same value - this is a given since anything that compresses a source into a much shorter representation allows that by definition (lets ignore feasibility/time/cost) b) Making a) in a way that the contents are usable for a given purpose, doesn't introduce severe noticeable changes, and plays ball with the remaining stuff (OS, build chains, the context where it's included in, etc) seems to be the actual difficult part So my conclusion was at the time that in terms of feasibility it's probably easier to hack the chain itself replacing the hash. But again, if there's a master "hash" for whatever artefact is produced that relies on all those hashes it would also need to be replaced?
- michaelt 6y ago
  For text files, tools for brute forcing a git commit hash [1] work by messing with the author and committer timestamps. Of course, that only gives you about 40 bits to play with (assuming the further you move the timestamp, the easier it is to detect) so it wouldn't be completely sufficient on its own. [1] https://github.com/DesWurstes/VanityCommit#alternatives https://github.com/DesWurstes/VanityCommit#alternatives

josefx 6y ago

> For example, if you merge a binary file, it'd be quite easy for them to generate two different versions of the same file, with the same SHA1 digest, and then use the second version to cause problems in the future. I think the last time I saw this come up the response was that git will just ignore your attempt to merge a new file if the checksum is the same. So you would have to compromise the repo server directly to replace it.