frequencies or common pairs of letters, which reduces
conscious recognition of the embedded repeating sequence.
2
Let Σ denote the set of all possible secret keys, namely,
the set of 30-character sequences corresponding to Euler
cycles in Figure 2. The number of Euler cycles in this graph
can be computed using the BEST theorem11 (where the
number of spanning trees of the K6 graph is 64 by Cayley’s
formula, and every vertex’s in-degree is 5, so Πv (deg (v)– 1)!
is 246), which gives
keys =Σ=
64 · 246 ≈ 237.8.
Hence, the learned random secret has about 38 bits of
entropy, which is far more than the entropy of standard
memorized passwords.
Training. Users learn a random 30-item secret key k ∈ Σ
by playing the SISL task in a trusted environment. To train
users, we experimented with the following procedure:
• While performing the SISL task the trainee is presented
with the 30-item secret key sequence repeated three
times followed by 18 items selected from a random
other sequence (subject to the constraint that there will
be no back-to-back repetitions of the same cue), for a
total of 108 items.
• This sequence is repeated five times, so that the trainee
is presented with a total of 540 items.
• At the end of this sequence, there is a short pause in
the SISL task and then the entire sequence of 540 items
(including the pause at the end) is repeated six more
times.
During the entire training session, the trainee is presented
with 7 × 540 = 3780 items, which takes approximately 30–45
minutes to complete. After the training phase completes,
the trainee runs through the authentication test described
next to ensure that training succeeded. The system records
the final playing speed that the user achieved.
repeating sequence on 80% of the trials. The task is designed
to keep each user at (but not beyond) the limit of his or her
abilities by gradually varying the speed of the falling circles
to achieve a hit rate of about 70%. Knowledge of the embedded repeating sequence is assessed by comparing the performance rate (percent correct) during times when the cues
follow the trained sequence to that during periods when the
cues follow an untrained sequence.
All of the sequences presented to the user are designed
to prevent conspicuous, easy-to-remember patterns from
emerging. Specifically, training as well as random sequences
are designed to contain every ordered pair of characters
exactly once with no character appearing twice in a row
(thus the sequence length must be 6 × 5 = 30). The result is
that while the trained sequence is performed better than an
untrained sequence, the participant usually does not consciously recognize the trained sequence. In order to confirm
this in experimental work, after SISL participants are typically asked to complete tests of explicit recognition in which
they specify how familiar various sequences look to them.
Compared to the original SISL task using 4 keys, our version increases the space of possible sequences from only
256 to over 240 billion. In addition, the gap we introduced in
the middle of the visual display makes it easier to associate
a column with the correct hand—left or right—responsible
for that column.
The SISL task is delivered to users as a Flash application via a Web browser. Participants navigate to our Web
site, www.brainauth.com, and are presented with a consent
form. Once they agree to participate, the applet downloads
a random training sequence and starts the task. Upon completion of the training and test trials, the explicit recognition test is administered, and results are uploaded to the
server. Once we describe our authentication system, we will
return to describe how the SISL applet functions in the bigger scheme of our experiments with multiple users.
3. THE BASIC AUTHENTICATION SYSTEM
USING IMPLICIT LEARNING
The SISL task provides a method for storing a secret key within
the human brain that can be detected during authentication,
but cannot be explicitly described by the user. Such a system
avoids the problem that people can be persuaded to reveal
their password and can form the basis of a coercion-resistant
authentication protocol. If the information is compromised,
a new identifying sequence can be trained as a replacement—resulting in a change of password.
The identification system operates in two steps: training followed by authentication. In the training phase, the
secret key learned by the user is as in the expanded SISL task,
namely, a sequence of 30 characters over the set S = {s, d, f,
j, k, l}. We only use 30-character sequences that correspond
to an Euler cycle in the graph shown in Figure 2 (i.e., a cycle
where every edge appears exactly once). These sequences
have the property that every non-repeating bigram over S
(such as ‘sd’, ‘dj’, and ‘fk’) appears exactly once. In order to
anticipate the next item (e.g., to show a performance advan-
tage), it is necessary to learn associations among groups
of three or more items. This eliminates learning of letter
sf
l
kj
d
Figure 2. The secret key we generate is a random 30-character
sequence from the set of Euler cycles in this directed graph.
The resulting sequence contains all bigrams exactly once, excluding
repeating characters.