sequences (or fragments) randomly interspersed with 8
foils. Authentication succeeds if the attacker shows a measurable performance gap on the correct 4 out of 12 presented sequences. An attacker who slows down on random
sequences will now have at most a ( )≈
12
4 1/ 1/500 chance in
passing the test. The number of trained sequences ( 4) and
the number of foils ( 8) can be adjusted to achieve an acceptable tradeoff between security and usability.
Similarly, a small number of authentication attempts
will not help a direct attacker pass the test. However,
memorizing the authentication test (360 symbols) and
later presenting it to a coerced user could give the adversary an advantage. To further defend against this memorization attack, we add one more step to the authentication
procedure: once the authentication server observes that
the user failed to demonstrate a measurable gap on some
of the trained sequences, all remaining trained sequences
are replaced with random foils. This ensures that an
attacker who tries to authenticate with no prior knowledge will not see all the trained sequences and therefore
cannot extract all trained sequences from a coerced user.
Consequently, a one-shot attack on a coerced user is not
possible. Nevertheless, by iterating this process—
taking the authentication test, memorizing the observed
sequences, and then testing them out on a coerced
trained user—the attacker may eventually learn all trained
sequences and succeed in fooling the authentication test.
During this process, however, the attacker must engage in
the authentication test where he demonstrates knowledge
of a strict subset of the trained sequences, but cannot demonstrate knowledge of all sequences. This is a clear signal
to the system that it is under attack, at which point the person engaging in the authentication test could be detained
for questioning and the legitimate user is blocked from
authenticating with the system until he or she is retrained
on a new set of sequences.
Eavesdropping security. Traditional password authentication is vulnerable to eavesdropping (either via cli-ent-side malware or via shoulder surfing) and so is the
authentication system presented here. An eavesdropper who obtains a number of valid authentication transcripts with a trained user will be able to reconstruct the
learned sequence(s). It is a fascinating direction for future
research to devise a coercion-resistant system where an
implicitly learned secret is used in a challenge-response
protocol with the server. We come back to this question at
the end of the paper.
5. 2. An experiment: extracting sequence fragments
One of the potential attacks on our system involves a malicious party profiling the legitimate user’s knowledge and
using that information to reverse engineer the trained
sequence to be able to pass the authentication test. Although
the number of possible trained sequences is too large to
exhaustively test on any single individual, each sequence is
constructed according to known constraints and knowledge
of sequence fragments might enable the attacker to reconstruct either the original sequence or enough of it to pass an
authentication test.
Further complicating the attacker’s life is the fact that
subjecting a person to many random sequences through
SISL may obliterate the learned sequence or cause the person to learn an incorrect sequence thereby making extraction impossible.
We note that physical presence is necessary in authentication systems designed to resist coercion attacks. If the
system supported remote authentication, then an attacker
could coerce a trained user to authenticate to a remote
server and then hijack the session.
Security enhancements. The security model above gives
the attacker one chance to authenticate and the attacker
must succeed with non-negligible probability. If the
attacker is allowed multiple authentication attempts—
iterating the extraction and test phases, alternating between
the two—then the protocol may become insecure. The reason is that during an authentication attempt the attacker
sees the three sequences k0, k1, k2 and could memorize
one of them ( 30 symbols). He would then train offline on
that sequence so that at the next authentication attempt
he would have a 1/3 chance in succeeding. If the attacker
could memorize all three sequences ( 90 symbols), and
then reconstruct the SISL task, he could subject a trained
user to all three of the memorized sequences offline in
order to reliably determine which is the correct authentication sequence through the users performance. Then the
attacker could train himself on that specific sequence. He
is then guaranteed success at the next authentication trial.
We note that this attack is nontrivial to pull off since it can
be difficult for a human attacker to memorize an entire
sequence at the speed the task is performed.
Another potential attack, already discussed in Section 3,
is an attacker who happens to be an expert player, but deliberately degrades his performance on two of the sequences
presented. With probability 1/3, he will show a performance
gap on the correct sequence and pass the authentication
test. We described a number of defenses in Section 3. Here
we describe a more robust defense.
Both attacks above can be defeated with combinator-ics. Instead of training the user on a single sequence, we
train the user on a small number of sequences, say four.
Experiments8 suggest that the human brain can learn multiple sequences and these learned sequences do not interfere with one another. What is more, new experiments that
we have carried out demonstrate that users can be trained
on multiple 30-character sequences within an interval of
24 to 48 hours—without measurable interference among
the sequences. Equivalently we could train the user on a
longer sequence and use its fragments during authentication. While our data above shows that the shortest possible
(three-item) fragments cannot be used to assess knowledge
of a longer sequence, we have more recently found that
sequential knowledge is reliably expressed for longer fragments (e.g., 5–7 items).
6 Thus, by investing additional time
in the initial training to encode more information, we could
use fragment-based tests to increase resistance to the eavesdropping attacks described above.
During authentication, instead of using one correct sequence and two foils, we can use the four correct