MAY 2014 | VOL. 57 | NO. 5 | COMMUNICATIONS OF THE ACM 115 only evaluate to 1 at a single point, meaning that the user has been trained on only one secret sequence.

The key feature of implicit learning is that even under duress it is impossible to extract a point k ∈ Σ from the user for which p(k) = 1. This abstract property captures the fact that the secret sequence k is implicitly learned by the user and not consciously accessible. In this paper, we use the implicit learning primitive to construct an authentication system, but one can imagine it being used more broadly in security systems.

The authentication procedure described in Section 3 provides an implementation of the predicate p(·) for some sequence k0 in Σ. If the procedure declares success, we say that p(k0) = 1 and otherwise p(k0) = 0. The predicate p is embedded in the user’s brain during the training session.

The basic coercion threat model. The SISL authentication
system from Section 3 is designed to resist an adversary
who tries to fool the authentication test. We assume the test
requires physical presence and begins with a liveness check
to ensure that a real person is taking the test without the
aid of any instruments. To fool the authentication test, the
adversary is allowed the following sequence of steps:
• Extraction phase: intercept one or more trained users
and get them to reveal as much as they can, possibly
using coercion.

• Test phase: the adversary, on his own, submits to the authentication test and his or her goal is to pass the test. In real life, this could mean that the adversary shows up at the entrance to a secure facility and attempts to pass the authentication test there. If he fails, he could be detained for questioning.

This basic threat model gives the attacker a single chance at the authentication test. We consider a model where the attacker may iterate the extraction and test phases, alternating between extraction and testing, later on in this section.

We also note that the basic threat model assumes that during the training phase, when users are taught the credential, users are following the instructions and are not deliberately trying to mislead the training process. In effect, the adversary is only allowed to coerce a user after the training process completes.

It is straightforward to show that the system of Section 3 is secure under this basic threat model, assuming the training procedure embeds an implicitly learned predicate p in the user’s brain. Indeed, if the attacker intercepts u trained users and subjects each one to q queries, his chances of finding a valid sequence is at most qu/|Σ|. Since each test takes about five minutes, we can assume an upper bound of q = 105 trials per captured user (this amounts to about one year of non-stop testing per user, which will either interfere with the user’s learned password rendering the user useless to the attacker, or alert security administrators due to the user’s absence prompting a revocation of the credentials). Hence, even after capturing u = 100 users, the attacker’s success probability is only

100 × 105/|Σ| ≈ 2− 16.

and assessment tests with increased sensitivity to individual knowledge to provide a reliable and accurate identification method by SISL performance.

Even at 1 and 2 weeks delay, participants exhibited the same modest tendency for better recognition of the trained sequence, ts > 2. 8, ps < 0.05. Again, recognition performance did not correlate with expression of sequence knowledge, rs < 0.16 and did not suggest any ability to recall the entire 30-item trained sequences.

5. SECURITY ANALYSIS

In this section, we analyze the security of the basic authentication protocol from Section 3 and propose a number of extensions that improve security. We also experiment with a particular attack that attempts to extract the secret sequence from the user one fragment at a time. Our Mechanical Turk experiment shows that this attack works poorly on humans.

5. 1. Implicit learning as a cryptographic primitive

We begin with an abstract model of the new functionality enabled by implicit learning. Traditional modeling of participants in a cryptographic protocol is as entities who hold secrets unknown to the adversary. These assumptions fall apart in the face of coercion since all secrets can be extracted from the participant.

Implicit learning provides the following new abstract functionality: the training phase embeds a predicate

p : Σ → {0, 1}
in the user’s brain for some large set Σ. Anyone can ask the
user to evaluate his or her predicate p at a point k ∈ Σ. The
predicate evaluates to 1 when k has been learned by the
user and evaluates to 0 otherwise. The number of inputs at
which p evaluates to 1 is relatively small. Most often p will

14

12

10

8

6

4

2

0

Exp 1 Before 1

week Before 2 weeks

1 week 2 weeks

Tr a ine d se quen ce a dv ant a ge( % )

Figure 5. Participants exhibited reliable sequence knowledge on both immediate assessments (shown for Experiment 1 and both conditions of Experiment 2) shown by a performance advantage for the trained sequence compared with untrained, novel sequences at test. Sequence knowledge is retained at both the 1- and 2-week delay test sessions. While there is some reduction in expressed knowledge after either delay, the lack of significant additional decay from 1 to

2 weeks suggests that information is likely to persist for significant periods following 2 weeks (exponential or power-law decay curves are commonly observed for many types of memory).