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

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 clef¹; 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 si², 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 texte³ ! 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).

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