Event

May 27: Towards a Theory of Onion Routing

 

Students, faculty, and staff are invited to attend the following departmental seminar:

Topic: Towards a Theory of Onion Routing

Speaker: Aaron Johnson, PhD Student, Department of Computer Science, Yale University

Date: Tuesday, May 27

Time: 9:45 to 11 a.m.

Location: 2222 Coover Hall

Abstract: Onion routing is a practical and popular protocol for anonymous communication on the Internet. As implemented in the Tor system, it is being used by an estimated 200,000 users to anonymize TCP connections online. However, while the roots of the protocol go all the way back to Chaum in 1981, not much has been rigorously shown about the anonymity it provides. The biggest obstacle to this analysis has been the existence of timing attacks. These attacks are possible because onion routing is connection‐oriented and low‐latency, which are two features that make it so useful in practice. In this talk, he will describe recent work by himself and collaborators that models and analyzes onion routing in the presence of timing attacks. First, he models the protocol formally using I/O automata, and
characterizes exactly which situations are distinguishable by the adversary, and therefore when a user is anonymous. Second, given that some situations are more likely than others, he performs a probabilistic analysis of this model. His analysis identifies two possible worst cases for a given user $u$, depending on how the other users choose their destinations. The first is when all other users always visit the destination of $u$; the second is when all other users never visit the destination of $u$. He then provides asymptotic estimates of $u$'s anonymity in these cases, as well as his anonymity in a more typical case. This is joint work with Joan Feigenbaum and Paul Syverson.

Speaker biography: Aaron Johnson is currently a PhD student in the Department of Computer Science at Yale University. Prior to this he did his B.S. (cum laude) study in computer science at Northwestern University. He serves as the program committee member for ACM Conference on Computer and Communication Security (CCS 2008) and ACM Workshop on Formal Methods in Security Engineering (FMSE 2008).

 

---