Communications of the ACM

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.