6 ms·

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shatt

by est31 7y ago

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shattered collision already: $ curl https://shattered.io/static/shattered-1.pdf https://shattered.io/static/shattered-1.pdf | wc -c 422435 $ curl -s https://shattered.io/static/shattered-2.pdf https://shattered.io/static/shattered-2.pdf | wc -c 422435 Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look up Merkle-Damgard construction: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co... There is benefit in storing the length at the prefix as well, as you can avoid length extension attacks, but that's not making attacks "much harder".

tny 7y ago
But even if the lengths are same, the resulting SHA1 will be different since you prefix the length before hashing
- est31 7y ago
  The shattered prefix was chosen as well, see my other comment in the thread: https://news.ycombinator.com/item?id=21980759 https://news.ycombinator.com/item?id=21980759 The only thing that prefixing the length makes difficult is using the same prefix multiple times: you basically have to make up your mind about the type and length before mounting the shattered attack. Also, the prefix means you have to do your own shattered attack and can't use the PDFs that google provided as proof of their project's success. Price tag for that seems to be 11k. [1]: https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection
toyg 7y ago
Yeah, that quote doesn't exactly make me confident about Linus's understanding of this particular issue.
- DarkWiiPlayer 7y ago
  It's not about it being the same length, but the length of the data being part of the hashed data, which, Linus assumes, will likely make it more difficult to find a collision. He even says at the beginning that he hasn't had a look at the attack yet and is just making an assumption.
  - est31 7y ago
    > It's not about it being the same length, but the length of the data being part of the hashed data As I tried to point out, the length is already part of what the SHA-1 function hashes: https://tools.ietf.org/html/rfc3174#section-4 https://tools.ietf.org/html/rfc3174#section-4 As a summary, a "1" followed by m "0"s followed by a 64- bit integer are appended to the end of the message to produce a padded message of length 512 * n. The 64-bit integer is the length of the original message. The padded message is then processed by the SHA-1 as n 512-bit blocks. Now, storing the length as a prefix does give you advantages: you can't mount a length extension attack, which limits your ability to exploit one shattered attack, e.g. the pdfs released by google, for different files/types of files. But it doesn't make mounting a novel shattered attack "much harder" as Linus claims.
    - magicalhippo 7y ago
      > But it doesn't make mounting a novel shattered attack "much harder" as Linus claims. From what I understood the core of Linus' argument[1] is that it's very hard to make a "bad" variant of the code which has the same length _and_ the same hash while still looking like sane code. For random data files, sure those are more at risk. [1]: https://marc.info/?l=git&m=148787287624049&w=2 https://marc.info/?l=git&m=148787287624049&w=2
      - wbl 7y ago
        A good thing no one checks binary assets into source control
      - est31 7y ago
runeks 7y ago
The point is that the hashed data must follow a specific data format, and can’t just be arbitrary data. This means that the collision data MUST contain the length at some specific offset in the data, which makes it harder to find a collision. The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.
- est31 7y ago
  Yeah the data must start with a specific prefix, but can otherwise contain whatever it wants. Anyways, even the shattered attack, which this paper says costs 11k to execute today, had a pdf specific prefix (the shown part is the same in both files): $ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -n 512 -C 00000000 25 50 44 46 2d 31 2e 33 0a 25 e2 e3 cf d3 0a 0a |%PDF-1.3.%......| 00000010 0a 31 20 30 20 6f 62 6a 0a 3c 3c 2f 57 69 64 74 |.1 0 obj.<</Widt| 00000020 68 20 32 20 30 20 52 2f 48 65 69 67 68 74 20 33 |h 2 0 R/Height 3| 00000030 20 30 20 52 2f 54 79 70 65 20 34 20 30 20 52 2f | 0 R/Type 4 0 R/| 00000040 53 75 62 74 79 70 65 20 35 20 30 20 52 2f 46 69 |Subtype 5 0 R/Fi| 00000050 6c 74 65 72 20 36 20 30 20 52 2f 43 6f 6c 6f 72 |lter 6 0 R/Color| 00000060 53 70 61 63 65 20 37 20 30 20 52 2f 4c 65 6e 67 |Space 7 0 R/Leng| 00000070 74 68 20 38 20 30 20 52 2f 42 69 74 73 50 65 72 |th 8 0 R/BitsPer| 00000080 43 6f 6d 70 6f 6e 65 6e 74 20 38 3e 3e 0a 73 74 |Component 8>>.st| 00000090 72 65 61 6d 0a ff d8 ff fe 00 24 53 48 41 2d 31 |ream......$SHA-1| 000000a0 20 69 73 20 64 65 61 64 21 21 21 21 21 85 2f ec | is dead!!!!!./.| The shattered attack was about a so-called "identical prefix" collision, while the shambles paper's collision was a "chosen prefix" one. You can choose it in both cases, but in the "chosen prefix" one both colliding prefixes can be entirely different (and can be as long as you want btw, the attack doesn't cost more if the prefix is 4 KB vs 4 GB), while in the "identical prefix" case it has to be identical.
- toyg 7y ago
  > the harder it is to find a collision that’s valid in the given application context In the double-digit thousands of dollars, an attack that gets 10x or 100x harder is still cheap for state actors. Assuming the NSA is at least a year or two ahead of the field, git should now accelerate its migration process.

by est31 7y ago

tny 7y ago

But even if the lengths are same, the resulting SHA1 will be different since you prefix the length before hashing

est31 7y ago
The shattered prefix was chosen as well, see my other comment in the thread: https://news.ycombinator.com/item?id=21980759 https://news.ycombinator.com/item?id=21980759 The only thing that prefixing the length makes difficult is using the same prefix multiple times: you basically have to make up your mind about the type and length before mounting the shattered attack. Also, the prefix means you have to do your own shattered attack and can't use the PDFs that google provided as proof of their project's success. Price tag for that seems to be 11k. [1]: https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection

toyg 7y ago

Yeah, that quote doesn't exactly make me confident about Linus's understanding of this particular issue.

DarkWiiPlayer 7y ago
It's not about it being the same length, but the length of the data being part of the hashed data, which, Linus assumes, will likely make it more difficult to find a collision. He even says at the beginning that he hasn't had a look at the attack yet and is just making an assumption.
- est31 7y ago
  > It's not about it being the same length, but the length of the data being part of the hashed data As I tried to point out, the length is already part of what the SHA-1 function hashes: https://tools.ietf.org/html/rfc3174#section-4 https://tools.ietf.org/html/rfc3174#section-4 As a summary, a "1" followed by m "0"s followed by a 64- bit integer are appended to the end of the message to produce a padded message of length 512 * n. The 64-bit integer is the length of the original message. The padded message is then processed by the SHA-1 as n 512-bit blocks. Now, storing the length as a prefix does give you advantages: you can't mount a length extension attack, which limits your ability to exploit one shattered attack, e.g. the pdfs released by google, for different files/types of files. But it doesn't make mounting a novel shattered attack "much harder" as Linus claims.
  - magicalhippo 7y ago
    > But it doesn't make mounting a novel shattered attack "much harder" as Linus claims. From what I understood the core of Linus' argument[1] is that it's very hard to make a "bad" variant of the code which has the same length _and_ the same hash while still looking like sane code. For random data files, sure those are more at risk. [1]: https://marc.info/?l=git&m=148787287624049&w=2 https://marc.info/?l=git&m=148787287624049&w=2
    - wbl 7y ago
      A good thing no one checks binary assets into source control
    - est31 7y ago

runeks 7y ago

The point is that the hashed data must follow a specific data format, and can’t just be arbitrary data. This means that the collision data MUST contain the length at some specific offset in the data, which makes it harder to find a collision. The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.

est31 7y ago
Yeah the data must start with a specific prefix, but can otherwise contain whatever it wants. Anyways, even the shattered attack, which this paper says costs 11k to execute today, had a pdf specific prefix (the shown part is the same in both files): $ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -n 512 -C 00000000 25 50 44 46 2d 31 2e 33 0a 25 e2 e3 cf d3 0a 0a |%PDF-1.3.%......| 00000010 0a 31 20 30 20 6f 62 6a 0a 3c 3c 2f 57 69 64 74 |.1 0 obj.<</Widt| 00000020 68 20 32 20 30 20 52 2f 48 65 69 67 68 74 20 33 |h 2 0 R/Height 3| 00000030 20 30 20 52 2f 54 79 70 65 20 34 20 30 20 52 2f | 0 R/Type 4 0 R/| 00000040 53 75 62 74 79 70 65 20 35 20 30 20 52 2f 46 69 |Subtype 5 0 R/Fi| 00000050 6c 74 65 72 20 36 20 30 20 52 2f 43 6f 6c 6f 72 |lter 6 0 R/Color| 00000060 53 70 61 63 65 20 37 20 30 20 52 2f 4c 65 6e 67 |Space 7 0 R/Leng| 00000070 74 68 20 38 20 30 20 52 2f 42 69 74 73 50 65 72 |th 8 0 R/BitsPer| 00000080 43 6f 6d 70 6f 6e 65 6e 74 20 38 3e 3e 0a 73 74 |Component 8>>.st| 00000090 72 65 61 6d 0a ff d8 ff fe 00 24 53 48 41 2d 31 |ream......$SHA-1| 000000a0 20 69 73 20 64 65 61 64 21 21 21 21 21 85 2f ec | is dead!!!!!./.| The shattered attack was about a so-called "identical prefix" collision, while the shambles paper's collision was a "chosen prefix" one. You can choose it in both cases, but in the "chosen prefix" one both colliding prefixes can be entirely different (and can be as long as you want btw, the attack doesn't cost more if the prefix is 4 KB vs 4 GB), while in the "identical prefix" case it has to be identical.
toyg 7y ago
> the harder it is to find a collision that’s valid in the given application context In the double-digit thousands of dollars, an attack that gets 10x or 100x harder is still cheap for state actors. Assuming the NSA is at least a year or two ahead of the field, git should now accelerate its migration process.