[193933] in North American Network Operators' Group
Re: SHA1 collisions proven possisble
daemon@ATHENA.MIT.EDU (valdis.kletnieks@vt.edu)
Thu Mar 2 17:29:05 2017
X-Original-To: nanog@nanog.org
From: valdis.kletnieks@vt.edu
X-Google-Original-From: Valdis.Kletnieks@vt.edu
To: James DeVincentis <james.d@hexhost.net>
In-Reply-To: <282798BA-220B-48D9-8800-AF1C5BF0131E@hexhost.net>
Date: Thu, 02 Mar 2017 17:28:52 -0500
Cc: nanog@nanog.org
Errors-To: nanog-bounces@nanog.org
--==_Exmh_1488493732_2719P
Content-Type: text/plain; charset=us-ascii
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.
--==_Exmh_1488493732_2719P
Content-Type: application/pgp-signature
-----BEGIN PGP SIGNATURE-----
Comment: Exmh version 2.5 07/13/2001
iQEVAwUBWLicpI0DS38y7CIcAQJJoQf+P6o0l0QpggfNcFZiOh8XOPc9Ah84VK/1
vsg0Rc+pdOd1ugVZ7dhVf/V0pOngkoHjywpy2ZPL1LsB3wrZGCb3AmMDcNspnauH
FhE8Yb/43lN3FLZ6SL2L62oQ89iKfBRCTa1dvXBzwrIvspEZO2LeJfj8/8+13/sh
OZSHnAKvrcK1ucl3+dRgbTeRERarpwLwFUDTAFS9SvpgT7Qedsza008sFktBbPBs
rK24R/dohgG3vGsK9w+xZmNlo4beUtkOA7zit9gRI5j8LEJkPgWMQvinQO8V+4+c
nxG7Schiuyz7JGoBiTrkjHbHtDwPelopjk7DkqqygGsI9lipHxMw/A==
=Zdoi
-----END PGP SIGNATURE-----
--==_Exmh_1488493732_2719P--
