Travis H. wrote:
On 7/11/06, Zooko O'Whielacronx <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]

Reply via email to