One Time Password Algorithm for Humans

Question

Is there a one time password generation algorithm (based on predefined secret and a changing value/time/counter/etc) that is simple enough that it can be processed by an average human but safe enough that the secret cannot be found with just a few passwords (say 5-10)?

I have seen questions on various specific password schemes and how secure they are. But I'd like to know more generally whether some well-know algorithms exist.

Intuition tells me, that if something is easy enough to be processed by a human, then its also easy to break. But then again I was very surprised that asymmetric encryption is possible, or secure key exchange (DH). So, surprise me!

---

Edit: Some clarification.

The question came up when I was pondering about two-factor authentication for outdoor use. A typical two-factor authentication for safe environments (home, office, ...) uses a password and an OTP generator in a device or on your phone. You loose the device/phone, there's still the password. A keylogger steals your password, there's still the device/phone.

But what about situations where both could be stolen? For example, you use an app to pick up an e-bike on the street or to open a locker in a train station. Someone might watch while you enter the password on your phone and later also steal the phone itself.

The problem could be solved by using passwords that become useless within a short time frame (eg. 10min). In addition the phone would have an individual secret (e.g. SSL client certificate) to make brute-force attacks against the password authentication harder.

mr.spuratic's suggestion around Blum's HCMU algorithm is pretty close to what I was looking for. It still looks a little too heavy weight for the average human, but with some practicing it would be feasible.

Answer 1

There are some commercial schemes, e.g. GridGuard from SyferLock that claim to do this, but I have never used them (I have no affiliation). This relies on the user choosing correctly from multiple options during authentication rather than a typical time or counter based OTP (which means no mental arithmetic).

Solitaire (Schneier), is often cited for a human-computable cryptosystem, it would need some adaption for authentication purposes though. A challenge-response authentication with shared key would be practical, but does not fulfill your description of the OTP.

What should work (with the usual caveat) would be an implementation of TOTP (RFC6238) or HOTP (RFC4226), using an alternate HMAC hash such as Blum's HCMU (Human Computable Machine Unbreakable, description here) mentally computable hash (see also the more generalised OCRA (RFC6287).

TOTP/HOTP are basically the (truncated) output of a HMAC using SHA-1, the input being a shared secret and timestamp or counter. You would need to use a strictly alphabetic representation of the input though, as Blum's algorithm applies only to alphabetic input.

Blum also co-authored a paper Towards Human Computable passwords (on ArXiv), though large parts of it are heavily mathematical. It doesn't briefly covers OTP in §7.2.

See also:

• https://crypto.stackexchange.com/questions/9787/are-there-cryptographic-hash-functions-that-can-be-computed-using-only-paper-and
• https://crypto.stackexchange.com/questions/844/is-there-a-secure-cryptosystem-that-can-be-performed-mentally

Answer 2

You could have a lookup table that's used like a one time pad.

Each page in the lookup book is a day's worth of OTPs, and you look up the book on the current date/time to get the correct OTP for that moment. This simulates a TOTP. You can trade off between security (how often the TOTP changes) and the thickness of your lookup book.

Answer 3

Steve Gibson put together something called "Perfect Paper Passwords" as sort of a demonstration of how it could be done. https://www.grc.com/ppp has the details. The site has downloadable code that can be used to build upon to make a more sophisticated implementation.

This is not time based, but is simply a sequence of one-time passwords, which can only be used in order. Even if the current password is sniffed, it provides no information about the next one. The number of characters per password and the "alphabet" are adjustable.

Here we see that codes 1A-D have already been used, and the next code to be used is E1 (Tygq).

Answer 4

To be honest, even the official TOTP algorithm isn't massively complicated, although you'd have to be pretty dedicated to calculate a HMAC in your head. However, this does suggest that you could reasonably have a calculated time based password system, using most of the same building blocks.

The main problems would be that people aren't as good as computers at a lot of things:

• People don't have built in time sources, so you need enough flexibility to handle someone being a reasonable length of time "out" from the source. You probably can't count on someone being more than about 5 minutes within the correct time, and even longer might be better, from a perspective of minimising calculation errors.
• People are slow at calculation. You can rely on a computer to perform millions of calculations in a second. A person can probably manage one calculation, once they've got the values needed. That also means you need to allow a lot longer for someone to enter a valid value.
• People make mistakes when doing repeated operations. That means that they're more likely to need to enter multiple values, if they make a single mistake in the process. Each attempt takes some amount of time.

Therefore, adapting the TOTP algorithm directly would involve:

1. Replace the HMAC step with something an average person can do mentally
2. Define an epoch which a human can work out a difference from mentally - maybe midnight of the current day, with some date based modification in place
3. Define an interval which is long enough for a human to both be able to perform some calculations in, and which can be identified as being a given number of intervals from the chosen epoch - five minutes would be doable, so calculating a code at 0912 would be (9*12 + 2*5 = 118 as a value)
4. Use the HMAC replacement with the value and the memorized key.
5. Transform the value to an appropriate range, potentially by discarding bits of it.

This will be less secure than the computer based one, since an attacker would be able to compute a lot of potential values quickly, so you'd also want to restrict how many attempts were allowed within a given interval.

And no, I don't know what a suitable HMAC replacement would be...