FlipThem – A game theoretic model of stealthy takeover of control over multiple resources

FlipThem – A game theoretic model of stealthy takeover of control over multiple resources

In recent years, the world witnessed a series of high-profile targeted attacks against governmental organizations and key security companies. These attacks showed that even the most secure networks can be compromised. They also induced an interesting discussion in the security industry and in the research community alike. A noteworthy outcome of this discussion was the FlipThem game, a model developed by researchers at RSA, which itself was a victim of a successful targeted attack in 2011.

What is the FlipThem game?

FlipThem is an attacker-defender game designed to study the problem of stealthy takeover of control over a critical resource. In FlipThem , control over the critical resource is obtained by “flipping” it for a certain cost, and the players receive benefits proportional to the total time that they control the resource. The payoff of each player is, therefore, determined by the difference between the benefit of controlling the resource and the cost of flipping it. Naturally, the goal of the players is to maximize their payoffs.

This is a simple, yet powerful model that can be extended in many directions. For instance, in the basic FlipThem  game, the players flip the resource without being able to observe who was in control before the flip. This model is ideal to study the security of a resource with offline properties, such as passwords or cryptographic keys. The basic model can be extended by giving the players the option to test if they control the resource before making a move. The extended model is used to study periodic security assessments and their positive effects.

How can be FlipThem  game useful?

Let’s assume that the resource is a secret password. In this case, the defender is the user possessing the password and the attacker is someone who wants to compromise the password. The attacker’s flip of control models attacks aiming at obtaining the user’s password including eavesdropping and off-line dictionary attacks. The user can always get the control back by changing the password. We may assume that the user does not know if the attacker successfully eavesdropped or cracked his password, whereas the attacker may learn when the password was last changed by the user when she compromises it. By analyzing this game, we can conclude that a periodic password refreshing strategy would be devastating for the user, because the attacker can quickly figure out the refresh period and schedule her flips right after the change of the password by the user, and thus, control the resource virtually all the time. On the other hand, if the user schedules his password changes according to a Poission process, then the attacker cannot learn information about the time of the user’s next change of the password. Thus, the use of FlipThem  allows us to devise a better password change policy than the periodic one when we face the above type of attacker.

Limitations of FlipThem model

A limitation of the original FlipThem  model is that it deals with a single resource. However, in practice, compromising a system may require attacking multiple resources at the same time. Hence, in our recent work in the CrySyS Lab, we developed the FlipThem  game, which is a generalization of FlipThem  to multiple resources. We introduced two control models: in the AND control model, the attacker needs to compromise all resources in order to take over the entire system, whereas in the OR control model, the attacker needs to control at least one resource (out of many available) to take over the entire system. Note that, for non-adaptive strategies, the two control models are completely symmetric in the sense that the benefit of one player in one model is equivalent to the benefit of the other player in the other model. Consequently, for non-adaptive strategies, it suffices to solve the game only in one of the control models.

In order to devise good multi-resource FlipThem  strategies, we introduced two combinations of single-resource FlipThem strategies: the independent and the synchronous combination. In the independent case, the player flips each resource independently of the other resources, whereas in the synchronous case, the player always flips all resources together. We studied and compared the two combinations, and derived analytical results for the players’ gains. Furthermore, in order to study more complex multi-resource strategies, we introduced the Markov strategy class, where the decision to flip a resource at a given time depends only on the time elapsed since the previous flip of the resource, and we showed how the best-response Markov strategy can be computed using a linear program.

Application of the model

Based on our findings, we can formulate a set of recommendations for the defender. These recommendations can readily be used in practice where the assumptions of the FlipThem  game apply, for example, when defining the key update strategy for a security infrastructure.

  • For the AND control model, we found that the defender should use independent flipping strategies. In practice, this means that cryptograhic keys should not be updated at the same time, but rather independently.
  • On the other hand, for the OR control model, the defender should use synchronous flipping strategies. In practice, this means to update cryptographic keys synchronously. However, the defender needs to pay attention to the cost of updating keys in the OR control model. If these costs are very heterogeneous, the key update processes should remain synchronized, but with different update rates across the keys.
  • If the attacker is non-adaptive, then a periodic defender strategy is a good choice. Periodic strategies have multiple advantageous properties such as higher benefits for the defender, robustness to optimization errors and ease of implementation in practice. However, periodic strategies perform poorly against an adaptive attacker. Thus, the defender carefully needs to assess what information is potentially available to the attacker when choosing his strategy.
  • Surprisingly, the defender’s benefit is not a smooth or monotonous function of his flip rates, which makes optimization difficult in practice. Numerical results imply that this observation holds for a wide range of strategy classes. The major reason behind this non-monotonous property is that, as the defender’s flip rate reaches a threshold, the attacker drops out of the game. In realistic cases, the defender’s flipping cost is much lower than the attacker’s flipping cost, which causes the attacker to drop out.

In our work, we focused on two clean control models: the AND and the OR models. However, these are just stepping stones towards a more general model.  In practice, it may not be necessary to compromise all resources in order to take over the system, and it may not be sufficient to compromise just a single resource. Instead, to take over the system, certain subsets of resources must be compromised, but it is sufficient for the attacker to choose any of those subsets. This can be described as a combination of the AND and the OR models. Our current work is focusing on proposing good defender strategies in this general model.

Levente Buttyán
Thanks for the work on the original paper for  Áron Lászka, Gábor Horváth, and Márk Félegyházi.