Logo Blog perso d'Ozwald

Crypto à retardement : vers une solution

Par Oz le - Sécurité
SSTIC challenge cryptographie

Ce billet constitue le troisième d'une série portant sur l'analyse a postériori de l'étape 2 du challenge SSTIC 2013. Si vous n'avez pas lu le premier de cette série et que vous souhaitez suivre mes diverses expériences correctement je vous conseille vivement de commencer par lui; et si, au contraire, vous voulez simplement connaitre le fin mot de l'histoire je vous recommande de sauter au dernier billet de la série :)

enigma - Creative Common CCBY by "joncallas" on flickr

Boostons l'analyse fréquentielle

En terminant le billet précédent par la comparaison de fréquences entre l'un des buckets chiffrés et un lorem ipsum encodé en base64 j'avais conclu que le clair original, bien que probablement ascii, n'était pas de l'anglais (ni probablement du français ou un autre dérivé de langue latine d'ailleurs). Pour autant, l'analyse fréquentielle est-elle totalement hors course ? Peut-être pas ! En effet, je sais que le clair original n'était pas similaire à du lorem ipsum, mais peut-être est il similaire à du code en C, ou à du HTML, ou à un autre truc potentiellement aussi exotique que du brainfuck. Pour identifier ça j'ai eu une idée toute bête : trouver pleins de textes variés et comparer leur analyse fréquentielle à celle de data. En pratique ça a donné un petit script python qui dumpait en boucle les dernier pastie de pastebin, les encodait en base64 et faisait l'analyse fréquentiel du blob base64 ainsi obtenu. Au bout d'environ 12h je me suis retrouvé avec 9322 textes différents et j'ai élu comme mon "champion" celui qui donnait l'erreur quadratique la plus faible quand il était comparé à data.

Pour les curieux voici à quoi il ressemble (il a déjà été supprimé de pastebin, il serait donc inutile de vous mettre le lien) :

RemoveBuildingForPlayer(playerid, 4024, 1479.8672, -1790.3984, 56.0234, 0.25);
RemoveBuildingForPlayer(playerid, 4044, 1481.1875, -1785.0703, 22.3828, 0.25);
RemoveBuildingForPlayer(playerid, 4045, 1479.3359, -1802.2891, 12.5469, 0.25);
RemoveBuildingForPlayer(playerid, 4046, 1479.5234, -1852.6406, 24.5156, 0.25);
RemoveBuildingForPlayer(playerid, 4047, 1531.6328, -1852.6406, 24.5156, 0.25);
...
CreateObject(1231, 1399.14575, -1845.25000, 15.20500,   356.85840, 0.00000, 3.14160);
CreateObject(1231, 1399.15137, -1838.06458, 15.20500,   356.85840, 0.00000, 3.14160);
CreateObject(1231, 1478.45117, -1862.11169, 15.20500,   356.85840, 0.00000, 3.14160);
CreateObject(1231, 1486.32324, -1862.03967, 15.20500,   356.85840, 0.00000, 3.14160);

Etant donné que nous sommes à posteriori et que nous "trichons" donc j'ai tracé l'analyse fréquentielle des buckets de mon "champion" et je l'ai comparé avec celle de la solution. Force est de constater que, contre toute attente, on trouve des éléments assez proche de la solution ! Les octets significatifs (i.e. apparaissant souvent) sont assez cohérents entre la solution du challenge et mon "champion" (bien qu'il y ait tout de même des différences). Les octets apparaissant peu sont, eux, complètement mélangés (mais ça, on pouvait s'y attendre). L'analyse complète prend plusieurs pages, mais voici un extrait de l'analyse du bucket 15 pour vous donner une idée de ce à quoi ça ressemble :

+++ data - bucket 15 +++
t [0xb] (0.04)  
L [0x17] (0.04) 
e [0x83] (0.04) 
o [0xd3] (0.04) 
K [0xf7] (0.04) 
...
z [0x7b] (3.67) =======================
j [0x73] (4.58) =============================
Z [0x7f] (4.76) ==============================
Y [0xbf] (5.01) ================================
T [0xf] (5.23)  =================================
D [0x7] (5.74)  ====================================
N [0x57] (6.76)===========================================
M [0x97] (9.37)============================================================

== Champion.txt - bucket 15 ===
q [0x71] (0.05) 
e [0x65] (0.10) 
n [0x6e] (0.15) =
7 [0x37] (0.20) =
B [0x42] (0.20) =
...
j [0x6a] (3.64) ===========================
N [0x4e] (3.89) =============================
L [0x4c] (4.53) ==================================
C [0x43] (5.37) ========================================
D [0x44] (5.47)=========================================
A [0x41] (6.79) ===================================================
M [0x4d] (7.53)=========================================================
w [0x77] (7.88)============================================================

Il y a donc des similitudes assez flagrandes, mais pas assez pour que je puisse résoudre le challenge en identifiants uniquement les chiffrés à des clairs en fonction de leur similitude de fréquence avec mon champion. L'attaque fréquentielle se rapproche donc de la solution, mais n'y arrive pas tout à fait...

La génétique à la rescousse

Je me retrouve donc à ce point avec une approche en force brute trop longue, et une approche en analyse fréquentielle trop approximative. J'ai alors eu l'idée de tenter une méthode d'optimisation numérique issue du champs d'étude de l'intelligence artificielle : un algorithme génétique :)

Je ne vais pas rentrer dans les détails mais l'idée centrale c'est de simuler les phénomènes d'évolution naturelles des organismes sexués. Dans mon cas :

  • un individu était caractérisé par l'ensemble des relations chiffré=>clair
  • les mutations consistaient à changer le clair associé à un chiffré en le remplaçant par un autre chiffré possible pour ce clair
  • les croisements consistaient à prendre la moitié des association en provenance d'un parent et l'autre moitié de l'autre (sans déc ;) !)
  • la fonction de notation consistait à compter le nombre de caractères ascii "improbable" obtenus dans le clair décodé. Les caractères ascii "improbables" étant, en gros, l'ensemble des caractères de controles (tabulation VERTICALE, bip, etc.)

Le programme a tourné une petite après-midi, mais sans grand succès. La convergence ne semblait pas vraiment au rendez-vous et, surtout, je me suis rappelé d'une bonne résolution qui m'a semblé plus prometteuse, donc j'ai abandonné l'approche génétique.

Une bonne résolution refait surface

Ma bonne résolution c'était d'utiliser un solver SAT la prochaine fois que je n'aurai pas de meilleure idée qu'une approche en force brute ! En plus, je savais que ce type d'approche pouvait donner de bon résultats dans l'attaque de chiffrements faibles, donc je me suis dit qu'il fallait absolument que je tente le coup !

La traduction de mon problème au format SAT a d'ailleurs été plus facile que ce à quoi je m'attendais. En effet, ce que je cherche à trouver c'est : pour chaque valeurs d'octets chiffrés de chacun de mes 16 buckets je veux retrouver la valeurs des 6 bits qu'encode le caractère base64 clair correspondant. J'ai donc créé un petit dictionnaire python qui m'a permi de faire rapidement les conversiont entre "bucket, valeur d'octet, bit" et "numéro de variable booléenne pour le solveur SAT" :

runner = 0
for bucket_id in range(16):
    for octet in range(255):
        for bit in range(8):
            correspondance['%d_%d_%d'] = runner
            runner+=1

Je me retrouve donc avec un peu plus de 5000 variables utiles (chaque bucket ne contient qu'environ 54 valeurs d'octets chiffrés différents; donc avec mon range(255) j'en fais plus que nécessaire). Maintenant il va falloir écrire les règles à respecter... La première est évidente : je vais exprimer la contrainte des bits nuls causées par la nature ascii du texte clair original (cf billet précédent). Au format dimacs ça s'exprime très simplement -XXX 0 (où XXX est le numéro de la variable booléenne correspondant au bit forcé à nul).

Je lance minisat sur ce problème et il me trouve une solution en un rien de temps :) ! Malheureusement ce n'est, évidemment, pas la bonne solution :-/ Le texte obtenu contient, après décodage base64, beaucoup de caractères non-imprimables dont je parlais dans mon approche génétique. Qu'à cela ne tienne, l'approche SAT permet de rajouter allègrement des contraintes, en effet je voudrai exprimer que chaque octet décodé n'a pas le droit d'être l'un des caractères non-imprimables. En pseudo-logique ça va donner quelque chose comme ça : "(octetX n'a pas la valeur ascii du charactère de controle 1) et (octetX n'a pas la valeur ascii du charactère de controle 2) et (octetX n'a pas la valeur ascii du charactère de controle 3) ..." donc je n'ai qu'à réussir à traduire un "octetX n'a pas la valeur ascii BBBBBBBB" sous la forme d'une suite de "ou" logiques et ça ira bien. Ca tombe bien, la loi de de morgan me dit que : "non (bit1=1 et bit2=0 et bit3=1, ...)" est identique à "bit1=0 ou bit2=1 ou bit3=0...".

Bref : interdire à un octet de prendre une valeur donnée est trivial en dimacs. Aussitôt dit aussitôt fait, j'interdit l'apparition de caractères non imprimables et je relance minisat. En un clin d'oeil j'ai une solution...qui n'est toujours pas la bonne -_-

Je commence à être ennuyé mais je me dit que je vais profiter de la facilité qu'il y a à interdire que certains octets prennent certaines valeurs en clair pour m'aiguiller dans la bonne direction. Je ressort donc mon "champion" de l'analyse fréquentielle, dont je parle en début de billet, et j'interdit à chacun de mes octets apparaissant significativement dans data d'être traduit en clair par l'un des octets apparaissant moins de 1% du temps dans mon champion. Je relance minisat et j'obtient une nouvelle solution....toujours pas bonne -_-

L'anneau unique

C'est là que je réalise que j'ai oublié une contrainte essentielle : l'algorithme de chiffrement peut être vu comme 16 bijections indépendantes, or moi je n'ai imposé nulle part qu'un clair ne pouvait correspondre qu'à une seule valeur chiffrée. Pour preuve j'en veux la solution que minisat me donne quand je lui donne peu de contraintes : AAAAAAAAA....AAA Il faut donc que je trouve un moyen d'exprimer, en dimacs, le fait que chaque octets clair ne peut pas apparaitre plus d'une fois dans chaque bucket. Pas simple à réaliser à partir de simples ET et OU... Après réflexion je me suis dit qu'il me suffirait de dire que, pour chaque bucket, le XOR de chaque octets clair est non-null avec n'importe quelle autre octet clair du même bucket. La solution est dans l'esprit et fonctionne : ce sont des simples propositions logiques, et elles imposent qu'aucun clair n'apparaisse plus d'une fois dans chaque bucket. Sauf que voilà, bien que certains solveurs permettent d'utiliser des XOR sur des vecteurs de bits, la syntaxe dimacs "pure" ne permet d'utiliser que des OR et des AND sur de simples bits... Enfer et damnation, ne parviendrais-je pas à exprimer cette contrainte pourtant simple et essentielle ???

Et bien si ;) ! Il se trouve qu'on peut exprimer des XOR sur des vecteurs de bits avec de simples OR et AND sur des bits. L'explication est un peu longue donc je vous invite à aller la lire directement sur cette page web, là où je l'ai trouvé. On y apprend par contre un énorme inconvénient des XOR : un simple XOR entre deux vecteurs de X bits implique 2 puissance (X-1) clauses dimacs ! Un XOR entre deux octets implique donc 128 clauses dimacs différentes...Heureusement je travaille en base64 et je n'ai donc à faire des XOR qu'entre des vecteurs de 6 bits, ce qui n'induit que 32 clauses à chaque fois et qui reste donc gérable. Arrivé là je me suis même demandé si ça n'avais pas été fait exprès par les concepteurs du challenge1... Quoiqu'il en soit j'exprime mes (environ) 555516 xor qui se traduisent en (environ) 1,5 millions d'expressions dimacs. Je donne mon nouveau fichier à manger à minisat et....j'attend.

Au bout d'une heure et demi de calcul minisat ne s'en sortait toujours pas. J'ai donc téléchargé, compilé, et testé cryptominisat. Pas de chance : au bout d'une heure cryptominisat n'avait toujours pas terminé lui non plus. J'ai donc cherché ailleurs et j'ai testé lingeling et, miracle, il m'a trouvé la solution en à peine une minute :-D !...Enfin...il m'a trouvé une solution, mais ça n'était toujours pas celle du challenge. Visiblement, je manquais de contraintes...

Markov à la rescousse

J'ai continué de jouer un petit peu avec lingeling en lui fournissant des dimacs un peu différents, basés sur diverses contraintes issues de l'analyse fréquentielle de mon champion (exemple : tous les octets chiffré apparaissant plus de 1% du temps dans data doivent forcément avoir leur clair présent dans le champion, etc.), mais sans succès. En effet, chaque nouvelle solution trouvée par lingelin n'était "visiblement" pas la bonne. Et c'est en réalisant ce que je venait de me dire que j'ai eu une idée : l'analyse fréquentielle du champion ne sera pas suffisante, il faut aussi que j'interdise les traductions "visiblement" improbables. En termes de techniques je me suis donc dit : j'identifie les suites de trois caractères les plus improbables (selon une mesure de markov) et je les interdit également ! Dans les faits j'ai plutôt implémenté un "pseudo-markov" capable de s'en sortir avec un échantillon de base aussi petit que mon texte "champion", mais l'idée reste la même et j'ai introduit des interdictions de plus dans mon dimacs : interdiction aux triplettes étrange ^^ !...Sauf qu'au bout d'une heure de calcul mon PC était encore en train de générer les règles d'interdiction :-/ Il y avait trop de triplettes improbables à interdire. J'ai donc opté pour un compromis en n'interdisant que certaines triplettes pour ne pas dépasser les 3 millions de règles dimacs et j'ai lancé lingeling. Quelques minutes de calcul ont suffit pour obtenir une solution...qui n'était toujours pas la bonne :-(

Destination finale ?

Bien...je commence à me dire que je suis dans une impasse et les tests prennent de plus en plus de temps (la moindre résolution demandée à lingeling prend environ 5mn, or avec la météo qu'on a en ce moment2 5mn avec le processeur qui chauffe à fond c'est presque une nouvelle forme de torture). Du coup j'ai décidé d'adopter une nouvelle approche : l'approche des autres (dont je vous parlerai dans le prochain billet).

  1. D'ailleurs si l'un d'entre eux voit ce blog je veux bien une réponse en commentaire et/ou par mail :)
  2. Je rédige cette ligne fin juillet 2013

Crypto à retardement : La force brute

Par Oz le - Sécurité
SSTIC challenge cryptographie

Dans le billet précédent (que je vous invite fortement à lire avant celui-ci) nous avons posé les bases du problème cryptographique de l'étape 2 du challenge SSTIC 2013. Dans ce billet-ci nous allons lancer nos premières attaques contre le mécanisme de chiffrement que nous avons réussi à identifier dans le billet précédent.

enigma - Creative Common CCBY by "joncallas" on flickr

Petite triche ?

Avant de poursuivre, nous allons tricher un peu pour montrer qu'on est dans la bonne direction et pour nous dérouiller avec une attaque fréquentielle qui marchera forcément. Notre "triche" va consister à tirer parti d'éléments connus de la solution pour émettre une hypothèse que nous avions peu de chance de formuler lors du challenge. On sait en effet que le contenu déchiffré est au format base64 (ça, c'est une information qu'on obtient sans tricher), mais en poussant un peu plus loin (puisqu'on connait le résultat) on peut supposer que le texte est formaté en lignes de 76 colones (ce qui constitue un formatage classique mais absolument pas systématique). Si on part de cette hypothèse on recherche, pour chaque bucket, les valeurs d'octets chiffrés dont la fréquence d'apparition se rapproche du facteur 1/76. Aussitôt dit aussitôt fait, on rajoute quelques lignes de python qui nous affichent, pour chaque bucket, les valeurs d'octets suceptible d'être des retours chariots (i.e. : dont la fréquence d'apparition est de 1/76, plus ou moins 5%) :

bucket : 0
    202 <=> \n ?
    0 <=> \n ?
    182 <=> \n ?
    42 <=> \n ?
    140 <=> \n ?

bucket : 1
    201 <=> \n ?
    149 <=> \n ?
    211 <=> \n ?
    233 <=> \n ?

bucket : 2
    150 <=> \n ?
    140 <=> \n ?

bucket : 3
    236 <=> \n ?
    254 <=> \n ?

bucket : 4
    208 <=> \n ?
    128 <=> \n ?
    70 <=> \n ?
    0 <=> \n ?

bucket : 5
    191 <=> \n ?

bucket : 6
    8 <=> \n ?
    190 <=> \n ?
    198 <=> \n ?

bucket : 7
    32 <=> \n ?
    150 <=> \n ?

bucket : 8
    47 <=> \n ?
    131 <=> \n ?
    39 <=> \n ?
    201 <=> \n ?
    53 <=> \n ?

bucket : 9
    252 <=> \n ?
    74 <=> \n ?
    0 <=> \n ?

bucket : 10
    115 <=> \n ?
    15 <=> \n ?
    143 <=> \n ?

bucket : 11
    31 <=> \n ?
    131 <=> \n ?

bucket : 12
    78 <=> \n ?
    178 <=> \n ?
    248 <=> \n ?

bucket : 13
    123 <=> \n ?
    61 <=> \n ?

bucket : 14
    141 <=> \n ?
    241 <=> \n ?

bucket : 15
    51 <=> \n ?
    117 <=> \n ?

L'affaire se profile bien puisque nous avons au moins un candidat par bucket, et rarement plus de 3. Voyons voir ce que cela donne si on affiche notre binaire "data" en remplaçant chacun des candidats possible par un retour de ligne, à la condition qu'il soit environ 76 caractères après le dernier début de ligne. Pour réaliser ce petit tour de passe-passe on utilise encore du python :

counter = 0
for index in range(len(data)):
    if ord(data[index]) in potentials[index%16] and counter>=76 and counter < 80:
        print '<%d>(%d[%d]){%d}'%(counter,ord(data[index]), index%16, index)
        counter = 0
    else:
        sys.stdout.write('X')
        counter+=1

Le résultat est sans appel :

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(78[12]){76}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(252[9]){153}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(8[6]){230}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(236[3]){307}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(182[0]){384}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(61[13]){461}
...
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(61[13]){43581}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(115[10]){43658}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(150[7]){43735}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(70[4]){43812}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(211[1]){43889}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(241[14]){43966}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<76>(131[11]){44043}
XXXXXXXXX

Le pavé de texte est parfaitement formaté avec des retours charriots à 76 caractères (à l'exception de la dernière ligne). Mieux encore : pour chaque bucket, un seul et unique candidat est utilisé tout au long du fichier pour représenter les retours à la ligne. Si j'étais arrivé à ce résultat lors du challenge je pense que ces éléments auraient suffit à valider toutes les hypothèses prises jusqu'alors :) !

Et ensuite ?

Retrouver les relations clair<=>chiffré pour chaque octet de la clef pour le caractère de retour charriot c'est bien mais insuffisant. Bien entendu, si nous connaissions l'algorithme utilisé (par exemple en ayant réverser le schéma FPGA) nous pourrions alors obtenir directement la clef grâce à cette identification, et ce sans avoir à lancer de brute force ( ;) ). Mais nous ignorons tout des détails de l'algorithme et nous allons donc devoir aller plus loin...

A cette étape, nous sommes en effet simplement confiant dans l'idée que nous avons à faire à un problème se ramenant à 16 substitutions simples. Le problème, c'est que la méthode usuelle pour casser ces chiffrement c'est d'identifier des relations "clair <=> chiffré" en se basant sur les fréquences d'apparitions des lettres en clair par rapport aux fréquences d'apparitions des lettres chiffrées. En effet, si nous faisons l'hypothèse que le document en clair est un texte anglais on va pouvoir supposer que les valeurs d'octets apparaissant le plus souvent correspondent en clair à des "e", puis "t", puis "a", et ainsi de suite. On remplacerait alors l'octet chiffré apparaissant le plus par un "e", le second par un "t", et ainsi de suite jusqu'à obtenir la solution. Nous avons pu utiliser cette méthode pour identifier les retours charriots en trichant mais nous n'allons pas pouvoir aller plus loin. En effet, nous pourrions tenter d'appliquer les correspondances chiffré/clair en nous basant sur du texte anglais, mais comme nous connaissons la solution nous savons que ça ne marchera pas. On pourrait alors, devant notre échec, supposer que nous avons à faire à un fichier PE et tenter d'extraire des fréquence à partir d'un corpus d'échantillon puis d'appliquer la même méthode de résolution. Là encore cette tentatives seraient inutiles (puisque nous connaissons le résultat et qu'il ne s'agit pas d'un fichier PE). Toujours dans l'hypothèse où nous ignorons la solution on pourrait se casser les dents longtemps en appliquant les fréquences de fichiers PNG, ELF, etc. ad nauseum.

Mais bref...comme nous connaissons la solution nous n'allons pas nous lancer dans des attaques n'ayant aucune chance de succès. Peut-être pouvons nous lancer une attaque par force brute ? Hélas non. L'attaque par force brute n'est pas envisageable puisque, par exemple pour le bucket 0, nous connaissons une unique correspondance entre l'une des 56 valeurs présentes dans le bucket et les 66 valeurs possibles de notre alphabet base64 (celle du retour à la ligne); il nous reste donc encore 55 correspondances à trouver dans un alphabet de 65 valeurs possibles. Une telle recherche offre un nombre de possibilité que l'on appelle en mathématique un "arrangement de 55 dans 65" et dont la modeste valeur est retranscrite ci-dessous :

>>> a(65,55)
2272831402139128821297169947857555184134220279801983436100673262342635520000000000000L

...tester toutes les combinaisons risque de prendre un peu de temps, et là on ne parle que d'un seul des buckets sur les 16 que l'on doit casser :-D !

Tentons donc de faire une hypothèse légitime et assez large pour que nous ne tombions pas dans un cas particulier : "le contenu qui a été encodé en base64 puis chiffré était soit un texte ascii, soit autre chose". On peut difficilement faire plus large, n'est-ce-pas ;) ? Si jamais c'était un texte ascii, qu'est ce que cela implique ? Cette hypothèse nous dit que tous les octets du texte clair ont leur bit de poids fort nul (en effet les valeurs ascii s'étalent de 0 à 126). Est-ce-que cette hypothèse peut nous avancer un petit peu ? Rappelons que, lorsqu'on encode en base64, on représente 3 octets quelconque par quatres valeur de l'alphabet base64 autorisé. Chaque élément de l'alphabet base64 représente ainsi une suite de 6 bits du clair. En appliquant l'hypothèse que le clair initial que nous recherchons est un texte ascii, on induit une contrainte sur sa représentation en base64 puisque nous savons que certains bits doivent être nuls. Le schéma ci-dessous (adapté par mes soins depuis un screenshot de la page wikipedia expliquant le base64 en anglais1) permet de visualiser les bits forcés à 0 quand on encode le mot "Man" en base64 (ce qui donne "TWFu") :

|C

Grace à ces bits forcés nous avons un nombre de possibilité de clair qui se réduit pour certain octets chiffré. En effet, les octets chiffrés se trouvant en première, seconde, ou troisième position d'un groupe de 4 lettres base64 perdent un bit de variabilité. Chacun de ses octets ayant perdu un bit d'information possède alors 32 clair possibles, au lieu de n'importe lequel des 64 de l'alphabet. Cette particularité de réduction du nombre de clairs possibles (et donc de la variété de chiffrés possibles) pourrait nous permettre de vérifier l'hypothèse selon laquelle le clair original était bien un texte ascii.

Pour vérifier cette hypothèse nous allons faire des nouveaux buckets. Ces nouveaux buckets vont suivre les même contraintes que les buckets originaux (à savoir : chaque octets du bucket X a été chiffré avec l'octet X de la clef) mais, en plus, nous voulons que chaque octet d'un bucket soit au commencement d'un bloc de 4 caractères base64 (et donc au commencement d'un bloc de 3 octets du clair que nous cherchons). Voici comment j'ai construit mes nouveaux buckets :

new_buckets = [ [] for i in range(16) ]
new_line = 0
for i,c in enumerate(data):
    if i>0 and (i+1)%77==0:
        new_line+=1
    else:
        if (i-new_line) % 4 == 0:
            new_buckets[i%16].append(c)         

for i in range(16):
    print i,len(buckets[i]), len(new_buckets[i]), len(set(new_buckets[i]))

Puis on va afficher, pour chacun des buckets : son numéro, le nombre d'octets contenu dans le bucket initial, le nombre d'octets de ce bucket qui appartiennent au nouveau bucket réduit, et le nombre de valeurs chiffrées différentes présentes dans ce bucket réduit. Le résultat semble, encore une fois, encourageant :

0 2754 680 14
1 2754 679 14
2 2754 680 12
3 2754 679 16
4 2754 680 16
5 2753 680 15
6 2753 679 13
7 2753 679 12
8 2753 680 16
9 2753 679 17
10 2753 679 11
11 2753 679 12
12 2753 680 15
13 2753 679 14
14 2753 679 12
15 2753 680 14

On se retrouve, grosso modo, avec seulement 14 symboles base64 dans des groupes contenant 680 symboles. Quand on regarde la table ascii on se rend compte que les symboles imprimables commencent plutôt par "01" ou "001", mais quasiment jamais par "000" (dans la série des "000" on retrouve surtout les tabulations, retour charriots, etc.). Or il n'y a que 24 symboles de l'alphabet base64 qui codent des suites d'octets commençant par 01 ou 001. L'hypothèse semble donc, encore une fois, tenir l'épreuve de l'analyse statistique et nous pouvons juger que cette réduction de diversité prouve bien que le clair original était un texte ascii.

En guise de bonus, cette vérification ne se contente pas de valider notre hypothèse, elle implique également une simplification drastique du problème. En effet, pour tous les octets chiffrés se trouvant en tête d'un groupe de 4 octets de la représentation base64 nous avons vu que le problème se résume à trouver un arrangement de 14 symboles parmi 24 possibles (au lieu de 55 parmi 64) :

>>> a(24,14)
170978946685747200L

C'est beaucoup mieux que tout à l'heure ! Mais ça reste, hélas, trop important (d'autant que ce n'est qu'une petite partie du problème). On pourrait bien tenter d'utiliser les octets chiffrés qui apparaissent à la fois en première, seconde, et troisième place des groupes de 4 symboles base64 puisque ce sont ceux qui ont le plus de bits forcés à nul (3) et donc le moins de clairs possibles, mais le nombre de cas à explorer reste trop large pour une attaque exhaustive :-(

Nous ne parviendrons donc pas à résoudre le problème par simple force brute, et il va falloir revenir à des éléments d'analyse fréquentielle. En cherchant dans cette direction j'ai tracé l'analyse fréquentielle de l'un de ces nouveau sous-ensemble (à savoir l'ensemble des octets chiffrés l'ayant été par l'octet 0 de la clef et qui sont au début d'un groupe de 4 caractères du blob base64 et ont, par conséquent, leur premier bit forcément nul) puis je l'ai comparé avec l'analyse fréquentielle du même sous-ensemble sur un lorem ipsum encodé en base64:

0 2754 680 14 set(['a', 'c', 'b', 'e', 'd', 'I', 'K', 'M', 'L', 'O', 'N', 'U', 'Y', 'Z'])
K   
e   
U   
L   
c   
a   
d   =
I   ==
b   ==
O   =================
Y   =======================
Z   ==========================
N   =========================================
M   ============================================================

lorem b64 :  851 15 set(['a', 'c', 'b', 'd', 'I', 'L', 'Q', 'S', 'R', 'U', 'T', 'Y', 'C', 'Z']) 
S   
C   
R   
U   
Q   ==
T   ==
L   =============
a   ==========================
Y   ==========================================
c   ===============================================
Z   ==================================================
I   ===================================================
b   ==========================================================
d   ============================================================

Ce qui m'a sauté à la figure en comparant ces deux résultats c'est à quel point ils sont différents ! La courbe provenant de data est beaucoup plus écrasée que celle du lorem ipsum, on ne peut pas considérer qu'elles sont similaires. L'analyse fréquentielle semble donc ne rien pouvoir apporter...

Bloqué ?

Dans ce billet-ci nous avons finalement pas mal piétiné...mais c'est pour vous faire partager les heures de galère que j'ai passé :-D2 En tout cas nous en retirons tout de même quelques petites choses : nous avons un élément de preuve tendant à renforcer l'hypothèse que le texte de base est un texte ascii qui a été encodé en base64 puis chiffré, et nous savons également qu'une analyse fréquentielle classique seule ne nous permettra pas de résoudre le challenge, pas plus qu'une attaque par force brute seule. Sommes nous bloqués pour autant ? Pas tout à fait :) ! Dans le prochain billet je vous expliquerai comment j'ai tenté de forcer l'utilisation des analyses fréquentielles, comment j'ai fait tourner un peu d'algorithmie génétique, et comment je me suis rappelé d'une de mes bonne résolution.

  1. Je vous conseille d'ailleurs de lire certains articles wikipedia dans plusieurs langues. Par exemple le base64 en anglais propose ce petit tableau très explicatif sur le fonctionnement de l'encodage, et la version française, elle, offre un tableau de correspondance entre les lettres base64 et leur valeurs en binaire.
  2. NDLR à postériori : au final j'ai passé environ 1 mois et demi sur cette série de billets, mais j'étais loin d'y travailler tous les jours

Crypto à retardement : introduction

Par Oz le - Sécurité
SSTIC challenge cryptographie

Cette année, plusieurs personnes ayant terminé le challenge SSTIC ont dit qu'il était sans doute possible de réaliser l'étape 2 sans analyser l'architecture logique qui était au coeur de l'étape. Pourtant, toutes les solutions que j'ai vu passent par l'analyse de ce schéma logique. Ayant moi-même calé lors de l'étape 2 et n'étant pas un grand fan de FPGA ni de schémas logiques, je me suis donc dit qu'il fallait que j'essaie de passer cette étape, à postériori, de façon purement cryptographique sans regarder le schéma logique. Cette série de billets va ainsi retranscrire mes différents essais (et ratés). Fan de crypto ou curieux ayant séché à l'étape 2 du challenge SSTIC, vos commentaires sont les bienvenus :) !

enigma - Creative Common CCBY by "joncallas" on flickr

Un peu de contexte

La première étape du challenge était très simple cette année, et en moins de 2h je me suis retrouvé avec l'archive de l'étape 2. Cette archive contenait les fichiers suivants :

data
decrypt.py
s.ngr
smp.py

En quelques dizaines de minutes à regarder ces fichiers le fonctionnement devient clair :

  • data contient des données chiffrées que l'on veut déchiffrer.
  • decrypt.py alimente un périphérique ("device") inconnu avec le contenu de data, le contenu de smp.py, et une clef de 16 octets passée en paramètre, puis il attend que le périphérique fasse son travail et il compare le md5 du résultat retourné avec une valeur connue et hard-codée. Une fois le résultat validé il le décode (c'est visiblement du base64) puis il enregistre le résultat décodé dans un fichier atad
  • s.ngr est un fichier au format propriétaire représentant l'architecture logique d'un FPGA; c'est probablement le périphérique inconnu auquel s'adresse decrypt.py.

L'objectif de l'approche 100% crypto que nous allons tenter de dérouler va donc être de faire totalement abstraction du FPGA, et de ne nous intéresser qu'aux données chiffrées ! A titre de rappel toutes les personnes ayant publié leur solution du challenge ont analysé le FPGA; au moment où j'écris cette ligne j'ignore donc s'il est vraiment possible de passer cette étape de façon purement cryptographique...croisons les doigts :)

( NDLR : maintenant que je suis en train de rédiger le dernier billet de la série je sais...et tout ce que je peux vous dire c'est qu'il va y avoir beaucoup d'échecs dans les billets à venir ;) )

Qu'est ce qui existe comme chiffrements simples ?

Pour que nous soyons en mesure de passer l'étape de façon purement cryptographique il faut que les chiffrements mis en oeuvres soient faibles et/ou mal utilisés, or nous n'allons pas essayer de décortiquer la façon dont l'algorithme a été implémenté sur le FPGA donc nous aimerions bien que ça soit la première hypothèse la bonne : les mécanismes de chiffrements utilisés sont faibles. Cherchons donc quel type de chiffrement a bien pu être utilisé en énumérant les chiffrements simples les plus classiques.

Qui dit chiffrement simple dit chiffrement de césar ! Malheureusement, un simple chiffrement de césar n'a pas besoin d'une clef de 16 octets, nous ne sommes donc pas face à celà. Si on a une clef on va plutôt penser à un chiffrement de césar à décalage variable avec une répétition de la clef; ou encore à un XOR avec répétition de la clef1; ou, plus généralement, à l'application d'une bijection simple entre l'ensemble des valeurs possibles d'un octet sur lui-même, cette bijection dépendant d'un octet de la clef (on aura donc 16 bijections simples, une par octet de la clef).

Si tel est le cas, on se retrouve à devoir casser 16 bijections indépendantes les unes des autres. Comment vérifier cette hypothèse ? Nous savons que le texte qui a été chiffré est en base64 et que ses octets ne peuvent donc prendre que 64 valeurs différentes (sur les 256 que peut prendre un octet dans le cas général). Si notre hypothèse est bonne (i.e. : que nous avons à faire à 16 bijections indépendantes) l'ensemble chiffré résultant de l'application de n'importe laquelle de ces bijection ne peut pas prendre, lui non-plus, plus de 64 valeurs différentes.

Pour vérifier ça on se pond un petit script qui compte combien de valeurs différentes il y a dans data en entier :

Number of different values in data    (of size 44053)    : 256

Bien, le document chiffré (d'une longueur de 44 053 octets) contient au moins un octet de chaque valeur possible. Maintenant, si je prend un octet sur 16 dans data(autrement formulé : "si je ne regarde que les octets qui ont été chiffré avec le premier octet de la clef"), combien de valeurs différentes vais-je avoir ?

Number of different values in bucket 0 (of size 2754)   : 56

Bingo :) ! J'ai moins de 64 valeurs différentes. Sauf erreur de ma part, la probabilité que les 2754 octets contenus dans mon échantillonage (appelé "bucket numéro 0") ne contienne que 56 valeurs différentes (sur les 256 que peut prendre un octet) est infinitésimale. J'ai un petit peu la flemme de faire le calcul là, mais si vous voulez le faire vous aurez sans doute besoin de la formule des arrangements. En tout cas ce résultat corrobore l'hypothèse des fonctions bijectives (qui sont un cas de boite de permutation crypto). Je peux d'ailleurs recommencer l'analyse en prenant toujours un octet sur 16, mais avec un décalage au démarrage de 1, 2, 3, etc. De cette façon, je vais vérifier les ensembles chiffré avec chacune de mes 16 bijections hypothétiques :

Number of different values in bucket 1 (of size 2754)   : 54
Number of different values in bucket 2 (of size 2754)   : 53
Number of different values in bucket 3 (of size 2754)   : 56
Number of different values in bucket 4 (of size 2754)   : 54
Number of different values in bucket 5 (of size 2753)   : 54
Number of different values in bucket 6 (of size 2753)   : 56
Number of different values in bucket 7 (of size 2753)   : 52
Number of different values in bucket 8 (of size 2753)   : 56
Number of different values in bucket 9 (of size 2753)   : 57
Number of different values in bucket 10 (of size 2753)  : 53
Number of different values in bucket 11 (of size 2753)  : 55
Number of different values in bucket 12 (of size 2753)  : 57
Number of different values in bucket 13 (of size 2753)  : 53
Number of different values in bucket 14 (of size 2753)  : 54
Number of different values in bucket 15 (of size 2753)  : 56

Le résultat est confirmé : nous sommes très probablement face à l'application de 16 fonctions bijectives codant un octets à la fois, indépendament les uns des autres.

Et si j'en savais moins ?

L'analyse précédente nous met sur la voie en nous confirmant un chiffrement "trivial", mais elle a un défaut : elle utilise 2 éléments dont nous avons pris connaissance grace au fichier decrypt.py (la taille de la clef, et le fait que le texte déchiffré est en base64). Dans un cas général nous ne pourrions donc pas l'utiliser. Comment arriver à la même conclusion sans nous servir de ces éléments ? Une méthode existe : l'analyse de Kasiski.

L'analyse de Kasiski est très bien expliquée sur wikipédia donc je ne vais pas tenter de faire mieux. Je résume donc uniquement le principe en une phrase : si nous avons une séquence d'octets qui se répète dans le texte clair on retrouvera cette répétition dans le texte chiffré si, et seulement si2, les deux instance du schéma répété dans le texte clair sont séparées d'un nombre d'octets multiples de la longueur de la clef (puisque, du coup, ces deux répétition du clair seront chiffrés avec les même bijections et donneront donc le même résultat chiffré).

Donc, en cherchant des suites d'octets de taille raisonnable qui se répètent dans le texte chiffré, on peut supposer que le nombre d'octets qui les séparent est probablement un multiple de la taille de la clef. En cherchant beaucoup de ces suites d'octets et en notant à chaque fois leurs écarts on devrait alors voir apparaitre un chiffre qui revient beaucoup plus souvent que les autres, ça sera la taille de notre clef.

Jetons quelques lignes de pythons dans un fichier texte3 ! D'ailleurs inutile de le lire, il n'est pas instructif et je l'ai mis ici uniquement pour que vous puissiez le copier/coller si l'envie vous prend de refaire les expériences à la maison :

def factors(n):
    """
    Retourne la liste des facteurs premiers d'un entier.
    Merci a : http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python
    """
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
def sort_by_occurence(l, reduced_result = False):
    """
    Prend une liste d'elements, retourne la liste dont j'ai supprime les repetitions et qui
    est triee par ordre d'apparence (les elements apparaissant le moins etant aux indices les plus faibles)
    Si "reduced_result" == False ce qui est retourne est en fait une liste de tuple (A,B) ou
    B est l'element de la liste passee en parametre, et A est son nombre d'occurence.
    """
    tmp = {}
    for i in l:
        if i in tmp:
            pass
        else:
            tmp[i] = l.count(i)
    tmpl = [ (tmp[i],i) for i in tmp.keys() ]
    tmpl.sort()
    if reduced_result == True:
        return [ B for A,B in tmpl]
    else:
        return tmpl

def kasiski(text, part_len = 6):
    """
    Tries to perform a kasiski analysis
    """
    all_starts = []
    all_frequencies = []
    patterns_done = []
    for starter in range(len(data)-part_len):
        starts = []
        init = text[starter:starter+part_len]
        if (not init in patterns_done) and (init in text[starter+part_len:]):
            patterns_done.append(init)
            for compare in range(starter+part_len, len(text)-part_len):
                if text[compare:compare+part_len] == init:
                    starts.append(compare)
            if len(starts)>1:
                print init,"\\t", min( [ starts[i+1] - starts[i] for i in range(len(starts)-1) ] )
                all_starts += starts
                ecarts = [ starts[i+1] - starts[i] for i in range(len(starts)-1) ]
                most_probable_freq = sort_by_occurence(ecarts, reduced_result=True)[-1]
                all_frequencies += factors(most_probable_freq)
        #else:
        #   print init,"\\t",starts
    return sort_by_occurence( all_frequencies )

Et quand on appelle kasiski(open('data').read()) voilà ce qu'on obtient :

[(1, 13), ... (19, 48), (24, 32), (64, 1), (64, 2), (64, 4), (64, 8), (64, 16)]

Cette liste doit se lire de droite à gauche et se traduit ainsi : le fichier 'data' contient 64 suites d'octets qui se répètent avec un espacement qui est un multiple de 16; il contient 64 suites d'octets qui se répètent avec un espacement multiple de 8 octets; ...; il contient 1 suite d'octet qui se répète avec un espacement multiple de 13 octets.

La différence d'apparition entre un espacement multiple de 16 et ses dauphins est tellement large que l'on peut conclure que nous sommes bien face à l'application de fonctions bijectives d'un octet, et que la taille de clef est de 16 octets. Tout ça sans aucune connaissance issue de decrypt.py, pas mal, non ^^ ?

Dernière confirmation

Histoire d'être vraiment certain de notre coup, on va se faire une dernière vérification. En effet, si on part du principe que l'on ignore tout du chiffré, l'analyse de Kasiski serait peut-être un peu légère pour nous convaincre. Pour enfoncer le clou nous allons donc carrément tracer l'analyse fréquentielle des sous-ensemble chiffré résultant chacun d'une unique bijection. Si l'hypothèse est bonne, les 16 analyses fréquentielles devraient être très similaires les unes aux autres.

J'ai donc pondu un mini script python qui trace la visualisation ascii des fréquences, et le résultat est assez parlant. Malheureusement, retranscrire ce tas de lignes de texte prendrait plusieurs pages donc, pour le blog, j'ai pondu une représentation graphique un peu moins parlante mais tout de même compréhensible. Sur la même image j'ai tracé le profil de fréquence en bar-graph de tous les buckets (i.e. de tout mes sous-ensembles de data) et du fichier data. Chaque colonne du bar-graph correspond à une valeur apparaissant dans le bucket, sa hauteur étant proportionnel à son taux d'apparition. On constate clairement que les tracés des buckets se chevauchent allégrement à gauche (i.e. : ils sont très similaires les uns aux autres et ils ne contiennent que peu de variété de valeurs différentes) alors que le fichier "data" entier, lui, contient une variété beaucoup plus grandes de valeurs (puisque son tracé est plus long) et que ces valeurs sont mieux réparties (le tracé est plus plat).

Analyse de fréquence du fichier "data" provenant du challenge SSTIC 2013 - Creative Common BYCCSA by ozwald from ozwald.fr

Arrivé à cette étape on a tout de même un bon nombre (deux ou trois) d'indices qui nous poussent dans la direction d'une clef de 16 octets paramétrant 16 bijections (ou "permutations") de l'ensemble des valeurs possibles d'un octet dans lui-même et qui sont appliquées successivement sur data. Maintenant il va falloir commencer à casser ces bijections...mais ça fera l'objet de prochains billets. Le prochain abordera d'ailleurs la possibilité des attaques en force brute, alors ne le manquez pas si vous aimez faire chauffer les [CG]PU ;)

  1. Les XOR sont très communs quand on veut faire un chiffrement informatique faible
  2. A quelques cas pathologiques près.
  3. Ce code fonctionne, je l'ai utilisé, mais il est TRES approximatif dans la démarche employée. Si vous voulez utiliser la méthode de Kasiski sans connaitre à l'avance la taille de la clef je vous conseille de ré-implémenter le tout de façon plus propre; je m'en voudrais de vous induire en erreur avec les résultats approximatifs de ce code expérimental.

Level up

Par Oz le - Perso
atmega eurobot robot électronique

Quasiment deux ans après mon dernier "level up" relaté sur ce blog j'en ajoute un nouveau obtenu début Mai : j'ai gagné un niveau en robotique grâce à une homologation réussie à la coupe de France 2013. Si on veut aller plus loin j'ai même gagné un second niveau en robotique grâce à un match gagné en coupe de France :) ! Comme pour le dernier "level up" cet article ne contiendra rien de passionant techniquement; si il n'y a que l'informatique qui vous passionne je vous conseille donc de zaper ce billet pour vous concentrer sur le précédent.

Eurobot - Coupe de France de robotique 2013 - équipe Planet Express - Creative Common CCBYSA by ozwald from ozwald.fr

Du 8 au 11 Mai dernier se déroulait donc la coupe de France de robotique à la Ferté-Bernard. J'y avais déjà participé à deux reprises en 2006 et 2007 mais nous n'avions malheureusement pas réussi à homologuer nos robots et, en plus, je ne comprenais rien à l'électronique mise en oeuvre à l'époque :( Depuis ces lointaines années j'ai "pas mal" progressé en électronique et il se trouve que cette année deux amis étaient motivés pour participer à la coupe de France avec moi (pour eux c'étaient leur première participation), nous avons donc tenté le coup.

Nous sommes arrivés dans la Sarthe le premier jour de la coupe avec un robot "quasiment terminé"1. Après un rapide tour des stands nos soupçons étaient confirmés : nous avions probablement le robot dont la mécanique faisait le plus pitié2 mais qu'importe, on était là pour s'amuser et homologuer. De façon prévisible nous avons rencontré pas mal de problèmes de dernières minutes et les "une ou deux heures" que nous estimions nécessaires pour rendre le robot opérationnel s'allongeaient tant et si bien que l'après-midi du deuxième jour de compétition nous n'avions toujours pas réussi à homologuer...

Eurobot - Coupe de France de robotique 2013 - équipe Planet Express, robot secondaire - Creative Common CCBYSA by ozwald from ozwald.fr

C'est alors que nous avons opté pour un "plan B" : le réglement de cette année autorisait l'utilisation de DEUX robots en même temps sur la table pour chaque équipe donc, pendant que notre electronicien-magicien s'acharnait à rendre notre premier (et unique) robot opérationnel, moi et le troisième larron nous sommes lancés dans la conception d'un second robot d'urgence qui pourrait nous permettre d'homologuer. En effet, pour que notre équipe soit homologuée il fallait qu'au moins un robot parvienne à quitter sa zone de départ et que l'équipe marque au moins un point. Notre robot principal n'avait aucun problème pour quitter sa zone de départ, mais il ne parvenait pas encore à marquer de points. Le cahier des charges du "robot" d'urgence a donc été réduit au strict minimum : inutile qu'il sache se déplacer, il doit juste marquer au moins un point. Là encore le réglement de cette année nous a facilité la tache puisqu'il était possible de marquer 12 points bonus juste en gonflant un ballon d'anniversaire3 au bout de 90 secondes de match. La conception du robot secondaire s'est donc imposée d'elle-même : un ventillateur de PC va gonfler un sac plastique de supermarché au bout de 90s; pour obtenir la puissance en 12V demandée par le ventillateur de PC nous avons soudé entre-elles une pile 9V et une pile 4.5V achetées au leader-price du coin; pour compter les 90s nous avons utilisé un atmega8 qui trainait dans ma boite à malices; pour convertir l'ordre de l'atmega en puissance pour le ventillo nous avons utilisé un simple transistor également en provenance de ma boite à malices; et pour fabriquer le "bouton d'arrêt d'urgence" obligatoire sur tout les robots de la coupe nous avons collé un bouchon de Coca Cola sur un bouton poussoir :) Avec un peu de cartons et quelques chutes de plexy par dessus ce bric-à-brac le robot d'urgence remplissait parfaitement sa mission : il répond à tout les critères de sécurité nécessaire pour être autorisé à participer et il gonfle bien un "ballon" (marquant 12 points) au bout des 90s réglementaires.

Nous nous sommes donc présenté une ultime fois à l'homologation et la magie a opérée : notre robot principal a, comme d'habitude, parfaitement quitté sa zone de départ puis il a échoué à toutes ses tentatives de marquer des points; mais le robot d'urgence a correctement gonflé son ballon au bout de 90s marquant 12 points pour le compte de l'équipe et scellant ainsi une homologation réussie :-D ! Champagne4 !

Une fois l'homologation en poche nous avons eu le droit de participer aux séries. Le premier match est sans appel : bug dans notre robot principal qui refuse de quitter sa zone de départ; aucun de nos deux robots n'ayant quitté sa zone de départ les points de gonflage de ballons ne sont pas comptabilisés et nous ne marquons donc aucun point. En face de nous un adversaire extrèmement sympathique avec un robot à la fois superbe et efficace nous colle une raclée 65 à 0. Quelques ajustements plus tard (en particulier une refonte mécanique complète du système de démarrage du robot principal et un recalibrage important de ses paramètres d'asservissements) nous participons à notre second match de série contre un adversaire tout aussi sympathique, avec un robot à la mécanique impressionante mais souffrant de gros problèmes électronico-informatique au moment de se présenter sur l'aire de jeu. Contraint par ses soucis électronico-informatique notre adversaire partait lui aussi sur une stratégie de secours consistant à uniquement sortir de sa zone de départ et gonfler un ballon; mais en n'utilisant qu'un seul et unique robot au lieu de deux. Enorme surprise de notre coté au bout de 20s de match : les ajustements faits sur le robot principal portent leur fruits et il parvient à marquer ses tout premiers 4 points5 ! Notre robot de secours gonfle bien son ballon au bout des 90s, tout comme notre adversaire qui empoche lui aussi les 12 points correspondants. Le score s'élève donc à 16 points contre 12 à la fin du match, nous empochons les 5 points de la victoire et notre adversaire le point de "non-forfait" ce qui porte le score final à 21 contre 13 : nous venons de remporter une victoire en coupe de France6 !

Cette victoire est d'autant plus savoureuse qu'en raison de contraintes diverses et variées nous devions quitter la coupe de France à l'issue de ce match, déclarant ainsi forfait pour les deux derniers matchs de série que nous aurions pu jouer. Au final nous resterons donc à la 136ème place (sur 146 possibles) ce qui dépasse notre objectif : nous avons homologué :) !

Qui sait, peut-être reviendrons nous l'an prochain avec un objectif plus ambitieux pour un nouveau level up ;) ...

  1. Expression consacrée de la coupe de France qui signifie "le robot ne marche pas mais avec beaucoup de café j'ai encore l'espoir de le faire marcher avant la fin de la compétition"
  2. Même les robots en LEGO avaient plus la classe que notre assemblage de bois/plexy/pistocolle
  3. Cette année le thème de la coupe était l'anniversaire puisqu'il s'agissait de la 20ième édition de la coupe
  4. Enfin...champomy en l'occurence puisque l'alcool était strictement interdit dans l'ensemble des batiments de la coupe :-(
  5. Quatres points qui illustrent d'ailleurs ce billet : sur la photo en tête de cet article notre robot vient d'ouvrir un "cadeau" en faisant basculer sa représentation en bois hors de la table
  6. Match "Robot-X" contre "Planet Express" : http://www.planete-sciences.org/robot/live/coupe2013/series/s3/

Dissection de programmes sous linux

Par Oz le - Geek
Hack LD_PRELOAD Linux Reverse Engineering algo gdb objdump

J'ai longtemps pensé que pour s'initier au reverse le chemin "standard" consistait à apprendre à débuguer ses propres programmes autrement qu'à coup de printf. Avec le recul je me dit qu'il y a beaucoup d'autres chemins, et j'ai bien envie de partager avec vous celui qui consiste à observer les programmes des autres :) J'avais déjà parlé de python-ptrace qui permet de faire des trucs très sympa, mais aujourd'hui on va découvrir ensemble beaucoup d'autres astuces d'ingénierie inverse dans le but d'analyser le fonctionnement d'une application flash. Accrochez votre ceinture et re-mobilisez toutes les connaissances de base que vous avez sur le fonctionnement d'un PC parce qu'il va y avoir de la variété dans les techniques (mal) employées dans cet article-fleuve !

Engin de chantier - Based on a Creative Common photo published by Elvert Barnes on Flickr

Un avertissement s'impose : je suis pentesteur de métier, pas réverseur, donc j'opère dans ce domaine en amateur et j'utilise certainement beaucoup de détours peu efficaces pour arriver au même résultat que ce qu'un pro obtiendrait de façon plus élégante et rapide. Donc si vous retenez quoique ce soit de cet article vous êtes maintenant prévenus : c'est de l'amateurisme et il y a certainement pleins de choses qu'il ne faut pas faire comme je vais l'exposer.

Plantons maintenant le décor. Slow Frog (un français !) expliquait en 2011 comment il avait écrit un bot en python pour jouer à sa place à un petit jeu flash consistant à tenir une pizzeria. Le jeu était simple et l'article très amusant. J'avais plus ou moins oublié cet article jusqu'à ce que je tombe sur une conférence de deux gars ayant codés des bots pour des jeux plus conséquents1 et je me suis alors dit que j'allais tenter le coup sur un jeu flash plus compliqué.

Petite digression à cette étape du récit : écrire un bot est probablement contre les CGU du jeu donc je ne vais pas le citer publiquement dans cet article (même si je doute que qui que ce soit ai envie de me chercher des noises pour avoir "triché" à un petit jeu flash). Sachez juste qu'il s'agit d'un jeu assez largement plus complexe que celui de la pizzeria, et qu'il fait intervenir un nombre non-négligeable d'information textuelle et/ou numériques.

Bref, je me suis donc dit que j'allais tenter d'écrire un bot pour ce petit jeu flash juste pour vérifier si j'en étais bien capable. La première optique emprunté était la plus intuitive : l'approche graphique. Le concept est simple : je prends un screenshot, puis je l'analyse. Pour ce faire j'ai mobilisé 3 briques logicielles de bases :

Ce qui m'a posé le plus de problème s'est avéré sans conteste la lecture des textes. En effet, la police utilisée était petite ce qui rendait la lecture difficile et les erreurs n'étaient pas rare (l'OCR se plantait environ une fois sur dix...ce qui est énorme dans le contexte du jeu qui m'intéresse). J'ai donc codé des vérification de cohérences entre chaque intervention de l'OCR, ce qui a pas mal aidé mais ne donnait toujours pas un résultat parfait. Après plusieurs mois à améliorer le système de temps en temps j'ai obtenu un taux de succès de 100% d'identifications correctes sur les icones diverses du jeu, mais toujours pas un taux de reconnaissance acceptable sur les informations textuelles. J'ai donc laissé tombé le projet, lassé de voir mon bot prendre des décisions farfelues toutes les 5mn sur la base d'information mal lues.

Plusieurs mois après je me suis remis à la tache, en décidant d'intercepter les communications entre le jeux flash et le serveur du jeu plutôt qu'en essayant de "lire" l'écran. En effet, l'information transmise par le serveur est déjà dans un format compréhensible par un logiciel, autant en profiter. Autre avantage de cette technique : les outils impliqués sont ceux que j'ai l'habitude de manier lorsque je fais des pentests web. Aussitôt pensé aussitôt fait : j'intercale un proxy d'interception entre mon navigateur web et internet. Déception : le jeu refuse de démarrer. Je passe le proxy en transparent : même problème. Je fabrique ma propre autorité de certification racine, je l'intègre aux autorité de confiance de mon navigateur, puis de mon OS, et je l'utilise pour générer dynamiquement les certificats SSL bidons à présenter au navigateur4. Hélas, j'ai toujours le même problème : le jeu flash refuse catégoriquement de contacter le serveur de jeu via mon proxy. Tristesse, déception, et incompréhension.

Qu'à celà ne tienne, je n'ai qu'à descendre plus bas dans l'OS pour intercepter ces communications réseau ! L'astuce à laquelle je pense alors est celle de LD_PRELOAD. Sous linux la variable d'environnement LD_PRELOAD permet de forcer le chargement d'une librairie partagée avant toutes les autres, ce qui autorise la surcharge de fonctions issues des librairies légitimes. Par exemple si je code une fonction printf puis que je la compile dans une librairie partagée et que je force le chargement de cette librairie en priorité via LD_PRELOAD, l'ensemble des processus que je lancerai ensuite feront appel à mon implémentation de printf plutôt qu'à celle de la libc :) L'idée derrière cette astuce c'est de surcharger les fonctions de communication réseau pour intercepter les informations envoyées et reçues dans le tunnel SSL5.

Pour mettre en place cette astuce il va falloir que j'identifie quelles sont les fonctions susceptibles d'êtres utilisées par le jeu pour ses communications. Normalement la commande ltrace permet de tracer (i.e. afficher) l'ensemble des appels à des fonctions de librairies partagées qu'un programme effectue. L'utilisation aurait donc été immédiate dans mon cas : je lance ltrace sur le processus du plugin-container de firefox faisant tourner le jeu, je cherche dans les fonctions qui sont affichées celles qui ont un lien avec des communications SSL, puis je les re-code afin de les surcharger avec LD_PRELOAD pour intercepter les informations en transit. Oui mais voilà : chez moi ltrace fait systématiquement planter firefox :( . J'ai essayé de restreindre son champs d'investigation en ne demandant que les fonctions de certaines librairies (pensant que, peut-être, c'était la latence ajoutée qui faisait planter le soft) mais rien n'y fait : impossible d'utiliser ltrace :(

De déception j'ai alors tenté de tracer uniquement les appels systèmes (avec le plus standard strace), ce qui a marché à merveille. Malheureusement je me suis retrouvé noyé dans une tonne d'appel système avec peu d'espoir d'y trouver quoi que ce soit en rapport avec SSL de toute façon.

Après cette mini digression vers les appels système je suis retourné aux librairies partagées. Si je ne pouvais pas tracer les appels effectivement réalisés, je pouvais au moins tenter de les deviner. Pour ce faire j'ai dumpé la table de liaison dynamique du plugin flashplayer grace à la super commande objdump6 :

$ objdump -T /opt/Adobe/flash-player/flash-plugin/libflashplayer.so

/opt/Adobe/flash-player/flash-plugin/libflashplayer.so:     file format elf32-i386

DYNAMIC SYMBOL TABLE:
00000000      DF *UND*  00000000  GLIBC_2.1   iconv
00000000      DF *UND*  00000000              gtk_main_iteration
00000000      DO *UND*  00000000              gtk_major_version
...
00000000      DF *UND*  00000000  NSS_3.4     CERT_DecodeCertFromPackage
00000000      DF *UND*  00000000              gdk_window_set_back_pixmap
00000000      DF *UND*  00000000              gdk_screen_get_display
00000000      DF *UND*  00000000              XFreeGC
00000000      DF *UND*  00000000              gtk_entry_get_text

L'option "-T" d'objdump affiche la liste des fonctions importées par le soft ciblé, ainsi que, parfois, la librairie dont elle est tirée. En lisant ces importations je n'ai réussi à identifier qu'un seul appel interessant pour l'interception de communications chiffrées : PR_Read7. Tant mieux pour moi, ça ne fait qu'un "suspect" à auditionner ! Pour la petite histoire sachez que cette fonction fait partie des utilities fournis par le framework Mozilla et qu'elle permet de lire dans une socket abstraite (qu'elle soit dotée d'une couche SSL ou non ne change pas l'appel à la fonction). Voici donc la surcharge que j'ai écrite :

#define _GNU_SOURCE //obligatoire pour utiliser "dlsym" qui n'est à priori pas POSIX. Plus d'info ici : http://linux.die.net/man/3/dlopen
#include <prio.h> //Pour avoir les headers mozilla
#include <stdint.h> 
PRInt32 PR_Read(PRFileDesc *fd, void *buf, PRInt32 amount) {
    // D'abord je retrouve la "vrai" fonction PR_Read
    static PRInt32 (*real_PR_Read)(PRFileDesc*, void*, PRInt32) = NULL;
    real_PR_Read = dlsym(RTLD_NEXT, "PR_Read");
    // Maintenant j'appelle la "vrai" fonction PR_Read
    PRInt32 res = real_PR_Read(fd, buf, amount);

    // Enfin je stocke les données reçus si jamais il y en a.
    if (res>0){
        FILE* f = fopen("/tmp/debug.log","a");
        fprintf(f, "PR_Read : %d\n",res);

        int i; char* mybuf = (char*) buf;
        fprintf(f, "<<<\n");
        for (i=0; i<res; i++) {
            if ((mybuf[i]>8) && (mybuf[i]<127)) {
                fprintf(f, "%c", mybuf[i]);
            } else {
                fprintf(f, "%x", mybuf[i]);
            }
        }
        fprintf(f, "\n>>>");
        fclose(f);
    }
    return res; // Et, bien sur, je retourne le résultat renvoyé par la "vrai" fonction PR_Read
}

La ligne de compilation ressemble à ça : gcc -O2 -I/usr/include/nspr -I/usr/include/nss -shared -ldl -fPIC -o surcharge.so surcharge.c

Les deux -I sont pour avoir les includes de prio.h (en fait je n'ai besoin que de l'un des deux, mais je ne sais plus lequel donc, de paresse, j'ai laissé les deux). Le -shared c'est parce que je veux compiler en librairie partagée, le -fPIC c'est pour obtenir du code qui fonctionne indépendament de sa position en mémoire (je me demande si le -shared n'inclus pas cette option d'ailleurs...) et le -ldl c'est pour être linké avec la librairie de link permettant de retrouver les fonctions originales que je surcharge via dlsym.8

Une fois compilé en *.so l'utilisation de ma fonction d'interception se fait comme ça :

$ export LD_PRELOAD="/home/ozwald/surcharge/surcharge.so"
$ firefox http://urldujeu.lan #Là on utilise normalement son programme
$ unset LD_PRELOAD # Une fois qu'on a fini on supprime la variable LD_PRELOAD pour que tout redevienne normal

Bonne surprise : quand j'utilise firefox mon fichier /tmp/debug.log contient bien des informations ! Mauvaise surprise : les informations contenues sont (très ? (trop ?)) nombreuses et à priori sans aucun rapport avec les actions du jeu (grace à un tail -f j'ai pu constater que, souvent, des actions se déroulaient au niveau du jeu mais ne déclenchaient aucune écriture dans le fichier de log). Déception...je n'ai visiblement pas intercepté la bonne fonction.

Appliquant le proverbe orc "quand ça ne marche pas en poussant, pousse plus fort" j'ai décidé de surcharger plus de fonctions. J'ai donc fait un plus simple objdump -x sur le plugin flash pour obtenir la liste des librairies linkées au lieu des fonctions. Dans le tas j'ai trouvé plusieurs librairies relatives à la communication et/ou au SSL :

Dynamic Section:
...
  NEEDED               libssl3.so
  NEEDED               libnss3.so
  NEEDED               libnssutil3.so
  NEEDED               libnspr4.so
...

Partant de cette liste j'ai identifié plusieurs fonctions appartenant à ces librairies et qui pourraient tremper dans de la communication. J'ai donc surchargé : PR_Read, PR_Recv, SSL_read, BIO_read, et BIO_gets !

Comme on pouvait s'y attendre ça a été un échec pitoyable. Aucune de ces fonctions additionnelles n'est utilisée par le jeu :(

La méthode orc ne fonctionnant visiblement pas j'ai opté pour...la méthode orc ! "Quand ça ne marche pas en poussant, pousse plus fort" (je suis parfois tétu), donc j'ai surchargé strncpy, strcpy, recv, fread, read, strtok, XDrawString, et Xutf8DrawString.

Cette méthode "très subtile" m'a octroyé une petite victoire : j'obtient des informations qui semblent correspondre aux évènements du jeu. Visiblement certaines de ces fonctions sont utilisées pour peupler la petite fenêtre de log qui résume les évènements de jeu en bas d'écran; donc j'obtient pas mal d'informations! Malheureusement je me suis vite rendu compte que celà ne suffirait pas pour écrire un bot robuste. En effet certaines informations étaient manquantes, il y avait énormément de "bruit", et la cohérence temporelle n'était pas assurée (i.e. certains évènements m'étaient remontés dans un ordre différent de ceux dans lequel ils se produisaient dans le jeu...je blame le multithread sur le coup).

Là j'ai l'impression d'être face à un mur... Devant mon incapacité à expliquer l'échec de la surcharge de PR_Read & co ainsi que l'échec silencieux de la méthode d'interception via proxy avec un certificat SSL pourtant "valide" je me suis dit que, peut-être, c'était le plugin flash qui faisait de la magie noire. Je me suis donc renseigné et j'ai trouvé Gnash et Lightspark qui sont deux logiciels complémentaires réalisant une implémentation libre d'un interpreteur flash. Rien de tel qu'un logiciel libre pour comprendre le fonctionnement de quelque chose donc j'ai installé gnash / lightspark et j'ai tenté de lancer le jeu. Malheureusement lightspark a planté :-( C'était prévisible de la part d'un logiciel jeune et dont les spécifications proviennent en grande partie de difficiles efforts d'ingénierie inverse du plugin flash officiel. J'ai forcé un petit peu dans cette voie en récupérant les versions de dévelopement9 de gnash et lightspark et j'ai re-tenté le coup avec les même résultats (i.e. plantage de lightspark).

Je me retrouve donc encore une fois coincé...une nouvelle approche s'impose ! Je vais dumper la mémoire du processus grace à /proc/PID/maps et /proc/PID/mem dans l'espoir de trouver des choses intéressantes. Dans l'esprit j'étais parti pour faire quelque chose à la memory eye en fait.

Pour ceux qui l'ignore voici un petit résumé de l'esprit des fichiers que je vais utiliser : Sous linux le pseudo-système de fichier /proc/ contient pleins d'information sur le fonctionnement en cours du système. Par exemple /proc/cpuinfo contient des informations sur votre processeur. Chez moi il contient ça :

$ cat /proc/cpuinfo
processor   : 0
vendor_id   : AuthenticAMD
cpu family  : 16
model       : 6
model name  : AMD Athlon(tm) II X2 250 Processor
...

En l'espèce nous allons nous intéresser aux fichiers /proc/PID/maps et /proc/PID/mem. Le plus simple à comprendre est /proc/PID/mem puisqu'il contient simplement la mémoire totale du système telle qu'elle est vue depuis le processus d'id PID. La mémoire adressable étant gigantesque nous allons cibler nos recherches grace à /proc/PID/maps qui contient la liste des segments de mémoire adressable qui sont effectivement alloués et accessibles par le processus en question. Pour faire un test vous pouvez lancer une commande less sur un fichier quelconque (ou juste un top, comme vous préférez), récupérer son PID grace à ps aux | grep NomDeVotreCommande puis faire un cat sur le /proc/PID/map correspondant. Voilà ce que ça donne chez moi (j'ai lancé un top dans un autre shell):

$ ps aux | grep [t]op
ozwald    9064  0.0  0.0   2700  1136 pts/0    S+   12:33   0:17 top
$ cat /proc/9064/maps
08048000-08055000 r-xp 00000000 03:02 730853     /usr/bin/top
08055000-08056000 r--p 0000c000 03:02 730853     /usr/bin/top
08057000-0807b000 rw-p 00000000 00:00 0          [heap]
...
b76f1000-b76f2000 rw-p 00185000 03:02 938394     /lib/libc-2.15.so
...
b7739000-b773a000 rw-p 00044000 03:02 417799     /lib/libncurses.so.5.9
...
bfc5c000-bfc7e000 rw-p 00000000 00:00 0          [stack]
...

Comme vous pouvez le voir nous obtenons des informations pour chaque plage allouée. En particulier nous avons :

  • l'adresse de début (0xbfc5c000 pour la stack par exemple)
  • l'adresse de fin (0xbfc7e000 pour poursuivre notre exemple de la stack)
  • les permissions ("rw-p" pour la stack)

Nous pouvons donc à présent cibler toutes les plages qui sont à la fois "R"eadable et "W"ritable par le processus, et y chercher des élèments parlant. Pour lire le contenu de ces zones mémoire il suffit d'ouvrir /proc/PID/mem en lecture seule, puis de faire un seek jusqu'à l'offset de début de plage, et à y lire autant d'octets que la taille de la plage. Le petit script python10 ci-dessous permet de dumper les plages mémoire du processus dont on passe le PID en paramètre :

#! /usr/bin/env python
import re
import sys
if len(sys.argv) != 2 :
    print "Merci de donner un PID en argument"
    print "Usage : %s PID"%sys.argv[0]
    sys.exit(1)

mypid=sys.argv[1]
mypid=str(mypid)
sys.stderr.write("PID = " + str(mypid) )
maps_file = open("/proc/"+mypid+"/maps", 'r')
mem_file = open("/proc/"+mypid+"/mem", 'r', 0)
for line in maps_file.readlines():  # for each mapped region
    m = re.match(r'([0-9A-Fa-f]+)-([0-9A-Fa-f]+) ([-r][-w])', line)
    if m.group(3) == 'rw':  # if this is a writeable region
        sys.stderr.write("\nOK : \t" + line+"\n")
        start = int(m.group(1), 16)
        if start > 281474976710655 :
            continue
        end = int(m.group(2), 16)
        sys.stderr.write( "start = " + str(start) + "\n")
        mem_file.seek(start)  # seek to region start
        chunk = mem_file.read(end - start)  # read region contents
        open("%d.dump"%start,'w').write(chunk) # dump contents to a file
    else :
        sys.stderr.write("\nPASS : \t" + line+"\n")
maps_file.close()
mem_file.close()

Bon, avec un tel outil les perspectives d'analyse sont démultipliées ! Je lance donc le jeu, récupère le PID de l'interpreteur flash officiel via un ps aux | grep [f]lash, et dump le contenu de sa mémoire en invoquant le script ci-dessus. Je me retrouve avec quelques dizaines de fichiers de dump, chacun correspondant à une plage mémoire. Après quelques grep bien sentis11 j'identifie des structures JSON qui semblent contenir des éléments de jeu et qui ressemblent à ça :

GameEvent:ClientArrival { "ClientID":"123", "ClientName":"Roger", ..}
GameStatus:OrdersWaiting { "Orders":[ {"ClientID":"123", "Product":"Pizza", ...}, {}, ..., {}] }

L'espoir renait parce que ces structures sont très intéressantes : d'une part elles contiennent toutes les informations dont j'ai besoin pour écrire un bot, et d'autre part le fait qu'elles soient en JSON me laisse penser qu'il s'agit bien là de l'information échangée en réseau dans le tunnel SSL et sur laquelle j'essaie de mettre la main depuis le début. J'ai donc creusé dans cette voie pour, finalement, obtenir un script python qui fonctionne en deux temps :

  1. Il identifie la zone mémoire où sont les structures JSON
  2. Une fois la zone identifiée avec certitude il dump cette zone en boucle en guettant des changements (ce qui signifierait l'arrivée d'un nouveau paquet d'information en provenance du serveur et donc l'arrivée d'un nouvel élément de jeu tel qu'un client).

La qualité d'information que j'ai obtenu avec ce script est exemplaire puisque, contrairement à la lecture de l'écran par OCR, je n'ai aucune erreur sur le contenu des texte. Malheureusement, lorsque plusieurs évènements se suivent très rapidement dans le temps (comme deux clients qui rentrent quasiment en même temps dans la pizzeria) mon script ne perçoit que l'un des deux évènements et rate l'autre qui se fait écraser en mémoire entre deux dumps. Il fallait s'y attendre puisque je fait du "poll" sur la mémoire au lieu d'avoir obtenu un système en "push" comme me le permettrait la surcharge d'une fonction par LD_PRELOAD :(

N'ayant pas envie d'abandonner j'ai poursuivi dans une "voie du milieu12" tirant partie de plusieurs des travaux effectués jusqu'à présent. Lorsque je dumpais les structures JSON directement depuis la mémoire j'ai remarqué que l'adresse où étaient les structures intéressantes ne bougeait quasiment jamais lors d'une même partie. Ces structures JSON n'arrivant pas là par magie (à moins que le plugin flash officiel pratique réellement la magie noire...) je me suis dit qu'identifier la fonction responsable de l'écriture de cette structure serait très intéressant puisque je pourrait peut-être la surcharger avec LD_PRELOAD.

La démarche que j'ai adopté a donc été la suivante :

  1. Lancer une partie
  2. Identifier le PID de l'interpreteur flash par ps aux | grep [f]lash
  3. Dumper la mémoire du processus et identifier l'adresse d'une structure JSON d'intérêt
  4. Attacher gdb au processus de l'interpreteur flash
  5. Poser un breakpoint sur les écritures à l'adresse de la structure JSON
  6. Afficher, automatiquement lors du déclenchement de ce breakpoint, le contenu de la mémoire (pour vérifier si j'ai bien une structure JSON comme je le pensait) ainsi que la backtrace des 4 derniers appels.

L'objectif de ce protocole étant d'identifier quelle partie de code est responsable de l'écriture de ces structures. En termes de commande voici ce que ça a donné :

$ ps aux | grep [f]lash
ozwald    9064  0.0  0.0   2700  1136 pts/0    S+   12:33   0:17 flash-plugin
$ python memory_dump_and_seek.py 9064
Dumping...
Seeking json...
The json object is at address 0xaa72f000
$ gdb
(gdb) attach 9064
(gdb) watch *0xaa72f000
Hardware watchpoint 1: *0xaa72f000
(gdb) commands 1
>silent
>x/1s 0xaa72f000
>bt 4
>cont
>end
(gdb) cont
Continuing.
0xaa72f000: "GameEvent:ClientArrival { "ClientID":"123", "ClientName":"Roger", ..}...
#0  0xb584c026 in ?? () from /lib/libc.so.6
#1  0x00000277 in ?? ()
#2  0xb2b2c1d9 in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
#3  0xb2b33f9b in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
0xaa72f000: "GameEvent:ClientArrival { "ClientID":"124", "ClientName":"Paul", ..}...
#0  0xb584c026 in ?? () from /lib/libc.so.6
#1  0x00000277 in ?? ()
#2  0xb2b2c1d9 in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
#3  0xb2b33f9b in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
0xaa72f000: "GameEvent:ClientArrival { "ClientID":"125", "ClientName":"Jean", ..}...
#0  0xb584c026 in ?? () from /lib/libc.so.6
#1  0x00000277 in ?? ()
#2  0xb2b2c1d9 in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
#3  0xb2b33f9b in ?? () from /opt/Adobe/flash-player/flash-plugin/libflashplayer.so
...

Voilà qui sent bon. A chaque interruption :

  • la zone mémoire contient bien ce qui ressemble à une structure JSON valide
  • la backtrace est systématiquement la même
  • cerise sur le gateau : la dernière instruction appelée (i.e. celle qui est responsable de l'écriture mémoire) appartient à /lib/libc.so.6 et sera donc surchargeable via LD_PRELOAD (alors que si ça avait été une fonction interne à l'interpreteur flash j'aurai été plus ennuyé).

Par contre ce qui me surprend à ce moment là c'est que j'avais déjà fait des tentatives infructueuses en surchargeant une bonne pelleté de fonctions de la libc (strcpy et strncpy en particulier, souvenez-vous du début de cet article...il y a 3 pages :D ). Quelle fonction de la libc peut donc être responsable de ces écritures ? A cette étape je suis certain qu'un gourou de gdb pourrait répondre en une commande. Malheureusement je ne suis pas un gourou de gdb :( J'ai bien tenté de demander gentimment, mais sans succès :

(gdb) info symbol 0xb584c026
No symbol matches 0xb584c026.

Bon..."Quand ça ne marche pas en poussant, pousse plus fort" donc je vais adopter, encore une fois, une technique très subtile :

  1. Tout d'abord on active l'enregistrement des sorties de gdb dans un fichier texte, en prévision d'un gros tas de donnée à traiter : set logging on
  2. On demande à gdb d'afficher TOUTES les fonctions que le processus connait13 : show functions.

Une fois ceci fait on quitte gdb et on se retrouve avec un fichier gdb.txt qui contient les logs de la session retranscrivant ce que nous avons eu sur la sortie standard et ressemblant à ça :

All defined functions:

Non-debugging symbols:
0x08049290  _init
0x080492b8  strerror_r@plt
0x080492c8  abort@plt
0x080492d8  sysconf@plt
...
=== NDLR : environ 40 000 lignes plus tard ===
...
0xb470e8f0  _nss_dns_getnetbyaddr_r
0xb470ec40  _nss_dns_getcanonname_r
0xffffe400  __kernel_sigreturn
0xffffe40c  __kernel_rt_sigreturn
0xffffe414  __kernel_vsyscall

Avec ces informations, retrouver la fonction que je cherche est simple comme bonjour puisqu'un grep et un sort suffisent. Pour rappel je cherche la fonction de la libc qui contient l'adresse 0xb584c026 puisque c'est l'instruction à cette adresse qui est responsable de l'écriture de la structure JSON que je recherche à l'adresse 0xaa72f000 :

$ grep -E 0xb584[bc] gdb.txt | sort -u
...
0xb584bea0  __strncasecmp_l
0xb584bea0  strncasecmp_l
0xb584bf20  memccpy
0xb584bf80  memcpy
0xb584c680  __strsep_g
0xb584c680  strsep
...

La coïncidence est trop belle : c'est memcpy le "coupable" (puisque 0xb584bf80 < 0xb584c026 < 0xb584c680) ! Il ne me reste donc plus qu'à surcharger memcpy pour vérifier la théorie. Attention cependant : surcharger strcpy et strncpy ne constituait pas vraiment un risque (ces fonctions sont censées traiter des chaines de caractères), mais surcharger memcpy est bien plus audacieux. En effet, memcpy est d'un usage beaucoup plus versatile et tout aussi courant (si ce n'est beaucoup plus). Quelques précautions s'imposent donc lors de l'écriture de la surcharge afin de s'assurer que l'on ne va intercepter que les mouvements de mémoire qui nous intéresse. D'une part ça nous facilitera le traitement des données interceptées et, d'autre part, ça va permettre de limiter le ralentissement des processus que nous surveillons même s'ils font très souvent appel à memcpy. J'ai donc adopté les précautions suivantes :

  • Je n'ai utilisé aucune tournure qui pourrait faire appel à une primitive memcpy lors de l'optimisation du compilateur (je ne sais pas s'il y a un risque d'appel récursif, mais je préfère ne pas tenter).
  • J'ai utilisé un fichier de dump différent par processus et par thread afin d'éviter les problèmes d'accès concurrents (j'aurai pu jouer avec des mutex, mais ça aurait potentiellement ralenti le schmilblick et puis c'est plus long à coder)
  • J'ai fait attention à ne pas trop introduire de bug dans mon code. Ca a l'air évident mais ça ne coute rien de le rappeler. Par exemple : avant d'accéder aux éléments de csrc pour vérifier si la zone mémoire copiée commence bien par la chaine de caractère que je veux ("Game") je m'assure que csrc contient au moins autant de caractères que ce que je vais lire...

Bref, voilà le code :

#include <sys/syscall.h> //for gettid
#include <sys/types.h> // this and below for getpid
#include <unistd.h>
void *memcpy(void *dest, const void *src, size_t n){
    static void* (*real_memcpy)(void* , const void*, size_t) = NULL;
    real_memcpy = dlsym(RTLD_NEXT, "memcpy");

    const char* csrc = (const char*) src;

    if ((n>4) && (csrc[0]==71/*G*/) && (csrc[1]==97/*a*/) && (csrc[2]==109/*m*/) && (csrc[3]==101/*e*/)){
        int write_this_much = 0;
        // I only want printable ascii :
        while ((write_this_much<n) && (csrc[write_this_much]>31) && (csrc[write_this_much]<127) ) { write_this_much++; }

        // Un fichier par processus et par thread :
        char filename[128];
        snprintf(filename,128,"/tmp/debug_%d_%d.log\0", (int)getpid(), (int)syscall(SYS_gettid) );

        FILE* f = fopen(filename,"a");
        fprintf(f, "memcpy : <<< ");
        fwrite(csrc, 1, write_this_much, f);
        fprintf(f, ">>>\n");
        fclose(f);
    }
    return real_memcpy(dest, src, n);
}

Malgré toutes ces précautions lorsque j'utilise ma surcharge en déclarant la librairie dans LD_PRELOAD firefox crashe lamentablement au démarrage :-( ...Et c'est là que j'ai un gros coup de chance : chromium-browser, lui, fonctionne comme si de rien n'était14 :) ! Je ne sais même pas pourquoi j'ai essayé sur chromium cette fois-là alors que je n'avais fait aucun test dessus auparavant, mais je m'en félicite ;)

Bon, avec un navigateur qui marche je vais sur le jeu flash, et je me fait une petite partie. Une fois la partie terminée j'ouvre /tmp/debug_8613_8613.log et je constate avec joie qu'il contient l'ensemble des structures JSON que je voulais ! Aucune corruption, à priori aucun manque, et l'ordre semble correct.

En conclusion donc : j'en aurai bien ch*é pour arriver à ce résultat et je ne comprends pas encore tout (pourquoi firefox plante-t-il ? Est-ce-que le plugin flash embarque sa propre librairie SSL ?? Pourquoi ltrace fait-il planter les softs qu'il surveille ? etc.), mais j'ai également appris beaucoup (dumper proprement la mémoire d'un process, définir les commandes à lancer automatiquement quand gdb déclenche un breakpoint, définir un breakpoint sur une écriture en mémoire, ...) et surtout : J'ai réussi à faire ce que je voulais15 :-D !!!

  1. Eux, avaient une motivation pécuniaire, contrairement à Slow Frog.
  2. En guise de rafinnement je prenais le screenshot dans un répertoire appartenant à un volume monté en tmpfs histoire d'être certain de ne pas fatiguer le disque par les écritures de screenshot répétées
  3. J'ai également testé tesseract, un autre logiciel de reconnaissance de caractère (OCR), mais j'ai trouvé qu'il donnait globalement des résultats moins bons.
  4. Merci OpenSSL et BURP :)
  5. Avec cette même fonctionnalité de LD_PRELOAD certains ont réalisé des keylogger, des rootkits, etc.
  6. Vous pouvez également utiliser nm -D à la place de objdump -T
  7. Je ne connaissais pas cette fonction avant de tomber dessus lors de ces recherche, je l'ai donc identifiée par tatonnement.
  8. Pfiou ça en fait des options de gcc...J'espère que je n'ai pas dit trop de bétises d'ailleurs :-D
  9. J'aime bien l'expression "bleeding edge" plutôt que "version de développement", mais bon...limitons les anglicismes quand ils ne sont pas nécessaires ^^
  10. Script largement pompé depuis le net; googlez pour retrouver la source originale, je ne l'ai malheureusement pas noté.
  11. Par exemple j'ai lancé des grep sur le nom des clients de la pizzeria que je pouvais voir à l'écran lors du dump de la mémoire.
  12. Comme le diraient certains sages.
  13. Attention, dumper l'ensemble des fonctions retourne beaucoup de résultats et ça peut donc prendre du temps. Dans mon cas pratique celà signifiait que le freeze du jeu était assez long pour me faire perdre la partie. Etant donné que l'adresse d'enregistrement des JSON changeait à chaque démarrage de partie, dumper les fonctions devait être la dernière étape de mon processus d'analyse :)
  14. En fait chromium-browser rame assez notablement, mais il fonctionne sans montrer la moindre envie de planter.
  15. Bon, il me reste à remplacer les fichiers par des tubes nommés (mkfifo) puis à écrire la partie logicielle qui va lire le flux d'information en temps réel dans ces tubes, puis à écrire la partie "IA" qui va décider comment jouer, puis à écrire la partie qui va envoyer les actions au jeu...Mais le plus difficile est fait, si si je vous jure ;) D'ailleurs, le plus difficile étant fait, je ne sais pas si ça m'intéresse encore de terminer ce projet lol

« Page 2 / 11 »