The code behind Google Authenticator

Implementing Time-base One-Time Passwords in Pharo

As a programmer I was curious how Google Authenticator, an iOS or Andriod mobile app used to implement two-factor authentication (2FA), really worked and how I could implement it myself. Since it is a lot of fun to experiment with and implement this kind of stuff in Pharo, I decided to give it a try.

Note: source code access instructions can be found at the end.

Screenshot showing Pharo computing the Google Authenticator code

Turns out that Google Authenticator is an implementation of something called ‘Time-base One-Time Passwords’ (TOTP). This is a standard algorithm specified in RFC 6238 (TOTP: Time-Based One-Time Password Algorithm) & RFC 4226 (HOTP: An HMAC-Based One-Time Password Algorithm). Additionally, Base32 encoding is used to represent keys.

Usage

Google Authenticator is used to improve username/password authentication by requiring one time passwords generated from a previously shared secret.

On the server side initialization starts with the generation of a new shared secret.

GoogleAuthenticator new
  randomSecret.

Next we send #base32Secret to this object to turn the secret into a more human friendly form.

'HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ'

Next this secret is shared with the client (this is often done using a QR code).

On the client side, initialization starts based on the shared secret.

GoogleAuthenticator new 
  base32Secret: 'HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ'.

One time passwords are computed by sending #next or #nextPadded.

The server asks the client to provide the next one time password. The client uses his instance to compute it and informs the server of it. The server then does the same computation to validate the one time password.

In the example shown in the screenshot above, the code is 672812.

Obviously, client & server clocks must be synchronized. One time passwords remain valid for a period of 30 seconds. The message #timeRemaining tells you how far along we are in the current period.

Here is a functional unit test in commented example style for the interaction we just described.

GoogleAuthenticatorTests>>testClientServer
 | server sharedSecret client |
 “Server side an authenticator is set up, 
  initialized with a secret”
 server := GoogleAuthenticator new.
 server randomSecret.
 “The shared secret is exchanged 
  between the server and the client”
 sharedSecret := server base32Secret.
 “The client sets up its authenticator, 
  initialized wit the shared secret”
 client := GoogleAuthenticator new.
 client base32Secret: sharedSecret.
 “Make sure we’re not too close 
  to the end of the current period”
 client timeRemaining < 2 ifTrue: [ 2 seconds wait ].
 “From now on, both are in sync, 
  generating the same one time passwords”
 self assert: client next equals: server next.
 self assert: client next equals: server next

Algorithm

Let’s explore the actual computation taking place from known initial values as seen in the following unit test.

GoogleAuthenticatorTests>>testSimple
 | time secret authenticator |
 time := 1478167454.
 secret := 'HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ'.
 authenticator := GoogleAuthenticator new.
 authenticator base32Secret: secret.
 authenticator time: time.
 self assert: authenticator nextPadded equals: '488676'.

Google Authenticator uses the following parameters:

• SHA1 HMAC
• 80 bit (10 byte) key/secret
• 64 bit (8 byte) time based message size
• 6 digit code length
• 30 seconds period
• external key/secret representation in Base32

TOTP does a computation based on 2 values: a key/secret and a time value.

Here the key/secret, externally represented (Base32 encoded) is the string ‘HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ’. First we have to decode it.

Base32Encoder new
  decode: 'HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ'.

This gives us the byte array #[61 198 202 164 130 74 109 40 135 103 178 51 30 32 180 49 102 203 133 217] (or in hex 3DC6CAA4824A6D288767B2331E20B43166CB85D9).

For the time value the Unix time is used, integer divided by the period. In our example, we’re using a fixed value, 1478167454 (corresponding to 2016–11–03T10:04:14Z).

1478167454 // 30.

The result, 49272248, is then converted to a byte array of size 8.

49272248 asByteArrayOfSize: 8.

This conversion gives us #[0 0 0 0 2 239 213 184] (or in hex 0000000002EFD5B8).

Now, the key/secret and the time based message are used to compute a SHA1 HMAC digest. This crypto algorithm is a standard part of Pharo.

(HMAC on: SHA1)
 key: #[61 198 202 164 130 74 109 40 135 103
        178 51 30 32 180 49 102 203 133 217];
 digestMessage: #[0 0 0 0 2 239 213 184].

This results in the following digest: #[127 67 212 219 236 88 54 168 158 177 36 112 177 244 112 88 224 169 130 215] (or in hex 7F43D4DBEC5836A89EB12470B1F47058E0A982D7).

Next, the RFC describes a way to convert (or truncate) this 20 byte array into a 32-bit integer. The first half byte (nibble) of the last of these 20 bytes is used as an offset to select 4 consecutive bytes. These 4 bytes are then converted to an integer, of which the top bit is cleared.

#[127 67 212 219 236 88 54 168 158 177
   36 112 177 244 112 88 224 169 130 215]
  last bitAnd: 16rF.

This gives us 7 as offset. As Pharo uses 1-based array indexing we add 1.

#[127 67 212 219 236 88 54 168 158 177
   36 112 177 244 112 88 224 169 130 215]
  copyFrom: 8 to: 11.

The 4 byte sub array is thus #[168 158 177 36] (hex A89EB124). Now we can apply the last truncation step.

#[168 158 177 36] asInteger bitAt: 32 put: 0. 

This gives us 681488676. The final step is to reduce this number to the required code length, 6.

681488676 \\ 1e6.

And so we finally arrive at 488676, the correct TOTP value !

Note: you can find a shared Smalltalk workspace containing all of the above code at http://ws.stfx.eu/QNWPLH9KNHV7

Source Code

The fully documented source code with unit tests can be found on SmalltalkHub in a project called GoogleAuthenticator. You can load it with the following expression:

Gofer it
 smalltalkhubUser: 'SvenVanCaekenberghe' 
          project: 'GoogleAuthenticator';
 package: 'GoogleAuthenticator';
 load.

This project also contains the source code and tests of Base32Encoder.