Blog index

Understanding one-time passwords

I recently spent some time investigating the HOTP (HMAC-based) and TOTP (Time-based) one-time password algorithms. You’re probably relying on one of these algorithms if you’ve enabled two-factor authentication for a service (e.g. GitHub) and are using something like Google Authenticator, Authy or 1Password to generate a 6 digit code when signing in.

I’ve enabled two-factor authentication on quite a few services I use and wanted to understand how the one-time password was being generated. I was surprised to learn quite how simple the algorithms are and thought I’d share what I understand. This post describes how to generate HOTPs in Ruby before moving on to demonstrate how the same code can be used to generate TOTPs.

Generating an HOTP in Ruby

The step numbers (1 to 3) below correspond to the steps in section 5.3 (“Generating an HOTP Value”) of HOTP RFC 4226.

1. Generate an HMAC-SHA-1 value

I’m using the key and a counter from the Test Values in Appendix D of HOTP RFC 4226 so that we can verify the output. In the real world you’d be given the key (often encoded in a QR code) by the site that you’re enabling 2FA for.

The resulting HMAC is a 20 byte (160 bit) string.

require 'openssl'

key = '12345678901234567890'
counter = 5
counter_as_byte_string = [counter].pack('Q>')

digest = OpenSSL::Digest.new('sha1')
hmac = OpenSSL::HMAC.digest(digest, key, counter_as_byte_string)

puts hmac.unpack('H*')
#=> 'a37e783d7b7233c083d4f62926c7a25f238d0316'
# Or as an array
# [0xa3, 0x7e, 0x78, 0x3d, 0x7b, 0x72, 0x33, 0xc0, 0x83, 0xd4,
#  0xf6, 0x29, 0x26, 0xc7, 0xa2, 0x5f, 0x23, 0x8d, 0x03, 0x16]

2. Generate a 4-byte string

2a. Generate the offset

The offset is the number represented by the last 4 bits of the last byte.

offset = hmac.bytes.last & 0x0f
# Equivalent to: 0x16 & 0x0f
# Equals: 0x06
# Or as a decimal: 6

2b. Take 4 bytes starting at the offset

bytes = hmac.bytes[offset..offset + 3]
# Equivalent to: hmac.bytes[6..9]
# Equals: [0x33, 0xc0, 0x83, 0xd4]
# Or as decimals: [51, 192, 131, 212]

2c. Mask the most significant bit of the first byte

To avoid any confusion around signed vs unsigned integers.

bytes[0] = bytes[0] & 0x7f
# Equivalent to: 0x33 & 0x7f
# Equals: 0x33 # No-op in this instance

3. Compute an HOTP value

3a. Convert the 4 bytes into a 32bit integer

There are two implementations below. The first uses bit-shifting and the second (suggested by James) uses Array#pack and String#unpack. While the second implementation is more concise, I’ve retained both as I think the first makes it easier to see what’s going on.

# 1. Bit-shifting
bytes_as_integer = (bytes[0] << 24) + (bytes[1] << 16) + (bytes[2] << 8) + bytes[3]
# Equivalent to: (0x33 << 24) + (0xc0 << 16) + (0x83 << 8) + 0xd4
# or in decimal: (51 * (2**24)) + (192 * (2**16)) + (131 * (2**8)) + 212
# Equals: 855638016 + 12582912 + 33536 + 212
# Equals: 868254676

# 2. Using `Array#pack` and `String#unpack`
bytes_as_integer = bytes.pack('c*').unpack('N')[0]
# Equals: 868254676

3b. Generate OTP

The OTP is the last n digits (6 by default) of the number we’ve generated.

digits = 6
puts bytes_as_integer.modulo(10 ** digits)
# Equivalent to: 868254676.modulo(1_000_000)
#=> 254676

The code in full

require 'openssl'

def generate_otp(key, counter, digits = 6)
  counter_as_byte_string = [counter].pack('Q>')
  digest = OpenSSL::Digest.new('sha1')
  hmac = OpenSSL::HMAC.digest(digest, key, counter_as_byte_string)
  offset = hmac.bytes.last & 0x0f
  bytes = hmac.bytes[offset..offset + 3]
  bytes[0] = bytes[0] & 0x7f
  bytes_as_integer = (bytes[0] << 24) + (bytes[1] << 16) + (bytes[2] << 8) + bytes[3]
  bytes_as_integer.modulo(10 ** digits)
end

otp = generate_otp('12345678901234567890', 5)
puts "OTP: %s" % otp

Generating TOTPs

The TOTP algorithm builds on HOTPs by specifying how the value of the counter should be calculated. This avoids the need to synchronise the counter between the server (e.g. GitHub) and the client (e.g. Authy) as both parties can calculate it in the same way.

The counter specified in the TOTP RFC is the number of 30 second intervals in the current unix time.

We can demonstrate the relationship between TOTPs and HOTPs using oathtool from the OATH Toolkit. We start by generating a TOTP based on the current time and then show that we can generate the same HOTP by using the counter we’re given in the verbose output.

# Generate TOTP for current time
$ oathtool --totp --verbose 3132333435363738393031323334353637383930
Hex secret: 3132333435363738393031323334353637383930
Base32 secret: GEZDGNBVGY3TQOJQGEZDGNBVGY3TQOJQ
Digits: 6
Window size: 0
Step size (seconds): 30
Start time: 1970-01-01 00:00:00 UTC (0)
Current time: 2016-12-21 10:52:10 UTC (1482317530)
Counter: 0x2F1F218 (49410584)

744955

# Generate HOTP using counter above
$ oathtool --hotp --counter 49410584 3132333435363738393031323334353637383930
744955

Note that the key we pass to oathtool above is the hex encoded representation of the example key we’re using in our Ruby script.

'12345678901234567890'.unpack('H*')
=> ["3132333435363738393031323334353637383930"]

Now that we know that the only difference is in the value of the counter we can update our Ruby script to generate TOTPs.

counter = Time.now.to_i / 30 # 30 second intervals in current unix time

otp = generate_otp('12345678901234567890', counter)
puts "OTP: %s" % otp

Assuming we’ve saved the Ruby script as totp.rb, we can use oathtool to verify the generated OTP.

$ ruby totp.rb
662110

$ oathtool --totp 3132333435363738393031323334353637383930
662110

Conclusion

I hope this post helps illustrate how relatively simple these two algorithms are. While the code certainly seems to work, there are no tests and I have no idea about its performance. If you’re looking to use something like this in production then you might want to check out The Ruby One Time Password Library (I’ve not tried this but it seems to have some tests) or the OATH Toolkit mentioned earlier.

After reading a draft of this post, Paul pointed me to this How Google Authenticator Works blog post from a couple of years ago. The author also wanted to understand how these one-time passwords are generated and has described the algorithm in their post. It might be worth reading if this post leaves you with unanswered questions.