Mysterious Google two step authentication - in debug

• Download source - 6 KB

Introduction 

Have you have enabled your Google account for two step authentication? If not -I strongly recommend to do so.  Do you know the nature of the code generated by Google Authenticator? There are no myths here  - this is just an implementation of RFC6238. And even more - you can add a new level of security to your application very easily without the need to use some monstrous security library. 

I will use PHP in this article - this means that the server side can use this code to validate the client one. But nothing stops you from implementing an OTP generation algorithm in JavaScript.

Background 

Two-step verification drastically reduces the chances of having personal information in your Google account stolen by someone else. Why? Because hackers would have to not only get your password and your username, they'd have to get your personal key used to generate the six-digit combination. 

How is this combination generated? Let's move through the process:

Assume that the secret code in base32 is GEZDGNBVGY3TQOJQGEZDGNBVGY3TQOJQ (this is actually a base32 encoded secret key 12345678901234567890.

Why is base32 and not base64 used? My guess takes into consideration the following points:

1. The resulting character set is all one case (usually represented as uppercase), which can often be beneficial when using a case-insensitive filesystem, spoken speech, or human memory.
2. The alphabet was selected to avoid similar-looking pairs of different symbols, so the strings can be accurately transcribed by hand. (For example, the symbol set omits the symbols for 1, 8, and zero, since they could be confused with the letters 'I', 'B', and 'O'.) 
3. The result can be included in a URL without encoding any characters. 

In other words, the encoded message is much easier to remember than base 64.

The variance of the code is time (to be more precise, it's 30 sec intervals). Bearing in mind that not all devices use NTP to synchronize, we might want to check 3-5 sequential codes to be sure that the right code is entered. The more secure your solution is, the less 30sec intervals you might want to check. 

 Let us take the current Unix Time Stamp: 

UnixTimeStamp (time()/30): 44376117.366667 

and calculate the HOTP - onetime password based on HMAC  (http://en.wikipedia.org/wiki/HOTP).

What do we need to calculate the 6 digit code? Take trunc of the value above - 44376117 and convert to hex 2a52035

Pack to a byte string: 

5(35)
 (20)
¥(a5)
<(2)
 (0)
 (0)
 (0)
 (0) 

If hex string has lesser than 16 characters, pad it from the left using 0 character. 

Decimal representation: 

0 0 0 0 2 165 32 53 

Now calculate sha1 HMAC (Hash-based Message Authentication Code (http://en.wikipedia.org/wiki/HMAС): 

hash_hmac ('sha1', '...<¥ 5...', 12345678901234567890)  
Result:  af2b88048dc8979b528af4e37085061d88aaaaa5   

hash_hmac is a commonly available cryptographic function, you may find it in any cryptographic library or toolkit. 

Let us convert it to a 6 digit sequence:

Step А: convert into hex  array 

Array ( [0] => af [1] => 2b [2] => 88 [3] => 04 [4] => 8d [5] => c8 [6] => 
  97 [7] => 9b [8] => 52 [9] => 8a [10] => f4 [11] => e3 [12] => 70 [13] => 85 [14] => 
  06 [15] => 1d [16] => 88 [17] => aa [18] => aa [19] => a5 ) 

Step B Transform each hex in the array to its decimal form  

Array ( [0] => 175 [1] => 43 [2] => 136 [3] => 4 [4] => 141 [5] => 200 [6] => 
  151 [7] => 155 [8] => 82 [9] => 138 [10] => 244 [11] => 227 [12] => 112 [13] => 
  133 [14] => 6 [15] => 29 [16] => 136 [17] => 170 [18] => 170 [19] => 165 )  

Step C  Take 19th array element (in this case 165)

And perform a bitwise operator & on mask 0xf   - we receive 5 for the current example. 

(hmac_result[offset+0] & 0x7f) << 24 = 200& 0x7f) << 
  24 = 11001000&100100111<< 24 = 1001000 << 24 =1001000000000000000000000000000=1207959552

(hmac_result[offset+1] & 0xff) << 16 = 151& 0xff) << 16 = 10010111&1001010101<<
    16=10111 << 16 = 100101110000000000000000

(hmac_result[offset+2] & 0xff) << 8 = 155& 0xff) << 8 = 10011011&1001010101<< 8=10111
    << 16 = 1001101100000000

(hmac_result[offset+3] & 0xff) = 82& 0xff) = 1010010&1001010101=10111 << 16 =1010010

1001000000000000000000000000000 | 100101110000000000000000 | 1001101100000000 | 1010010 =
1001000100101111001101101010010 = 1217895250 

Step D: Take the result

1217895250 and retrieve the modulus of division on 10 pow length of the needed sequence (for 6 it is 1000000).

Let's divide - we will get 1217.89525, thus modulus is - 895250.  

We are finished with our algorithm: this is the result generated, in particular, by Google Authenticator application: 895250.

Code 

Let's use PHP to implement the algorithm above. 

Required libraries: to simplify the development and not reinvent the wheel, it is always useful to try to find if someone else has implemented it already. For PHP, I have adopted:

• Base32 implementation for PHP by Bryan Ruiz.
• PHP HMAC hash implementation from community feedbacks on http://php.net/manual/ru/function.hash-hmac.php

As a result, a proof of concept implementation of RFC6238 was born: rfc6238.php which contains the helper class TokenAuth6238 with several useful functions. 

Generating a secret 

A secret is used to provide a base for your application and the device generating the code to validate the user's identity. The secret is important and should be transferred over a secured channel. If the attacker will get access to the secret, it's possible to generate the verification code and get around the security procedure.

secret = Base32::encode("yourrandomsecretkey")

Google authenticator

Google provides Android and iPhone applications that generate the verification code for the user.

Install the application and create a new account by entering the code. Name your account as you want and enter the secret generated in the previous step. Choose a time based token.

Now you can see on your smartphone a 6 character long password that allows you to validate the user's identity.

Validating the integrity 

Now that we have the secret and the smartphone is generating the verification code, let's try to validate it.

<?php require_once("rfc6238.php");
$secretkey = 'GEZDGNBVGY3TQOJQGEZDGNBVGY3TQOJQ';  //your secret code
$currentcode = '571427';  //code to validate, for example received from device


if (TokenAuth6238::verify($secretkey,$currentcode))
{
    echo "Code is valid\n";
}
else
{
    echo "Invalid code\n";
} 

Generating the code 

You can also generate the verification code yourself using the library.

print TokenAuth6238::getTokenCodeDebug($secretkey,0); 

Generating the QRCode for GOOGLE Authenticator

You can also generate the image that can be used by the mobile device to configure the authentication program:

print sprintf('<img src="%s"/>',TokenAuth6238::getBarCodeUrl('','',$secretkey)); 

When you run such a script and you put in the correct secret and correct verification code, it will print "Code is valid" or "Invalid code" on the standard output.

Points of interest

Using these few simple steps, you can add an additional validation layer into your authentication process in your application and thus provide higher security for your users.

The mentioned helper class for OTP can be forked at GitHub: https://github.com/Voronenko/PHPOTP.