oss-security - rsync vulnerable to collisions

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <CACYkhxh_MQAzXnFgRV4pOyx-xDVbAJhg2EQ2qNzxicRt1ahrsw@mail.gmail.com>
Date: Mon, 28 Jul 2014 11:18:50 +1000
From: Michael Samuel <mik@...net.net>
To: oss-security@...ts.openwall.com
Subject: rsync vulnerable to collisions

Hi,

After some semi-public discussion on Twitter I have come up with a method
of creating blocks that collide under the rsync algorithm.

The rsync algorithm consists of two checksums - a rolling sum based off
Addler32 (notable difference - it doesn't use a prime modulus in
rsync), and MD5.
MD4 was used before rsync 3 (protocol version < 30), so presumably the change
was introduced do to security concerns about MD4.

Fast MD5 collisions have existed for quote some time - the attack I used as a
basis is from 2006, and the much more serious chosen-prefix collision is from
2009.  Generating a collision on my desktop PC takes less than a minute.  I have
not yet created a chosen-prefix collision, but I believe a similar
technique is possible.

Note that rsyncing a file over itself with two colliding blocks will
not break rsync as it
prefers copying data from it's original location.  The minimum
requirement is that an
attacker can write to synced file twice - the process would need to be:
- introduce collision 1
- rsync
- introduce collision 2
- rsync

Also note that a full file md5sum is calculated, so introducing these
collisions would
cause rsync to fail for that file (DoS attack)... unless it's the
first block you're switching.

If you use --inplace, the change is introduced despite the error
message - this may be
common when moving around virtual machine images or databases.

Note that changing the block size is not a very effective mitigation
(the collision can be
aligned to both block sizes), and the checksum seed doesn't help - it
should've been
fed into md5 before the data, not after.

I provided colliding blocks to both Wayne Davison and the Internet Bug Bounty a
week ago.  The IBB ticket is still sitting in New, and my last
response from Wayne was
effectively denying that this is a vulnerability.  Since this
information is known to the
few that follow me on Twitter, I have decided it best to inform oss-security.

I provided Wayne with some rather awful patches that bring in libdetectcoll and
blake2b.  He has not provided feedback, so I have not done further work on this.

I won't provide full details yet, but if any distributions would like
some collisions to
perform specific tests (perhaps on Openstack Swift), please get in
contact privately.

For more information of MD5 colliisons and libdetectcoll, please see
Marc Stevens'
excellent work: https://marc-stevens.nl/research/

Regards,
  Michael

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.