# SHA1 collisions proven possisble

valdis.kletnieks at vt.edu valdis.kletnieks at vt.edu
Thu Mar 2 22:28:52 UTC 2017

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 484 bytes
Desc: not available
URL: <http://mailman.nanog.org/pipermail/nanog/attachments/20170302/2c2b74b3/attachment.sig>