MAY 2014 | VOL. 57 | NO. 5 | COMMUNICATIONS OF THE ACM 111
participants complete sequences containing all minimal-length fragments needed to try to reconstruct the identification sequence: our results show that participants do not
express reliable sequence knowledge under this condition,
indicating that the underlying sequence information is
resistant to attack until longer subsequences are guessed
correctly by the attacker.
2. AN OVERVIEW OF THE HUMAN MEMORY SYSTEM
The difference between knowing how to perform a well-learned skill and being able to explain that performance is
familiar to anyone who has acquired skilled expertise. This
dissociation reflects the multiple memory systems in the
5 Memory for verbally reportable facts and
events depends on the medial temporal lobe memory system
(including the hippocampus). However, even patients with
an impaired medial temporal lobe, for example as a result
of Alzheimer’s disease, show an intact ability to acquire
new information implicitly, including exhibiting normal
learning of certain physical tasks.
3 Several decades of experimental cognitive psychology have led to the development of
tasks that selectively depend on this type of implicit, nonconscious learning system.
2. 1. The SISL task
The Serial Interception Sequence Learning (SISL) task7 is a
task in which human participants learn a sequence of letters without being aware of what they have learned. The task
requires participants to intercept moving objects (circles)
delivered in a predetermined sequence, much like this is
done in the popular game “Guitar Hero” (Figure 1).
In our variant of SISL, each circle appears at the top of
one of six different columns, and falls vertically at a constant
speed until it reaches the “sink” at the bottom, at which
point it disappears. The goal for the player is to intercept
every object as it nears the sink. Interception is performed
by pressing the key that corresponds to the object’s column
when the object is in the correct vertical position. Pressing
the wrong key or not pressing any key results in an incor-
rect outcome for that object. In a typical training session
of 30–60 minutes, participants complete several thousand
trials and the order of the cues follows a covertly embedded
While in this paper we focus on coercion-resistant user
authentication systems, authentication is just the tip of the
iceberg. We expect that many other coercion-resistant secu-
rity primitives can be designed using implicit learning.
Threat model. The proposed system is designed to be
used as a local password mechanism requiring physical presence. That is, we consider authentication at the entrance to
a secure location where a guard can ensure that a real person
is taking the test without the aid of any electronics.
To fool the authentication test, the adversary is allowed to
intercept one or more trained users and get them to reveal as
much as they can, possibly using coercion. Then the adversary, on his own, engages in the live authentication test and
his goal is to pass the test.
We stress that as with standard password authentication,
the system is not designed to resist eavesdropping attacks
such as shoulder surfing during the authentication process.
While challenge-response protocols are a standard defense
against eavesdropping, it is currently an open problem to
design a challenge-response protocol based on implicit learning. We come back to this question at the end of the paper.
Benefits over biometric authentication. The trained secret
sequence can be thought of as a biometric key authenticating the trained participant. However, unlike biometric keys
the authenticating information cannot be surreptitiously
duplicated and participants cannot reveal the trained secret
even if they want to. In addition, if the trained sequence is
compromised, a new identifying sequence can be trained as
a replacement, resulting in a change of password.
In a related work, Denning et al.
1 proposed using images
to train users to implicitly memorize passwords. This
approach may not be as resistant to rubber hose attacks since
users will remember images they have seen versus ones they
have not. Additionally, image-based methods require large
sets of images to be prepared and used only once per user,
making the system more difficult to deploy. Our combinatorial approach lets us lower bound the entropy of the learned
secrets, is simple to set up, and is designed to leave no conscious trace of the trained sequences.
User studies. To validate our proposal, we performed a
number of user studies using Amazon’s Mechanical Turk.
We asked the following core questions that explore the fea-
sibility of authentication via implicit learning:
• Is individual identification reliable? That is, can trained
users re-authenticate and can they do it over time?
• Can an attacker reverse engineer the sequence from
easily obtained performance data from a trained
Across three experiments, we present promising initial
results supporting the practical implementation of our
design. First, we show that identification is possible with
relatively short training and a simple test. Second, the
information learned by the user persists over delays of
1 and 2 weeks: while there is some forgetting over a week,
there is little additional forgetting at 2 weeks suggesting a
long (exponentially shaped) forgetting curve. Finally, in a
third experiment we examined an attack based on having
Figure 1. Screenshot of the SISL task in progress.
Progress this section