Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Currently, a magnet link containing a 40-digits long SHA-hash value, is assigned to every torrent which is created. Therefore, this hash should be unique to identify a torrent and send the right bytes (packages) to the right people. So therefore, there are 16^40 (1461501637330902918203684832716283019655932542976) possible hashes to uniqueliy identify a torrent. What happens after this number has been reached or two torrents with different content have the same hash? (Although this practically never happens, there is a chance of (x+1)/(16^40) where x is the number of public torrents aka. assigned hashes, that your hashes collide.)

So to make long things short: What happens if two magnet-link-hashes are equal for different contents? What happens after every magnet-link has been used?

share|improve this question
add comment

3 Answers

up vote 9 down vote accepted

1640 is a huge number. For instance, if you consider each torrent to consist in a single byte each (so they are quite uninteresting torrents), and you pack them all on 10 TB hard disks (for a torrent to exist, it must exist on at least one hard disk on the planet), and if each such disk weighs about 100g, then the total weight of the disks is about 24 billions of times the mass of the whole Earth.

So I am quite confident in stating that this number will not be reached.

Risks of collisions are actually higher. If you accumulate 160-bit hash values (outputs of SHA-1) then, on average, the first collisions should appear after about 280 values (this is known as the birthday paradox). So the situation you describe may occur much earlier than after exhaustion of the 1640 space. But 280 is still huge, and cannot be practically achieved (280 torrents mean more than one hundred thousand billions of torrents per human being on Earth).

If a hash collision occurred, then streaming either of the two colliding files would most probably cease to work; downloaders would obtain a mixture of both files. Other torrents would remain totally unaffected.

An interesting question is whether you could, given an existing torrent T, handcraft another T' which hashes to the same value -- it would be used as a weapon to prevent usage of T. To do that, you would have to break second preimage resistance of the hash function. SHA-1 has a few known weaknesses, but for now there is no known method for obtaining a second preimage, except luck (try random values until one matches). Luck (aka "brute force") has average cost 2160, which is completely out of reach of today's (and tomorrow's and next decade's) technology.

share|improve this answer
1  
Actually, for all these torrents to have different hashes, most of them must be of size at least 160 bit (= 20 bytes). So the weight of the disks is 20 times as much as you calculated. –  Paŭlo Ebermann Aug 16 '11 at 16:57
    
Indeed. I thought about this earlier with MD5-hashes instead of SHA, since they're much shorter. It would be interresting to try out crafting torrents with pre-defined hashes. Although, I guess it's impossible to sucessfully "prevent" usage of a torrent by interrupting the network with other files. On an average connection with approx. 300 GB downloaded data, about 160 MB fail. By sending "junk" into the network, this number will significantly increase, although automated algorithms will prevent those "bad peers" from spreading. –  MechMK1 Aug 16 '11 at 19:04
add comment

From my understanding the hash is made from the file metadata and a short subset of the binary file. There is a chance (so small as to be effectively nill but not actually) that 2 files could feed into the formula and come out with the same Hash.

You could fake a file if you know how the hash is formulated so that it appears to be the same file but actually has different content. But there are also error checks in the file process so that assuming you choose a good file as the primary seed the bogus file parts would be discarded in the error checking when reassembling the file and the Torrent client would call out for those parts again. Theoretically you might be able to break that as well but the amount of effort that would be required to break both makes that attack vector unusable.

And the accidental collision is handled by the error checking. So you may end up with some garbage packets but it will not prevent the torrent client from completing the file.

share|improve this answer
    
Actually, the metadata of a BitTorrent includes hashes of all the pieces. So a hash of the metadata protects the integrity of the whole document. –  Paŭlo Ebermann Aug 16 '11 at 17:12
    
@Paulo - I can still inject garbage if I back in the hash.(OK someone that knew more and had far to much time on their hands could) But that is a good point. It does make it harder to fake the metadata hash. –  Chad Aug 16 '11 at 17:21
    
Yes, if you break the hash, you can do malicious stuff. The standard assumption is that it is hard to break SHA-1, e.g. you would need longer than your lifetime to do this. –  Paŭlo Ebermann Aug 16 '11 at 17:24
    
@Paulo - My point was even if you could break the hash for the metadata or a chunk there is error correction that will toss out the garbage data anyway. You are right it is currently not practical. But should it become practical it will still not break BT. –  Chad Aug 16 '11 at 17:27
    
Is there error correction apart from the hashes of the Chunks included in the metadata? I'm not a bitTorrent expert (never used it, only just looked at the specification). –  Paŭlo Ebermann Aug 16 '11 at 17:44
add comment

What happens if the computer processing the torrent file gets struck by a cosmic ray and processes incorrectly? What happens if an asteroid strikes the Earth and destroys every computer before the torrent file can finish downloading?

If the probability of a failure occurring is many orders of magnitude lower than the probability of another failure that causes the same result, then there is no point worrying about that failure. This is a failure that is many billions of times less likely than thousands of other failures that cause much worse results.

The probability that one computer will make an error calculating a single SHA-1 hash is much, much larger than the probability that any computer will encounter two sets of data that produce the same SHA-1 hash.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.