Is there any way for two people to securely authenticate each other without access to any special software (like PGP)? For example, when speaking over the phone or by sending SMSes to each other or using some other text channel. Assume they can securely exchange any necessary secrets beforehand and also have access to software then, but at the time they need to do the authentication they have only basic phones or perhaps calculators.

Obviously the simplest thing is for each person to have a password that they say to the other, but this is not secure, because one person always has to go first. If the other is an impersonator they now have one of the passwords. So I'm probably looking for some kind of a challenge-response mechanism here - but whatever works.

  • 1
    Is this on topic? I don't see the I.T. half of "I.T. Security" in this question. – David Stratton Jan 29 '13 at 1:52
  • @DavidStratton Yes. I did close a question earlier as "not related to IT", but mostly because I considered it too trivial. In many ways, we're more "Intellectual" than Technology. If you'd like to poke more at figuring out what that line is, a post in meta.security.stackexchange.com would be the way to go. – Jeff Ferland Jan 29 '13 at 2:01
  • Thanks for the clarification! I'll poke around a bit as you suggested. – David Stratton Jan 29 '13 at 2:12
  • Do you need to prevent third parties (e.g. eavesdroppers) from telling whether the two authenticated? – Mike Samuel Jan 29 '13 at 5:56
  • 3
    Mandatory XKCD xkcd.com/1121 – Cristian Dobre Jan 29 '13 at 7:34

So I'm probably looking for some kind of a challenge-response mechanism here

I'd guess so. Print up a few pages of text in the following format:

# Challenge Response    # Challenge Response
1 monkey    character   2 sinew     orange
3 bottle    helmet      4 glass     glove

You'll both have the same list. Whenever you authenticate it doesn't matter who goes first. Provide a challenge word and check the response. You might say, "3 - Bottle," and wait for your friend to look it up saying, "Helmet." Both of you cross the number off the list and never use it again.

They're authenticated by providing the correct word in response. Then they pick a number and do the same thing to guard against a case where your friend may have challenged an attacker, thus providing them with a number-challenge pairing and using it in replay.

The words can be random letters, the result of picking random lines from a very long wordlist, etc as long as they're randomly chosen.

| improve this answer | |
  • 2
    Interesting, thanks, but could you elaborate on how to prevent replay attacks? Eg. this scenario: Mallory calls Alice Alice: Challenge 1 Mallory: sorry, bad reception, let me call you back Mallory calls Bob Mallory: Challenge 1 Bob: Response 1 Mallory calls Alice back Mallory: Response 1 Alice: Oh good, it's you, Bob! In this scenario Bob had no way of knowing Challenge 1 had already been used and Alice only used it once, successfully, as far as she can tell. – EM0 Jan 29 '13 at 1:25
  • 1
    Maybe the solution is as simple as having separate challenge response lists for the two of them, so that Bob would never respond to a challenge intended for Alice? – EM0 Jan 29 '13 at 1:26
  • Well, the two-way authentication would avoid that because the same C/A can't be used again and would be detected if used going the other direction. "Hey, you just asked me a question that is crossed-off. What's up with that? Start over." That does rely on both parts of the auth being completed, though. Two lists might be harder to work with, but could be an improvement in earlier detection. – Jeff Ferland Jan 29 '13 at 2:00
  • It would be detected next time unless I'm misunderstanding something, but by that stage the attacker has already succeeded at least once. Separate lists for the two people sounds like it could work around that. Do you see any issues with that approach? – EM0 Jan 29 '13 at 2:42
  • 1
    @EM Alice accidentally challenges Eve with #1. Eve doesn't reply. Alice crosses out #1. Eve calls Bob and challenges him with #1. Bob replies. Bob then challenges Eve with #2. Eve doesn't have an answer. Eve tries to make the best out of it.. she effects a deep voice and calls Alice, challenging her with #2. Eve doesn't have any answers, though. She'll never have the answer to a question that the asking party hasn't already crossed off their list. That said, two lists does fix some human security factors / complacency. – Jeff Ferland Jan 29 '13 at 5:28

As a meta-answer, consider the attack types:

  • Active attacks on the line: the bad guys plug on the line, observe the communication, and interfere with it. When both Alice and Bob have done their games with passwords or whatever, and are both convinced that they talk to the right person, the attackers cut the line and promptly redirect both conversations to Charlie and Deborah, who imitate the voices of, respectively, Bob and Alice. Charlie talks to Alice, Deborah talks to Bob. This is a full (wo)man in the middle attack and it is unavoidable. Conceptually, this means that authentication is relative to the exchanged data; if you just authenticate the line then you are trusting the network for being immune to active attacks. Therefore, in your model, you must assume that such active attacks do not happen.

  • Passive attacks on the line: also known as "eavesdropping". This is a well-known kind of attack practised by law enforcement agencies and spies all over the world, and it predates phones, too. For a simple authentication issue, eavesdropping is not a danger, since passive attackers, by definition, are passive: they do not prevent or interfere with communications. But they may learn quite a lot, and use that ill-gotten knowledge to help the third kind of attacker (see below).

  • Impersonation: Charlie or Deborah tries to impersonate Bob or Alice when talking to Alice or Bob. This is a weakened variant of the full active attack explained above, in that the attacker does not get to hijack an ongoing conversation; he must start right away. In order to avoid an eavesdropper learning enough to perform an ulterior impersonation, the protocol must not be fully deterministic; otherwise, a replay attack is possible (simply put, Charlie says to Alice exactly what Bob said to Alice the day before).

A special note must be made about simultaneous double impersonation: this is a variant of the MitM attack, in which Charlie calls Alice and Deborah calls Bob simultaneously; Charlie and Deborah are in adjacent rooms and have ear plugs so that both can hear both conversations; they then "forward" messages between Alice and Bob. This is the "low tech" variant of the active attack explained above. That variant can be averted by using an extra characteristic: during a normal phone call, one participant is the caller, and both participants know which one is the caller. In the double impersonation setup, Alice and Bob are both "receivers". So the authentication protocol must be asymmetric: the caller/receiver role MUST be used in the choice of challenges/answers.

So you end up, basically, with the solution shown by Jeff Ferland: a challenge/response protocol, where challenges and responses are one-time passwords. Alice/Bob must never reuse a challenge, or accept to respond to a reused challenge. To prevent simultaneous double impersonation, an extra convention must be enforced: receiver talks first. In Jeff's protocol, Alice will send a challenge ("what is word number 17 in the list ?") to which Bob must respond; and Bob will also send a challenge to Alice, to which Alice must respond. Let's add the extra convention: if Alice calls Bob, then Bob must issue the first challenge; Alice will send here challenge only after responded to Bob's challenge. In the MitM scenario, both Charlie and Deborah are callers, so they both receive challenges, and have no response to feed on. And now it is safe (up to confidentiality issues with eavesdroppers, and in-conversation hijack by powerful attackers, both of which being deadly, and can be thwarted only with cryptography).

| improve this answer | |
  • Some good points, thank you. I think the person answering the call would typically issue the challenge anyway ("hey, you called me, so you prove who you are first"), but it's a good idea to make this part of the protocol. – EM0 Jan 29 '13 at 15:39

Inetresting question, but authentication is really just validating that "you are who you say you are", right? The matter of securely is open to interpretation and will likely change as time progresses or the method used no longer becomes "good enough". So a simple passphrase is secure, but no longer considered "good enough" because it can be guessed or eavesdropped or whatever. Your telephone example can be better secured by use of a second, "out of band" confirmation, such as calling a certain number or sending a photo of the person's face via MMS. That could easily become not secure enough though too. Jeff's answer is a good simple method. I suppose the classic answer is the movie answer "Tell me something only you and I would know?" Then the something is variable-ized and can change each time after use, allowing for better security. If identity was verified previously the something could be an item of knowledge from the previous encounter.

On further thought this seems perhaps more appropriate for 3rd party validation than by key exchange. My "good enough" train of thought thinks that the challenge response lists will become unmanageable eventually and require the use of software or some technology the original question dislikes.

They could decide on a mutual, trusted third party beforehand. When meeting the two exchange a password of their choice. With their "basic phones" they could contact the third party via voice or SMS and have each persons password validated only by the third party. The third party can use the password as a public key, protecting the first party's private key. Thus, the public key password can be changed without affecting the private key and requiring excessive re-authentication of the first party by the third party.

| improve this answer | |
  • But how would the trusted third party be authenticated, ie. when you get a message saying "yes, authentication succeeded" how do you know it really came from them? Also, I don't understand what you mean by "use the password as a public key". – EM0 Jan 29 '13 at 6:50
  • I was thinking along the lines of talking to your credit card company for instance. If they call you, you don't trust them, so you call them to verify. This aside, you could set up a similar, or different authentication with the trusted third party. – Mike Jan 29 '13 at 7:39
  • As for password as public key, I was thinking along the lines of SSL certs, using public and private keys. The public key can be shared and distributed, used to validate against a private key. I'm pretty much making a comparison of the discussed methods of challenge-response to shared secrets, such as SSH, to a method which offloads or outsources the validation (per your constraints on technology) to a third party. A synchronized set of random value generators (a la RSA SecurID) seemed too obvious a cheat around the software rule. – Mike Jan 29 '13 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.