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.

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 anglais¹) permet de visualiser les bits forcés à 0 quand on encode le mot "Man" en base64 (ce qui donne "TWFu") :

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é :-D² 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 ↩