Some time ago, I became interested in the idea of mutual authentication between people—not computers, but actual humans with nothing to hand except their brains and… well, I guess their hands, too. Whether in person or over some communication medium, how could two people quickly and easily verify with high confidence that the party they were speaking with was the legitimate, intended recipient of the communication?

This is not a new problem, and there’s already some good discussion out on the Internet. There’s even an xkcd about it, sort of. I definitely don’t have the knowledge to come up with a complete solution to this problem—and it seems like that may always be impossible depending on the parameters—but just for fun I’d like to write out my idea here.

Suppose Alice and Bob wish to communicate, but they also want to verify each other’s identities first. To do that, Alice and Bob first agree on a secret word or phrase over a secure connection. Suppose they choose they choose the phrase “mambo dogface banana patch”. Alice and Bob remember the phrase and don’t share it with anyone.

Later, when they wish to mutually authentication, Alice challenges Bob by sending him a single letter of the alphabet of her choice. Suppose she sends the letter O. Bob counts the number of times that letter occurs in the secret phrase—in this case, two times—and sends that number back. Alice also counts for herself and checks her result against Bob’s response. If they match, then Alice can begin to assume that Bob is really Bob. Alice can continue to challenge Bob with different letters until she is satisfied. Similarly, Bob can challenge Alice with different letters. When both are satisfied, communication may begin.

It should be noted that either party can challenge the other with letters that aren’t in the secret phrase. In this case, they should simply expect a response of zero.

This protocol is vulnerable in several ways. Perhaps the most obvious is that a malicious party, Eve, could listen to Alice and Bob trade challenges and responses and slowly gather a mapping of letters to numbers. Later, without knowing the secret phrase, Eve could impersonate either party by responding based on her learned mapping. I learned recently that this is called a replay attack. One mitigation against this would be to cross out letters as they’re used, but that violates the “just brains, no tools” criterion I set out at the beginning. For paranoid parties—who probably shouldn’t be using this protocol in the first place—it’s possible to simply discard phrases after every communication and agree on new ones later on, but this is cumbersome.

While certainly vulnerable, I think this simple sort of approach ought to be enough to (a) provide any level of authentication between two people without tools and (b) satisfy the budding crypto nerd in me who just wants to have fun with this stuff.