Logo Blog perso d'Ozwald

Crypto à retardement : à la règle et au compas

Par Oz le - Sécurité
SSTIC challenge cryptographie

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 :) !

enigma - Creative Common CCBY by "joncallas" on flickr

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.

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 :

Hamming fingerprinting of base64 charset - Creative Common CCBYSA by Ozwald from ozwald.fr

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...1

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


Dromi le 2013/09/10 13:10

Super intéressant ! Merci !
Puisque tu te remets doucement à l'électronique, n'oublie pas que le hardware peut aussi être très utile en crypto ! Entre ceux qui utilisent leur carte graphique pour faire des calculs plus rapides (méthode bruteforce, avec la fourberie en plus), ou ceux qui implémentent des processeurs de crypto en FPGA, il y a de quoi faire ! (toi aussi reconvertit toi en mineur de Bitcoins sur FPGA...)

  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 :)

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.