I keep getting asked about hash-based one-time-password mechanisms, so I decided to write-up a little blog entry.

First, let's take a 10-mile-high look at hash functions, willingly ignoring all security-relevant aspects. One of the traits a cryptographic hash function should exhibit is that for an input value X an output value X' is computed, which can not be used to deduce the original input value of X. For example, given the input value

X = 4711

then a pseudo-hash function could be to just add up all the number's digits. Thus, this pseudo-hash function would yield the result value

X' = 13

because 4+7+1+1 equals 13. However, given the result value 13 one can not deduce the original input precisely (other input values will also yield 13 but we'll ignore this aspect for now). This computation is employed recursively in hash-based one-time-password algorithms: given a passwort of

X = 74117101114103101110809798101108

than the first iteration yields

X' = 88

and the second iteration produces

X'' = 16

X''' = Y = 7

and we'll stop here for the demonstration purposes (and because we can not proceed in a meaningful manner with a single digit value).

Now, let's construct our one-time-password mechanism using our pseudo-hash function: the user enrolls by providing the n'th hash of his password to the server. For our example, let n be 3; hence, our user enrolls by submitting n=3 and Y=7 to the server. The user is subsequently able to authenticate by sending n=2 and X=16 to the server: the server validates that the hash value of X (-> 16) equals to the stored value of Y (-> 7) and since that is correct it now stores n=2 and Y=16 in its database. The next user authentication would send n=1 and X=88 to the server and the validation would pass once again. However, at this point our one-time password logic has reached it's practical limits because n would be 0 next and thus the original password would have to be sent to the server (which we don't want to do).

Real one-time-password implementations commonly use values of 500 or even 5000 for n. Therefore, they allow a feasible number of successful authentications before requiring a password change. A beneficial trait of real cryptographic hash functions is that they (usually) produce results of a constant length. Thus, the length of the inputs and outputs remain constant (whereas our cross-summing approach requires ever increasing numbers for every increase in n).

Last - but definitively not least - we must also realize that cross-summing lacks (at least) two important security and cryptographic traits:

1. it's not collision free: for any given Y a (rather random but) valid X is easily computed and that number could (fraudulently) be used for authentication,
2. it's enumerable/brute-forceable (unless X is reaalllly large and n is reallly small and thus impractical to handle).

That's it - well, not really: many other security aspects need to be addressed, but an entirely different blog entry.