Have you ever used AWS Multi-Factor Authentication? Have you ever received a text containing a 6-digit authorisation code for some important action? Does your bank require you to have a little Authorisation Device that gives you a fresh 6-digit number every 30 seconds?

If so, then chances are the number shown on that device or in that text, used the HOTP algorithm to generate and securely verify that message. It's an algorithm that, since it's publication in December 2005, seems to have become the defacto standard for generating and verifying One-Time Passwords.

In this post I'll be going over the structure of the algorithm, the key concepts and underlying technology, then we'll implement our very own HOTP authentication device and use it with a real-life service.

A Primer on HMAC

HMAC is an algorithm for generating a Message Authentication Code, MAC. Think of it like your traditional checksum, but with the added benefit of ensuring both integrity and authenticity. Integrity, meaning the message hasn't been changed. Authenticity, meaning the source of the message is verified. These integrity and authenticity are verified by regenerating the MAC and comparing it to the sent version. Generating the MAC relies on sharing the same secret key, which means that before the algorithm can be used the secret key has to be shared between correspondents.

HMAC uses a cryptographic hash function, in combination with a secret key, to generate the Message Authentication Code. While, HMAC algorithms can use any cryptographic hash function, the strength of the HMAC depends upon which underlying hash function is used. While the implementation and theory behind HMAC's is very interesting, it's a bit beyond the scope of this post. For further reading see the wiki page, which includes a handful of implementations. For our purposes the standard python HMAC module will be fine for implementing our HMAC-based One-Time-Passwords.

Python HMAC

The Python standard library comes with a HMAC module that implements an RFC2104 compliant interface. It's incredibly simple to use:

import hmac

# Our Secret key
SECRET_KEY = "asdf7{123;(!asdf"
MESSAGE = "This is the message to verify"

hm = hmac.new(SECRET_KEY, MESSAGE)
print hm.digest()

Which will give us this (reproducible) output:

4\xde\xfbap\x97\xa5z\x00\xc6Ye\x95K{\x83

We can use the encode method of the returned string to represent the bytes returned in our preferred encoding, e.g. hex, or base64.

HMAC codes are usually created with the intention of comparing them, while standard python a == b comparison could be made, doing so leaves the analysis vulnerable to timing attacks. The HMAC module provides a method to securely compare two digest results.

import hmac

# Our Secret key
SECRET_KEY = "asdf7{123;(!asdf"
MESSAGE = "This is the message to verify"

# Our expected result
expected = '4\xde\xfbap\x97\xa5z\x00\xc6Ye\x95K{\x83'

hm = hmac.new(SECRET_KEY, MESSAGE)
actual = hm.digest()

print 'Valid Message? ', hmac.compare_digest(expected, actual)

By default, Python HMAC uses the MD5 hashing algorithm, but, we can switch it out by passing the cryptographic hash function we want to use as the third argument to hmac.new. We'll be using the SHA1 algorithm, like so:

import hmac
import hashlib

hm = hmac.new(SECRET_KEY, MESSAGE, hashlib.sha1)

One Time Passwords

There are a number of open standards that describe One time password algorithms. The original S/KEY or Lamport's Scheme which was originally developed to authenticate users into a unix-like system from untrusted terminals. S/KEY has served as the basic model for a variety of proprietary one time password schemes, which are and have been in use in many large companies. OTP algorithms secure things like bank accounts, VPN access, email access and are increasingly used in two-factor or multi-factor authentication schemes.

What we're going to do in this article is produce a python CLI tool that allows us to generate one time passwords; then we'll test our implementation against a real authentication provider.

The Implementation

Setup

First things first, lets setup our project. Things we need:

  • Virtual Env,
  • git
  • Directories,
  • setup.py
  • __init__.py

I'm going to assume you're familiar with virtual environments and git; if not check google for git tutorials, and the virtualenv tool has documentation.

On to Setting up the project directory. I'm going to call my tool heimdall; but, I guess you can feel free to pick any fictional or non-fictional character that personifies security, watchfulness, and protection. So, create our top level project directory, and add our heimdall package, then add the __init__.py file.

Which will give you a layout like this:

+-- heimdall
    |
    +-- heimdall
    |    |
    |    +-- __init__.py
    |
    +-- setup.py

Now, for the setup.py I use this sample as a starting point for my scripts - because it's got a sprinkling of comments that means I don't have to re-read the setup.py documentation. Again.

$ curl https://raw.githubusercontent.com/pypa/sampleproject/master/setup.py > setup.py

Ok, first things first - How do we want to use our soon to be written tool? In order to generate a valid HOTP, we just need the secret key; so our only usage (for now) will be to get an One-Time-Password:

heimdall <secret-key>

This obviously isn't ideal in terms of security (leaving our super-secret-key in the bash history), and usability (requiring it each time), but it's just for demonstration purposes for now, so we won't worry too much.

We'll need to trim down setup.py, how exactly you choose to do this is up to you. The only part that should effect the rest of the code in this post is entry_points:

# To provide executable scripts, use entry points in preference to the
# "scripts" keyword. Entry points provide cross-platform support and allow
# pip to create the appropriate form of executable for the target platform.
entry_points={
    'console_scripts': [
        'heimdall=heimdall:main',
    ],
},

All it says is I'm going to be calling a main function, located in the heimdall python module, not much else too it.

To support our usage above, I'm using the argparse module - because it's included in py2.7 - So the main method looks like this:

def main():
    '''
        Main entry point for our script.
    '''

    parser = argparse.ArgumentParser(
        description='Heimdall HOTP Generator.'
    )

    parser.add_argument(
        'secret_key',
        help='Base32 encoded secret key'
    )

    parser.add_argument(
        ['--encoding', '-e'],
        help='Secret key encoding',
        dest='encoding',
        default='base32',
        choices=['base32', 'raw', 'base64']
    )

    args = parser.parse_args()

    secret_key = None

    if args.encoding is 'base32':
        secret_key = base64.b32decode(
            args.secret_key
        )

    elif args.encoding is 'base64':
        secret_key = base64.b64decode(
            args.secret_key
        )

    elif args.encoding is 'raw':
        secret_key = args.secret_key

    print "%d" % get_hotp(secret_key, get_counter())

    exit(0)

Our main method needs to accept input in a couple of different encodings, because our secrets shouldn't be limited, we'll assume base32 as a sane default as it's relatively common in the wild.

The Algorithm

The HOTP algorithm is described by this marvellously simple formula:

HTOP(K, C) = Truncate(HMAC-SHA1(K, C))

In english: we take the output of our HMAC, given a secret key and an 8-byte counter value, and truncate it to the desired length output.

As long as our secret key is correctly and securely shared, and both parties use the same counter variable, we will always be able to generate and verify a secure one time password. The simplicity of this formula is entirely intentional, this algorithm was intended to run in all manner of devices, from full computers and smart phones, to little more than battery powered 6-character LED screens, even embedded in smart cards. But, for all it's simplicity the underlying HMAC algorithm makes taking any number of one-time passwords and rebuilding the secret key a difficult problem to solve. You could generate billions of passwords and still never successfully work it backwards.

The Truncate Function

The truncate function in the formula above is designed to take the 160 character output from the HMAC function and turn it into a six-digit zero padded code. It does this by taking the output of the hash function, applying a process it calls dynamic truncation.

def truncate(hsh, n=6):
    '''
    Truncate the hash into a six digit OTP. hash is
    assumed to be an array of bytes.
    '''
    # Grab our last byte, the value of the
    # lower 4 bits used as the offset value
    # to determine the starting point of our slice
    offset = hsh[-1] & 0xf

    # Starting with our offset byte, take successive bytes.
    #
    # We mask our 4 bytes (32-bits), against a 31-bit mask.
    # Resulting in an unsigned 31-bit integer.
    binvalue = \
        (hsh[offset] & 0x7f) << 24 \
        | (hsh[offset+1] & 0xff) << 16 \
        | (hsh[offset+2] & 0xff) << 8 \
        | (hsh[offset+3] & 0xff)

    # Take our binary value and mod it by
    # 10^{digits} to get our n-digit code
    return binvalue % (10 ** n)

The Truncate function is the most complex part of the underlying algorithm.

The truncate function uses the last byte of the HMAC digest to determine the starting point for a 4-byte slice. That slice defines a 32-bit integer value, that is then masked to return a 31-bit unsigned number.

An unfortunate side effect of this truncation is that it decouples the secure hash value from the actual password value, this is going to happen with any truncation, however the intention of this method is to give equal chance to all the bytes in the hash towards contributing to the final password.

To illustrate, imagine if we just took the bottom 4 bytes:

binvalue = \
    (hsh[0] & 0x7f) << 24 \
        | (hsh[1] & 0xff) << 16 \
        | (hsh[2] & 0xff) << 8 \
        | (hsh[3] & 0xff)

This is a much simpler algorithm. However, let's say we didn't trust our hash function, lets assume we had a weaker hash function or some horrific weakness was discovered in SHA1. Now, because our truncate function is only looking at the bottom 4-bytes we've potentially made ourselves vulnerable to Chosen-prefix collision attacks, making our hash less secure.

But, what about the Avalanche Effect? Surely, if we just use the top 4-bytes we'll be protected against this chosen-prefix attack, right? Well, it would certainly be a better algorithm to use than the naive one above. However, ultimately the cryptographic strength of the passwords being generated depends on the strength of our underlying hash. If it's not as strong as we initially anticipated, we will have to change it; the truncation method is an attempt to avoid this fact by increasing the reliance on different parts of the hash to try and draw in as much of the underlying pseudo-randomness of the hash as possible. Rather than a static patch of bytes, it takes it's starting point from the hash itself.

The Counter Value

RFC 6238 called Time-Based One-Time Password Algorithm (TOTP), is an extension to the original HOTP algorithm allowing a simple way for clients and servers to maintain the same counter value. The algorithm it employs to do this is mind-bending, and horrendously complex, so I've simplified it down some:

(Current Unix time) / 30

Just kidding. It literally says, default to using the unix epoch broken into 30 second segments. However, the language in RFC indicates that the UNIX epoch value above, could be substituted for a counter starting at any time, and it as long as it is communicated to the client, it really doesn't matter what value we pick. The full formula defined in the TOTP RFC is:

T = (Current Unix time - T0) / X

Where T0 is our starting counter value, X is the step we're using - in most cases 30 seconds.

The RFC also specifies that type used for our T value must a larger-than a 32-bit integer, so as to be effective past the year 2038. For more details, take a look at the Year 2038 Problem. It's just like y2k, but for unix time.

The Code

Now we have a reasonable understanding of our algorithm, we can code it up. We'll take our truncate function from above, write up a short method to get the counter variable as per the TOTP spec, and the get_hotp method to pull it all together.

def truncate(hsh, n=6):
    '''
    Truncate the hash into a six digit OTP. hash is
    assumed to be an array of bytes.
    '''
    # Grab our last byte, the value of the
    # lower 4 bits used as the offset value
    # to determine the
    offset = hsh[-1] & 0xf

    # Starting with our offset byte, take successive bytes.
    #
    # We mask our 4 bytes (32-bits), agaist a 31-bit mask.
    # Resulting in an unsigned 31-bit integer.
    binvalue = \
        (hsh[offset] & 0x7f) << 24 \
        | (hsh[offset+1] & 0xff) << 16 \
        | (hsh[offset+2] & 0xff) << 8 \
        | (hsh[offset+3] & 0xff)

    # Take our binary value and mod it by
    # 10^{digits}
    return binvalue % (10 ** n)


def get_counter(t0=0):
    '''
        Get a counter value as per RFC 6238
    '''
    return (int(time.time()) - t0) / 30


def get_hotp(secret_key, counter):
    '''
        Retrieve a HOTP
    '''
    msg = struct.pack('>Q', counter)
    hm = hmac.new(secret_key, msg, hashlib.sha1)
    hsh = array.array('B', hm.digest())

    return truncate(hsh)

Couple things to note. First, is the conversion of our counter value from a python int to an 8-byte array. This conversion important because the ascii (or any string encoding) representation of the number will be significantly different to the pure byte representation. Second, we convert our hmac digest into a byte array for our truncate method to use the example implementation given by the HOTP spec - there are a couple other ways to do this but we may as well follow the spec.

Sweet. So, now we can generate HMAC-based One-Time-Passwords, the next step is checking if they're legit. To make sure our HOTP's are correct, we could write unit tests (and we should). However, it's so much more exciting to try out our code with something real world. For this, I'm going to use my AWS account and turn on Multi-Factor Authentication for logins. Details on turning it on available here. As part of the process of turning it on, you need to provide 2 HOTPs, so, if our code actually works, and we generate 2 OTPs amazon will do the boring testing for us.

Note: This is a pretty terrible testing methodology, but it's a bit more real-world than unit testing.

So, fire up the AWS console, go to the IAM service and find the MFA button. In the "Manage MFA Device" dialog you want to select "a Virtual MFA Device" . The next step will show you a very pretty QR code. We can't decode QR codes, so click the little "Show secret key for manual configuration" arrow and copy that secret key. If you want to be sure you don't accidentally lock yourself out of your AWS account somehow, stop now - go download the Google Authenticator app and setup an actual MFA device using the QR code.

Once you've copied your secret, head back to your terminal and run this:

$ heimdall <your-secret-key>
324854

The 6-digit code you get back will of course be different to the above. Stick the first code in the first box and wait about 30s. Running it again should give you a new 6-digit code:

$ heimdall <your-secret-key>
631196

Stick the second code in and click "Activate". If everything has gone according to plan, you won't have to wait too long, you'll see another dialog saying: "The MFA device was successfully associated", and that's that. To turn it off, simply click "Manage MFA Device" and then click "Deactivate MFA Device".

Prologue

The wikipedia article for SHA1 indicates that the hash function is theoretically vulnerable to hash collisions after 2^61 operations, that number looks like this:

2,305,843,009,213,693,952

Or:

Two quintillion,
three hundred five quadrillion,
eight hundred forty-three trillion,
nine billion,
two hundred thirteen million,
six hundred ninety-three thousand,
nine hundred fifty-two.

Which was just fun to type out.