Using Time-Based One-Time Passwords for Multi-Factor Authentication in AD FS 3.0

I often get the question if it is possible in AD FS 3.0 to use the Google Authenticator as the second factor for authentication. When we read the documentation for the Google Authenticator, we find that this product is actually based on two RFC's. One of these is RFC6238; a Time-Based One-Time Password (TOTP) Algorithm. This algorithm is actually not only used in Google's Authenticator, but also in the Microsoft Verificator, and potentially in many other time-based authenticators. This means that if we were able to implement TOTP as a multi-factor authentication provider in AD FS, we could use any of the verificator apps out there, and we wouldn't have to create our own! RFC6238 references another RFC; RFC4226. Where RFC4226 describes the mechanism to create a code out of a secret key using some HMAC algorithm ("HOTP: An HMAC-Based One-Time Password Algorithm"), RFC6238 adds the time-based component to the code ("TOTP: Time-Based One-Time Password Algorithm").

TOTP is based on a secret key, shared between the server and the client. Using this key, codes are generated. The generation of the TOTP codes also involves a time component; by doing this, the generated code is only valid for a limited amount of time. (According to RFC6238, by default, 30 seconds.) Next to that, there are some additional requirements, perhaps not imposed by the RFC's themselves, but maybe by Google's implementation or simple user friendliness.

What we will create

We will create a Multi-Factor Authentication Provider for AD FS 3.0 that adheres to these requirements;

- Implement a Time-Based One-Time Password for MFA in AD FS 3.0.
- The secret key is a 16-character key using [A-Z][2-7] (due to Base32 Encoding).
- Generated codes are 6 characters long and only contain numbers.
- Generated codes are valid for 30 seconds.
- Implement some time tolerance (client and server might not have the exact same time).
- Codes cannot be used more than once.
- Configure the Authenticator app using a QR Code.
- Adhere to the (encryption) protocols in the RFC6238 and, hence, RFC4226.

- Should work with the Google Authenticator App and the Microsoft Verificator App and potentially other apps that implement TOTP based on RFC6238.

Creating Secret Keys, Intervals and Codes

First, we need to be able to generate the 16-character secret key consisting of the characters that are allowed. The RFC dictates; "The keys SHOULD be randomly generated or derived using key derivation algorithms." We will use the Random function in the .NET framework to accomplish this.

 public static string GenerateSecretKey()
{
      Random random = new Random((int)DateTime.Now.Ticks & 0x0000FFFF);
      return new string((new char[secretKeyLength]).Select(c => c = allowedCharacters[random.Next(0, allowedCharacters.Length)]).ToArray());
}

In this snippet, allowedCharacters is a string containing the characters that are allowed in the secret key, and it's defined elsewhere in the code.

To generate codes that are valid for X seconds, the RFC dictates that we should count the number of X second intervals from the Unix Epoch (1970-1-1):

"X represents the time step in seconds (default value X = 30 seconds) and is a system parameter."
"T0 is the Unix time to start counting time steps (default value is 0, i.e., the Unix epoch) and is also a system parameter."

By default, we will use intervals of 30 seconds.

 private static long GetInterval(DateTime dateTime)
{
      TimeSpan elapsedTime = dateTime.ToUniversalTime() - unixEpoch;
      return (long)elapsedTime.TotalSeconds / validityPeriodSeconds;
}

In this snippet, unixEpoch is defined elsewhere as DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc).

Using the Secret Key and the Interval, we can generate the TOTP code. The code can't be longer than 6 numeric characters, we'll simply truncate it if it turns up longer. If it's shorter, we will prepend it with 0's. According to RFC4226 we have to use Base32 encoding, and we will use SHA1 for the HMAC key. (I won't bother you with the details, read the RFC if you're interested in this stuff. The RFC contains sample code in what I think is Java, but this my .NET translation of that code.)

 private static string GetCode(string secretKey, long timeIndex)
{
    var secretKeyBytes = Base32Encode(secretKey);
    HMACSHA1 hmac = new HMACSHA1(secretKeyBytes);
    byte[] challenge = BitConverter.GetBytes(timeIndex);
    if (BitConverter.IsLittleEndian) Array.Reverse(challenge);
    byte[] hash = hmac.ComputeHash(challenge);
    int offset = hash[19] & 0xf;
    int truncatedHash = hash[offset] & 0x7f;
    for (int i = 1; i < 4; i++)
    {
        truncatedHash <<= 8;
        truncatedHash |= hash[offset + i] & 0xff;
    }
    truncatedHash %= 1000000;
    return truncatedHash.ToString("D6");
}

private static byte[] Base32Encode(string source)
{
    var bits = source.ToUpper().ToCharArray().Select(c =>
        Convert.ToString(allowedCharacters.IndexOf(c), 2).PadLeft(5, '0')).Aggregate((a, b) => a + b);
    return Enumerable.Range(0, bits.Length / 8).Select(i => Convert.ToByte(bits.Substring(i * 8, 8), 2)).ToArray();
}

We can now generate a secret key, calculate the proper interval starting 1970-1-1 and create a 6-character TOTP code.

Validating Codes

We now need to be able to validate code entered by a client. Since the client and the server might not have the exact same time, and transferring the code from the clients machine to the server might take "some" time, chances are that the client is presenting the server with "the previous code" or "the next code" (from the server's perspective). So when we validate the TOTP code provided by the client, we must also validate if the code presented perhaps is the previous or the next code. Therefore we will implement a configurable future- and past-tolerance. This tolerance is implement by means of past- and future intervals. Remember that 1 interval, by default, is 30 seconds. (From the RFC: "We RECOMMEND that at most one time step is allowed as the network delay. ")

Another thing we need to take into account when validating the codes, is that a code for a specific user can only be used once. Once a user has used the code has to successfully authenticate, the same code cannot be used again. The hard part, from an AD FS MFA perspective, is to check whether or not the code has been used previously. Since you might have multiple AD FS servers in a farm, and these servers do not share state, we cannot use in-memory lists or other objects to check if a code has been used previously. The easiest way to get this check accomplished is by using a database that all servers in the AD FS farm can access and use to store and check used keys. This is also the mechanism I chose to implement. Here is the SQL script for the database that I'm using in my sample.

 USE [master]
GO

CREATE DATABASE [TOTPAuthentication]
 CONTAINMENT = NONE
 ON  PRIMARY 
( NAME = N'TOTPAuthentication', FILENAME = N'https://storageaccount.blob.core.windows.net/container/TOTPAuthentication.mdf' , SIZE = 1048576KB , MAXSIZE = UNLIMITED, FILEGROWTH = 1024KB )
 LOG ON 
( NAME = N'TOTPAuthentication_log', FILENAME = N'https://storageaccount.blob.core.windows.net/container/TOTPAuthentication_log.ldf' , SIZE = 1048576KB , MAXSIZE = 1073741824KB , FILEGROWTH = 10%)
GO

USE [TOTPAuthentication]
GO

CREATE TABLE [dbo].[Secrets](
    [upn] [varchar](255) NOT NULL,
    [secret] [char](16) NOT NULL,
 CONSTRAINT [PK_Secrets] PRIMARY KEY CLUSTERED 
(
    [upn] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

CREATE TABLE [dbo].[UsedCodes](
    [upn] [varchar](255) NOT NULL,
    [interval] [bigint] NOT NULL
) ON [PRIMARY]

GO

The method to validate the codes could look something like this;

 private static bool CheckCode(string secretKey, string code, string upn, DateTime when)
{
    long currentInterval = GetInterval(when);
    bool success = false;
    for (long timeIndex = currentInterval - pastIntervals; timeIndex <= currentInterval + futureIntervals; timeIndex++)
    {
        string intervalCode = GetCode(secretKey, timeIndex);
        bool intervalCodeHasBeenUsed = CodeIsUsed(upn, timeIndex);
        if (!intervalCodeHasBeenUsed && ConstantTimeEquals(intervalCode, code))
        {
            success = true;
            SetUsedCode(upn, timeIndex);
            break;
        }
    }
    return success;
}

In the snippet, you see that we use a configurable tolerance; pastIntervals and futureIntervals. We now need to implement the "CodeIsUsed" method to check whether the code has been previously used or not. Of course, after a successful authentication we would also have to indicate that the code has been used; SetUsedCode. Last, I want to point out to you the ConstantTimeEquals method. We could simple do "a.Equals(b)" or "a == b" or something like that, but apparently some hackers would then be able to find out where in the process the codes are different, to finally hack the code. (https://codahale.com/a-lesson-in-timing-attacks/) You could just use "a == b", but if you want to, here is the code for the Constant Time Equals operation;

 protected static bool ConstantTimeEquals(string a, string b)
{
    uint diff = (uint)a.Length ^ (uint)b.Length;
    for (int i = 0; i < a.Length && i < b.Length; i++)
    {
        diff |= (uint)a[i] ^ (uint)b[i];
    }
    return diff == 0;
}

We are pretty much done. We only now need to tie a secret key to a user. I have chosen to store the secret keys in a database. I could use Active Directory for that, but due to possible replication latency and permissions issues I have chose not to use that.

Putting it all together

Now that we have all to code to create a secret key, to create a time-based code and to validate it, it's time to combine all the components into the AD FS Multi-Factor Authentication provider. I have chosen to implement this MFA in the following manner;

The first time the user is required to use MFA, and uses the TOTP MFA Provider, a secret key is generated. Using the QR Code "generator" from Google, I will show the user the correct QR code. The user uses this QR code to configure the application. This is shown ONLY ONCE. The key is then stored in the database. If the user should lose the application, or phone, delete the key from the database and the next time the user logs on, he will get a new secret key and a new QR code. (For a taste of the QR code; click here.)

After the initial setup, the secret key from the database will be used to validate the codes from the client.

Now, using the same methodology I described earlier here, or the methodology described on MSDN, we can create our MFA Provider for AD FS 3.0. You can download the whole C# project here. You will have to create the proper reference to the AD FS DLL, create a database and configure the proper SQL Connection String. After compilation, copy it to the AD FS servers in the farm, add the DLL to the Global Assembly Cache and register the MFA provider. (Not sure how to do that? Check the references I pointed out to you!)

Good luck! I've tested the solution with the Microsoft Verificator App, some "random" Google Authenticator Apps for Windows Phone and some for Windows. I don't own an iPhone, iPad or Android device. So if you have tried this solution with any of those devices and apps; please let me know how that worked!

Some key things to take into account before you start using this codebase for your own authentication provider:

Safety

This code has not been created with safety in mind. Think about encrypting the location where secret keys are stored.

Stability

No proper error handling has been implement. This could severely impact the working of the AD FS farm.

Support

This is only Proof-of-Concept code. This code is NOT SUPPORTED by me or Microsoft in any way, shape or form.

 # THIS CODE AND ANY ASSOCIATED INFORMATION ARE PROVIDED “AS IS” WITHOUT
# WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT
# LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS
# FOR A PARTICULAR PURPOSE. THE ENTIRE RISK OF USE, INABILITY TO USE, OR 
# RESULTS FROM THE USE OF THIS CODE REMAINS WITH THE USER.