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

[Ondrej Mikle]

Travis H. wrote:
> On 7/11/06, Zooko O'Whielacronx <zooko at zooko.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 majordomo at metzdowd.com