hashes in p2p, was Re: switching from SHA-1 to Tiger ?

On 7/11/06, Zooko O'Whielacronx <zookozooko.com> wrote:
> I hope that the hash function designers will be aware
that hash
> functions are being used in more and more contexts
outside of the
> traditional digital signatures and MACs.  These new
contexts include
> filesystems like ZFS [3], decentralized revision
control systems like
> Monotone [4], git [5], mercurial [6] and bazaar-ng [7],
and peer-to-peer
> file-sharing systems such as Direct Connect, Gnutella,
and Bitzi [6].

MD4/5 are commonly used as a unique fixed-size identifier of
an
arbitrarily-chosen* length of data in p2p file systems, and
we are all
aware of the collision attacks.  They bring up some
interesting points
to consider:

1) What semantics can one induce by using a collision
attack, given
the existing protocols/clients?  There are some rumors the
MPAA or
RIAA is using protocol-level attacks to "poison"
p2p networks like
bittorrent and KaZaa.  Can cryptanalysis results be playing
a part?

2) How do we refactor these widely deployed systems with a
new,
stronger hash function?

3) Are the requirements of this hash different than for
cryptographic
uses?  For example, I can imagine an argument being made
that finding
one preimage is not a problem with such hashes, since the
purpose of
the hashes is to use them as a reference to the preimage,
which you
may simply download.  On the other hand, you don't want
people to be
able to find a second preimage.

[*] In this sense there may be two kinds of arbitrary, (a)
fixed by
the protocol, and (b) unspecified by the protocol.

Similar questions may be asked about e.g. operating systems
which use
hashes to indicate what binaries are allowed to be executed
(I have
seen a patch somewhere which does this for NetBSD).
-- 
Resolve is what distinguishes a person who has failed from a
failure.
Unix "guru" for sale or rent - http://www.li
ghtconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098
0C55 1484

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

Travis H. wrote:
> On 7/11/06, Zooko O'Whielacronx <zookozooko.com> wrote:
>> I hope that the hash function designers will be
aware that hash
>> functions are being used in more and more contexts
outside of the
>> traditional digital signatures and MACs.  These new
contexts include
>> filesystems like ZFS [3], decentralized revision
control systems like
>> Monotone [4], git [5], mercurial [6] and bazaar-ng
[7], and peer-to-peer
>> file-sharing systems such as Direct Connect,
Gnutella, and Bitzi [6].
> 
> MD4/5 are commonly used as a unique fixed-size
identifier of an
> arbitrarily-chosen* length of data in p2p file systems,
and we are all
> aware of the collision attacks.  They bring up some
interesting points
> to consider:
> 
> 1) What semantics can one induce by using a collision
attack, given
> the existing protocols/clients?  There are some rumors
the MPAA or
> RIAA is using protocol-level attacks to
"poison" p2p networks like
> bittorrent and KaZaa.  Can cryptanalysis results be
playing a part?

RIAA uses only very basic cryptanalytic attacks.
Specifically, Kazaa 
(FastTrack protocol) uses very stupid UUHash algorithm,
which works like 
this: first 300kB are hashed with MD5, then 300 kB at 1MB
boundary is 
added to hash, then 300 kB at 2MB boundary, then 300kB at
each 2^n MB 
boundary. It is clear that it is very easy to generate
collisions for 
UUHash.

For other networks, mostly sybil attacks are used (spawning
a lot of 
fake nodes and fake files with the same name so that search
turns them up).

> 2) How do we refactor these widely deployed systems
with a new,
> stronger hash function?

An example how to handle this might be aMule and eMule
clients. The 
basic ed2k protocol only uses MD4 hashes (it is hash list,
the hash in 
magnet link is the MD4 hash of MD4 hashes of file blocks).
These two 
clients add protocol extension called AICH algorithm
(basically it is 
Merkle tree of SHA-1 hashes). The root hash might be a part
of magnet 
link, but does not have to be (since it is not part of the
original 
protocol).

If the root hash is part of the magnet link, then the
received tree can 
be checked. If it is not part of the magnet link, then the
client 
attempts to retrieve it from clients that support AICH. If
at least 10 
clients send the same root hash and if that is at least 92%
of all 
received root hashes, such root hash is considered trusted
for the 
current session. It is definitely not 100% secure, but the
more clients 
support AICH, the more often you will find the root hash in
magnet link 
(thus being able to check the received tree). Even in the
absence of 
root hash in magnet link, the attacker needs to control
significant 
portion of network to be able to spoof the root hash with
some high 
probability.

A simple concept that would allow replacing the hash
functions would be 
adding optional parameters to protocol specification. Then
users can 
switch clients "continuosly", i.e. users with
old clients will not be 
cut off of the network each time hash function changes.


------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com