Wednesday, December 21, 2011

Google Authenticator: Using It With Your Own Java Authentication Server

The Google Authenticator application for mobile devices is a very handy application that implements the TOTP algorithm (specified in RFC 6238). Using Google Authenticator you can generate time passwords that can be used to authorize users in an authentication server that shares the secret key of the requesting users.

Google Authenticator is mainly used to access Google services using two-factor authentication. However, you can take advantage of Google Authenticator to generate time based password to be authenticated by a server of yours. The implementation of such a server is pretty simple in Java and you can get some inspiration getting the source code of the Google Authenticator PAM module. In this blog post, we will go through a simple implementation of the TOTP algorithm in a Java class.

Generating the Secret Key.

To generate the secret key we will use a random number generator to fill up a byte array of the required size. In this case, we want:
  • A 16 characters Base32 encoded secret key: since Base32 encoding of x bytes generate 8x/5 characters, we will use 10 bytes for the secret key.
  • Some scratch codes (using Google's jargon).

// Allocating the buffer
byte[] buffer =
  new byte[secretSize + numOfScratchCodes * scratchCodeSie];

// Filling the buffer with random numbers.
// Notice: you want to reuse the same random generator
// while generating larger random number sequences.
new Random().nextBytes(buffer);

Now we want to extract the bytes corresponding to the secret key and encode it using the Base32 encoding. I'm using the Apache Common Codec library to get a codec implementation:

// Getting the key and converting it to Base32
Base32 codec = new Base32();
byte[] secretKey = Arrays.copyOf(buffer, secretSize);
byte[] bEncodedKey = codec.encode(secretKey);
String encodedKey = new String(bEncodedKey);

Loading the Key Into Google Authenticator

You can manually load the key into Google Authenticator, or generate a QR barcode to have the application loading it from it. If you want to generate a QR barcode using Google services, you can generate the corresponding URL with a code such as this:

public static String getQRBarcodeURL(
  String user,
  String host,
  String secret) {
  String format = "https://www.google.com/chart?chs=200x200&chld=M%%7C0&cht=qr&chl=otpauth://totp/%s@%s%%3Fsecret%%3D%s";
  return String.format(format, user, host, secret);
}

Verifying a Code

Now that we've generated the key and our users can load them into their Google Authenticator application, we need the code required to verify the generated verification codes. Here's a Java implementation of the algorithm specified in the RFC 6238:


private static boolean check_code(
  String secret,
  long code,
  long t)
    throws NoSuchAlgorithmException,
      InvalidKeyException {
  Base32 codec = new Base32();
  byte[] decodedKey = codec.decode(secret);

  // Window is used to check codes generated in the near past.
  // You can use this value to tune how far you're willing to go. 
  int window = 3;
  for (int i = -window; i <= window; ++i) {
    long hash = verify_code(decodedKey, t + i);

    if (hash == code) {
      return true;
    }
  }

  // The validation code is invalid.
  return false;
}

private static int verify_code(
  byte[] key,
  long t)
  throws NoSuchAlgorithmException,
    InvalidKeyException {
  byte[] data = new byte[8];
  long value = t;
  for (int i = 8; i-- > 0; value >>>= 8) {
    data[i] = (byte) value;
  }

  SecretKeySpec signKey = new SecretKeySpec(key, "HmacSHA1");
  Mac mac = Mac.getInstance("HmacSHA1");
  mac.init(signKey);
  byte[] hash = mac.doFinal(data);

  int offset = hash[20 - 1] & 0xF;
  
  // We're using a long because Java hasn't got unsigned int.
  long truncatedHash = 0;
  for (int i = 0; i < 4; ++i) {
    truncatedHash <<= 8;
    // We are dealing with signed bytes:
    // we just keep the first byte.
    truncatedHash |= (hash[offset + i] & 0xFF);
  }

  truncatedHash &= 0x7FFFFFFF;
  truncatedHash %= 1000000;

  return (int) truncatedHash;
}

The t parameter of the check_code method and verify_code methods "is an integer and represents the number of time steps between the initial counter time t0 and the current Unix time." (RFC 6238, p. 3) The default size of a time step is 30 seconds, and it's the value that Google Authenticator uses too. Therefore, t can be calculated in Java as

t = new Date().getTime() / TimeUnit.SECONDS.toMillis(30);

Download the Library

A ready to use library can be downloaded from GitHub, where Mr. Warren Strange kindly started a repository with the code from this post and packaged it in a Maven project. The library contains a complete implementation of the server-side code, better documentation and some example code in the test cases.

Conclusion

You can now use the Google Authenticator applications and use it to generate time based passwords for your users, authenticated against your own authentication server.

As you can see, the required code is pretty simple and all of the required cryptographic functions are provided by the runtime itself. The only nuisance is dealing with signed types in Java.

Enjoy!

22 comments:

Strange Brew said...

Hi Enrico

Thanks so much for this!

Using your sample, I put together a small project on github that may useful to others:

https://github.com/wstrange/GoogleAuth

Grey said...

Hi.

Thank you very much for doing that, I'm really glad it helped you.

Bye

Emre Baran said...

This is very helpful! Thank you.

How would I extract/see what the scratch codes are?

David Molloy said...

Thanks to both of you for this - it's proven very useful for me to get this going.

By the way, creating a hyperlink using the generated Google Charts link may cause some HTTP 400 Malformed errors and the image may not load up. They will work pasting in the browser but not as an img src link (probably some redirects going on)

To fix this, simply change www.google.com in the url generation code to chart.googleapis.com

Enrico Maria Crisostomo said...

Thank you very much to point this out!

Nick H said...

Hi Enrico,

Thanks for posting your code - I wondered what sort of license you publish this code under? Specifically, would it be okay to make use of it within a non-opensource project?

Thanks again, and to Mr Strange for putting it together into a Maven project.

Enrico Maria Crisostomo said...

Hi Nick,

You're welcome.

I made no reference about a license for the code published in this blog post (and in practically all the others) mainly because my goal was the code being illustrative.

On my part, please feel free to use the code in your project and I'm really, really glad you asked. If you want, you can put a mention in the source file. Nobody will ever se it, but nonetheless it's a memento. :)

Cheers,
-- Enrico

Jay said...

Hi Grey / wstrange

Many thanks for the great effort.
I tried your code and it works fine.

Can you please clarify this ?
In my mobile 'Google Authenticator' apps I registered the the generated QR code.
And when I tried to test the authTest() method by invoking it continuously it returned true even after that code expired and I see a new code on my mobile. I tried continuously until 5 different codes were generated. It works fine with the initial code.

I am confused. I thought it should work only till that code is valid and displayed in my mobile. ?

Thanks
Jay

Enrico Maria Crisostomo said...

Hi Jay.

As you can see in the code shown in the post, the verifyCode method is invoked in a loop whose purpose is verifying a code in a time window of size 6: 2 * window and window equals 3. That's why the code is valid even though the authenticator application is shown the next one.

Why this behaviour? Because a code generated by a client wouldn't pass the server validation unless the clock of the server and the client are synchronised within a very small error (much smaller than one minute). The code above validates a code if it's one of the codes which are generated in a 6 minutes "tolerance window" centred in the current time: [-3, 3]. You can adjust the size of the tolerance window by setting the window parameter to another value.

Hope this helps,
-- Enrico

carlgo11 said...

I followed this example but the verify-code I enter is never the correct one according to the output. :/

Enrico Maria Crisostomo said...

Which window size are you testing with? Keep into account that the code changes over time and if the two clocks are skewed, then the code won't be the same when calculated at the same instant. That's why the code is usually checked over a time window.

carlgo11 said...

the window int? It's set to 3 as it is in the example.

Enrico Maria Crisostomo said...

To keep thing simple and the jargon as well: in that loop you increase the coordinate of the "time period" on which you calculate the code. If we use a period of 30 seconds, you're checking 1 minute and a half in the past and 1 minute and a half in the future. Check your clock skew and see whether it's bigger than that. If it is, either you synchronise them or you raise the window size. The former is the better option between the two.

carlgo11 said...

Yeah I changed it to 1000 but it still didn't work (plus I think it took like 10 sec or so to enter the code). I made 2 pastebins with my code, http://pastebin.com/s6xxCg3R & http://pastebin.com/aZdtVamd
The first one verifies the code and the second one outputs a QR barcode link.

Really appreciate your help, I've tried to get this working for a week now :/

Enrico Maria Crisostomo said...

You're welcome. Which value are you passing to the t parameter or the check_code method? I suspect you're not passing the correct time_period. Google uses a 30-seconds period, so that you must take the UNIX time in milliseconds, divide it by 30.000 (the size of a 30-second window in milliseconds) and use that value as t.

carlgo11 said...

Right now it's on 100. What should I set it to if I want uhm let's say a 1 minute time frame?

Enrico Maria Crisostomo said...

1 minute means window size == 2. I believe, as I said, your problem may be t. Try to set t to new Date().getTime() / 30000 when you invoke check_code.

carlgo11 said...

wow that worked! Thank you so much! You literally saved my day :D

Enrico Maria Crisostomo said...

I'm really glad that it helped. By the way, this made me realise that the blog post assumes that people know what the aforementioned RFC says. I'll correct it and add further information so that nobody else gets stuck on this issue.

Anonymous said...

Really nice tutorial. Thanks alot.

Skip Walker said...

How are the scratch codes work/are supposed to work? I can't find a lot of good information on how they work.
I see that they are supposed to be used in some manner to gain access if the MFA is lost or broken. However, I can't really find how

I see that they are generated in a some complicated manner. What I don't see is why that is done, and then what one does with them after they are generated. The credentials repository is passed the scratch codes, ostensibly to store them.

Is the idea that when a MFA is lost or broken, the user is provided an alternate link, where they verify a scratch code? Once the scratch code is verified, do we reset the MFA so they can set up a new one?

Enrico Maria Crisostomo said...

Hi Skip,

Scratch codes are emergency passwords you can use to log into your account, for example when you can't use the Google Authenticator application for some reason. If and how to use them is up to your backend. You could ignore them or allow each of them once (as Google does), etc. Google, in fact, suggests you print them and take them with you in case Google Authenticator is inaccessible (you lost the phone) even temporarily (the battery is dead).

The credential repository is passed the scratch codes because they indeed are passwords, but as I said the policy is yours.

Hope this helps,
-- Enrico