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]
