Game Theory For Hackers

every two days welcome to the one o'clock game 3 for hackers with xenon fish before we get started I just want to thank our gold sponsors st. Mary's University USA a Trend Micro digital defense and sans who ever have this happen today if they weren't here so make sure to stop by and thank your sponsors ok so I like to welcome Wednesday to the stand and get your content right is this going through to the camera

I can also just yell hello sorry would all right I'm gonna all right cool game theory for hackers will be applied to cyber security and I'm Lindsey Vonn Tish some people also know me as judo I respond to hate you whatever let's rearrange everyone this is my first time a piece in San Antonio at San Antonio and actually my first time in San Antonio as well yes right okay awesome okay yeah for sure alright so a little bit about me I'm a recent recent college grad actually from Anchorage Alaska and in college I studied computer science and economics and got really really excited about cybersecurity when I did my first CTF out outside I also breathe fire and I'm

in a band I'm pretty much doing what you know age 17 year old Lindsay would wanted me to do hacking things playing a band breathing fire but anyways in in August I moved to Dallas to be a data analyst for a a corporation down there and I've gotten really really involved with local infoset groups who here is from Dallas hackers assistant yeah I actually first gave this talk at Dallas hackers Association it was a ten minute presentation on the prisoner's dilemma where I gave out free beer to the people who could best screw over their friends it was lovely so what is game theory game theory is sort of the interdisciplinary marriage of statistics and behavioral economics

the cool thing about it is it's been used throughout history to model war and cons of historic and modern there was a game theorist on staff during the Cold War actually multiple there are game theorists on staff at NFL teams and I believe in I believe even one who monitors who who models soccer and so it's to model the choices and decisions made by rational actors during times of conflict and competition I know what you're thinking where are we going to find rational actors definitely not in this room but um so I'm not giving out free beer this time but a little bit of a road map we're going to go through the prisoner's dilemma game and I will be

taking volunteers up to do to do things you have been warned if you are in here I'm a I'm a gang cue up and so we'll go through a couple different iterations of the prisoner's dilemma just to demonstrate that next we'll go into the signaling game which is just to demonstrate model how false information can change outcomes and then into my only computer based game a network detection game so the prisoner's dilemma is probably one of the most popular game theory games you can see it in TV popular psychology movies definitely cop shows so I think everyone knows what it is but just in case two individuals are arrested after committing a crime however there's no evidence so they're

separated and they're both offered the same plea deal if you rat out your co-conspirator they'll take the fall for everything you'll walk out scot-free and everything will just go away for you however this offer has been offered to both individuals but only one of them can accept it if they both confess a choice that will call defecting on their partner they will both go to prison however if they both manage to cooperate without communicating and confuse the roof a sailboat confess they'll both receive a little bit of a slap on the wrist and go their own way now I think the best way to demonstrate human lead games is with people so I need two

people to come up here for a second all right someone whispered oh cool guy in the back someone else just run up here and I will be doing I will be doing demos so I'm going to hand what I'm gonna set this down for a sec you guys are not friends not anymore at least I have imprisoned you and I've given you guys oh no I have given I have given you guys this choice I'd like you to write down this the choice on your posters an art note just without thinking about it go

oh hey I can walk around with this awesome alright so real fast can you tell tell us what you chose and why no I decided to trust her and hopefully uh it'll pay off hopefully my trust will pay off I just said it wasn't us alright so they've uh they they both managed to stay silent oh you guys are free to go for now they both managed say silence silent is that the right decision and is that the rational decision and is there a difference so I have a a simplified payoff matrix here we have Alice and Bob who have committed a crime and gotten caught and been offered the prison as the prisoner's dilemma deal they both have the choice

to cooperate with each other and stay silent or to defect and rat the other individual out and now the thing to keep in mind is the higher payoff is better for the individual actor so the highest payoff on this matrix is to the choice to defect if the other player cooperates and the lowest payoff is that negative one that you get if you cooperate while the other player defects no because Alice and Bob cannot communicate they have no way of knowing what the other individual will choose so they have to base their decision solely off of what they think the other person might do so if Alice believes that Bob will choose to cooperate she'll choose to defect for

that higher payoff similarly if she believes Bobble choose to defect she will defect as well for that higher payoff Bob will make the same choices defecting if he believes Alice will choose to cooperate and affecting if Alice will choose to defect so this lands us and does in defect defect and this is what we call the Nash equilibrium this is the logical outcome of the game now as we've seen this is not this not always the outcome when people play because we are with cooperate cooperate we have an option that is better for both players without any making anyone in the game worse off and this is called the Pareto optimal outcome now one thing to keep in mind is this

game is not always played in a vacuum when I did this at Dallas hackers Association a lot of a lot of the people told me hey well we're Dallas hackers association of queer friends we're not we're not gonna rat each other out and that mathematical model I just showed you does not take account anything except the the potential payoff of going to prison a repeated game is when our two our two conspirators Alice and Bob go out commit a crime get caught make a choice and then they go out and do the same thing again they get in the same situation where they have to make that choice again and again and again and you

would think at some time at point they would give up the life of crime or at least learn not to get caught but here we are so I'd like to bring up two more people to do this a couple of times all right I see you in the red shirt what's your name Roman that's an awesome name also I love your shirt all right who wants to send this poor kid to jail all right I like house only did someone's hand go up after that oh I believe the two pens are right there all right so phase away from each other don't don't look at Roman don't don't show any mercy for him and I'd like you to write your first

decision down

and then I'm again I'm going to ask you to explain your choice all right are you ready cool all right I chose to cooperate I'm going to jail well we we've been committing crimes together this whole time and it's been working out want to do the same thing I just I just wanted to see what what happened and and I thought and I thought I just I would do it so I chose to do fat yeah so he goes to jail now but there's more wait wait wait stay here now knowing but knowing what the decision your opponent made I'd like you guys to do it again

this is definitely gonna be a most interesting one I've ever done all right I'm gonna go to you for I'm gonna go to you first this time what do you choose to do what because since because since I defected him the last round I I don't think he would trust me this round we get into that later this guy is gonna be a game theory expert all right what about you I cooperated all right so just just to rub it in a little bit more like you guys to do it one more time

all right I don't have an extra piece of paper so just write your choice on that piece of paper that's just to hold you accountable so that when he defects on you again you can't just change your answer all right what do you choose to do defect same thing last round because it happened twice nice all right what about you I definitely alright thank you so much you guys all right so now I know who to commit crimes with and who not to commit crimes with which really that's exam periods about alright so we're going to go into the the repeat these are the rules again so with this exact same payoff matrix so we're going to go into the P repeated

game no Roman mentioned that the reason he continued to defect was he believed that his opponent would decide to start defecting and that's what we call a punishment strategy a punishment strategy is used to essentially motivate the other player to cooperate with you and now there are multiple types of punishment strategies but I believe the most realistic and I believe it was shown here is the grim trigger punishment strategy which is very very simple you're gonna cooperate until betrayed and then you're going to defect every single time afterwards now this does leave you open to betrayal in the beginning once but there's there's a huge amount of room for retribution afterwards one thing we need to keep in

mind however is the discount map the discount factor which is essentially a measure of patience because the payoff in the future is worth just is worth at least a little bit less than payoff that you can get right now and the discount factor is just D a number between 0 & 1 that represents that decrease in payoff so if you're playing against an opponent who you think will be using the grim triggered punishment strategy you know that as long as you cooperate with them your opponent will cooperate with you so the payoff to cooperate is going to be one minus the discount factor multiplied by one the payoff you'll get for cooperating with them multiplied by one

the best possible payoff if when they cooperate in the story the payoff you'll get when they cooperate in the future multiplied by the discount factor out on into the future and that will simplify down to one the payoff to defect is one minus the discount factor multiplied by two the payoff you'll get for defecting when they cooperate plus zero the best-possible pay off when they defect on you later in the future on out into the future and that will simplify down to 2 multiplied by 1 minus D and when you set those equal to each other you get D is equal to 1/2 this means for the payoff of cooperation to be greater than the payoff of defecting

the discount factor or the discount factor has to be greater than 1/2 future payoff must be worth at least more than 1/2 the present payoff now once you do betray your opponent and this is little logic our friend was going for you know that they're going to defect every single time afterwards so the payoff to cooperate is going to be equal to the discount factor minus 1 the payoff to defect will always be equal to zero because your opponent will continue defecting out into the future when you said the when you set those equal to each other you get a discount factor of 1 so for the payoff to cooperate to be greater than the payoff to defect the

discount factor has to be greater than 1 which means future payoff has to be worth more than present payoff which is not possible so once you have defected it is always better to continue to defect No so so that's that's a more human based scenario we're going to move into a simple attack-defense scenario that takes a bit more of a cybersecurity angle although this scenario is very very simple you have a game between an attacker and a defender the attacker can choose to attack or pass and the defender can choose to monitor their systems or not monitor their systems if there's a cost for the defender to monitor their system and there's a cost for the attacker to attack a system that

has been monitored so if we try and find the logical outcome of the game we know that for the attacker if they believe the defender won't mana or will monitor their system they will choose to pass and if they believe it they won't monitor their system they'll choose to attack similarly if the defender believes the attacker will attack they'll choose to monitor but if they believe the defender will not attack they'll choose to not monitor now in this scenario we don't have a Nash equilibrium we don't have a we don't have an end where the choices line up so what does this end up meaning so let's look what this means is a likelihood that the that one of the

players will do something can force the player to do something else so let's let P equal the likelihood that the defender will monitor their systems the expected value of attacking is equal to the probability that that system is monitored multiplied by the payoff of attacking a monitored system plus the probability that the system is not monitored multiplied by the payoff of attacking a non monitored system the expected value of passing will always be equal to zero when you set those when you set those equal to each other you get a P of one-half which means with it's a 50-50 probability a system is defended the attacker is indifferent about attacking so if there's a way so

the pilot the previous games we've seen have been simultaneous games where the players cannot communicate with each other except for in case of the repeated game the decisions they've made in the past however as soon as we add communication between players we also add the element for miss truth and falsehood so the signaling game shows what happens when one player can misrepresent their capabilities or intentions so we have a signaling game and this will be again between the attacker attackers and defenders and defenders are going to be either high quality defenders who have the capability to monitor their system and low quality defenders who do not and a defender can signal that they're a high

quality defender and that their systems are secure at a cost and this cost is higher to low quality defenders than it is to high quality defenders and the attacker does not know which capabilities the defender has all the attacker can see is whether or not a signal has been given which makes it a game with incomplete information so here we have our decision tree thus first the first move in the center is just a move by Nature and that determines with probability 1/3 that the that the defender is either high quality or low quality next moving out is the choice of the defender to either signal or not and signaling comes at a cost finally at the

is is the choice by the attacker to attack or pass and you see the line between two of between two of the sets of nodes that's because the attacker only knows whether they've seen in a signal or not they don't know the capabilities of the defender so the attacker does not know which of those nodes they're on so let's start with a separating equilibrium where high quality defenders will signal and low quality defenders will not signal this leads to a simple solution for the attackers they will if there's a signal they will pass if there's no signal they will attack however this does not work out for the low quality defenders who are getting that payoff of negative 10

if you can see it on this side for for getting attacked every single time so if they start signalling if all defenders signal high quality if high quality and low quality defenders signal attackers will attack a certain percentage of the time based off of the probability that the defender giving the signal is high quality or low quality and in this case high quality defenders are signalling 1/3 of the time and low quality defenders are signaling 2/3 of the time so if attackers attack X percent of the time we're now the payoff to high the payoff of attacking a high quality defender is negative 10 and the payoff of attacking a low quality defender is 10 so the expected value of attacking

given that they've seen a signal is going to be equal to the probability that the signal came from a high quality defender multiplied by the payoff of attacking a high quality defender and that pi there is payoff I realize I didn't make that clear earlier plus the probability the signal came from a low quality defender multiplied by the payoff of attacking a low quality defender which is going to be equal to three and a third the expected value of passing is always zero so in this scenario the expected value of attacking is always greater than the expected value of passing meaning attackers will attack a hundred percent of the time so if we go back to the decision tree we'll

find that this is even worse for the low quality defenders because not only are they getting that that negative payoff from being attacked they're also having to pay the cost of signalling so some of them will stop signaling and this leads us to our semi separating equilibrium which is the only true equilibrium of the game high-quality defenders will signal and low quality defenders will signal X percent of the time attackers will attack a signal Y percent of the time and if there's no signal they'll attack a hundred percent of the time and below is just the probability that the signal came from a high quality or low poly defender which is relevant later but I

use Mathematica to solve it for me so if Y is the probability the attacker will attack a defender we actually want to look at the expected value to the low quality defender of giving a signal so why we multiply Y the probability that they will be attacked by the payoff of sending a signal and getting attacked plus one minus y the payoff or the sorry the probability that they will not get attacked plus their x the payoff of sending a signal and getting passed over we compare that to the expected value of not sending a signal which is always getting attacked so that's always negative ten when we set those equal to each other we get y is equal to

seventeen twentieths this means attackers will attack if they see a signal 17 times out of 20 now we need to find X the probability that a defender without the tech to monitor their system will signal that they can the expected value of attacking is going to be equal to the probability it's it's a high-quality defenders sending a signal multiplied by the payoff of attacking a high-quality defender plus the probability it's a low-quality defender sending the signal multiplied by the payoff of attacking a low-quality defender the expected value of passing will always be equal to zero so if we set that equal and solve for X we'll get 1/4 which means 1/4 of low-quality defenders will signal that they can

monitor their systems so this is how the game ends up looking where this is this is how it ends up evening out in a scenario like this high-quality defenders will signal and low-quality defenders will signal a quarter of the time if an attacker sees a signal they'll attack 17 times out of 20 if no signal is seen they will they will attack every single time now the interesting thing about human based games is it often feels like there are an infinite amount of choices which is why I believe that the true interdisciplinary power of game theory actually is shown in computer versus computer games so this is a simplified attack simulate or this is a simplified

simulation between a server and notes we've got two types of nodes user nodes who want to just want to send along the data and malicious nodes that want to corrupt the data and the server wants to watch for malicious traffic but doesn't want to watch every single node because then service will suffer so the game for the server is pretty simple after the server connects with a node and receives a packet you can do one of three things nothing which is the safest nothing happens no one wins send along the packet which is good if the node is a user bad if the node is malicious and watch the node which is bad if the nose

is user and good if the node is malicious similarly for the nodes they can do nothing nothing happens no one wins everything is safe send along the packet or corrupt the packet so first if we look at the game between a user node and a server node the first thing we notice is that choosing to corrupt the packet is the opposite of what a user node would do a user node would not corrupt a packet therefore the choice to corrupt is strictly dominated by the options to do nothing and send because that's either in either option no matter what the server does it's always better to do nothing or send for the user node than corrupt a packet so we can remove

this from our payoff matrix if we look at the game between the server and the malicious node we a similar set off with different payoffs for the note now now like the now like the user note the option to send for the militias note is strictly dominated by the option to do nothing no matter what the server does do nothing send or watch the packet the malicious node would prefer to do nothing than send the packet on so we can remove this from our payoff matrix and when that's removed the option to send along in the packet is strictly dominated by the option to do nothing for the server so we can remove this this brings us to a much

more simplified game between the server and the malicious node now what does this end up meaning user nodes will always choose to send along a packet or do nothing with it and malicious nodes will always choose to do nothing or corrupt the packet so what in this scenario what does a repeated game between the malicious node and the server look like so here we're returning to the repeated game idea that we've brought up in the prisoner's dilemma the server can do nothing or watch the packet and the malicious node can do nothing or corrupt the packet now in the scenario like before we'll have the server use a grim trigger punishment strategy the server can do nothing or

will do will choose to do nothing unless the node has corrupted a packet however if the node corrupts a packet it will be watched for every single inner iteration afterwards so as long as the malicious node has not corrupted a packet the server will choose to do nothing so for the malicious node the payoff to do nothing is going to be equal to one minus that discount factor multiplied by the payoff of doing nothing x with the discount factor on out into the future which will end up being equal to 0.5 the payoff to corrupt will will end up being will end up being equal to one minus the discount factor oh there's the type of

my slide oh well so but it isn't for doing nothing to have a higher payoff than corrupting the packet the future payoff must be worth more than half of the current payoff this discount fact this depends on the patience of whoever set this system up now once the malicious node does corrupt a packet the server will watch it for every single inter interaction afterwards the payoff of doing nothing will be equal to zero and the payoff of corrupting will be equal to negative three multiplied by one minus that discount factor and this when you set these equal to each other the payoff of doing nothing will always be greater than the payoff to corrupt so once the note has corrupted a packet

it's better to just continue along doing nothing so where do we go from here what do we do with this information this is not the end-all be-all guide to game theory this is just a taste of it I want everyone here to leave wondering how they can apply game theory to how they can wondering how they can apply game theory to the things they do in their job in their life secretly in their sketchy home lab made of raspberry PI's and there now there are a lot of limitations in game theory I think in especially in my watered-down scenarios I think the biggest limitation is realism for example going back to the signaling game how exactly does a

defender signal that they're a high quality defender especially creditably as we know if a company were to say hey we're unhackable well actually as we've seen they're gonna go down in about 5 hours and we'll be able to watch the whole thing play out on Twitter so uh so adding that realism in is hard I actually have another version of that game where I've added in two types of defender or two types of attackers into a script kiddies who are who are deterred by the signal and the idea of of attacking a high quality defender and more brave attackers who see that signal and get a really high payoff from attacking a defender that is lied and

signal that they're high quality when they're not but that gets more and more complex and has 16 payouts I think another place I'd like to go with this as modeling CTF who here knows tinker tinker once said that he does not like CDF's because it's not hacking it's a model of another person's brain and I think it would be incredibly exciting to start applying applying game theory to CTF and think about to think about how the person set it up would have set it up with if there are seven equally equally equal equal options that could get you a flag which one is the most likely based on what you've seen throughout the rest of the CTF so the

takeaway here is that I want you to think about how these models can be applied one of the other there are of course limitations as they're the ones I mentioned earlier there's also the limitations of determining those payoffs and motivation the payoffs I used in my example I used because they made the math easier there's also a question of complexity as these games get more and more complex they get larger and larger not only leaving room for error but rumored for missing or leaving room for misinterpretation but game theory has been used to model to model warfare to model sports to model football even I think the next step is to start applying it to cyber security my contact

information is below as well as on my sources I'd like to use some of this time too for anyone with questions comments snide remarks let me know yes

I think focused a lot of time this year on the defender side of fishing I'm going to repeat your question back for the video the question is in times in cases of fishing if you don't really send a signal you just report it should we start suddenly sending a signal back and I hate to say this but that depends on your opponent because if you send a signal back they might know that they've been caught they might give up they also might try harder so that's what I think that would be a very fun question to model to see do they get deterred do they try harder what what are the responses of those attackers any other

questions all right well you'll know how you'll know where to find me I'll be wandering around in a blazer thank you so much everyone for coming thank you everyone again who participated as well that was that was definitely the most fun demo I've done yes thank you so much I'm Jun oh please hit me up with any questions later yeah thank you [Applause]