Mutual Authentication

2019-09-26

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](https://security.stackexchange.com/questions/29842/mutual-authentication-for-humans/29878)
out on the Internet. [There's even an xkcd about it, sort
of.](https://xkcd.com/1121/) 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](https://security.stackexchange.com/a/29878) 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.