4 ms·

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

by 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
- zie 6y ago
  I agree in binary formats, it's easier to accomplish, but it by no means is easy. Thankfully most source code is plain text. There are mostly trivial ways to encode information in whitespace/etc, but again, the ability to carry some useful information AND commit a SHA1 collision is currently non-trivial. Plus Git has specifically put in some hardening for the existing SHA1 hashes to make this even less feasible in the particular application of a git repo. A pipe wrench to the back of the head(or social engineering) of some random committer is probably a LOT easier to accomplish. That said, if your primary nemesis is one the giant nation states(US, China, Russia, Etc) AND you were very high target for them, then all bets are off, as they can pretty much accomplish whatever they want against any individual/small group on the planet. I would imagine most of us are not even remotely in this situation.
bawolff 6y ago
I dont think this is true. For a chosen prefix collision you need to be able to hide a few bytes of binary data in the file. Sometimes that is prohibitive but in most file formats that is do-able.
- zie 6y ago
  OK, let's assume what you say is true. You spent the $100k or whatever to compute a SHA1 hash collision and you can replace the bits 11011 with the bits 1010. How is this useful? It *MIGHT* be useful, but chances are it's not very useful, as lots of data formats are pretty lossy and a random bitflip here or there doesn't matter that much. Just because you have a SHA1 collision doesn't mean you can put any bits wherever you want and still have it be a SHA1 collision. The really hard part is being able to flip whatever bits you want(to achieve some goal, like a RCE or whatever) AND make it a SHA1 collision. This is currently very much an open problem, nobody has been able to demonstrate(that we are aware of).

by zie 6y ago

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
zie 6y ago
I agree in binary formats, it's easier to accomplish, but it by no means is easy. Thankfully most source code is plain text. There are mostly trivial ways to encode information in whitespace/etc, but again, the ability to carry some useful information AND commit a SHA1 collision is currently non-trivial. Plus Git has specifically put in some hardening for the existing SHA1 hashes to make this even less feasible in the particular application of a git repo. A pipe wrench to the back of the head(or social engineering) of some random committer is probably a LOT easier to accomplish. That said, if your primary nemesis is one the giant nation states(US, China, Russia, Etc) AND you were very high target for them, then all bets are off, as they can pretty much accomplish whatever they want against any individual/small group on the planet. I would imagine most of us are not even remotely in this situation.

bawolff 6y ago

I dont think this is true. For a chosen prefix collision you need to be able to hide a few bytes of binary data in the file. Sometimes that is prohibitive but in most file formats that is do-able.

zie 6y ago
OK, let's assume what you say is true. You spent the $100k or whatever to compute a SHA1 hash collision and you can replace the bits 11011 with the bits 1010. How is this useful? It *MIGHT* be useful, but chances are it's not very useful, as lots of data formats are pretty lossy and a random bitflip here or there doesn't matter that much. Just because you have a SHA1 collision doesn't mean you can put any bits wherever you want and still have it be a SHA1 collision. The really hard part is being able to flip whatever bits you want(to achieve some goal, like a RCE or whatever) AND make it a SHA1 collision. This is currently very much an open problem, nobody has been able to demonstrate(that we are aware of).