6 ms·

As Deregibus explains elsewhere, this is almost certainly using the same hash collision. https://news.ycombinator.com/item?id=13728116 https://news.ycombinator

by mccr8 10y ago

As Deregibus explains elsewhere, this is almost certainly using the same hash collision. https://news.ycombinator.com/item?id=13728116 https://news.ycombinator.com/item?id=13728116

simcop2387 10y ago
That's not quite what he's saying. He's saying it's using the same research but you can't reuse a hash collision like that since the contents of the two images you give it are unknown before hand.
- dsp1234 10y ago
  You can reuse the PDF from Google because it's not particularly reliant on the contents of the images. You can replace the images that Google used with your own (indeed that's what the service does) and it will output two files that themselves have the same hash (but that hash will be different than the original provided PDFs)
  - simcop2387 10y ago
    Interesting. I need to read more into this because I didn't think that kind of thing was possible. I thought you'd have to recalculate it from scratch because of the two images being different but apparently I didn't understand how this worked.
    - dsp1234 10y ago
      (very)psuedocode: goto showImage1; showImage1: renderImage1(); exit showImage2: renderImage2(); exit If an attacker can hash a block that means "goto showImage1" and "goto showImage2" with the same hash, then you can see that the contents of those images doesn't matter, as long as the data for those images occurs after the logic for choosing them. (and no that's not what this attack does in reality, but just a logical framework for understanding why the images don't matter)
    - modeless 10y ago
      Both images are in both files. The only difference is the part of the file (where Google put the collision) which switches the image shown.
- furyofantares 10y ago
  You can reuse a collision by appending identical data to both pieces of colliding data and the result still collides. The collision google found exists in the PDF before the JPEGs, and both JPEGs are appended after the collision -- the difference in the earlier data is where the differing instructions exist that say either to display the first or the second JPEG.
  - simcop2387 10y ago
    I see, i had misunderstood how they had done their attack. Makes a lot of sense.
Deregibus 10y ago
Yeah, I think that's pretty much the case. The first 320 bytes of the two PDFs released by Google result in the same SHA-1 state. Once you're at that point as long as you append identical data to each of the files you're going to get identical hashes. This is just taking those same 320 bytes and appending the combined images of your choice. edit: as versteegen points out it's 320 bytes, not 304.
- schoen 10y ago
  I had a whole discussion in another thread about this: https://news.ycombinator.com/item?id=13716581 https://news.ycombinator.com/item?id=13716581 I learned a lot from it. One thing is that this property is true of any Merkle-Damgård-type hash if the hash internal state is the same size as the hash digest. This is true of SHA-1 and of several other famous and widely-used hashes, but not true of every hash, including some of the most recent designs like several SHA-3 candidates and SHA-3 itself. In a hash without this property, you can have a collision condition H(X)=H(Y) (and len(X)=len(Y)) yet typically H(X+a)≠H(Y+a). Edit: len(X)=len(Y) is also necessary because Merkle-Damgård hashes encode the message length into internal padding, so if you happened to have two colliding inputs that were different lengths, they will generally not produce a collision when the same string is added to each.
  - kzrdude 10y ago
    And SHA(-2)-512/X (The truncation to X forms) are also good for avoiding length extension
    - schoen 10y ago
      Yep, I have a long list in the other thread (transcribed from Wikipedia). It's nice to finally understand why the truncation forms exist!
  - TorKlingberg 10y ago
    This is really good to be aware of, even if there were no collisions. I could imagine someone making for example a signed cookie scheme that is value,SHA1(secret,value). Someone could then change it to value+foo,SHA1(secret,value+foo) without knowing the secret, and it would verify as a valid signed cookie.

by mccr8 10y ago

As Deregibus explains elsewhere, this is almost certainly using the same hash collision. https://news.ycombinator.com/item?id=13728116 https://news.ycombinator.com/item?id=13728116

simcop2387 10y ago

That's not quite what he's saying. He's saying it's using the same research but you can't reuse a hash collision like that since the contents of the two images you give it are unknown before hand.

dsp1234 10y ago
You can reuse the PDF from Google because it's not particularly reliant on the contents of the images. You can replace the images that Google used with your own (indeed that's what the service does) and it will output two files that themselves have the same hash (but that hash will be different than the original provided PDFs)
- simcop2387 10y ago
  Interesting. I need to read more into this because I didn't think that kind of thing was possible. I thought you'd have to recalculate it from scratch because of the two images being different but apparently I didn't understand how this worked.
  - dsp1234 10y ago
    (very)psuedocode: goto showImage1; showImage1: renderImage1(); exit showImage2: renderImage2(); exit If an attacker can hash a block that means "goto showImage1" and "goto showImage2" with the same hash, then you can see that the contents of those images doesn't matter, as long as the data for those images occurs after the logic for choosing them. (and no that's not what this attack does in reality, but just a logical framework for understanding why the images don't matter)
  - modeless 10y ago
    Both images are in both files. The only difference is the part of the file (where Google put the collision) which switches the image shown.
furyofantares 10y ago
You can reuse a collision by appending identical data to both pieces of colliding data and the result still collides. The collision google found exists in the PDF before the JPEGs, and both JPEGs are appended after the collision -- the difference in the earlier data is where the differing instructions exist that say either to display the first or the second JPEG.
- simcop2387 10y ago
  I see, i had misunderstood how they had done their attack. Makes a lot of sense.

Deregibus 10y ago

Yeah, I think that's pretty much the case. The first 320 bytes of the two PDFs released by Google result in the same SHA-1 state. Once you're at that point as long as you append identical data to each of the files you're going to get identical hashes. This is just taking those same 320 bytes and appending the combined images of your choice. edit: as versteegen points out it's 320 bytes, not 304.

schoen 10y ago
I had a whole discussion in another thread about this: https://news.ycombinator.com/item?id=13716581 https://news.ycombinator.com/item?id=13716581 I learned a lot from it. One thing is that this property is true of any Merkle-Damgård-type hash if the hash internal state is the same size as the hash digest. This is true of SHA-1 and of several other famous and widely-used hashes, but not true of every hash, including some of the most recent designs like several SHA-3 candidates and SHA-3 itself. In a hash without this property, you can have a collision condition H(X)=H(Y) (and len(X)=len(Y)) yet typically H(X+a)≠H(Y+a). Edit: len(X)=len(Y) is also necessary because Merkle-Damgård hashes encode the message length into internal padding, so if you happened to have two colliding inputs that were different lengths, they will generally not produce a collision when the same string is added to each.
- kzrdude 10y ago
  And SHA(-2)-512/X (The truncation to X forms) are also good for avoiding length extension
  - schoen 10y ago
    Yep, I have a long list in the other thread (transcribed from Wikipedia). It's nice to finally understand why the truncation forms exist!
- TorKlingberg 10y ago
  This is really good to be aware of, even if there were no collisions. I could imagine someone making for example a signed cookie scheme that is value,SHA1(secret,value). Someone could then change it to value+foo,SHA1(secret,value+foo) without knowing the secret, and it would verify as a valid signed cookie.