4 ms·

Git prepends type and length, that makes an attack significantly more difficult, and certainly you cannot just directly translate the pdf attack to Git. For ap

Git prepends type and length, that makes an attack significantly more difficult, and certainly you cannot just directly translate the pdf attack to Git. For applications, such as signing pdf or other documents, SHA-1 should be retired. But the collective crypto community have said that for more than a decade, so I have little sympathy for companies that is affected by this. But for Git, there is no reason for immediate concern. Should they upgrade to a more secure hash function, yes. Ideally they make it rather straight forward to use different function in the future and perhaps multiple hash functions. I doubt anyone is able to find an input that MD5 and SHA-1 both hash to the same value. It would significantly reduce reliance on a single hash function.

dlubarov 10y ago
> Git prepends type and length, that makes an attack significantly more difficult, and certainly you cannot just directly translate the pdf attack to Git. With the attack vectors discussed above, the type would always be blob. I don't think the length field is much help either; see https://news.ycombinator.com/item?id=13720725 https://news.ycombinator.com/item?id=13720725
- hvidgaard 10y ago
  The length field makes the attack significantly more difficult. In the publish attack, you take 2 fixed input and prepend special data to make the collision. With Git, you have additional constraint. Either it needs to be of exact length, this may or may not be an issue, but most likely is unless we find a new weakness in SHA-1, or you must be able to handle the changing input. In all the examples in your link, while true that you can add "silent data" to all of the examples, they are all examples of structured data. So not only do you have to figure out the collision, you have to do so within the structure of the format you're attacking. This is a lot harder than just prepending the exact bytes you want.
  - jwilk 10y ago
    > The length field makes the attack significantly more difficult. In the publish attack, you take 2 fixed input and prepend special data to make the collision. That's not how the attack works. Not at all.
    - hvidgaard 10y ago
      If you ignore the prepend part, it is in essence taking known input and calculate a collision. > This is an identical-prefix collision attack, where a given prefix P is extended with two distinct near-collision block pairs such that they collide for any suffix S. And > Our example colliding files only differ in two successive random-looking message blocks generated by our attack. We exploit these limited differences to craft two colliding PDF documents containing arbitrary distinct images.
johncolanduoni 10y ago
> I doubt anyone is able to find an input that MD5 and SHA-1 both hash to the same value. It would significantly reduce reliance on a single hash function. As was mentioned in the original collision thread, concatenating insecure hash functions has fundamental weaknesses: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis...
- hvidgaard 10y ago
  Sort of. It does not improve brute force resistance in a meaningful way, but that is not the purpose either. It protects against one of the hash functions being broken. Let us assume that we have 2 160bit hash functions, and one is broken to the degree that we can find collisions in constant time. This now means that we can break the combined hash in 2^80 rather than 2^80 + 2^80. The total brute force complexity was not improved, but the reliance on either hash function was.
  - johncolanduoni 10y ago
    Yes, but you picked two hash functions which are known to be insecure. Their complexity reduction argument appears to apply to cases where you are not using pure brute force for either hash, which would be the case if you were attacking MD5 and SHA1.
    - hvidgaard 10y ago
      I did so quite on purpose. Both are concidered broken, but combined, only the bruteforce attack is known to work, i.e. "the whole is greater than the sum of its parts".

dlubarov 10y ago

> Git prepends type and length, that makes an attack significantly more difficult, and certainly you cannot just directly translate the pdf attack to Git. With the attack vectors discussed above, the type would always be blob. I don't think the length field is much help either; see https://news.ycombinator.com/item?id=13720725 https://news.ycombinator.com/item?id=13720725

hvidgaard 10y ago
The length field makes the attack significantly more difficult. In the publish attack, you take 2 fixed input and prepend special data to make the collision. With Git, you have additional constraint. Either it needs to be of exact length, this may or may not be an issue, but most likely is unless we find a new weakness in SHA-1, or you must be able to handle the changing input. In all the examples in your link, while true that you can add "silent data" to all of the examples, they are all examples of structured data. So not only do you have to figure out the collision, you have to do so within the structure of the format you're attacking. This is a lot harder than just prepending the exact bytes you want.
- jwilk 10y ago
  > The length field makes the attack significantly more difficult. In the publish attack, you take 2 fixed input and prepend special data to make the collision. That's not how the attack works. Not at all.
  - hvidgaard 10y ago
    If you ignore the prepend part, it is in essence taking known input and calculate a collision. > This is an identical-prefix collision attack, where a given prefix P is extended with two distinct near-collision block pairs such that they collide for any suffix S. And > Our example colliding files only differ in two successive random-looking message blocks generated by our attack. We exploit these limited differences to craft two colliding PDF documents containing arbitrary distinct images.

johncolanduoni 10y ago

> I doubt anyone is able to find an input that MD5 and SHA-1 both hash to the same value. It would significantly reduce reliance on a single hash function. As was mentioned in the original collision thread, concatenating insecure hash functions has fundamental weaknesses: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis...

hvidgaard 10y ago
Sort of. It does not improve brute force resistance in a meaningful way, but that is not the purpose either. It protects against one of the hash functions being broken. Let us assume that we have 2 160bit hash functions, and one is broken to the degree that we can find collisions in constant time. This now means that we can break the combined hash in 2^80 rather than 2^80 + 2^80. The total brute force complexity was not improved, but the reliance on either hash function was.
- johncolanduoni 10y ago
  Yes, but you picked two hash functions which are known to be insecure. Their complexity reduction argument appears to apply to cases where you are not using pure brute force for either hash, which would be the case if you were attacking MD5 and SHA1.
  - hvidgaard 10y ago
    I did so quite on purpose. Both are concidered broken, but combined, only the bruteforce attack is known to work, i.e. "the whole is greater than the sum of its parts".