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).