On Wed, 01 Mar 2017 22:57:06 -0600, James DeVincentis via NANOG said:
- Google created a weak example. The difference in the document they generated was a background color. They didn’t even go a full RGBA difference. They went from Red to Blue. That’s a difference of 4 bytes (R and B values). It took them nine quintillion computations to generate the correct spurious data to create a collision when they controlled both the documents with a 4 byte difference. That spurious data inflated the PDF by at least a few hundred KB.
Note that we haven't actually seen the algorithm yet. And it's quite possible that Google intentionally limited it to a *very visible* 4 byte change, so that just opening a PDF viewer of both documents is sufficient to demonstrate that a change was made. As a result, we can't rule out the possibility that "size of altered data plus/ times size of spurious data" equals a constant - in other words, limiting the change to 4 bytes causes a lot of spurious data, but careful choice of a larger number of altered bits results in a smaller spurious pile of bits. It *may* be possible to totally stash all the spurious bits elsewhere in the object via steganographic means - consider for instance a video stream. It may be possible to splice in/out a significant segment of video (possibly CGI'ed), and hide all the spurious bits in one/two bit changes in the rest of the stream. Remember that in a good hash function, changing one input bit should on average change close to half the output bits. So how many bits get changed by 2, or 3, or 4 bit of input change? If the attack is based on the ability to bias that "on average" in one direction or another, it's quite possible that applying a bias across 128 changed input bits is actually *easier* than when you only have 32 bit of change bias to apply....
They didn’t dare attempt it because they knew it’s not possible.
As I point out above, we don't actually know that for a fact.