SHA1 should be used since MD5 is not strong enough. However, I was thinking of an idea of hot reduce the size of queries:
What if you could specify only the beggining of the hash and a * to indicate that any bytes may follow. Some files with the wrong hash would be returned, but since the whole hash is in the replies, those would be filterd out. Extra hits are also much cheaper than extra bytes in queries.

This, of course requires the hashes to be in base32, since the '*' char could not be recognized in raw binary data.

/Tor