SMS Authentication: random OTP or a cryptographic one

Question

I'm adding two-factor authentication using SMS to enhance an existing login process. Since I'm not working with physical tokens, I was wondering what is considered the safest:

Sending random 8 character strings or 8 digit hashes generated using some kind of Time-based One Time Password (TOTP)algorithm.

My own considerations were the following: Hashes generated using TOTP don't have to be stored in order to check if they are entered correctly by the user. Randomly generated tokens do need to be stored and linked to a user account and a time stamp.

Yet, the process of randomly generating a string seems easier and appears to have less vulnerable spots that can be compromised.

Answer 1

If done properly, time-based one-time passwords will be reasonably secure. That's a bigger "if" than usually assumed.

What would work would be the following:

1. Decide about your time granularity, e.g. 5 minutes. All dates considered here will be a multiple of that granularity (i.e. 8:05:00, 17:25:00... but not 16:34:00).

2. Generate a secret symmetric key K of appropriate size (16 bytes straight from /dev/urandom, CryptGenRandom(), java.security.SecureRandom or System.Security.Cryptography.RNGCryptoServiceProvider, depending on your religion).

3. When generating a one-time password P for user U at time T, compute:

   P = encode(HMAC/SHA-256(U || T, K))

   which means that you "concatenate" the user name and the current date into a custom structure (XML, ASN.1, text-with-separator... whatever fits your bill, as long as it is deterministic and non ambiguous), over which you compute a MAC, using specifically HMAC with SHA-256 as underlying hash function, and K as key. The encode() function is something which truncates the output of HMAC and encodes it into something that can be displayed on a phone and typed in by a user.

4. You send P to the user. At time T' (presumably not long after T), the user comes back and enters a password P'. You then recompute the value of P for time T' and for time T'-5min, for the same user U. If either value matches P', then authentication succeeds, otherwise it fails.

The tricky points:

• You must not truncate "too much". The attacker may want to try his luck and send a random password; the space of possible passwords must be wide enough to make such success highly improbable.

• You can use any "encoding" you want as long as it is deterministic and mostly uniform. For instance, interpret the HMAC value (a 256-bit string) as a big integer (in the 0..2²⁵⁶-1 range) and take the remainder of the division of that integer by 100000000; you can then represent that value in decimal (left-padded with zeros if necessary), to get a nice 8-digit password. The remainder operation is the "truncate" and it will be sufficiently unbiased in this situation. If you prefer 8 letters, divide by 26⁸ and use base 26 to represent the remainder.

• The granularity is linked to the security. Note that upon verification, we try exactly two passwords (we need that, because the password must be valid even if the user gets his SMS at 11:34 and enters it back at 11:36). This divides by 2 the difficulty for the attacker: if passwords are 8-digit sequences, then there are 100000000 possible passwords, but the attacker has probability 1/50000000 of success. A granularity of 5 minutes means that a one-time password is valid for 5 to 10 minutes. If we want to make this lifetime more precise (e.g. 5 to 6 minutes) then we must lower the granularity (e.g. down to 1 minute) and accept more passwords (for T', T'-1, T'-2... to T'-5) which raises the success rate for the attacker (here 1/16666667). There is a trade-off here: more precision implies less security. In my opinion, it is best to keep security high and to tolerate password lifetime to freely vary in the 5-to-10 minutes range.

  Note that this question granularity is precisely the point where security of time-based passwords departs from that of randomly chosen passwords. As explained above, you need to accept N successive passwords for some N (at least 2), and the chances of success for the attacker are N times as much as what he would have for a random password of the same size.

• For multi-frontend systems, the key K must be shared because the server which receives the first request and generates the password is not necessarily the same than the one who receives the second request and must verify the password; but both must use the same key. Also, all frontends must have the same notion of time (use NTP).

• The key K needs not be permanently stored; it is acceptable that it does not survives reboots, since the generated passwords are short-lived anyway. You could generate K when the server starts (this means that a password sent by SMS before the reboot will not be accepted after the reboot, which is probably no big deal). Mind, though, that transient keys can be a hassle with multi-frontend systems (the frontends must somehow use the same key).

• You want to add some guard mechanisms to avoid vandal attacks: people who ask for one million authentications for a given user U. User U does not want to receive one million spurious SMS; and you certainly do not want to pay for the sending of one million SMS (these things ain't free). One possible countermeasure is to use the SMS-based password only as a second authentication step, after having verified the user's principal (non moving) password (or whatever is your first authentication factor in your two-factors system).

Answer 2

Provided you use a cryptographic hash of a concatenation of high-entropy randomly-generated server-side-secret, a timestamp known to the client, along with a username, I don't see a flaw in that method. Granted I would not use an 8-digit number (e.g., 1 in 100 million chance of randomly bypassing) or 8-digit hexadecimal number (1 in ~4 billion chance), but would take the cryptographic hash and convert it to base-36 (lowercase letters plus numbers) (1 in 2 trillion) or base-64 (1 in 100 trillion) and take the first 8 characters (though preferably more characters). Note for base64 it may make sense for UX purposes to sanitize some characters used that are commonly confused; e.g., don't make a user differentiate between a I or l or 1, O or 0 (in a seemingly random string) and possibly strip +, / from base64. You also must make sure that at the screen where the user inputs the OTP that the time_str and user_name are passed back.

Also make sure you compare the time_str in a constant time fashion (otherwise by timing attacks can figure out the token by trial and error) and expire the OTP password if its not in a valid time period. Note, if you worry that a random chance of 1 in 100 trillion to break in is not safe enough, you could additionally track bad login attempts from IP addresses and block them/require CAPTCHAs/rate limit them after about 5 to 10 bad attempts.

Here's some sample python code:

import hashlib
import time
import base64

secret_str = 'pcA2Sh1e2ovxzjcih4OUiGKHBzytB8FaVScTo0iQ'
time_str = str(time.time())
user_name = 'drjimbob'

def get_hash_from_time_username(time_str, user_name):
    hash = hashlib.sha512(secret_str+time_str+user_name).digest()
    b64_hash = base64.b64_encode(hash) 
    # starts as 86 characters long (excluding `=` at end)
    for ch in ['0','O','1','I','l','+','/', '=']:
        b64_hash = b64_hash.replace(ch,'')
    b64_hash = b64_hash[:8] 
    # overwhelming odds roughly ~1 in 10^60 it will be shorter than 8 chars
    if len(b64_hash) < 8: # in very rare exception repeat the hash.
        b64_hash = (b64_hash + b64_hash)[:8]
    return b64_hash

def check_from_time_username(input_one_time_pass, time_str, user_name):
    cur_time = time.time()
    if cur_time < int(time_str): # time_str in future; user changed time_str
        return False
    if cur_time - 3600 > int(time_str): # time_str is more than an hour old
        return False
    if len(input_one_time_pass) < 8:
        return False
    b64_hash = get_hash_from_time_username(time_str, user_name)
    is_ok = 0 
    for i in range(8):
        is_ok += ord(b64_hash[i]) ^ ord(input_one_time_pass[i])
        # bitwise compare to have constant time string comparison
    return is_ok == 0

Answer 3

I recommend that you use a random value. That's the simplest approach. In security, simple is good.

You could use a TOTP, but why bother? (You mention they don't have to be stored in a database, but so what? You have a database; why not use it?) A TOTP solution can be secure too if you implement it properly, but it's more complex and there are more opportunities to make a mistake. Just witness the length of @Thomas Pornin's answer.

Bottom line: KISS. Use a random value.

Answer 4

The method of OTP generation will not matter if you send it over an un-encrypted, insecure channel like SMS. SMS is like outsourced email without the possibility of PGP. See this blog post for a bit of info on that: http://www.wikidsystems.com/WiKIDBlog/another-nail-for-sms-authentication/why-using-sms-for-authentication-is-a-bad-idea