PBKDF2 et génération des clés de chiffrement de disque

Dans mon billet sur les flops et le temps pour casser un password par brute force, je prenais uniquement en compte la puissance en FLOPS sans prendre en compte le type de hash et les itérations. J’ai récemment parlé dans un billet du temps nécessaire à un supercalculateur pour casser un mot de passe issu d’une fonction de hash. En partant du postulat : 1 FLOPS = 1 hash. À présent, je vais essayer de calculer le temps nécessaire à ce même supercalculateur pour casser une clé réalisée non pas seulement avec un hash mais avec une fonction de type PBKDF2.

Le PBKDF2 (Password-Based Key Derivation Function) est une fonction de dérivation de clé qui est implémentée dans la majorité des logiciels de chiffrement de disque. C’est aujourd’hui la meilleure référence en matière de sécurité pour la création de clé de chiffrement. Il est basé sur ces éléments :

• Un algorithme de HMAC (SHA512, RIPEMD, WHIRLPOOL,etc)
• Un mot de passe
• De la Salt pour lutter contre une attaque par rainbow table
• Des itérations pour ralentir la génération de clé

Ces itérations sont très importantes car elles permettent d’accroitre considérablement le temps nécessaire au test de toutes les combinaisons d’un mot de passe. Et c’est sur cela que ce billet va se concentrer.

Je vais reprendre l’excellent travail d’explication du fonctionnement de Truecrypt de Bjorn Edstrom et ses fonctions en python. Dans un premier temps je vais chercher à générer une clé PBKDF2-PKCS#5, puis dans un second temps je vais chercher à calculer le temps qu’il faut pour générer la clé en fonction des différents éléments la composant.

1 / Les algorithmes de hachage

Truecrypt utilise soit le RIPEMD-160 soit du WHIRLPOOL soit du  SHA512 comme générateur de hash. Le RIPEMD-160 et le WHIRLPOOL sont tous les 2 issus du standard ISO/IEC 10118-3:2004 alors que le SHA512 est issu du FIPS PUB 180-2. Dans les 2 cas ce sont des standards récents qui datent respectivement de 2004 et 2002.

Le RIPEMD est considéré comme le plus faible des 3 car il ne génère un résultat que sur 160 bits, alors que les 2 autres font un hash de 512bits. Pour pallier ce manque, Truecrypt fait 2000 itérations à cet algorithme au lieu de 1000 comme pour les 2 autres.

Le SHA-512 est de la famille du SHA-2 qui est dérivé du SHA-1. Le SHA-1 possède des failles qui ont été découvertes en 2005, son remplacement par le SHA-3 est en cours.

2 / Hash, HMAC et PBKDF2

Voici rapidement l’explication des différentes fonctions.

Le hash est  l’empreinte d’un mot de passe généré par un algorithme à sens unique (SHA, MD5, RIPEMD, Whirlpool, etc).

Le HMAC est une fonction de hash qui va créer l’empreinte d’un texte tout en le combinant avec un mot de passe.

Une fonction PBKDF2 combine un HMAC, un texte, de la salt et des itérations.

3 / Générer le hash d’un password en python

Tout d’abord je vais chercher à savoir combien de temps prend mon ordinateur pour générer le hash d’un password.  Pour cela il faut télécharger d’abord les 2 librairies ripemd et whirlpool qui ne sont pas implémentées par défaut en python contrairement au SHA512.

Puis dans un SHELL python on va les tester :

import whirlpool
whirlpool.new("artiflo.net").hexdigest()
'220f227652e6af8b180697d416d387e73917c4d8a69360dd0e5dd5520dbf1684b09883bd2b5dcc4ae75fa93765b8aa7484be225a43ce12ab3ff11d0b700da4eb'

import ripemd
ripemd.new("artiflo.net").hexdigest()
'b6fb9b189dc3089fb4565948f9187bf07bfa6323'

from hashlib import sha512
sha512("artiflo.net").hexdigest()
'fb5b25552b64cde7e901a2097a900835b96dff747b95ce97eaaeb8e3088abdbf9c2eb54f467e6c6c9f45c6b431552579a4cf21bdae92f6e7e915d4a70d639982'

Comme prévu, le hash généré par le RIPEMD ne fait que 160 bits, il est plus court que les hashs de 512bits de SHA512 et Whirlpool.

Maintenant qu’on peut générer un hash, il faut timer l’opération en utilisant la fonction timeit de python (le résultat est donné en secondes) :

import whirlpool
import timeit
timeit.Timer(stmt='whirlpool.new("password").hexdigest()', setup='import whirlpool').timeit(1)
0.0012343376151203668

import ripemd
timeit.Timer(stmt='ripemd.new("password").hexdigest()', setup='import ripemd').timeit(1)
0.00041234010131928941

from hashlib import sha512
timeit.Timer(stmt='sha512("password").hexdigest()', setup='from hashlib import sha512').timeit(1)
1.2002927298731502e-05

Tous ces résultats sont donnés en hexdigest() qui contrairement au digest() retourne uniquement des caractères hexadécimaux. Pour indication voici un tableau comparant les performances entre le hexdigest() et le digest().

Type de retour	Temps WHIRLPOOL	Temps RIPEMD160	Temps SHA512
hash digest	0,000718894	0,000397197	9,13E-06
hash hexdigest	0,001234338	0,00041234	1,20E-05
Différence	71,70%	3,81%	31,41%

La différence est essentiellement due à l’implémentation de la fonction de hachage et son optimisation.

4 / Générer une clé PBKDF2 en python

Maintenant que générer un hash et le timer est fait, il faut à présent reproduire la même opération, mais cette fois-ci pour générer une clé PBKDF2.

Voici à présent en python un exemple de fonction permettant de générer des clés de chiffrement en suivant la norme PBKDF2 en utilisant comme HMAC soit du RIPEMD-160 soit du WHIRLPOOL : hashtime.py

import struct
import math

import ripemd
import whirlpool

#
# Hash funcs.
#

def HASH_WHIRLPOOL(data):
    return whirlpool.new(data).digest()

def HASH_RIPEMD160(data):
    return ripemd.new(data).digest()

def hexdigest(S):
    tmp = ''
    for s in S:
        tmp += '%02x' % ord(s)
    return tmp

#
# HMAC funcs.
# http://en.wikipedia.org/wiki/HMAC
#

def HMAC(hash_func, hash_block_size, key, message):
    if len(key) > hash_block_size:
        key = hash_func(key)
    if len(key) < hash_block_size:
        key += '\x00' * (hash_block_size - len(key))
    assert len(key) == hash_block_size
    ipad = ''
    opad = ''
    for i in xrange(hash_block_size):
        ipad += chr(0x36 ^ ord(key[i]))
        opad += chr(0x5c ^ ord(key[i]))
    return hash_func(opad + hash_func(ipad + message))

def HMAC_RIPEMD160(key, message):
    return HMAC(HASH_RIPEMD160, 64, key, message)

def HMAC_WHIRLPOOL(key, message):
    return HMAC(HASH_WHIRLPOOL, 64, key, message)

#
# PBKDF2.
# http://www.ietf.org/rfc/rfc2898.txt
#

def xor_string(str1, str2):
    # TODO: slow!
    str3 = ''
    for i in xrange(len(str1)):
        str3 += chr(ord(str1[i]) ^ ord(str2[i]))
    return str3

def PBKDF2(hmacfunc, password, salt, iterations, derivedlen):
    """Derive keys using the PBKDF2 key strengthening algorithm."""
    hLen = len(hmacfunc('', '')) # digest size
    l = int(math.ceil(derivedlen / float(hLen)))
    r = derivedlen - (l - 1) * hLen
    def F(P, S, c, i):
        U_prev = hmacfunc(P, S + struct.pack('>L', i))
        res = U_prev
        for cc in xrange(2, c+1):
            U_c = hmacfunc(P, U_prev)
            res = xor_string(res, U_c)
            U_prev = U_c
        return res
    tmp = ''
    i = 1
    while True:
        tmp += F(password, salt, iterations, i)
        if len(tmp) > derivedlen:
            break
        i += 1
    return tmp[0:derivedlen]

Dans un shell python :

from hashtime import *
PBKDF2(HMAC_RIPEMD160, "Password", "\xefD\x03\xaf\x93\xa6\xff\xe2", 2000, 32)
"\xc7\x076\xb8\x85v\t\x04\xebf\xcc\xed\xd7\xf1k\xf5\xb4V\xb8\xae_@e\x81v\\\xb6\xa6\xfd\xcf\xab\x9d\x9c\x11\x85O\x92\xd6\xd0|h\xf4\xe8\xf2\x1f\xf8>A\xc9V[\x87\xca\xb6l\xcb ,\xa2\xe0\xbbI\xc5\x98\x0b\x00\x04\x9d\xaa\x00d\x9ds\x14\xfc~\xbb?\x98\x96-\x87\xe9wG\x89\x87\xda\xdbaH\xba\x17\x96\xf5\x18\x84w\x9f\x8e\xed\xb5$\x05\xf1\xd4\xf7\x1b\xce\xccw\x1f\x97:\xf2\xdd\xa6V\x06\x11s\x00\xefV=\xffG[e\xc6\xa4\x91\xccX;\xa2\x1e`\x04D\x8d+P?F\x95\x84\xd4\x84=\xa9\xb4\xaeOw\x0e\xd9J_\x0b\xb8\xc2\x05x4\xa4\xf2l\x7f\x1f\xe3C\xc4\xe4\xbc\xb3\xca\x99\xf6\xdb?\xb58\xfa\x08\\y\xd2\xcd\xa4K]\x87\xcf\x12z\x0e\xa3\x85\xf2\xc0\x86\xb3\xb32N]\x96\xc7>veN'g\xb9G\x877\xebWU\x81\x06\xd5\xe7\xbe\x80%\xf4\xae\xab=W\xebG?='\xbd\x15\xd7R\xff{>h\x18E\xb2\x7f\x1eU\xfb%\x1e"

Dans cet exemple, l’algorithme de hachage est le RIPEMD-160, le mot de passe est password, \x12\x34\x56\x78 représente 8 bytes de SALT, il y a 2000 itérations, et le résultat doit faire 32 bytes (256 bits). Le résultat retourné peut être utilisé comme clé de chiffrement du volume.

5 / Temps nécessaire à la génération de clé PBKDF2

Maintenant que l’on peut générer une clé PBKDF2, je vais chercher à calculer le temps qu’il faut à l’ordinateur pour la créer. Toujours en python, je vais utiliser de nouveau timeit :

import timeit
from hashtime import *
timeit.Timer(stmt='PBKDF2(HMAC_RIPEMD160, "password", "\xefD\x03\xaf\x93\xa6\xff\xe2", 1000, 32)', setup='from hashtime import PBKDF2,HMAC_RIPEMD160').timeit(1)
2,45778555264

Un E8400 aura mis 2.45 secondes pour générer la clé de 32bytes avec 1000 itérations. Ce qui est très lent, car le calcul en python utilise mal le processeur double coeur n’utilisant que 50% de chaque cœur. Si j’utilise le SHA512 qui est mieux optimisé, le même calcul ne prend plus que 0.0265 secondes.

Si je compare le temps nécessaire à la génération de mes clés en fonction du nombre d’itérations, voici le résultat :

Itérations	Temps WHIRLPOOL	Temps RIPEMD160	Temps SHA512
1	0,00603894	0,003798531	6,75E-05
10	0,037742737	0,025784201	0,000572174
50	0,179296185	0,126092814	0,001372526
100	0,355860458	0,247183001	0,002717242
250	0,885099095	0,61641127	0,006668987
500	1,770519854	1,229154459	0,013259093
1000	3,552058341	2,457785553	0,026551702

6 / Taille de la salt

Dans Truecrypt la taille de la SALT fait 512bits (64bytes). La salt n’est pas faite pour ralentir la génération du mot de passe mais uniquement à lutter contre les attaques par rainbow table. La taille de la SALT n’influe donc pas sur la sécurité du mot de passe.

Taille de la salt	Temps WHIRLPOOL	Temps RIPEMD160	Temps SHA512
8 bytes SALT	3,61966696 s	2,445668758 s	0,026664285 s
16 bytes SALT	3,612824251 s	2,445481045 s	0,026254751 s
32 bytes SALT	3,614185051 s	2,444231824 s	0,026657202 s

7 / Complexité du mot de passe

La complexité ou la taille du mot de passe n’entre pas en compte non plus dans le temps pour générer le hash.

Taille du mdp	Temps WHIRLPOOL	Temps RIPEMD160	Temps SHA512
password	3,606672422	2,450537066	0,02637023
p@sSw0rd!%	3,617122965	2,452563037	0,02644918
18p@sSw0rd!%ch4p10n2	3,610235201	2,459733353	0,026785168

8 / Comparaison entre hash et PBKDF2

Dans mon billet sur les flops et le temps pour casser un password par brute force, je prenais uniquement en compte la puissance en FLOPS sans prendre en compte le type de hash et les itérations. Dans mon exemple il est intéressant de constater la différence de vitesse que peut avoir un algorithme bien optimisé et un autre simplement porté. Voici un tableau reprenant les informations collectées plus haut :

Comparaison	Temps WHIRLPOOL en seconde	Temps RIPEMD160 en seconde	Temps SHA512 en seconde
Temps pour 1 hash	0,001234338	0,00041234	1,20E-05
Temps pour 1 clé PBKDF2 avec 1 itération	0,00603894	0,003798531	6,75E-05
Temps pour 1 clé PBKDF2 avec 1000 itérations	3,552058341	2,457785553	0,026551702

Dans le tableau on peut voir que faire 1000 itérations au lieu d’une ne veut pas dire que cela va prendre 1000 fois plus de temps. À présent, je compare le temps nécessaire à générer 1 hash et à générer 1 et 1000 clés PBKDF2, voici ce que cela donne :

	WHIRLPOOL	RIPEMD160	SHA512
hash / PBKDF2	3,892454071	8,212130937	4,621899273
hash / 1000 PBKDF2	2876,70404	5959,578524	2211,10223

Créer une clé PBKDF2 avec 1 itération va prendre 3.8 fois plus de temps que simplement générer un hash. Alors que créer la même clé, mais cette fois-ci avec 1000 itérations, va prendre 2876 fois plus de temps.

9 / Les itérations et le brute force

/ ! \ Attention ce ne sont que des approximations théoriques / ! \

L’impact sur le temps pour briser un mot de passe est bien réel et significatif si je reprends les calculs sur la puissance en FLOPS. Le FLOPS (Floating-point Operations Per Second) étant une mesure qui permet d’évaluer la puissance des microprocesseurs en nombre de calculs en virgule flottante par seconde. En juin 2009 le plus gros supercalculateur était capable de réaliser 1105 TéraFLOPS (1105 x 10^12 FLOPS ce qui équivaut à un millier de milliards d’opérations par seconde) pour une consommation énergétique de 2400KW.  En reprenant le postulat 1 FLOPS = 1 hash on obtenait ce tableau :

Longueur du mdp	Complexité	Nombre de combinaisons	Puissance de calcul	Temps en année	Temps en jour	Temps en heures	Temps en minutes	Temps en seconde
8	62	2,1834E+14	1,105E+15	6,27E-09	2,29E-06	5,49E-05	0,0033	0,20
8	94	6,09569E+15	1,105E+15	1,75E-07	6,38E-05	0,0015	0,0919	5,52
12	62	3,22627E+21	1,105E+15	0,09	33,79	811,0273	48661,6405	2,92E+06
12	94	4,7592E+23	1,105E+15	13,66	4984,92	1,20E+05	7,18E+06	4,31E+08
14	62	1,24018E+25	1,105E+15	355,89	1,30E+05	3,12E+06	1,87E+08	1,12E+10
14	94	4,20523E+27	1,105E+15	1,21E+05	4,40E+07	1,06E+09	6,34E+10	3,81E+12
16	62	4,76724E+28	1,105E+15	1,37E+06	4,99E+08	1,20E+10	7,19E+11	4,31E+13
16	94	3,71574E+31	1,105E+15	1,07E+09	3,89E+11	9,34E+12	5,60E+14	3,36E+16
18	62	1,83253E+32	1,105E+15	5,26E+09	1,92E+12	4,61E+13	2,76E+15	1,66E+17
18	94	3,28323E+35	1,105E+15	9,42E+12	3,44E+15	8,25E+16	4,95E+18	2,97E+20
20	62	7,04423E+35	1,105E+15	2,02E+13	7,38E+15	1,77E+17	1,06E+19	6,37E+20
20	94	2,90106E+39	1,105E+15	8,33E+16	3,04E+19	7,29E+20	4,38E+22	2,63E+

À présent, en implémentant les itérations et en prenant une moyenne des 3 résultats, on pourrait donc dire que 1 test de hash PBKDF2 = 3000 FLOPS. Le plus gros supercalculateur peut donc faire 1105 x 10^12 / 3000 =  3.68 x 10^11 calculs de hash à la seconde. Ce qui se traduit sous forme de tableau ainsi :

Longueur du mdp	Compléxité	Nombre de combinaisons	Puissance de calcul	Temps en année	Temps en jour	Temps en heures	Temps en minutes	Temps en seconde
8	62	2,1834E+14	3,68E+11	1,88E-05	6,87E-03	1,65E-01	9,89	593,32
8	94	6,09569E+15	3,68E+11	5,25E-04	1,92E-01	4,60	276,07	16564,37
12	62	3,22627E+21	3,68E+11	278,00	1,01E+05	2,44E+06	1,46E+08	8,77E+09
12	94	4,7592E+23	3,68E+11	41009,06	1,50E+07	3,59E+08	2,16E+10	1,29E+12
14	62	1,24018E+25	3,68E+11	1,07E+06	3,90E+08	9,36E+09	5,61674E+11	3,37E+13
14	94	4,20523E+27	3,68E+11	3,62E+08	1,32E+11	3,17E+12	1,90454E+14	1,14E+16
16	62	4,76724E+28	3,68E+11	4,11E+09	1,50E+12	3,60E+13	2,15908E+15	1,30E+17
16	94	3,71574E+31	3,68E+11	3,20E+12	1,17E+15	2,80E+16	1,68285E+18	1,01E+20
18	62	1,83253E+32	3,68E+11	1,58E+13	5,76E+15	1,38E+17	8,29949E+18	4,98E+20
18	94	3,28323E+35	3,68E+11	2,83E+16	1,03E+19	2,48E+20	1,48697E+22	8,92E+23
20	62	7,04423E+35	3,68E+11	6,07E+16	2,22E+19	5,32E+20	3,19032E+22	1,91E+24
20	94	2,90106E+39	3,68E+11	2,50E+20	9,12E+22	2,19E+24	1,31389E+26	7,88E+27

En prenant cet exemple, un mot de passe de 12 caractères d’une complexité de 62 symboles sera cassé en 33 jours dans le cas de l’utilisation d’un algorithme sans itération mais cela prendra 278 ans dans le cas d’un algorithme PBKDF2.

10 / Conclusion

Les itérations de PBKDF2 jouent donc bien leur rôle dans la sécurité de la clé de chiffrement en allongeant de 2000 à 6000 fois le temps nécessaire pour calculer une clé.

Aujourd’hui Truecrypt (contrairement à freeOTFE) ne propose pas à l’utilisateur de définir lui-même le nombre d’itérations (1000 pour le Whirlpool et le SHA512 et 2000 pour le RIPEMD). Mais cela peut être aussi un second élément de sécurité, si l’utilisateur peut définir lui-même le nombre d’itérations, il possède alors 2 éléments de sécurité : 1 fort avec son mot de passe, et 1 faible avec son nombre d’itérations. L’attaquant devra alors réaliser une attaque non seulement sur le mot de passe, mais aussi sur le nombre d’itérations, augmentant d’autant plus la difficulté.