Posted on June 19, 2008 in Anomos by John 3 Comments »

The previous tracking code model was a major headache. The codes were visible to all members of a circuit, they (potentially) leaked information about the topology of the network, and required that members of the circuit perform multiple decryption attempts for each packet they received. Luckily, there’s a nice alternative which has been staring us in the face the whole time. The tracker can wrap each part of the tracking code in layer after layer of public key encryption. In other words, after generating the tracking code “0:3:2″ the Tracker uses an encryption function E_peer(c), where c is the concatenation of the next tracking code digit and the encryption function corresponding to the next peer. If the tracking code “0:3:2″ is to pass a message m from peer “a” to peer “d” through the circuit “a -0-> b -3-> c -2-> d” then the expanded encryption function is:

E_a(0 . E_b(3 . E_c(2 . E_d(m))))

Each peer removes a layer of encryption and passes the message along. This is essentially the way in which Onion Routing networks, such as Tor, protect their routing information.

Posted on June 2, 2008 in Anomos by John 36 Comments »

Anomos is a decentralized peer-to-peer file sharing system derived from BitTorrent which is capable of protecting its user’s identities by means of an advanced, planned mix network. Its purpose is twofold. In one way it is simply an intellectual exercise; we are computer scientists interested in encryption, the limits of anonymity, and the design of networks. In another sense it is a profound demonstration of individual liberty, a demand for freedom, privacy and anonymity on the Internet. Here I will give a brief outline of the technical details of Anomos. As the project is still in the early stages of development some aspects of it are still subject to change.

General Features

  • File transfers through Anomos are anonymous (the degree of this anonymity will be discussed in a future post). After being sent, packets are routed through a number of intermediary nodes before reaching their final destination. These intermediary nodes can only confirm that their neighbors are participating in the network, they cannot confirm that their neighbors are sharing or merely relaying information, nor can they determine what is being shared.
  • Downloading with Anomos is decentralized — the downloader receives parts of the requested file from a number of different sources, similar to how BitTorrent functions.
  • Connections within Anomos are End-To-End encrypted.
  • Communication with the Tracker is also encrypted.

Growing the Network

Like many BitTorrent systems Anomos relies on a centralized Tracker server to initiate downloads. However, to provide anonymity, the Anomos Tracker has been almost completely redesigned. When a client connects to the Tracker for the first time, they are assigned a small number of neighbors with whom they will directly communicate. Each neighbor the Tracker assigns to the client is given a locally unique ID (meaning that no two neighbors of the client will have the same ID). Using the the IP addresses provided by the Tracker and the local IDs, the client establishes connections with their neighbors.

After the connections have been formed the network may look like this:

Tracking Codes

Much of the power of Anomos comes from its “tracking code” system. The Tracker maintains a weighted undirected graph modeling the network. The graph’s vertices (the circles in the above images) represent clients, the edges (the arrowed lines) represent connections, and the weights (not pictured above) allow for fine grained control of how connections are formed (for instance: the tracker may route less traffic through peers who are heavily loaded). When an anonymous connection needs to be formed, the Tracker computes a path between the two peers involved. The path consists of a list of the peers through whom the packets should pass. The tracker then uses the numbered connections between those peers to create a description of the path (called a Tracking Code) which can be given to anyone without compromising the anonymity of the uploader or downloader. For instance if P0 wants to send a request to P9 then the Tracking code for that connection might be “0:1:2:4:0″

When P0 receives the tracking code, she creates the packet which needs to be sent, pops the first number off the tracking code, and sends the packet to her neighbor with that number. The process is repeated until the packet gets to its destination. Astute readers may notice that with this scheme the tracking codes would shrink and thereby reveal the recipient of the message at the second to last node. The actual codes are padded with a pseudorandom number at each node in the circuit to prevent this. You might also notice that with this scheme the recipient of the message doesn’t immediately know whether to pass the message on or to keep it. In order to resolve this, each peer initially assumes that they are the intended recipient and therefore try to decrypt the message. If the result of the decryption is garbage they pass the message on as per the Tracking Code, otherwise they respond. We’ve come up with a much better way to do this.

Requesting a file

If a client wants to download a file he first requests it from the tracker over secure HTTP. The tracker finds a small number of other users who have the file or parts of it and generates Tracking codes which connect the downloader to each of them. The Tracker also crafts the request data to be sent to each of these peers and encrypts it with each respective peer’s public key (which the Tracker knows but the downloader does not). This allows us to do end-to-end encryption without the uploader or downloader gleaning information about the network from seeing the same public key multiple times. The Tracker also generates an AES key for encrypting further communications between uploader and downloader. Here’s an example of a response the client might receive:

After receiving this, the client will create a packet containing the data in red (which the client himself cannot read), and send it through the network.

Sharing

After the initial request, the AES key generated by the Tracker is used to encrypt data between the two sharers. These sharers then pass messages in almost exactly the same way they would have in BitTorrent. The downloader sends a request, the uploader responds with a chunk.

Misc


In BitTorrent share ratios (the ratio of Amount Uploaded / Amount Downloaded) are used to punish peers who take without giving back. This can often be a barrier to entry for peers with few files or files which are not popular. Anomos helps these peers by adding their Amount Relayed to their Upload count, thereby rewarding people who donate their bandwidth to help others share anonymously.

I’ve presented some of the basics about the Anomos P2P system here, in future posts I will discuss more advanced topics such as how dropped connections are handeled, the level of anonymity the system provides, and perhaps an overview of the BitTorrent protocol.

We’ll be putting the source code repository online soon. If you’d like to be informed of major developments or would be interested in testing (several months from now) send us an email at: participateanomos.info

– John