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 is also 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 will still run fine in Google Authenticator and is a valid OTP.
  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/user@host.com%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.

Feel free to share this link via:

63 Responses

  1. Cesar Hsun says:

    I always spent my half an hour to read this webpage’s content all the time along with a mug of coffee.|

  2. These are genuinely enormous ideas in regarding blogging. You have touched some pleasant points here. Any way keep up wrinting.|

  3. I like what you guys tend to be up too. This type of clever work and coverage! Keep up the wonderful works guys I’ve incorporated you guys to blogroll.|

  4. We are a bunch of volunteers and starting a brand new scheme in our community. Your web site offered us with helpful info to work on. You have done an impressive activity and our entire group can be thankful to you.|

  5. My partner and I absolutely love your blog and find many of your post’s to be what precisely I’m looking for. Do you offer guest writers to write content for you personally? I wouldn’t mind writing a post or elaborating on many of the subjects you write with regards to here. Again, awesome blog!|

  6. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your weblog? My blog is in the very same area of interest as yours and my users would truly benefit from a lot of the information you provide here. Please let me know if this okay with you. Thanks!|

    • himanshu says:

      Yes! absolutely fine. I have no intentions to monetize my blogs. Feel free to quote from my blogs and give credit.

  7. WOW just what I was looking for. Came here by searching for keyword|

  8. whoah this weblog is magnificent i love studying your articles. Stay up the great work! You know, lots of persons are searching round for this information, you can aid them greatly. |

  9. My family every time say that I am killing my time here at web, except I know I am getting familiarity all the time by reading such fastidious articles.|

  10. Awesome blog! Do you have any hints for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally overwhelmed .. Any recommendations? Many thanks!|

  11. I all the time emailed this weblog post page to all my associates, since if like to read it afterward my links will too.|

  12. Appreciating the commitment you put into your website and detailed information you present. It’s great to come across a blog every once in a while that isn’t the same old rehashed material. Great read! I’ve saved your site and I’m adding your RSS feeds to my Google account.|

  13. I was suggested this web site by my cousin. I’m not sure whether this post is written by him as nobody else know such detailed about my trouble. You’re amazing! Thanks!|

  14. Can you tell us more about this? I’d care to find out some additional information.|

  15. Thanks in favor of sharing such a fastidious opinion, article is fastidious, thats why i have read it completely|

  16. Very descriptive post, I enjoyed that bit. Will there be a part 2?|

  17. Can I simply just say what a comfort to uncover somebody that truly understands what they’re discussing on the net. You actually realize how to bring an issue to light and make it important. More and more people need to look at this and understand this side of your story. I was surprised that you’re not more popular because you certainly have the gift.|

  18. Thanks for one’s marvelous posting! I really enjoyed reading it, you might be a great author.I will always bookmark your blog and will often come back down the road. I want to encourage yourself to continue your great writing, have a nice morning!|

  19. Now I am going to do my breakfast, once having my breakfast coming over again to read further news.|

  20. I’ve learn a few excellent stuff here. Certainly price bookmarking for revisiting. I wonder how much effort you place to make this sort of great informative web site.|

  21. I read this paragraph completely regarding the resemblance of most recent and preceding technologies, it’s awesome article.|

  22. I will right away seize your rss as I can’t to find your email subscription hyperlink or e-newsletter service. Do you have any? Please let me recognize so that I may just subscribe. Thanks.|

    • himanshu says:

      Thank you! I have no plans to start an email subscription service or store any emails. If I might start in future, will let you know.

  23. Ned Hoke says:

    I know this web page offers quality based content and other stuff, is there any other web site which offers such data in quality?|

  24. fantastic publish, very informative. I wonder why the other specialists of this sector do not understand this. You must proceed your writing. I am sure, you have a great readers’ base already!|

  25. Interesting blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my blog stand out. Please let me know where you got your theme. Thank you|

  26. Jed Vella says:

    Link exchange is nothing else however it is simply placing the other person’s weblog link on your page at appropriate place and other person will also do similar in support of you.|

  27. Its like you read my mind! You appear to know so much about this, like you wrote the book in it or something. I think that you could do with some pics to drive the message home a bit, but instead of that, this is excellent blog. A fantastic read. I’ll definitely be back.|

  28. Louie Siu says:

    Very good post! We are linking to this great article on our site. Keep up the great writing.|

  29. Thank you for any other informative blog. Where else may I get that kind of information written in such a perfect method? I have a venture that I’m simply now operating on, and I have been on the glance out for such information.|

  30. Usually I don’t learn post on blogs, but I would like to say that this write-up very pressured me to try and do it! Your writing taste has been surprised me. Thank you, very nice article.|

  31. Wonderful beat ! I wish to apprentice while you amend your website, how can i subscribe for a blog website? The account aided me a acceptable deal. I had been a little bit acquainted of this your broadcast provided bright clear idea|

  32. This excellent website truly has all the info I wanted concerning this subject and didn’t know who to ask. |

  33. Neat blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my blog stand out. Please let me know where you got your theme. Appreciate it|

  34. Hello there! I could have sworn I’ve visited this website before but after going through some of the posts I realized it’s new to me. Anyhow, I’m definitely happy I came across it and I’ll be bookmarking it and checking back frequently!|

  35. John Rhone says:

    I was able to find good info from your content.|

  36. Hi there, I would like to subscribe for this website to get newest updates, thus where can i do it please help.|

    • himanshu says:

      Thank you! I have no intention to start a newsletter right now since I dont collect any emails. If maybe in future, I’ll let you know.

  37. Nice replies in return of this difficulty with firm arguments and explaining all about that.|

  38. Please let me know if you’re looking for a writer for your site. You have some really good posts and I think I would be a good asset. If you ever want to take some of the load off, I’d really like to write some articles for your blog in exchange for a link back to mine. Please blast me an email if interested. Cheers!|

  39. You have made some good points there. I looked on the web for more info about the issue and found most individuals will go along with your views on this web site.|

  40. I love reading a post that can make men and women think. Also, thank you for permitting me to comment!|

  41. I needed to thank you for this wonderful read!! I absolutely loved every little bit of it. I’ve got you book marked to check out new stuff you post…|

  42. Fantastic website. A lot of helpful info here. I’m sending it to some pals ans additionally sharing in delicious. And of course, thanks on your effort!|

  43. My developer is trying to convince me to move to .net from PHP. I have always disliked the idea because of the expenses. But he’s tryiong none the less. I’ve been using WordPress on various websites for about a year and am concerned about switching to another platform. I have heard very good things about blogengine.net. Is there a way I can import all my wordpress posts into it? Any kind of help would be greatly appreciated!|

  44. There’s certainly a lot to know about this subject. I love all of the points you’ve made.|

  45. I’ve been surfing on-line greater than three hours these days, but I by no means found any interesting article like yours.
    It is pretty worth sufficient for me. In my opinion, if
    all site owners and bloggers made just right content as you did, the internet will probably be
    much more helpful than ever before.

  46. This design is wicked! You obviously know how to keep
    a reader entertained. Between your wit and your videos, I was almost moved to start
    my own blog (well, almost…HaHa!) Fantastic job. I really enjoyed
    what you had to say, and more than that, how you presented it.
    Too cool!

  47. Aw, this was a really good post. Taking a few minutes and actual effort to produce
    a really good article… but what can I say… I procrastinate a whole lot and don’t
    manage to get nearly anything done.

    My webpage; MelodiFOsnoe

  48. With havin so much written content do you ever run into any issues of plagorism or copyright infringement? My site has a lot of unique content I’ve either written myself or outsourced but it appears a lot of it is popping it up all over the internet without my agreement. Do you know any techniques to help protect against content from being stolen? I’d certainly appreciate it.|

  49. Ahaa, its pleasant dialogue concerning this article here at this blog, I have read
    all that, so at this time me also commenting here.

  50. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get four emails with the same comment. Is there any way you can remove me from that service? Appreciate it!|

    • himanshu says:

      If you have selected ‘subscribe to emails’ for comments by mistake, then in the email notification, you will get a link to unsubscribe. Hope this helps.

  51. Hi, all the time i used to check website posts here early in the break of day, as i enjoy to find out more and more.|

  52. It’s difficult to get knowledgeable people in this subject, but
    you sound like you know what you’re speaking about! Thanks

    my blog coin purse insert

Leave a Reply

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