Poor man's authentication algorithm?

Question

Brainstorming request

I need an idea for an authentication algorithm with some unusual requirements.

The algorithm would be used to verify that the sender of a message is legitimate.

Restrictions:

1. The "transport layer" is e-mail
   • the sender ('Alice') is a human being
   • Alice only has access to a web browser and internet access (including a webmail account) as her tools; therefore she can't do very complicated calculations
   • The receiver ('Bob') is a computer with no direct access from the internet.
   • Bob has an email account that it checks periodically.
   • Bob can send email.
   • No sending info to a 3rd party: Alice and Bob can't send any out-of-band info. Reading some publicly available info (such as the time from a time server) is ok.

Assumptions:

• Alice can access some information locally: maybe she carries a notebook, or we could even assume her web mail account is hack-proof, therefore sensitive information can be stored there.
• Alice and Bob can exchange sensitive information directly at a time prior to the authentication (private keys?)

Non-goals:

• encoding of the actual payload of the message is not necessary.
• speed/latency are not (big) issues

Some ideas to get you started:

1. Plain old hard-coded password.
   Problems:

   • brute force attack (not likely)
   • eavesdroping possible if the communication is done in clear text, then replay attacks possible

2. Simple algorithm based on current date/time
   Example: Alice adds the current date, hour and minute and sends the result as the auth token, which Bob can verify. Let's assume that read-only access to a time server does not violate rule #7 (no 3rd party).
   Problems:

   • security through obscurity: the algorithm is somewhat safe only because it is not publicly available (well, it is now... oops!)

3. Some sort of challenge-response mechanism - Alice sends a request for authentication, Bob replies with a challenge, Alice sends the expected response and the actual payload.
   What are the details of the mechanism? I don't know :)

What can you think of? I'm hoping to see some creative answers ;-)

Edit:

Maybe an example would make rule #3 clearer: let's assume that Alice is using a proprietary closed-source device <cough> iPhone <cough> to access the Internet, or she is standing in front of a public internet kiosk.

Answer 1

My idea of a human-friendly low-tech challenge-response mechanism:

1. Bob changes the challenge every time he receives a valid message (for example he makes a salted hash of the current time)
2. every invalid message sent to Bob makes him reply with the current challenge, so Alice can query him by sending an empty mail
3. once Alice knows the challenge, she goes to https://www.pwdhash.com/
   • in "Site Address" she enters the current challenge
   • in "Site Password" she enters her personal password (which is known to Bob)
   • PwdHash generates a "Hashed Password"
4. Alice writes a message to Bob, using the hash just created as the subject
5. Bob receives the message, hashes the current challenge and Alice's password according to the PwdHash algorithm, and sees if his result matches the message subject
6. if it does, Bob accepts the message and and sends out a confirmation containing the new challenge (essentially this is step 1)

Advantages:

• cheap & simple, may even run on reasonably modern mobile devices
• human friendly (no math, easy to remember, prerequisites easily available on the net)
• no replay attack possible
• no clear text passwords over the wire
• does not run out of passwords (like one-time pads do)
• no inherent time limits (like RSA tokens have)
• the PwdHash web site can be saved on disk and called locally, no third party dependency here

Disadvantages:

• Bob and Alice must pre-share a key (Alice's password), therefore Alice cannot change her password off-site
• compromising Alice's password is the easiest attack vector (but that's the case with almost all password protected systems)

Note that PwdHash is an open hashing algorithm, Bob can easily implement it. The PwdHash web site works without post-backs, everything is client side JavaScript only, no traces left behind.

Answer 2

Two options I can think of:

• Issue a card with one-time passwords (communication before the fact, notebook)
• Electronic device that produces pincodes (avoids replay-attacks)

Answer 3

In addition to Treb's answer, you can use one-time passwords you can print instead of SecurID. See "Perfect Paper Passwords" for details.

Answer 4

Am I missing something obvious in suggesting a simple public/private key and signing the email?

Firefox has at least one extension to allow GPG in webmail.