Exploring Time-based One Time Password

Have you ever wondered how Google Authenticator works? Or ever wondered how the bank could use a token to generate a password (this password changes continuously over time) and users could use this password to log into the banking system. The mystery is that this token is a tiny device, consuming a very little power and has no connection to the internet, how can this device generate a password that can be authenticated by the bank server system?

Diagram

Description

1. The server generates a random number S for each user

2. The user will store S in his mobile app as a secret value.

   1. For Google Authenticator, this is done through scanning a QR code

   2. For bank tokens, this number will be set up for each specific user each time it is allocated to the user

3. On the client's device (Mobile App or token) there will be a clock activated and the server will record this time as T0.

4. After every period of time T (normally 30s), a new password Px will be generated.

A Simple Online Demo

Details

Here's the simple Px creation process: (be noted that all the calculations here are kept simple for ease of illustration)
At time Tx, a password will be generated based on the value of S and the change of a counter value Cx. The Cx is calculated as follows:

Cx = (Tx-T0)/T; // where T is the time the password is re-generated.

From there, Px is the password generated at time Tx calculated by:

//999983 is a prime number
// to make sure the password will be 6 digit long
Px = (S^Cx) % 999983;

In practice, the HMAC is used to generate the Px, the pseudocode is as followed:

S = xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
secret = BASE32_DECODE(TO_UPPERCASE(REMOVE_SPACES(S)))
Cx = (Tx - T0) / T
hmac = SHA1(secret + SHA1(S + Cx))
ar_bytes = hmac[LAST_BYTE(hmac):LAST_BYTE(hmac) + 4]
big_int = INT(ar_bytes)
Px = big_int % 1,000,000