Ce billet est le dernier d'une série de 4 portant sur l'analyse à postériori de l'étape 2 du challenge SSTIC 2013. Si vous n'avez lu aucun des billets précédents je vous invite à lire au moins l'introduction du premier avant de plonger dans celui-ci. Si vous avez lu les billets précédents : félicitations, vous arrivez au bout du tunnel :) !

Les classiques

Dans les billets précédents j'ai avancé pas mal dans la cryptanalyse de data mais je reste encore relativement loin de la solution. Il est probable qu'en forçant dans cette voie je finisse par obtenir la bonne solution, mais il est temps d'explorer une autre voie ! Jusqu'à présent j'ai beaucoup avancé par recettes persos en tirant parti de mes connaissances sur la crypto du 19ème siècle et antérieur, mais je pense qu'il est temps de se pencher sur ce qui se fait dans les attaques crypto un peu plus modernes.

J'ai donc raffraichi pas mal de vieux souvenirs de cours et j'ai éliminé une à une toutes les attaques modernes.

• La cryptographie différentielle ? Elle se matérialise généralement sous la forme d'une attaque par clair choisi, or moi je n'ai pas d'implémentation du chiffreur donc ce n'est pas possible.
• La cryptographie linéaire ? Même punition, même motif.
• L'attaque boomerang ? Idem.

Au final je me suis dit que je ne trouverai pas de protocole d'attaque "tout prêt" utilisable dans mon cas. Tout ce temps n'était pas perdu pour autant ! A force de lire toutes ces méthodes d'attaques, et les descriptifs des chiffrements attaqués, j'ai réalisé que le schéma SBox-PBox-XOR était vraiment très, très, très répandu et que les SBox tenait un rôle de première importance dans la force du chiffrement. Je me suis alors dit : "et si on était en face d'un algorithme de chiffrement de ce type, particulièrement nul ?". Le "particulièrement nul" était légitime, puisque c'était notre hypothèse de base depuis le départ (après tout c'est un challenge, on est censé pouvoir le casser !). Sur wikipédia on vous explique que l'une des caractéristiques les plus essentielles des SBox c'est de générer beaucoup de changements de bit (environ 1 sur 2) quand on change un seul bit en entrée; j'ai donc supposé qu'on avait à faire à une SBox tellement nulle qu'elle changeait un seul bit quand on changeait un seul bit en entrée :)

Ce bon vieux Hamming

En formulant cette hypothèse de faiblesse de la SBox, je ne sais pas pourquoi, j'ai immédiatement pensé à la distance de hamming : si je prends deux octets qui diffèrent d'un seul bit, et que je les passe dans ma mauvaise SBox, leur représentation chiffrée diffèrerons, elles aussi, d'un seul bit ! Ce qui devient vraiment sympa c'est que, lorsque je passerai ces représentation chiffrées dans la PBox, les deux octets résultants diffèreront, eux aussi, d'un seul bit entre eux (une PBox se contente de ré-ordonner les bits de façon déterministe). La cerise sur le gateau c'est que si j'applique un XOR à mes deux sorties de SBox, les deux octets que j'obtiendrai diffèreront, encore une fois, d'un seul bit ! En bref : si la SBox est aussi nulle que je l'ai supposé, deux octets ayant une distance de hamming de 1 seront chiffrés (par tout l'algorithme de chiffrement) en deux octets ayant une distance de hamming de 1 entre eux.

Arrivé à ce point j'ai fait une petite généralisation illégitime : si la SBox est vraiment pourri, peut-être que la distance de Hamming est laissée invariante par l'application de l'algorithme de chiffrement. Formulé comme ça, ça n'a pas forcément l'air super excitant, mais en fait, ça pourrait devenir essentiel. En effet, je sais que mon texte d'origine est en base64 et qu'il contient donc un sous-ensemble des valeurs possibles d'un octet. Peut-être qu'avec un peu de chance l'ensemble des distances de Hamming d'un élément de l'alphabet base64 aux autres éléments de ce même alphabet est caractéristique ? Peut-être pourrais-je donc me servir de cet "ensemble des distances aux autres éléments de l'alphabet" comme d'une espèce d'empreinte digitale.

Pour vérifier cette seconde hypothèse (i.e. : que l'ensemble des distances est partiellement caractéristique) j'ai tracé, pour chaque élément de l'alphabet base64, une droite horizontale composé de rectangles colorés. Chaque rectangle coloré correspond aux éléments de l'alphabet distant de la distance X de mon élément de référence (X étant écrit sur le rectangle coloré). Je vous mets l'image ci-dessous et je vais expliquer la première ligne ensuite, ça sera sans doute plus clair comme ça :

La première ligne de cette image montre "l'empreinte digitale" de la lettre de code ascii "0xa" (c'est à dire du caractère "retour charriot") dans l'alphabet base64. On voit que ce caractère:

• n'est distant d'une distance 0 que d'un seul autre élément de l'alphabet base64 (à savoir : lui-même)
• est distant d'un unique caractère de l'alphabet base64 d'une distance de 1
• est distant de 7 caractères de l'alphabet base64 d'une distance de 2
• est distant de 16 caractères de l'alphabet base64 d'une distance de 3
• ...
• est distant d'un seul caractères de l'alphabet base64 d'une distance de 7

En regardant l'image dans son ensemble on a l'impression qu'il n'y a pas deux lignes qui soient identiques. C'est une bonne nouvelle pour nous : notre élément caractérisant (i.e. : l'ensemble des distances de Hamming aux autres éléments de l'ensemble) est bel et bien caractérisant puisqu'unique à chaque symbole de l'alphabet base64 !

Je vais donc pouvoir tracer les "empreintes de Hamming" des octets chiffrés de data et en tirer des conclusions. Malheureusement, nous avons vu que nos buckets ne contiennent qu'environ 55 valeurs différentes (au lieu des 65 possibles) et mes empreintes seront donc partielles...Je ne vais ainsi sans doute pas pouvoir faire d'identification immédiates, mais je vais au moins pouvoir faire des éliminations. En effet je sais que si je trouve une distance de Hamming de 7 entre deux octets chiffrés ceux-ci appartiendront forcément à l'ensemble des clairs qui possèdent au moins une distance de Hamming de 7; de même si je trouve un octet qui a deux distance de Hamming de 1 il ne peut correspondre qu'aux clairs qui ont au moins deux distances de Hamming de 1; et ainsi de suite.

En appliquant cette méthode j'obtient une réduction drastique du problème. Pour beaucoup d'octets chiffrés je me retrouve avec moins de 10 clairs possibles. C'est donc une bonne avancée, mais c'est insuffisant. Comment aller plus loin ? En triangulant :) ! Après tout, nous avons une propriété de conservation d'une distance, et quand on cherche à placer des points les uns par rapports aux autres en connaissant la distance qui les sépare, moi ça me fait penser à de la triangulation. En substance je vais donc passer plusieurs fois sur l'ensemble de tous mes octets chiffrés en supprimant les clairs potentiels qui ne sont pas à une distance possible par rapport aux clairs possibles des autres chiffrés.

Formulé de façon plus "informatique" :

pour chaque octet chiffré, A :
    je vais étalibr une liste temporaire, L, contenant tous les clairs possibles vis à vis de la triangulation
    Cette liste est initialement vide
    pour chaque autre octet chiffré, B je vais :
        mesurer la distance de hamming, H, le séparant de A. 
        pour chaque clairs possible de B :
            je rajoute à ma liste L les clairs qui y sont distants de H. 
    la nouvelle liste de clairs possibles pour A est l'intersection de son ancienne liste de clairs possible et de la liste L.

Ca a l'air assez bourrin mais, vous savez quoi ? Ca marche :) En quelques itérations (à la louche une vingtaine) et moins de 5s de calculs je me retrouve avec un seul clair possible pour chacun des chiffré. En appliquant la substitution ainsi trouvée j'obtient bien la solution de l'étape 2 ! Comme quoi tous les essais relatés dans les billets précédents étaient inutiles...¹

Comme quoi, il était aisé de passer cette étape sans regarder le FPGA, mais encore fallait-il faire LA bonne hypothèse...

1. Si on fait abstraction de l'expérience acquise et d'une petite entourloupe : avec la triangulation pure j'obtient en fait quelques milliers de combinaisons possibles et pas directement la bonne solution. Ca reste aisément bruteforçable, mais j'ai préféré hard-coder les relations chiffré<=>clair que j'avais trouvé pour les retours charriots tout au début de l'analyse puisque, là, je tombe directement sur le bon résultat par triangulation :) ↩