HOTP et TOTP

Cet article présente les algorithmes crypto HOTP et TOTP.

Exemples de support matériel ou logiciel utilisant les protocoles HOTP et TOTP.

Associés à un code pin, on obtiendra une authentification forte.

Définition authentification forte :

• L’utilisation de 2 facteurs d’authentification parmi les 3 cités ci-dessous.
  • Ce que je sais.
    • Un mot de passe, un code pin
  • Ce que je possède.
    • Un support matériel. Token,smartphone,smartcard …
  • Ce que je suis.
    • Une empreinte biométrique

One Time Pasword : Mot de passe à usage unique.

2 variantes d’otp :

Le totp :

• Le Time-based One Time Password (Time Based Tokens)
• Basé sur le temps

Le hotp :

• Le Hmac-based One Time Password (Event Based Tokens)
• Basé sur un compteur

Les algorithmes sont identiques. Seul le type de compteur change. TOTP est basé sur HOTP :

Pour hotp :

• Le compteur est un compteur de type incrémentiel
  0, 1 , 2 , 3 etc …

Pour totp

• Le compteur est un compteur basé sur le temps (epoch Posix)
• Pour mesurer le temps, il faut choisir une origine :
  • L’origine de l’heure POSIX a été choisie comme étant le 1er janvier 1970 00:00:00 UTC
  • Cette date correspond à l’heure 0 de Posix
  • Elle est appelée l’epoch Posix (et également epoch Unix).

Exemple en python

import time
int(time.time())

Retourne le nombre de secondes depuis le 1er janvier 1970 00:00:00 UTC

K est la clef secrète (clef partagée)
TC est le compteur de temps

Etape 1 :

Génération d’un HMAC-SHA1

HMAC(K,TC) = SHA1( (K  xor 0x5c5c…)  || SHA1((K  xor 0x3636… || TC))

Retourne 20 octets (longueur du HMAC-SHA1)

Etape 2 :

Extraction d’une chaine de 31 bits à partir du HMAC calculé à l’ étape 1

Sbits = DT(HMAC(K,TC))

La fonction DT (Dynamic Truncation) est détaillée plus bas.
Retourne une chaine de 31 bits

Etape 3 :

Génère un token à partir de la chaine Sbits calculée à l’ étape 2

Snum  = StToNum(Sbits)

StToNum convertit Sbits en décimal

T = Snum mod 10^Digit

• Digit : longueur du token : généralement 6
• mod : modulo
• T : Retourne une valeur comprise entre 0 et 999999 qui correspond au token

Description de la fonction DT (Dynamic Truncation) de l’étape 2

DT(String)

• String, qui est le hmac calculé à l’étape 1, est une chaine composée de 20 octets (String[0]…String[19])
• On extrait les 4 bits de poids faible de l’ octet 19. La valeur est contenue dans OffsetBits
  • OffsetBits est donc compris entre 0 et 15
  • OffsetBits donne la position dans String pour extraire les 4 octets

affichage hexa :

0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5  6  7  8  9   
xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xy
                                                          ^

Les 4 derniers bits (y) donnent la position où sont extraits les 4 octets.

• Extraction :
  • Offset = StToNum(OffsetBits)
  • Extraction de 4 octets à partir de OffsetBits
  • Retourne 31 bits de Offset (le bit de signe est positionné à 0)
  • Exemple :
    • si OffsetBits est égal à 5 (0101 en binaire), on extrait aa bb cc dd à partir de l’ octet 5

Affichage hexa :

0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5  6  7  8  9   
xx xx xx xx xx aa bb cc dd xx xx xx xx xx xx xx xx xx xx xy
               ^^ ^^ ^^ ^^                                ^

Puis on positionne à 0 le bit le plus significatif

    a    a    b    b    c    c    d    d
    xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 
    0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
    ^  

La raison de masquer le bit le plus significatif (bit de signe) est d’éviter des erreurs de calcul (bit de signe).

Pour lever toute ambiguïté l’algorithme supprime le bit de signe.

Préparation des données :

K est le secret partagé :

• en base 32: LVACVMXXD4AIPVLFZ6QL337GS2MM7X5Y
  • la clef est généralement en base 32 pour simplifier et éviter les erreurs de saisies
• Conversion en hexa : 5d402ab2f71f0087d565cfa0bdefe69698cfdfb8
  • (convertisseur on line base32 -> base 16 : tomeko.net)

C (compteur) est le compteur de temps :

• 1400320015 = Samedi 17 mai 2014 / 09h 46m 55s (Conversion on line www.epochconverter.com)
• TC = (unixtime(now) – unixtime(T0)) / TS (1400320015 /30) = 46677333
• TS est généralement égale à 30 – cela permet de découper le temps en tranche de 30 secondes
• Conversion en hexa
  • 46677333d = 0x2C83D55
• Conversion en 8 octets
  • 0000000002C83D55

Les données sont préparées il faut maintenant appliquer les 3 étapes de l’algorithme :

Etape 1 : HMAC-SHA1

HMAC(K,TC) = SHA1((K xor 0x5c5c…) || SHA1((K xor 0x3636… || TC))
HMAC(5d402ab2f71f0087d565cfa0bdefe69698cfdfb8, 0000000002C83D55)

On obtient : e562f2dadefc81a384551c3278d5ec42417ab4da

Etape 2 : Extraction des 4 octets et potitionnement à 0 du bit de signe

Extraction des 4 octets:

offset 0  1  2  3  4  5  6  7  8  9  0  1  2  3  7  5  6  7  8  9
       e5 62 f2 da de fc 81 a3 84 55 1c 32 78 d5 ec 42 41 7a b4 da
                                     ^  ^  ^  ^                  ^

les 4 derniers bits donnent l’ offset : 0xa (10d => d comme décimal)
Les 4 octets à extraire sont donc : 1c 32 78 d5

Positionnement à 0 du 31 ème bit
1c 32 78 d5 on ne conserve que les 31 bits (le dernier bit à gauche est positionné à 0)
1c 32 78 d5 and 7f ff ff ff = 1c 32 78 d5
Dans cet exemple, le bit de signe étant déjà égal à 0 , cela ne change rien

Etape 3 : Génération du token

• Conversion en décimal
  • 1c3278d5 = 473069781
• Modulo 10^6
  • 473069781 % 10^6 = 069781

Nous obtenons le token : 069781

On remplace simplement le compteur de temps par un compteur incrémentiel

00 00 00 00 00 00 00 01
00 00 00 00 00 00 00 02
00 00 00 00 00 00 00 03 etc ...

Préparation des données :

K est le secret partagé :

• en base 32: WLBQPZMXG5EML4IOPZPAW5K6HRWAW5DQ
  la clef est généralement en base 32 pour simplifier et éviter les erreurs de saisies
• Conversion en hexa : B2C307E5973748C5F10E7E5E0B755E3C6C0B7470
  (convertisseur on line base32 -> base 16 : tomeko.net)

C (compteur) est le compteur incrémentiel

• Dans cet exemple le compteur est égal à 8 (conversion sur 8 octets)
• On obtient : 0000000000000008

Etape 1 : HMAC-SHA1

 HMAC(K,TC) = SHA1((K xor 0x5c5c…) || SHA1((K xor 0x3636… || TC))
 HMAC(B2C307E5973748C5F10E7E5E0B755E3C6C0B7470, 0000000000000008)
 On obtient : aeeed68be51b23e1b7ea1a1aaae93bdee303b439

Etape 2 : extraction des 4 octets et positionnement à 0 du bit de signe

Extraction des 4 octets:

     offset 0  1  2  3  4  5  6  7  8  9  0  1  2  3  7  5  6  7  8  9
            ae ee d6 8b e5 1b 23 e1 b7 ea 1a 1a aa e9 3b de e3 03 b4 39
                                       ^^ ^^ ^^ ^^                    ^

les 4 derniers bits donnent l’ offset : 0x09 (9d => d comme décimal)
Les 4 octets à extraire sont donc : ea 1a 1a aa

Positionnement à 0 du 31ème bit
ea 1a 1a aa on ne conserve que les 31 bits (le dernier bits à gauche est positionné à 0)
ea 1a 1a aa and 7f ff ff ff = 6a 1a 1a aa

Etape 3 : Génération du token

• Conversion en décimal
  • 6a1a1aaa = 1780095658
• Modulo 10^6
  • 1780095658 % 10^6 = 095658

Nous obtenons le token : 095658

import sys
import base64, hashlib, hmac
import struct, time, math

def get_totp_token(secret, time_window, key_len):
    key = base64.b32decode(secret)
    msg = struct.pack(">Q", time_window)
    h = hmac.new(key, msg, hashlib.sha1).digest()
    o = ord(h[19]) & 0x0f
    otp = (struct.unpack(">I", h[o:o+4])[0] & 0x7fffffff)
    return '%6d' % (otp % int(math.pow(10, key_len)))

def test_user_pin(secret, key_len, user_pin):
    time_window = int(time.time())/30
    print "Reference temps " + str(time_window)
    for offset in [0, -1, -2, 1]:
        print "offset:  " + str(offset * 30)
        cur_pin = get_totp_token(secret,time_window+offset, key_len)
        if str(cur_pin) == str(user_pin):
            print '   temps: '+str(time_window+offset), 'token: '+ str(cur_pin)
            return True
    return False

# Déclarer le secret partagé codé en 32 bits dans la variable : secret
secret = "LVACVMXXD4AIPVLFZ6QL337GS2MM7X5Y"
key_len = 6

# Déclarer le token dans la variable : user_token
user_token = "364525"
if test_user_pin(secret, key_len, user_token):
    print " ACCEPT"
else:
    print " DENY"

import hmac, base64, struct, hashlib, time

def get_hotp_token(secret, intervals_no):
    key = base64.b32decode(secret, True)
    msg = struct.pack(">Q", intervals_no)
    h = hmac.new(key, msg, hashlib.sha1).digest()
    o = ord(h[19]) & 0x0f
    h = (struct.unpack(">I", h[o:o+4])[0] & 0x7fffffff) % 1000000
    return h

secret = 'WLBQPZMXG5EML4IOPZPAW5K6HRWAW5DQ'
print 'Count', 'Token'
for i in xrange(8, 16):
    print '%04d' %i, ' %06d' % get_hotp_token(secret, intervals_no=i)

Affiche les 7 premiers token.

Comme vous pouvez le voir, l’algorithme de génération de token n’ est pas bien compliqué.
Pour des explications complémentaires je vous renvoie vers la RFC 4226.