Once upon a time

One-Time-Passwords always fascinated me. Long long time ago in a land far far away I suddenly had this idea. The idea was simple and in today’s terms pretty common, perhaps trivial. One-Time-Password without the need for an extra token. After the user keys in their username and password, they get sent a random password via SMS. Ten years ago there wasn’t anything that did that. I created a basic RADIUS implementation with support for different SMS gateways, all in Java. Sadly however, with no funding, no clue how to turn it into a business, and just finishing my computer science degree, it had to be abandoned for an easier day job.

I was recently pulled into looking at two-factor-authentication (2FA) solutions. I used SecurID at a previous job, and know of several solutions in this area. I was quite pleased to discover many soft-token solutions working on mobile phones (iphone, blackberry, HTC, Nokia) and USB-based ideas like Yubikey. I was even more pleased to discover open source initiatives in this area, and OATH HOTP in particular.

HMAC-based One-Time-Password (HOTP) is reasonably simple to implement. It’s open, free and secure. Perhaps not militrary-grade security, but pretty good security nevertheless. I also must have found half a dozen free HOTP apps for my iphone (I’m using oathtoken), and it seems like there are apps for almost any phone. When coming to implement it on the server though, I felt a little disappointed. There are a couple of pam modules for linux (HOTP toolkit and Barada), but neither seem very stable or widely used.

What about python implementations then?? I was genuinely surprised there were virtually none. I found one, but it seemed rather specific to the Hebrew University and slightly complex. Or maybe I was too lazy to work out what it actually did…

So I then decided to write my own. It’s a very basic implementation, and by no means ‘production ready’, but it seems to work. I tested it against the test vectors on the rfc, and with my oathtoken iphone app, and it seems to match. I even implemented TOTP, a time-based variant instead of counter based – and that worked too!

UPDATE: code on github


#!/usr/bin/env python
"""
OATH HOTP + TOTP Implementation in python.

Based on http://tools.ietf.org/html/rfc4226

Parameter and function names kept inline with the RFC
(e.g. HOTP, Truncate, K, C etc)
"""

import hmac
import hashlib
import array
import time
import unittest


def HOTP(K, C, digits=6):
    """
    HOTP accepts key K and counter C
    optional digits parameter can control the response length

    returns the OATH integer code with {digits} length
    """
    C_bytes = _long_to_byte_array(C)
    hmac_sha1 = hmac.new(key=K, msg=C_bytes,
                         digestmod=hashlib.sha1).hexdigest()
    return Truncate(hmac_sha1)[-digits:]


def TOTP(K, digits=6, window=30):
    """
    TOTP is a time-based variant of HOTP.
    It accepts only key K, since the counter is derived from the current time
    optional digits parameter can control the response length
    optional window parameter controls the time window in seconds

    returns the OATH integer code with {digits} length
    """
    C = long(time.time() / window)
    return HOTP(K, C, digits=digits)


def Truncate(hmac_sha1):
    """
    Truncate represents the function that converts an HMAC-SHA-1
    value into an HOTP value as defined in Section 5.3.
    http://tools.ietf.org/html/rfc4226#section-5.3
    """
    offset = int(hmac_sha1[-1], 16)
    binary = int(hmac_sha1[(offset * 2):((offset * 2) + 8)], 16) & 0x7fffffff
    return str(binary)


def _long_to_byte_array(long_num):
    """
    helper function to convert a long number into a byte array
    """
    byte_array = array.array('B')
    for i in reversed(range(0, 8)):
        byte_array.insert(0, long_num & 0xff)
        long_num >>= 8
    return byte_array


class HotpTest(unittest.TestCase):
    """
    a very simple test case for HOTP.
    Based on test vectors from http://www.ietf.org/rfc/rfc4226.txt
    """
    def setUp(self):
        self.key_string = '12345678901234567890'

    def test_hotp_vectors(self):
        hotp_result_vector = [755224, 287082, 359152,
                              969429, 338314, 254676,
                              287922, 162583, 399871,
                              520489, 060613]
        for i in range(0, 10):
            self.assertEquals(HOTP(self.key_string, i),
                              str(hotp_result_vector[i]))

    def test_totp(self):
        """
        a simple test for TOTP.
        since TOTP depends on the time window, we cannot predict the value.
        However, if we execute it several times, we should expect the
        same response most of the time.
        We only expect the value to change
        once or not at all within a reasonable time window.
        """
        value = TOTP(self.key_string, digits=8, window=20)
        value_changes = 0  # counting the number of changes to TOTP value
        for i in range(0, 100000):
            new_totp = TOTP(self.key_string, digits=8, window=20)
            if new_totp != value:
                value_changes += 1
                value = new_totp
        self.assertTrue(value_changes <= 1)

if __name__ == '__main__':
    unittest.main()

4 Responses to “Once upon a time”

  1. Lyndsy Simon

    I am working on implemented TOTP-based 2FA on a website project, and just completed a review of the Python packages available these days.

    I ended up settling on “oath”: http://pypi.python.org/pypi/oath/

    It seems to be fully-featured, and even allows you to specify a clock drift, which is quite handy.

  2. Yoav Aner

    Hi Lyndsy,

    Yeah. It looks quite comprehensive and robust. In 2010 when I wrote the post/code, this implementation didn’t exist. In fact, virtually no python implementation existed, hence why I implemented this.

    I only later posted it on github just to allow easier changes and discussion. It’s by no means the best implementation, and I nearly haven’t touched it at all since. I’m still quite pleased at the relative simplicity of the implementation that still meets the specifications pretty well (even if not every possible edge-case of it).

    I think simplicity and clarity is the major strength of OATH as a specification, and I’d like to think one of the main reasons for its relative widespread adoption.

    Cheers
    Yoav

  3. Ray

    It is easy to get the TOTP from your API, and it’s weight maybe lighter than package Pyotp.

    But may I ask you a basic concept about the relationship between key(token shared secret) and the algorithm of hash?

    Well, according to the test value from RFC6238, I do not really understand why we should define three(sha-1, sha-256, sha-512) key strings? for example, why we can not use the same key_string_sha1 to test sha-1, sha-256, and sha-512? I mean, it is a strict requirement for key length and algorithm of hash(like 64 bytes -> sha-512)?

    By the way, if I have a original key(32 char), I need to get its TOTP(by sha-512), should I change its length? In fact, I can not get the correct TOTP change or not…I sure other parameters are OK. Thanks

    Best wish,
    Ray

  4. Yoav Aner

    Hi Ray,

    I’m not a crypto expert, and to be honest I got confused by this thing as well. In principle, the key size can be anything and there’s no connection between the key and the hashing implementation (SHA-1, SHA-256 etc). The RFC states that the key is “12345678901234567890”, but in practice, the test vectors fail for SHA-256 and SHA-512. Through some trial and error I realised that the key was actually extended for each case for some strange reason…

    Apparently I’m not the only one who picked up on it. E.g. https://github.com/hackedd/php-oath/commit/db052d0c4d88ef95ca302d20d75fb17664e0d5f6#diff-fb669e338d1ba1a8b5fe528032c490e1R11

    EDIT: found an errata that writes about this https://www.rfc-editor.org/errata_search.php?rfc=6238

    For any practical purpose, use whatever key meets your security requirements. Just bear in mind that whatever hash you choose, the overall security can only be as strong as your key.

    Hope this helps!

    Cheers,
    Yoav

Leave a Reply

css.php