[BitTorrent] bt2 protocol features

Vitenka vitenka at ntlworld.com
Sun Jun 6 08:15:26 EDT 2004


> MD5 and SHA1 are especially designed to be collission resistant. As a
> result, the change you find a collission (two different inputs with the same
> output) is almost 0.

Ok, resistant yes, impossible no.  A given hash size has only a finite 
number of possible hashes.  Even a simplistic analysis would tell you 
that it is then impossible to have more chunks than that uniquely 
identified.  Of course, a decent sized hash makes that number larger 
than the number of atoms in the universe.

Currently, the only people with any reason to send data which matches a 
hash but is not the real data are those trying to cheat the system. 
They would like to pretend to have chunks which they do not have.  But 
the system does not reward this because, as you say, the chances of 
deliberately finding a piece of matching data are very very low.  By the 
time they have created one, they could have just downloaded a chunk the 
normal way and offered that up for download.

However - under the new system it is not finding a piece of data for a 
given hash that is the problem.
It is finding two pieces of data which happen to share a hash.  This is 
much much more likely.

(Consider the birthdays problem.  The chance that any given person 
shares *your birthday* is very low.  One in 365.  But in a room full of 
people, the chance that there are two of them who share a birthday is 
very high.  You only need 30 people before the chance is 50/50.  Try it!)

So similarly with this new system it is now every legitimate client 
which might be generating the clash.  And once enough files are being 
shared by bittorrent, the chances of a clash become very likely.

And worst of all - if a clash DOES happen, there is no way to detect or 
recover from it in the hashes alone.  So every person who want chunk 73 
of mpeg45 will get chunk 4 of executable10 - which happens to match and 
is in the caches.

This would screw up the seeding of the new file quite badly.

A quick bit of maths would be enough to determine how many chunks a 
given hash size could safely cover.

But it seems more natural to add some identifying information (and the 
ISPs who are running these caches would probably appreciate it too) 
rather than simply increasing the hash size.
That would also help in diagnosing the problem - if another file is in 
the caches with the same name as the one which messed up then you have a 
good guess as to why it went wrong.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70
http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
     BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
     http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list