Niall’s Weblog

I have been working quite a bit recently on my BitTorrent implementation. My project is faring reasonably well so far - it can successfully download large real-world torrents at decent speed. In the course of development, I have been focusing solely on the core specification, as documented here. Having gotten support for peer connections - outgoing and incoming - working, I started to notice something. Some peers would send ostensibly random data to my client. Investigation of this led me to conclude these were peers using the Message Stream Encryption protocol.

I am not hugely interested in avoiding traffic shaping, but the encryption protocol looks like fun to implement and I’d like my software to be able to communicate with these funky peers (instead of just killing them, as it does now). I know very little about cryptography, but I know a little more now that I have begun implementing MSE. MSE really has two components - a Diffie-Hellman (D-H) key exchange to negotiate a secret, and RC4 stream cipher to encrypt the data. Both these functions are used in Secure Sockets Layer. However it should be pointed out that MSE is more about obfuscating the data to confuse traffic shapers than hiding its contents from prying eyes.

Fortunately for me, the OpenSSL library contains nice implementations of both D-H key exchange and RC4 . Before I can get to the nitty gritty of actually negotiating obfuscated streams, I had to make considerable changes to my software’s peer handling logic. I had written the peer response handler with quite hard assumptions about the nature of the incoming peer handshakes - for example, assuming the first byte would be the length of the protocol string. Furthermore I needed to add some timekeeping logic for each peer, because MSE handshake depends on timing for synchronisation. The initial peer handshake message is variably padded and so time must be considered to know when the message is complete. For example a MSE handshake from peer A may be considered invalid by peer B a) if A sent less than 96 Bytes within 30 seconds or b) if A sent more than 608 bytes.

My first step has been to re-work my peer handshake handling so that MSE handshakes can be distinguished and separately handled by the software, while traditional handshakes continue to work. Code to do this has been committed. The next step is to actually support crypto peers. For anyone curious about where the source code for my software is, I am not yet ready to release it. I have distributed it to a small group of testers to help iron out some of the bugs, but I don’t feel its ready for public release. I am being somewhat selfish and sitting on my personal project until I have polished it to where I want it to be. If you are really interested though, shoot me an email (niallo (*) niallo dot net).

I started working on a BitTorrent implementation in 2006. The protocol is kind of fun and there is a need for a lightweight UNIX implementation in my opinion. rTorrent is quite usable, but absolutely huge - something like over 40,000 lines of C++ last time I looked. My implementation is ~3,500 lines at present and has most of the needed functionality - although admittedly it will not support downloading of multiple torrents at a time, nor the fancy UI of rTorrent. Even assuming it doubles in size by the time its finished, that is still quite lightweight in comparison. It is written in C, Yacc and uses libevent - and its under the BSD license. I develop it completely under OpenBSD, although across multiple platforms (to weed out the endianness and pointer-size bugs). It should be easily portable to other systems with some glue (much like OpenSSH or OpenNTPd). Anyway, it has shaped up rather well and in fact I have been able to actually download some ‘real-world’ torrents with it. However, I still need to overhaul the network scheduler. Once I am satisfied with this part, I will publish the source code. The network scheduler is a complicated component - with numerous research papers on the subject! - and I plan to cover it in future postings.

For now, I want to post a quick summary of how BitTorrent works. I’m going to describe ‘vanilla’ BitTorrent - without distributed, trackerless operation and unofficial encrypted streams. The best complete “specification” I have found is this wiki page - the official specification being rather useless. Unfortunately, the official Python implementation sources are a neceesary reference at times also.

BitTorrent splits data into a number of units called pieces. Typically these pieces are 256K. Each piece has an associated 20 byte SHA-1 hash to verify integrity. The pieces are sub-divided further into what are called ‘blocks’ - typically 16K. Each peer has zero, some or all pieces. Metadata is distributed in .torrent files. Very likely you are familiar with downloading these files via HTTP and then feeding them to a BitTorrent implementation in some way. These files are encoded in a mixed binary/ASCII format called ‘bencode’ - which is a kind of mini-language supporting nested strings, integers, dictionaries and lists. Its actually quite a pain to parse in a language like C - it took me quite some time to write the Yacc parser. The metadata contains things like, number of pieces, piece sizes, hashes for each piece, tracker URL and filenames. Pieces are all zero-indexed. This gets a little complicated in multi-file torrents, where you must determine which file piece X falls within, and at what offset. My implementation uses mmap(), and has translation routines to nicely abstract these calculations away

Each peer must initially ‘announce’ itself to the tracker, and is supposed to send further updates periodically. Communication with the tracker is done via HTTP GET, with the tracker returning a bencode’ed dictionary as its response. This response includes a list of other peers - whose addresses are in fixed-length (IPv4) binary format, making it a little difficult to use IPv6 for BitTorrent, at least without protocol changes. There are a variety of peer messages. Data is transferred in terms of pieces, offsets and lengths (block size). Peers tell each other which pieces they have by sending a bitmap - one bit per piece.

The basics of the protocol are fairly straight forward. Aside from some poor decisions in terms of the bencode format for encoding messages, it is not hard to code support. As I said above, things start to get tricky when it comes to peer communication strategies. One thing of note is that the most efficient algorithm for downloading pieces is believed to be ‘rarest first order’. To my knowledge, nobody is using a sequential download order - which is why partial BitTorrent downloads of audio or video data are notoriously unplayable.