Attacks and Countermeasures

We identify a number of possible attacks which serve to impersonate the user. In the following scenarios, Mallory is an attacker who wants to impersonate Alice.

Brute-force attack. Mallory attempts to impersonate Alice by picking random images in the challenge set, hoping that they are part of Alice's portfolio. The probability that Mallory succeeds is $1\; /\; \{nm\}$, which depends on the choice of $n$, the number of images in the challenge set, and $m$, the number of portfolio images shown. For example, for $n=20$ and $m=5$, we get $1\; /\; \{205\}\; =\; 1\; /\; 15504$, which is equivalent to a four-digit PIN. To prevent brute-force attacks, the system may deny access after a small number of trials.

Educated Guess Attack. If Mallory knows Alice's taste in images he might be able predict which images are in Alice's portfolio.

Our first countermeasure is to use Random Art, which makes it hard for Mallory to predict Alice's portfolio images, even if he knows her preferences. Our user study shows that if photographs are used instead of Random Art, it is easier to predict some portfolio images chosen by Alice, given some knowledge about her.

Since users tend to pick the most aesthetically appealing pictures for their portfolios, it will be clear which images in the challenge set are the portfolio images if they are not all equally appealing. We therefore hand select images to ensure that no weak images are used. (We call images weak, if no user would select them for their portfolio). Hand selecting images is not a drawback, since a Déjà Vu system can function with a fixed set of images, on the order of 10,000 images.

Observer Attacks. Ross Anderson shows that observation of PIN codes on ATMs has been used to impersonate users [And94]. Similarly, if Mallory observes Alice during multiple authentications, he can know Alice's portfolio perfectly. We propose the following countermeasures.

• If the size of Alice's portfolio $p$ is larger than the number of portfolio images in a challenge set $m$, the probability that an observer sees the same portfolio images after one observation is $1\; /\; \{pm\}$. Although the security is still weakened after an observer learns images in a portfolio, an observer still can not impersonate Alice easily.

  Assuming that the images are displayed in a way that only Alice can see them clearly, the observer gains no knowledge of the portfolio by observing which images she selects, since the position of the portfolio images within the challenge set is randomized.

• The method for the image selection is hidden, such that an observer cannot see whether a given image is in the portfolio or not. If the observer cannot see which keys are pressed or can not determine which images are selected, he gets no useful information.
• The portfolio images can be slightly changed in each authentication. The goal is that a legitimate user can still recognize her portfolio images, while leaking less information about the portfolio to an observer. Further study is needed to explore image distortion methods and to determine how modifications in images are perceived by users.

Intersection Attack. If all the portfolio images are part of the challenge set, and all decoy images are changed in each challenge, Mallory can use the intersection of two challenge sets to reveal the portfolio. This is a serious problem, but we can design a system which can resist this attack through the following countermeasures.

• The same challenge set (portfolio images and decoy images) is always presented to the user. If it remains the same, an intersection attack does not reveal any useful information. The drawback, however, is that since the decoy images remain the same across many login sessions, Alice might start to remember decoy images and flag them as portfolio images in future authentication sessions. Future study is needed to see if this is the case.
• A small number of decoy images remain in the challenge set over multiple authentications. Again, the problem with this approach is that users may learn a decoy image if it is repeated enough times and then mistake it for a portfolio image.
• The authentication can be split up into multiple stages. Each stage presents a challenge set with a random number of portfolio images. If a user makes a mistake in any stage, all subsequent stages will only display decoy images without any portfolio images. This prevents an adversary from performing repeated impersonation attacks to discover the entire portfolio.
• We find in the user study that the failure rate is much lower for Déjà Vu than for password or PIN-based systems. This increased accuracy allows us to tighten the bound on unsuccessful logins before the account is blocked. This, however, opens the door to denial-of-service attacks which may render this method impractical.

Another possibility is to combine the countermeasures such that Mallory does not receive any useful information from multiple unsuccessful logins. First, the system uses the multi-stage authentication, which reveals only decoy images after the user makes an error in any stage. In addition, the system discards portfolio and decoy images that are shown in any unsuccessful login attempt. A shortcoming is that too few images may remain in the portfolio, and the system would need to perform a portfolio replenishment phase after a successful login. Since this takes time and may annoy the user, this method might be impractical. To prevent a denial-of-service attack from depleting the portfolio, the system can disable logins after a small number of unsuccessful login attempts. In case a user successfully authenticates after an unsuccessful attempt, the system can then replace the previously discarded portfolio images and perform a training phase with the images the user forgot.