Time-based One-time Passwords
Recently I ended up playing with Time-based One-time Passwords as a second factor when authenticating with various services. When I saw an RFC referenced in the references section, I looked at it to get a better idea of how complicated the algorithm really is. It turns out that TOTP is very simple. So simple that I couldn’t help but put together a quick and dirty implementation in Python.
TOTP itself is documented in RFC 6238. It is a rather short RFC, but that’s because all it really says is “use HOTP and feed it these values”.
HOTP is documented in RFC 4226. This RFC is a bit longer since it has to describe how the counter value gets hashed and the resulting digest gets mangled. Reading it, one will learn that the HMAC-SHA1 is the basic building block of HOTP.
HMAC is documented in RFC 2104.
With these three documents (and a working implementation of SHA1), it is possible to implement your own TOTP.
The Key
If you follow those four RFCs, you’ll have a working TOTP. However, that’s not enough to make use of the code. The whole algorithm is predicated on having a pre-shared secret—a key. Typically, the service you are enabling TOTP for will issue you a key and you have to feed it into the algorithm to start generating passwords. Since showing the user the key in binary is not feasible, some sort of encoding is needed.
I couldn’t find any RFC that documents best practices for sharing the key with the user. After a while, I found a Google Authenticator wiki page describing the format of the key URIs used by Google Authenticator.
It turns out that this is a very common format. It uses a base32 encoding with the padding stripped. (Base32 is documented in RFC 4648.)
The “tricky” part is recreating this padding to make the decoder happy. Since base32 works on 40-bit groups (it converts between 5 raw bytes and 8 base-32 chars), we must pad to the nearest 40-bit group.
The Code
I tried to avoid implementing HMAC-SHA1, but I couldn’t find it in any of the modules Python ships with. Since it is a simple enough algorithm, I implemented it as well. Sadly, it nearly doubles the size of the code.
Warning: This is proof-of-concept quality code. Do not use it in production.
import struct import hashlib import base64 import time # The pre-shared secret (base32 encoded): key = "VGMT4NSHA2AWVOR6" def HMAC(k, data, B=64): def H(m): return hashlib.sha1(m).digest() # keys too long get hashed if len(k) > B: k = H(k) # keys too short get padded if len(k) < B: k = k + ("\x00" * (B - len(k))) ikey = "".join([chr(ord(x) ^ 0x36) for x in k]) okey = "".join([chr(ord(x) ^ 0x5c) for x in k]) return H(okey + H(ikey + data)) def hotp(K, C, DIGITS=6): def Truncate(inp): off = ord(inp[19]) & 0xf x = [ord(x) for x in inp[off:(off+4)]] return ((x[0] & 0x7f) << 24) | (x[1] << 16) | (x[2] << 8) | x[3] return Truncate(HMAC(K, struct.pack(">Q", C))) % (10 ** DIGITS) def totp(K, T=time.time(), X=30, T0=0, DIGITS=6): return hotp(K, long(T - T0) / long(X), DIGITS=DIGITS) # pad to the nearest 40-bit group if len(key) % 8 != 0: key=key + ("=" * (8 - (len(key) % 8))) key=base64.b32decode(key.upper()) print time.ctime(), time.time() print "TOTP: %06d" % totp(key)
This code is far from optimal, but I think it nicely demonstrates the simplicity of TOTP.
References
- RFC 2104 — HMAC: Keyed-Hashing for Message Authentication
- RFC 4226 — HOTP: An HMAC-Based One-Time Password Algorithm
- RFC 4648 — The Base16, Base32, and Base64 Data Encodings
- RFC 6238 — TOTP: Time-Based One-Time Password Algorithm
- Google Authenticator wiki