How Google Authenticator works

Introduction

Today’s we will learn how Google Authenticator App algorithm works. The code here is in C# but you can adapt to any language. There are many copies of the algorithm but hard to find one which really works in all aspects, right from the OTP generation to the QR code generation which the Google Authenticator App can read correctly. We’ll learn how 2FA (Two-factor authentication) works, specifically the TOTP (Time based OTP) algorithm.

Goal

Goal is to make you understand in the simplest terms how the Google Authenticator App algorithm works. You can manipulate the algorithm to write your own. I was a bit curious as to what goes behind the App and how the 2FA works. So here it is.

Pre-requisites

  1. QR code generator code or service which the Google Authenticator App can ready correctly.
  2. Piece of code to generate Base32 string of a given string.
  3. Read about how arrays and numbers are stored in Little Endian and Big Endian format in memory.
  4. Visual Studio console application project or Visual Studio Code targeting minimum .Net framework 4.6 or greater. I’ve uploaded a Visual Studio 2019 console application code at the bottom.
  5. Determine the maximum number of digits you want in the OTP.
  6. Determine for how many seconds do you want the OTP to remain valid.

Background and Foundation

This algorithm is based on the standard IETF – RFC6238. This IETF document describes the Java implementation but you can find many flavours of C#, Javascript and other language implementations.

Funny part is that the IETF code does not say anything about the Big Endian format conversion of timestamp (below). I broke my head a lot to find that out. It also does not talk clearly about Base32 encoding of the secret key. It cleanly talks about converting the secret to a Hex string and converting it to a byte array. By following the steps in the IETF code, you will get an OTP value but it will not work with the Google Authenticator App. You can use the IETF code for your own 2FA implementation.

There are many different ways you can implement 2FA, but here we’ll focus on Google Authenticator App implementation. We’ll implement the code compliant with the standard but the explanations will be in simplest terms. I’ll also post a link to the JavaScript version, which also has a working copy online for you to test out.

Note of caution: Google Authenticator App uses a weaker implementation of the RFC6238 standard. You need to be aware of this. I’ll explain this point later down. Check the Wikipedia Pitfalls section. It has already been cracked here via Hashcat tools.

Steps of the algorithm

  1. The secret (string) which is shared between the client (you) and the Server application.
  2. Get the Base32 encoded string of the secret.
  3. Get total number of milliseconds that have passed since the Unix Epoch (which is January 1, 1970 at 00:00:00 GMT). Let this be TotalMilliseconds.
  4. Since we want the OTP to be valid for 30 seconds, we will divide the TotalMilliseconds in the previous step with 30000. If you want the OTP to be valid for say 60 seconds, divide by 60000. In this sample, we’ll stick to 30 seconds validity since Google Authenticator also does the same. We’ll call this value as TimeStamp.
  5. Convert the TimeStamp value to a byte array and reverse the byte array since the algorithm assumes Big Endian storage format. Since .Net or more specifically Intel processors store arrays in Little Endian format, we need to convert the array into Big Endian format. This is basically just reversing the storage order of each element of the array. ARM processors these days can support both the Endian formats.
  6. Initialize the .Net cryptography class HMACSHA1 with the secret. This secret will be used as a key to encrypt the data to SHA-1 format. Of course you can use SHA-256 or SHA-512 depending on your needs. We are using SHA-1 since that is what Google uses.
  7. Compute the HASH by passing the TimeStamp as the data that needs to be encrypted.
  8. Apply the Bitwise and shift operators to get an integer value.
  9. We want the length of the OTP to 6 digits. So we divide the integer value in the previous step with 10 raise to the power of 6. If you want 4 or 8 digits of OTP, divide by 10 raise to the power of 4 or 8 respectively.
  10. Done! The value you get in the previous step is the OTP and is valid for 30 seconds or for the RemainingSeconds.

Jump into code

Important note: Focus mainly on the GenerateOTP method. The rest of the methods are supplementary. The steps described above match the GenerateOTP method.

  1. Get the secret from the Server application. The Server application may provide you with a QR Code and also a secret string along with the QR code. To make things simple grab the secret string from the server application and paste it in the secret variable.
  2. Set the lengthOfOTP variable to 6. You can set it to 4 or 8 or any number you want. I haven’t tried more than 8 :). You need to check out the maximum value.
  3. The timestamp variable contains the total milliseconds that have passed since Unix Epoc. Keep in mind that this line DateTimeOffset.Now.ToUnixTimeMilliseconds() will only work from .Net framework 4.6 on wards. If you want an equivalent version of this line meant to run for framework versions before .Net 4.6, refer this.
  4. Convert the timestamp value to a byte array and reverse the array to a Big Endian format and store it in data variable. Important note: Keep in mind that you have to pad the byte array with ZEROs for all the preceding elements which are empty. This converted byte array will have 16 elements. Inside the GetBigEndianBytes method, the BitConverter.GetBytes method pads the trailing empty elements with 0 (zero). So when you reverse this array, the preceding empty elements become padded with zero.
  5. Convert the secret to a Base32 string and convert it onto a byte array and store it in bytes variable.
  6. Create a new instance of HMACSHA1 class and pass bytes (variable) as a key for encryption.
  7. Use the data variable and pass to ComputeHash method and get the computed Hash byte array into hmacValue variable. Important note: This array has 20 elements. So the Hash computed is 160 bits (20 * 8). Google uses 80 bits here. So is weaker in implementation. But we are using full 160 bits here, since it is recommended by the standard.
  8. Apply the Bitwise and Binaryshift operators to the various values from the offset. This part of the code was taken directly from the standard’s site – IETF – RFC6238 and get a integer value into code variable.
  9. Take the modulo value of the code variable and Math.Pow(10, lengthOfOTP)
  10. Hurray! The resultant number is your OTP which will be valid for 30 seconds. I’ve written a small C# console application which will display the seconds remaining for the OTP to expire.
  11. Sometimes the OTP value in this case will be 4 or 5 digits. Don’t worry, it is a valid OTP and will run fine in your application which uses Google Authenticator.
  12. Wrap all the method below in a class called Program.
private static void GenerateOTP()
{
	int lengthOfOTP = 6;
	string secret = "2MG4RSHZ7SLM3QDLOBV433QA5B";
	var timestamp = DateTimeOffset.Now.ToUnixTimeMilliseconds() / 30000;
	var data = GetBigEndianBytes(timestamp);
	var bytes = Base32Encoding.ToBytes(secret);

	HMACSHA1 aa = new HMACSHA1(bytes); // key to encrypt
	byte[] hmacValue = aa.ComputeHash(data);

    //The offset will vary if used with HMACSHA256, HMACSHA384 or HMACSHA512 classes
	int offset = hmacValue[hmacValue.Length - 1] & 0xf; 
	int code = ((hmacValue[offset] & 0x7f) << 24) |
				 ((hmacValue[offset + 1] & 0xff) << 16) |
				 ((hmacValue[offset + 2] & 0xff) << 8) |
				 (hmacValue[offset + 3] & 0xff);

	double num = (double)code % Math.Pow(10, lengthOfOTP);
	Console.WriteLine(num.ToString());
}

static void Main(string[] args)
{
	GenerateOTP();

	Console.WriteLine("Remaining seconds");
	int end = RemainingSeconds();
	for (int i = 0; i < end; ++i)
	{
		Console.Write("\r{0}  ", RemainingSeconds());
		Thread.Sleep(1000);
	}

	Console.WriteLine("\r\nRegenerate OTP. Restart program.");
	Console.ReadLine();
}

public static int RemainingSeconds()
{
	int step = 30;
	return step - (int)((DateTimeOffset.Now.ToUnixTimeMilliseconds() / 1000) % step);
}

private static byte[] GetBigEndianBytes(long input)
{
	var data = BitConverter.GetBytes(input);
	Array.Reverse(data);
	return data;
}

You will also need to add this class which converts a string to Base32 encoded string. This was taken from one of the Stackoverflow’s answer.

//https://stackoverflow.com/questions/641361/base32-decoding   (Shane's answer)
public static class Base32Encoding
{
	public static byte[] ToBytes(string input)
	{
		if (string.IsNullOrEmpty(input))
		{
			throw new ArgumentNullException("input");
		}

		input = input.TrimEnd('='); //remove padding characters
		int byteCount = input.Length * 5 / 8; //this must be TRUNCATED
		byte[] returnArray = new byte[byteCount];

		byte curByte = 0, bitsRemaining = 8;
		int mask = 0, arrayIndex = 0;

		foreach (char c in input)
		{
			int cValue = CharToValue(c);

			if (bitsRemaining > 5)
			{
				mask = cValue << (bitsRemaining - 5);
				curByte = (byte)(curByte | mask);
				bitsRemaining -= 5;
			}
			else
			{
				mask = cValue >> (5 - bitsRemaining);
				curByte = (byte)(curByte | mask);
				returnArray[arrayIndex++] = curByte;
				curByte = (byte)(cValue << (3 + bitsRemaining));
				bitsRemaining += 3;
			}
		}

		//if we didn't end with a full byte
		if (arrayIndex != byteCount)
		{
			returnArray[arrayIndex] = curByte;
		}

		return returnArray;
	}

	public static string ToString(byte[] input)
	{
		if (input == null || input.Length == 0)
		{
			throw new ArgumentNullException("input");
		}

		int charCount = (int)Math.Ceiling(input.Length / 5d) * 8;
		char[] returnArray = new char[charCount];

		byte nextChar = 0, bitsRemaining = 5;
		int arrayIndex = 0;

		foreach (byte b in input)
		{
			nextChar = (byte)(nextChar | (b >> (8 - bitsRemaining)));
			returnArray[arrayIndex++] = ValueToChar(nextChar);

			if (bitsRemaining < 4)
			{
				nextChar = (byte)((b >> (3 - bitsRemaining)) & 31);
				returnArray[arrayIndex++] = ValueToChar(nextChar);
				bitsRemaining += 5;
			}

			bitsRemaining -= 3;
			nextChar = (byte)((b << bitsRemaining) & 31);
		}

		//if we didn't end with a full char
		if (arrayIndex != charCount)
		{
			returnArray[arrayIndex++] = ValueToChar(nextChar);
			while (arrayIndex != charCount) returnArray[arrayIndex++] = '='; //padding
		}

		return new string(returnArray);
	}

	private static int CharToValue(char c)
	{
		int value = (int)c;

		//65-90 == uppercase letters
		if (value < 91 && value > 64)
		{
			return value - 65;
		}
		//50-55 == numbers 2-7
		if (value < 56 && value > 49)
		{
			return value - 24;
		}
		//97-122 == lowercase letters
		if (value < 123 && value > 96)
		{
			return value - 97;
		}

		throw new ArgumentException("Character is not a Base32 character.", "c");
	}

	private static char ValueToChar(byte b)
	{
		if (b < 26)
		{
			return (char)(b + 65);
		}

		if (b < 32)
		{
			return (char)(b + 24);
		}

		throw new ArgumentException("Byte is not a value Base32 value.", "b");
	}

}

Conclusion

Hope this helped you learn how the 2FA works in Google Authenticator app. This was the simplest overview I could come up with. If you have question, then fire a mail to code@onezeroeight.co

Acknowledgements

This blog was made possible by a number of blogs and stack overflow answers. Here are the acknowledgements.

  1. Here, IETF – RFC6238 and this.
  2. The Google Authenticator source code.

Additional resources

  1. Wonderful Javascript resource for the above code implementation. Also has a JsFiddle hosted working sample online.
  2. You can download the source files from here. This is a Visual Studio 2019 console app (.net 4.7.2 version).
  3. To generate your QR code from the secret which the Google Authenticator App can read correctly. Just replace the highlighted (blue) part with your secret string.
    https://chart.googleapis.com/chart?chs=200x200&cht=qr&chl=200x200&chld=M|0&cht=qr&chl=otpauth://totp/code@onezeroeight.co%3Fsecret%3D2MG4RSHZ7SLM3QDLOBV433QA5B
  4. Embed the image in previous step into your web application. Google Authenticator App will read this QR code correctly. You can replace code@onezeroeight.co with your own application text.
  5. Another fantastic explanation on QR code generation in C# – here. I also tried a different NuGet package, but the QR codes generated in both the cases are not recognizable in Google Authenticator. Yet to figure this out. The formats look different but needs to be worked out for them to be readable in the App.

Update:

Figured out another way to generate QR code which Google Authenticator App can read. You can download the source code from this link which was given above. Run the QRCodeEncoder solution. Keep in mind that this QR code solution needs .net framework 4.6.2. On the form it asks you to enter a string to be encoded into a QR code. Keep other parameters default. Paste this string:

otpauth://totp/code@onezeroeight.co?secret=2MG4RSHZ7SLM3QDLOBV433QA5B

Replace your secret string with the text marked in blue above. Again, you can replace code@onezeroeight.co with your own application text. The resultant QR code you get will be readable in Google Authenticator App.

Use the above library if you want to explore how QR codes are generated and decoded. For other folks who directly want to generate QR code there are plenty of resources like this. Enter the above text after replacing the secret string in the Free Text section and you are done!

Feel free to share this link via:

1,031 Responses

  1. Hola! I’ve been reading your weblog for some time now and finally got the bravery to go ahead and give you a shout out from Kingwood Tx! Just wanted to mention keep up the great job!

  2. We absolutely love your blog and find a lot of your post’s to be exactly I’m looking for. Would you offer guest writers to write content for you? I wouldn’t mind composing a post or elaborating on most of the subjects you write regarding here. Again, awesome blog!

  3. Howdy, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of spam comments? If so how do you reduce it, any plugin or anything you can suggest? I get so much lately it’s driving me insane so any assistance is very much appreciated.

  4. I wanted to type a quick remark to be able to appreciate you for all of the awesome ideas you are sharing on this website. My extended internet search has now been honored with beneficial strategies to exchange with my best friends. I ‘d tell you that most of us website visitors are definitely fortunate to exist in a superb site with many marvellous people with great techniques. I feel very privileged to have encountered the web site and look forward to so many more thrilling moments reading here. Thank you again for everything.

Leave a Reply

Your email address will not be published. Required fields are marked *

Enter Captcha Here : *

Reload Image