Krisztian Gado - A Game Theoretic Analysis of TOR's Resilience to Entry-Exit and End-to-End Attacks

I'm always giving advice on that part I get it over 30 years yeah but it too tough it's tough yeah yeah well you also stay up here we're about ready to me okay Wow I feel like I'm at Catholic Church right because they're people way in the back and we have all these empty seats up here so good thing it's mic so you can hear back there but if you know there's not that many people here you know make the speaker feel a little more welcome you might want to move up all right okay our next speaker is Chris paddle he is a researcher at Lewis and Clark College and his interest cross computer science and economics which is

why he did this really interesting research project he's gonna report a lot yeah hi so essentially we are going to talk about the tor browser today and economic perspective and economics perspective using game theory how do we make tor browser more secure in terms of like you know if someone wants to compromise the purpose of tor browser then how would they do it and what can we do against this now bear with me if you don't know what tor browser is or you don't know what game theories and how you know the two merge together I will give you a brief intro about cyber security and game theory and how this can benefit from each other

essentially then I will talk about the Tor network I will give you a non-technical description of how that looks like and a basic idea about how we can model this and how we can model the attacks that we are interested in and how we can model making it safer and so I will show you some results ultimately and about what kind of numbers are we talking about how many times would an attacker succeed and how many times would they fail before and after our improvements as well and you know I will give you a snapshot of how we want to improve our models ultimately so how does cyber security come into play and why is it interesting for me or for us

as a group of researchers you know we are very interested in keeping anonymity through cyber security that's our field we want to make sure that whatever you do if you want to keep animals in the internet you will be able to do so and you know some people want to uncover this unanimity and identify you you know and this can interfere with your First Amendment rights in some ways or it can also prevent you from getting certain websites in certain countries I won't name names here at one point fingers but you know not you can't access any website in any country you go to and so how does game theory coming to this well we will talk about systems

design or mechanism design here and I will just say an example and a very simple mathematical description of the solution to that example that demonstrates how if you think about agents that want to maximize their utility from some perspective how this can lead to in a sub efficient suboptimal outcome in some ways and and how an improvement to a system that should be an improvement at zero cost can lead to an even more sub optimal outcome in some ways so let's think about two points a and B that are you know somewhat apart from each other and we can get to this from point A to point B via path ACB on the top and a YB on the bottom now how

long does it take from get from A to B on these two paths so let's define a function X and X is going to be the fraction of the people who take that road so that's how much time of an hour is going to take you to get from Y to be in terms of this path so from a to Y it's going to take you one hour and from by to B is going to take you the fraction of the people taking this road so if for example nine-tenths of the people are taking this road then it's going to take them 54 minutes and if one tenth of the people are taking this road

and it will take them six minutes and on the top from a-z B we have the same function essentially just in the reverse order so how long will it take people on average if they keep repeating this path every day from A to B to get from A to B so you know a person will take path AZ B on day one and they will realize that most people took this path so it took them two hours to get there because everyone took this path but then they will notice that a YB would have taken them only an hour because no one took that path and you know from by 2 B they would have gotten

then there really fast so they were switched from a ZB some people to a YB and this will keep balancing out until until we reach equity bream and it will take 90 minutes for both paths to to get from A to B this is like you know standing in a line in a shopping mall essentially now let's introduce an improvement to the system so we can teleport from Z to Y at zero cost so basically you can just teleport there and continue your path what will how much time will it take for people to get from A to B this way so let's consider that you know people take the top path first so the fraction of

the people taking the top path let's say that's 1 and you can see that from Z to B it's gonna take them 1 hour to get to point B no matter what so if they take that path they have an incentive kind of to teleport down immediately because at in the worst case scenario it will take them 1 hour if everyone is taking the bottom path but best-case scenario or anything then worst case scenario it would take them less than 1 hour so they would take the teleportation machine sort of no matter what on the bottom path people can't teleport up so it doesn't really matter if they went bottom they will keep going bottom from

that point so into having introduced this improvement into the system it will take 120 minutes for every single agent to get from point A to point B and this is pretty mind-blowing if you ask me because you you just made an extra option that has no cost yet it made the system as a whole more inefficient so what's tor tor is essentially much like Google Chrome in some ways except you would use this if you want to keep an anima so if you don't want your ex-spouse or your government or whoever that is to know which websites you are visiting who we are talking to on the internet you would use a tor browser and

yeah that's that's the purpose of it essentially now how does it work exactly so if you we start at the top left corner at your computer so that's you and then you were using your internet service provider you will connect to the Tor server now the Tor server has an has main three main components an entry a middle and an exit node and each of these uses layered encryption so each component can only see the previous and the subsequent connections you are making so the entry node could only see you and the middle node and the exit node could not only see the middle node and your destination but you know the exit node wouldn't you

wouldn't know where the information is coming from so because of this you know Tory's run with volunteers and not everyone wants to be an exit node because let's say you are doing something illegal the police would be knocking on your door if you had an exit notice if you know someone you store for non legal purposes so essentially middle and entry nodes have no cost whatsoever you can't really be caught but exit nodes are somewhat dangerous to running in this regard so at the end of the day let's say you are using tor from Alaska and you want to access a website in say South on Europe so tor would keep routing you through different computers

proxies if you know the technical term all around the globe keep bouncing you until you know it connects you to your final destination and then backwards in a different path though that's that's important to highlight that the internet is asymmetric so if you go from A to B on one path then backwards is going it's likely going to be a different path so how can this thing be attacked so this is the mathematical notation don't be scared by it if you are not familiar with math about of a path B construct so in the curly brackets you see the two eyes at the two ends those are the internet service providers essentially for purse for personnel at time T that's

all PN T means and NB t and na T all those regardless Internet service providers poor person and time T before and after the Tor network and in the center the three-letter T's those are the entry middle and exit nodes essentially so the type of attacks we are looking at are correlation attacks this can be entry exit and end-to-end attacks and the distinction between these and how this work is that an entry exit attack would corrupt to tor nodes in the Tor network so the entry node and the exit node a correlation attack can succeed if and only if the entry and exit nodes are corrupted and end-to-end attack would be your internet service providers in some way doing an attack on

you at the two ends of communication so how are these carried out well there are a variety of ways to do a correlation attack some of them could be voter marking so the packages you send are somehow marked and you know if you know that you mark the package at one end and it comes out at the other end the package with your mark on it you know it was you and so you can relate the person who sent the package initially initially and the person who received the package and so you identified who is talking to who and alternatively you could use timing you could basically delay packets in certain fashions so that you can

identify that it's you really delaying what's happening so tor itself admits that you know despite certain updates they still are vulnerable to correlation attacks if you read the frequently asked questions section in their paper so tours routing how does that work so first it has a bandwidth threshold it assigns which it uses to select the exit nodes we are looking at an exit node can be any node that's entry eligible and exit eligible at the same time and if an exit a selected exit node is below this bandwidth threshold then it will keep selecting new new potential exit nodes until one of them is an exit node essentially then it will slack middle and entry nodes and you know as I said

these can be exid eligible nodes as well then it will use any AES so it does tor doesn't distinguish in between a sec chooses before the Tor network well it can't and but it chooses any yes after the tour Network which will be something we'll talk about later on and it will keep you know repeating this process until you your communication ends so what would an attacker do in this scenario so obviously they would make all of their nodes exit eligible because exit eligible notes can be selected to be both entry and exit notes so they kind of double dip it's very similar to selecting boss from a bag and that's what they would do and also they

would make their bandwidth as high as possible because higher bandwidth nodes have a higher probability of being selected so how do we I am so sorry I gave that away so how safe are you the point over a year if you keep using tor browser for a year based on our simulations you would be safe only 60 percent of the time with you know very if you corrupt it only a few nodes basically it would be pretty easy to uncover the identity of you if you you store over here so what can we do about this to lower the probability so first we would separate the selection pools of entry nodes and exit nodes so if an

entry node is selected it couldn't be an exit node so these would be separate and you know this works are based on the properties of simple bayesian statistics you can verify it if you want to secondly we would drop the bandwidth threshold and this would not impact the speed of the Tor network severely in any way because if you think about it any path has five components and the bandwidth threshold only applies to one of these so if you drop it from this one it's pretty unlikely that it would impact the speed overall since you know you're only as fast as your slowest component essentially it's a bottleneck we care about not not the speed of one

single component on the Third Way you wouldn't want to choose the same autonomous system twice so when you first communicate with the Tor network until the entry node you cannot choose that autonomous system I internet service provider apologies but after the exit node and between your destination using data and control plane tools you have some control over whether you want to route over Verizon let's say again if you have one strategy through them and ultimately I we are aware that the Internet is mostly asymmetric well in fact it is asymmetric but still you can make two or more symmetric and you should do that so you you should only drop or deconstruct paths once it's

absolutely necessary you you you would want to keep reusing the same path over users and destinations for as long as possible because this kind of decreases the amount of tries attackers have to catch you and to UM eyes you so what are our results so you know you have this fancy functions here and all we do on the x-axis basically is increase the resources attackers have so those being how many exit nodes they control and after separating you know the section post we did some optimal some optimization problem very simple math we calculated what would be the most ideal way to split in between and three nodes and exit nodes and that's the blue line

your attack success probability as your resources increase essentially for an attacker after you implement our improvements so as you can see it's like on the red line with very realistic numbers it would be fifteen percent essentially somewhere around that that you already identified and on the blue line it would be about five percent the chance that you are identified in a single try over the path and you know what does this mean this would mean that over a year's time beat how many times you toward reconstructs paths and those numbers all taken into mind as we as I said before you stay you stay secure sixty percent of the time before and without improvements you would stay

secure about 85 percent of the time so you know there's a twenty five percent gain pretty significant I would say and with very simple improvements now it's important to emphasize that you as a if some of you here are too or denote volunteers running volunteers then you have no control over this whatsoever the only person or organization who could actually implement these changes is the Tor network itself so the summary essentially correlate the correlation attacks can hurt tor users well yeah they can I just demonstrated how and in the literature it was thought after 2010 there was a huge update to tor that because of the introduction of guard notes correlation attacks are not dangerous anymore or you know they are

negligible well they are not because you know Python improved it became much more famous machine learning became much bigger so they are correlation attacks are indeed dangerous again and you know game theory kind of is applicable to cyber security and it can be made to make tor much more secure in in terms of these attacks with very simple with a very simple analysis you can you can go a long way and ultimately that's that so I just would like to thank my collaborator some of who are sitting here in the third fourth fifth row actually and I'm open to questions [Music]

that's not entirely true so you could use it so on average tor will keep reusing the same you know guard nodes so guard nodes are entry notes basically tor keeps reusing for the same user for about 120 days so for the first three to four months hundred twenty days four months your probability wouldn't change so if you weren't identified then you got a friendly exit node entry node then you're good for that period until your exit entry node changes once your entry node changes and you can check this then you are in danger again so let's say you ever identify the first time then you know you're already identified it doesn't matter but if you wouldn't

identify the first time you can just keep reusing it because you won't be afterwards either unless you're Internet service providers you know change somehow yeah yes yes tor has to implement it absolutely but you know you can apply this principle to your life and think about what you do in such ways think the way an attacker would think and no matter what kind of field you are in cyber secure interested in cyber security or actually no matter what just think with the heads of the other person think about what resources they have and what they would do don't just assume that the introduction of a bandwidth threshold or a guard node would have a significant impact in the long run which

which it does but you know you could do better still could you repeat that oh not yet we are still working on this research and we actually want to implement mechanism which isolates these malicious packets so we want to be looking at some we want to send information to ourselves basically using tor and if we notice some anomalies let's say oh the packet size changed or oh there is a weird kind of you know timing discrepancy in how we receive these packets back then we want to isolate you know the nodes that were involved and then identify which one is malicious basically yeah so our research is not done yes yeah so that yeah so

let's say we know that the user is identified well you know that's tough luck but we don't want another user to be identified as well if in case that happens yeah and you know modeling that takes time we are using Monte Carlo simulations and we want to improve upon them because you know there Tour simulators but the problem with them is there are way too many functions that do crazy things that you don't actually know what kind of distributions they use that you can't really say if they are accurate or know when you are simulating such measures yes yeah it's a work in progress yeah our Monte Carlo simulations if you run it once it's pretty fast the only you

know when we run it like 200 times to check our standard errors that's when it gets slow and tedious yeah thank you