Attacks on the Pynchon Gate's use of BitTorrent

The paper spends some time beating around the bush with the traffic analysis issues concerning spam; yes, you can try to flood a nym, and if the server passes variable amounts of traffic through to the user, you can correlate input and output. This is a problem with all nym servers, as we showed in the paper, and is why Pynchon is designed to query once a day and (hopefully) request a bucket size larger than the incoming messages. The ability to review an index of messages was something that was first proposed during discussions about Underhill, the SURB-based nym-server for Mixminion, and it is intended to be used as a last resort. Yes, we waste bits by making a large fixed-size bucket request each time; it's that, or let the traffic amounts fluctuate (you don't even need spam for this.) And finally, given the once-a-day request, timing of responses to flame wars isn't an issue. 

(In Wulff's defense, we did talk about allowing different bucket sizes for different users, as long as the buckets stayed the same size for the user, and we hadn't completely made up our minds that users should be requesting an identical number of buckets each time (I don't think; honestly, I need to re-read the paper.) But as it stands now, the spam attack won't work except to potentially DOS a user, and the attack he pointed out is pretty much the same as the attack we showed against SURB and MURB-based nym servers in Nick's section demonstrating that incoming non-malicious spam kills the anonymity of a user of nym.alias.net if the passive attacker can watch the nym-server and the end-user.)

Spam handling in Pynchon, in general, is a much more serious open question -- what sort of policies should the nym server have for blocking/filtering inbound spam? If it is at all worthwhile as an anonymity service, it's going to be holding 10s to 100s of thousands of email addresses, all getting V1aGRA L0tt3ry spam. What do we do about that?

He raised some points about denial of service, but didn't mention the Byzantine distributor problem except as a passing reference to "the Byzantine postman recovery procedure suggested by the followup", which is sort of odd -- why DOS a user when you can DOS the whole network? Had he not made reference to the followup paper by the fairly unique name, I'd have thought he hadn't read it. (Note that while the Byzantine Postman problem has been published, we haven't settled on a solution yet, and the paper he is referring to is a technical report. I hope to have a protocol I am happy with "soon", since we'd like to get this beyond the prototype stage and into deployment after all these years, but I'm still poking sticks at it.)

But where his paper gets interesting (for me) is the bit about BitTorrent attacks. The amount of time Bram and I spent thinking about that part of the system was fairly limited. The intention was to borrow a BitTorrent-like protocol (ideally unmodified BitTorrent, but we haven't gotten that far in our implementation of the system to know for sure) for the transfer of the databases, with the collator operating as the "tracker" in this setting. Obviously using a public tracker would be inviting mayhem, but Wulff shows that BitTorrent itself may not be up to the challenge.

Wulff presents a Byzantine distributor-based attack in which the honest distributors are prevented from obtaining the full database (and thus effectively taken off-line during their update phase), while the malicious distributors get the entire database, and increase their chances of comprising the full set of distributors the user queries (and breaking the user's anonymity). Basically, he's saying by including BitTorrent in the protocol, we've given the attacker a means of rendering arbitrary distributors incapable of answering queries while the attacker's distributors are still able to. Oops.

This isn't that surprising of a result, given that the priorities of BitTorrent, and the priorities of Pynchon's bandwidth-sparing protocol, are rather different: BitTorrent needs to make sure first and foremost that individual file chunks never become extinct from the cloud, and secondly that the chunks get to where they need to go as efficiently as possible. Pynchon, on the other hand, has a dedicated seeder that is completely reliable, is more concerned with actual bandwidth usage rather than latency, and has additional security concerns. BitTorrent wasn't designed for the Pynchon model, and Wulff's analysis shows that to be a problem. 

And, indeed, it is an interesting problem. I can see some higher-level protocol ways of handling this, but more interesting would be to make BitTorrent more robust against Byzantine servers. I have to think on that one. (I've spent a fair bit of time thinking about how to improve BitTorrent against Byzantine agents, actually, but not for the Pynchon use-case -- just the regular BitTorrent user scenario.) It might make sense to simply start from basic principles here and design a bandwidth-sparing protocol for Pynchon without the BitTorrent assumptions.