7 ms·

Wow, it works! I thought this was supposed to require Google-level resources and months on processing time. Did the initial collision somehow enable more simila

Wow, it works! I thought this was supposed to require Google-level resources and months on processing time. Did the initial collision somehow enable more similar ones?

kiallmacinnes 10y ago
yea, this.. wow. Is this the first hash function which went from "secure" to collision-as-a-service in a matter of days? Was sha1 particularly weak, or the published research particularly strong? or maybe something else?
- schoen 10y ago
  As other people explained, and just to summarize, this service is a way of reusing Google's specific collision (as a prefix to new collisions), and isn't a way of making arbitrary colliding files or file formats. You can't, for example, use this to make something other than PDFs that collide; for that, you'll have to redo a computation on the scale of Google's!
  - dheera 10y ago
    Why wouldn't you be able to? Most file formats have ways of including comment data, including JPEG, GIF, HTML, C code, and most others. You could potentially create a piece of noble C code and a piece of malicious C code that collide. (However, creating a piece of malicious code that matches an existing codebase that doesn't contain a comment would be hard, if I understand correctly.)
    - aidenn0 10y ago
      This reuses the prefix that Google calculated, which is a PDF header. Therefore you can only generate PDFs with this technique. If you want to dedicate a few hundred GPU-years to it, you could generate similar colliding prefixes for other formats by doing what Google did.
      - dheera 10y ago
        Ah, I see, thanks.
  - orblivion 10y ago
    I thought I heard that some file formats have "headers" that go at the end of the file. I think a demo of this was a file that was both a zip and a PNG or something. If I remembered right, you should be able to make a similar hack here.
    - schoen 10y ago
      If the only headers are at the end, then yes, that's a really neat idea. I'm not sure of the constraints for zip files. Maybe it would be interesting to brainstorm with some people with a lot of file format knowledge to find additional such formats. But if the formats have any constraints at all on the first few hundred bytes, those generally won't be satisfied by the prefix here.
- danielweber 10y ago
  It was known for a while to move away from SHA-1. Any TLS certificates using SHA-1 were supposed to become invalid on January 1st. But I wasn't expecting that google's 110 GPU-year work meant that we could create colliding PDFs on demand.
  - kiallmacinnes 10y ago
    Absolutely, but knowing something smells a little off vs having a documented collision feels like the point where we we go from "No longer advised for use" to "It's broken". Usually its when we hit "It's broken" that average Joe developer/operator/etc starts to form their migration plan, and usually they have some time before the attack becomes reasonable to execute outside of pure research / "nation state" attacks.. It seems that block of time was just a few days (a day?!) for SHA1. And it's that, even if we're talking about an easy to abuse format like PDFs apparently are, that makes me question what just happened? Was sha1 secretly terrible? was the research just that good? or was there some other factor that allowed this to happen? Also, sure, the major browsers have a date for SHA1 as a TLS signature hash retirement.. But SHA1 is used for a whole pile of other stuff with absolutely no transition plan! January 1st was absolutely never going to be the last day people used SHA1.
    - nicky0 10y ago
      Look into the details. This isn't what you think it is.
- amenghra 10y ago
  Day, not days.
  - hbbio 10y ago
    Faster than the zip quine.
- deleted 10y ago
  [deleted]
- dom0 10y ago
  This works the same way with any Merkle-Damgard-constructed hash function; basically it's just a length extension attack.
  - danielweber 10y ago
    How do you length extension when both outputs are the same length?
    - cstejerean 10y ago
      It's a length extension on the beginning part of the PDF. There are 2 headers that have the same hash. As long as you append the same suffix to both of those headers, the hash will be the same. In this case the headers happen to contain a switch that select between one of two images. So the length extension is adding both images to both of the headers. Since the headers have the same hash and the suffix has the same hash, the overall document has the same hash. But because of the switch in the header you see two completely different contents. So basically H1 and H2 have the same SHA1 hash. By adding suffix I1I2 to both you get H1I1I2 and H2I1I2. That's the length extension.
      - danielweber 10y ago
        If you got two different messages to get into the same internal state with SHA-3, the same thing would apply, wouldn't it? Would that be a length extension attack on SHA-3? This is really a terminology question. I had a clear understanding of "length extension attacks" but it seems on this comment page people are using something else now. I've been looking over crypto.stackexchance and twitter to see if I missed the memo but this looks like a new usage.
        cstejerean 10y ago
        It's a different usage of the term than the normal case, but it takes advantage of the same vulnerability to length extension. It doesn't necessarily apply to SHA-3 and other sponge functions because there is a difference there between the internal state of the hash function and the actual hash itself. The internal state is much larger than the hash output for a sponge function like SHA-3, which means you can get two messages that have the same hash without having the same internal state, and therefore appending a suffix would mostly likely change that internal state enough to no longer have a hash collision.
- mrb 10y ago
  SHA1 has been deprecated for a while. It certainly wasn't considered "secure" on the day the attack was announced. For example CAs have been moving away from SHA1 signatures for a few years.
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)
      - 10y ago

Wow, it works! I thought this was supposed to require Google-level resources and months on processing time. Did the initial collision somehow enable more similar ones?

kiallmacinnes 10y ago

yea, this.. wow. Is this the first hash function which went from "secure" to collision-as-a-service in a matter of days? Was sha1 particularly weak, or the published research particularly strong? or maybe something else?

schoen 10y ago
As other people explained, and just to summarize, this service is a way of reusing Google's specific collision (as a prefix to new collisions), and isn't a way of making arbitrary colliding files or file formats. You can't, for example, use this to make something other than PDFs that collide; for that, you'll have to redo a computation on the scale of Google's!
- dheera 10y ago
  Why wouldn't you be able to? Most file formats have ways of including comment data, including JPEG, GIF, HTML, C code, and most others. You could potentially create a piece of noble C code and a piece of malicious C code that collide. (However, creating a piece of malicious code that matches an existing codebase that doesn't contain a comment would be hard, if I understand correctly.)
  - aidenn0 10y ago
    This reuses the prefix that Google calculated, which is a PDF header. Therefore you can only generate PDFs with this technique. If you want to dedicate a few hundred GPU-years to it, you could generate similar colliding prefixes for other formats by doing what Google did.
    - dheera 10y ago
      Ah, I see, thanks.
- orblivion 10y ago
  I thought I heard that some file formats have "headers" that go at the end of the file. I think a demo of this was a file that was both a zip and a PNG or something. If I remembered right, you should be able to make a similar hack here.
  - schoen 10y ago
    If the only headers are at the end, then yes, that's a really neat idea. I'm not sure of the constraints for zip files. Maybe it would be interesting to brainstorm with some people with a lot of file format knowledge to find additional such formats. But if the formats have any constraints at all on the first few hundred bytes, those generally won't be satisfied by the prefix here.
danielweber 10y ago
It was known for a while to move away from SHA-1. Any TLS certificates using SHA-1 were supposed to become invalid on January 1st. But I wasn't expecting that google's 110 GPU-year work meant that we could create colliding PDFs on demand.
- kiallmacinnes 10y ago
  Absolutely, but knowing something smells a little off vs having a documented collision feels like the point where we we go from "No longer advised for use" to "It's broken". Usually its when we hit "It's broken" that average Joe developer/operator/etc starts to form their migration plan, and usually they have some time before the attack becomes reasonable to execute outside of pure research / "nation state" attacks.. It seems that block of time was just a few days (a day?!) for SHA1. And it's that, even if we're talking about an easy to abuse format like PDFs apparently are, that makes me question what just happened? Was sha1 secretly terrible? was the research just that good? or was there some other factor that allowed this to happen? Also, sure, the major browsers have a date for SHA1 as a TLS signature hash retirement.. But SHA1 is used for a whole pile of other stuff with absolutely no transition plan! January 1st was absolutely never going to be the last day people used SHA1.
  - nicky0 10y ago
    Look into the details. This isn't what you think it is.
amenghra 10y ago
Day, not days.
- hbbio 10y ago
  Faster than the zip quine.
deleted 10y ago
[deleted]
dom0 10y ago
This works the same way with any Merkle-Damgard-constructed hash function; basically it's just a length extension attack.
- danielweber 10y ago
  How do you length extension when both outputs are the same length?
  - cstejerean 10y ago
    It's a length extension on the beginning part of the PDF. There are 2 headers that have the same hash. As long as you append the same suffix to both of those headers, the hash will be the same. In this case the headers happen to contain a switch that select between one of two images. So the length extension is adding both images to both of the headers. Since the headers have the same hash and the suffix has the same hash, the overall document has the same hash. But because of the switch in the header you see two completely different contents. So basically H1 and H2 have the same SHA1 hash. By adding suffix I1I2 to both you get H1I1I2 and H2I1I2. That's the length extension.
    - danielweber 10y ago
      If you got two different messages to get into the same internal state with SHA-3, the same thing would apply, wouldn't it? Would that be a length extension attack on SHA-3? This is really a terminology question. I had a clear understanding of "length extension attacks" but it seems on this comment page people are using something else now. I've been looking over crypto.stackexchance and twitter to see if I missed the memo but this looks like a new usage.
      - cstejerean 10y ago
        It's a different usage of the term than the normal case, but it takes advantage of the same vulnerability to length extension. It doesn't necessarily apply to SHA-3 and other sponge functions because there is a difference there between the internal state of the hash function and the actual hash itself. The internal state is much larger than the hash output for a sponge function like SHA-3, which means you can get two messages that have the same hash without having the same internal state, and therefore appending a suffix would mostly likely change that internal state enough to no longer have a hash collision.
mrb 10y ago
SHA1 has been deprecated for a while. It certainly wasn't considered "secure" on the day the attack was announced. For example CAs have been moving away from SHA1 signatures for a few years.

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)
    - 10y ago