INFO002 : Cryptologie

TP1 : compromis temps / mémoire, les tables arc-en-ciel

Automne 2021

• Consignes

  • Langage de programmation

• Liens utiles

• Préliminaires

  • Fonctions d'empreintes

  • Configuration globale

  • Indices et textes clairs

• 1. Idée du compromis temps-mémoire

• 2. Mise en œuvre concrète : précalcul de la table

  • 2.1. Indices et empreintes

  • 2.2. Table arc-en-ciel

    • Chaines d'indices

    • Table

• 3. Mise en œuvre concrète : recherche dans une table arc-en-ciel

• 4. Finitions

• 5. Pour aller plus loin

  • 5.1. Plusieurs tables

  • 5.2. Dictionnaire

• Erreurs fréquentes

Consignes

Le rendu de ce TP se fera uniquement par TPLab et consistera en une archive (zip, tar, etc.) contenant votre code et impérativement un fichier README.

Attention :

1. README doit être un fichier texte contenant les réponses aux questions du TP et vos commentaires / remarques / explications pertinentes, ainsi que le degré d'avancement dans le TP.

2. Votre programme doit fournir une interface textuelle utilisable. Reportez-vous à la section Finitions pour l'interface de ma version du code.

3. Vous devez fournir également une interface pour tester les fonctions intermédiaires. (Notamment pour les questions 1, 2, 3, 5 et 6.) Ma version permet par exemple de tester la fonction i2c (question 3) avec

   $ ./rbt test i2c 1234567
   alphabet = "abcdefghijklmnopqrstuvwxyz"
   taille_min = 5
   taille_max = 5
   N = 11881376
   
   i2c(1234567) = "csghj"

   Attention, les questions que je ne peux pas tester risquent de ne pas être notées !

4. Votre code (C, C++, Java, Python, ...) doit pouvoir être testé sous Linux sans bibliothèque exotique. N'oubliez pas d'inclure la procédure à suivre pour tester vos programmes, et si vous faites du C / C++, fournissez un fichier Makefile pour la compilation.

5. TPLab refusera les soumissions de plus de 1Mo. Il n'est pas nécessaire de joindre les fichiers de données (tables arc en ciel). Pour info, la taille de mon archive (compressée) fait moins de 10 Ko, et elle fournit plus de fonctionnalités que demandées dans ce TP. (Elle fait moins de 22Ko si j'inclus la seule bibliothèque externe libdivide.)

Langage de programmation

Le langage de programmation est libre mais vous devez vérifier avec l'encadrant si vous souhaitez utiliser autre chose que C, C++ ou Java.

Gardez le point suivant en tête pour votre choix : le programme final (création de tables arc-en-ciel) fait beaucoup de calculs. Les exemples demandés dans le TP restent de taille raisonnable, mais un langage compilé reste de loin préférable. (Et si vous utilisez C ou C++, n'oubliez pas d'activer les options d'optimisation lors de la compilation avec -O3.)

Pour information, avec ma version du programme (en C) la création des tables pour la question 13 a pris

• moins de 1 seconde pour la première table (couverture de 92.9%) ou moins de 2 secondes (couverture de 99.3%),

• environ 1 minutes et 15 secondes pour la seconde (couverture 91.2%) ou presque 13 minutes (couverture 99.8%).

Liens utiles

• encadrant de TP : Pierre.Hyvernat@univ-smb.fr,

• la version précédente du sujet, par J.O. Lachaud,

• A Cryptanalytic Time-Memory Trade-Off, l'article original de Martin E. Hellman qui a introduit cette technique,

• Making a Faster Cryptanalytic Time-Memory Trade-Off, une amélioration par Philippe Oeschslin.

Préliminaires

L'objectif est d'inverser une fonction de hachage H (MD5, SHA1, ...), c'est à dire, étant donné une empreinte y, de retrouver un x t.q. y = H(x). En pratique, seul l'empreinte des mots de passe est stockée sur un système, et cela permet donc de retrouver un mot de passe à partir de son empreinte.

Fonctions d'empreintes

Voici par exemple comment accéder aux fonctions de hachage standard en C avec la bibliothèque openssl (paquet libssl-dev sous Debian / Ubuntu):

typedef unsigned char byte;         // facultatif

#include <openssl/md5.h>
void hash_MD5(const char* s, byte* empreinte)
{
    MD5((unsigned char*)s, strlen(s), empreinte);
}

///////////////////////////////////////////////////////

#include <openssl/sha.h>
void hash_SHA1(const char* s, byte* empreinte)
{
    SHA1((unsigned char*)s, strlen(s), empreinte);
}

Configuration globale

Notre programme d'inversion sera paramétré par les données suivantes :

• une fonction de hachage H (MD5 ou SHA1),

• une chaine alphabet contenant les caractères autorisés dans les textes clairs (par exemple "ABCDEFGHIJKLMNOPQRSTUVWXYZ"),

• une borne inférieure taille_min et supérieure taille_max pour la taille des textes clairs valides,

• un nombre N donnant le nombre total de textes clairs valides. Ce nombre est calculé à partir de la taille de l'alphabet et de taille_min et taille_max.

Indices et textes clairs

Étant donné un alphabet et taille_min et taille_max, il est possible de numéroter les textes clairs. Si alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", taille_min = taille_max = 4, on prend

0      -> AAAA
1      -> AAAB
2      -> AAAC
...
25     -> AAAZ
26     -> AABA
27     -> AABB
...
456974 -> ZZZY
456975 -> ZZZZ      # 456976 = 26^4

Le texte clair associé à un nombre est donc sa représentation en base 26. En particulier, la dernière lettre correspond à n modulo 26.

Si taille_min = 1 et taille_max = 3, on prendra

0        ->   A
1        ->   B
...
25       ->   Z
26       ->  AA
27       ->  AB
51       ->  AZ
52       ->  BA
53       ->  BB
...
701      ->  ZZ
702      -> AAA
703      -> AAB
...
18277    -> ZZZ

Autrement dit :

• pour les nombres entre 0 et 26-1 = 25, le texte clair associé est la lettre correspondante ;

• pour les nombres entre 26 et 26 + 26² - 1 = 701, on soustrait 26 avant de calculer leur représentation en base 26, sur 2 caractères : 53 -> 53-26 = 27 -> BA

• etc.

    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    taille_min = 4
    taille_max = 4
    N = 456976

    i2c(1234) = "ABVM"

    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
    taille_min = 1
    taille_max = 6
    N = 20158268676

    i2c(150106454) = "Table"
    i2c(75324) = "arc"
    i2c(1651) = "en"
    i2c(4173921) = "ciel"

1. Idée du compromis temps-mémoire

Pour commencer, supposons une fonction de hachage H simplifiée : une fonction sur l'ensemble {0, 1, 2,..., N-1}. Étant donné une "empreinte" y (un nombre entre 0 et N-1), on recherche une "entrée" x (un nombre entre 0 et N-1).

Méthode lente (recherche exhaustive)

On teste toutes les entrées possibles et on s'arrête dés qu'on a trouvé x t.q. H(x) = y.

Au pire cas, il faut tester N entrées.

Méthode "rapide" (précalcul)

Si on a précalculé toutes les empreintes et qu'elles sont stockées dans un tableau sous la forme (N = 1000000)

# entrée empreinte
037981   000003
004101   000004
020890   000004
018762   000006
...
133532   999998
022795   999998

Ce (gros) tableau est trié selon la seconde colonne (empreinte).

La fonction H n'est pas forcément injective : il peut donc y avoir des répétitions et des "trous" dans la seconde colonne du tableau.

Pour inverser une valeur, on fait une recherche dichotomique sur y (dans la seconde colonne) pour obtenir directement x t.q. y = H(x).

Par rapport à la précédente, cette méthode nécessite un précalcul très long et de sauvegarder un tableau de taille N. Par contre, l'inversion est très rapide.

Méthode intermédiaire (compromis temps-mémoire)

Si on précalcule des empreintes "consécutives" (empreinte d'empreinte), on peut obtenir un tableau de la forme

# entrée H(entrée) H(H(entrée))
450527   884710    000005
090419   808110    000006
160224   535710    000006
...
876129   619817    999997

On sauvegarde alors uniquement les première et dernière colonnes pour obtenir

# entrée   H(H(entrée))
450527     000005
090419     000006
160224     000006
...
876129     999997

On cherche alors x t.q. H(x) = y de la manière suivante

1. on fait une recherche dichotomique de y dans la dernière colonne. Si on le trouve, on obtient x' (dans la première colonne) t.q. y = H(H(x')). On peut donc poser x = H(x') !

2. Si on ne trouve pas, on fait une recherche dichotomique de H(y) dans la dernière colonne. Si on le trouve, on obtient x' (dans la première colonne) t.q. H(y) = H(H(x')). x' est un candidat pour un inverse de y.

   On teste si y = H(x') : dans le cas positif, on a trouvé un inverse, dans le cas négatif, on continue la recherche.

Par rapport à la deuxième méthode, celle ci nécessite autant de précalculs, mais stocke un tableau plus petit. Par contre, elle nécessite légèrement plus de calcul lors de chaque recherche.

On peut généraliser cette construction en calculant un tableau (toujours trié selon la dernière colonne)

# e      H(e)     HH(e)    HHH(e)   HHHH(e)  HHHHH(e) H6(e)    H7(e)    H8(e)
...
731124   132518   839817   585511   145152   061620   317423   511013   020511
...
611196   895417   928719   758225   350428   648619   882210   264133   390232
...
522119   229321   851653   812066   064431   699105   247523   487930   677201
...

On peut alors stocker uniquement les premières et dernières colonnes:

# e       H8(e)
...
731124    020511
...
611196    390232
...
522119    677201
...

On peut généraliser la méthode de recherche précédente : on diminue l'utilisation de la mémoire en augmentant le temps de calculs.

Dans ce cas, on recherche H^k(y) (pour k = 0,1,2,...) dans la dernière colonne, et lorsqu'on le trouve, on teste le candidat potentiel c = H^8-k-1(x) correspondant. Ce candidat vérifie H^k(H(c)) = H^k(y) mais pas forcément H(c)=y.

(Note : la quantité de précalculs ne change pas vraiment...)

2. Mise en œuvre concrète : précalcul de la table

2.1. Indices et empreintes

Le compromis temps/mémoire décrit plus haut était basé sur une fonction sur un ensemble {0, 1, ..., N-1}. Nous allons l'adapter en transformant notre fonction de hachage H : TextesClairs → Empreintes en une fonction {0, 1, ..., N-1} → {0, 1, ..., N-1} :

Les nombres entre 0 et N-1 seront appelés des indices. Il y en autant que les textes clairs valides.

La fonction Empreintes → {0, ..., N-1} sera appelée h2i. On peut choisir h2i(y) = y % N, mais pour limiter les collisions, on utilise plutôt h2i(y, t) = (y+t) % N, où t dépend de la colonne dans laquelle on se trouve.

D'autre part, comme l'empreinte y est un très grand nombre, on n'utilise en fait que ses 8 premiers octets :

  h2i(y, t) = (y[0...7] + t) % N

alphabet = abcdefghijklmnopqrstuvwxyz
taille_min = 4
taille_max = 5
N = 12338352

MD5("oups") = 72eb471fb3bd65c03d29f2fcbb9984d6
h2i(MD5("oups"), 1) = 10419507

2.2. Table arc-en-ciel

Chaines d'indices

Dans la version "simple", la table consistait en des chaines x, H(x), HH(x), HHH(x), .... Les chaines seront maintenant de la forme

Si on note i2i la composition de i2c, H et h2i, les chaines sont de la forme

  fonction de hash = MD5
  alphabet = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  taille_min = 4
  taille_max = 5
  N = 387515648

  chaine de taille 1: 1 ... 1
  chaine de taille 2: 1 ... 48955774
  chaine de taille 10: 1 ... 73028587
  chaine de taille 100: 1 ... 52594470
  chaine de taille 1000: 1 ... 289365202

Table

Il est difficile de garantir que toutes les valeurs possibles sont présentes dans une table arc-en-ciel. En pratique, il suffit qu'elle recouvre l'ensemble des valeurs le mieux possible. Une table pourra ainsi recouvrir 88.3% ou 97.8% des valeurs...

Le plus simple pour cela est de faire commencer les chaines par des indices choisis aléatoirement.

hash function: MD5
alphabet: abcdefghijklmnopqrstuvwxyz
alphabet length: 26
min size: 5
max size: 5
nb clear texts: 11881376
height: 100 (M)
width: 200 (T)
content:
000000000: 15 --> 251367
000000001: 6 --> 520575
000000002: 32 --> 607033
000000003: 86 --> 726176
000000004: 47 --> 815557
000000005: 8 --> 1082040
000000006: 49 --> 1240685
000000007: 51 --> 1401769
000000008: 75 --> 1413059
000000009: 73 --> 1424209
...
000000090: 89 --> 11063920
000000091: 12 --> 11067438
000000092: 24 --> 11088833
000000093: 82 --> 11375342
000000094: 59 --> 11379781
000000095: 33 --> 11396870
000000096: 61 --> 11420612
000000097: 18 --> 11542432
000000098: 26 --> 11771236
000000099: 35 --> 11795828

3. Mise en œuvre concrète : recherche dans une table arc-en-ciel

Pour inverser la fonction de hachage H, nous allons en fait inverser la fonction i2i comme décrit dans la section pertinente. Il y a deux subtilités supplémentaires :

1. la fonction i2i prend en paramètre le numéro de colonne

2. comme la fonction h2i n'est pas injective, un inverse pour i2i ne donne pas forcément un inverse pour H, mais seulement un candidat pour un inverse pour H.

En pseudo-C, cela ressemble à

// essaie d'inverser l'empreinte h
//   - table : table arc-en-ciel
//   - hauteur : nombre de chaines dans la table
//   - largeur : longueur des chaines
//   - h : empreinte à inverser
//   - clair : (résultat) texte clair dont l'empreinte est h
int inverse(table, hauteur, largeur, h, *clair) {
    int nb_candidats = 0;
    for (t = largeur - 1; t > 0; t--) {
        idx = h2i(h, t);
        for (i = t + 1; i < largeur; i++) {
            idx = i2i(idx, i);
        }
        if (recherche(table, hauteur, idx, &a, &b) > 0) {

            for (i = a; i <= b; i++) {
                if (verifie_candidat(h, t, table[i][0], clair) == 1) {
                    return 1;
                } else {
                    nb_candidats++;
                }
            }
        }
    }
}

où

// recherche dichotomique dans la table les premières et dernières lignes dont
// la seconde colonne est égale à idx
//   - table : table arc-en-ciel
//   - hauteur : nombre de chaines dans la table
//   - idx : indice à rechercher dans la dernière (deuxième) colonne
//   - a et b : (résultats) numéros des premières et dernières lignes dont les
//     dernières colonnes sont égale à idx
int recherche(table, hauteur, idx, *a, *b) {
   ...
}

// vérifie si un candidat est correct
//   - h : empreinte à inverser
//   - t : numéro de la colonne où a été trouvé le candidat
//   - idx : indice candidat (de la colonne t)
//   - clair : résultat : contient le texte clair obtenu
int verifie_candidat(h, t, idx, *clair)
{
    for (int i = 1; i < t; i++) {
        idx = i2i(idx, i);
    }
    clair = i2c(idx);
    h2 = H(clair);
    return h2 == h;
}

m = hauteur;
v = 1.0;
for (i = 0; i < largeur; i++) {
    v = v * (1 - m / N);
    m = N * (1 - exp(-m / N));
}
couverture = 100 * (1-v);

4. Finitions

1. Ajoutez une interface textuelle facilement scriptable pour utiliser facilement votre programme :

   • tester les fonctions pertinentes à chaque question du TP (cf la liste de mes tests plus bas),

   • créer une table arc-en-ciel avec les paramètres choisis,

   • donner la couverture d'une table en fonction des paramètres choisis (sans créer la table),

   • inverser une valeur en utilisant une table existante.

   Sans aucun argument, votre programme devra afficher un petit message d'aide.

2. Ajoutez la possibilité de contrôler l'affichage d'information lors du calcul d'une table / inversion d'une valeur. Il peut notamment être intéressant d'afficher régulièrement une estimation du temps de calcul restant...

Voici par l'interface simplifiée de mon propre programme :

  $ ./rbt --help
  usage: ./rbt <CMD> [OPTIONS] [ARGS]

Available commands:
  create <M> <T> <FILENAME>
            create the corresponding rainbow tables (M=height, T=width)
  info <FILENAME> [LIMIT]
            display some information about the table from given file
  stats <M> <T>
            give some information (cover, size) about rainbow tables without
            computing them
            (M=height, T=width)
  crack <H> <FILENAMES> ...
            crack the given hash with the rainbow tables
  bruteforce <H>
            brute force the given hash
  test ...
            development tests ("./rbt test list" for available tests)

Available options:
  --md5                 use md5 hash function (default)
  --sha1                use sha1 hash function
  --alphabet <s>        allowed characters for clear text
  --min-size <n>        minimum size of clear text
  --max-size <n>        maximum size of clear text
  -s <n> / --size <n>   exact size of clear text
  -d <n> / --delay <n>  number of seconds between consecutive log messages (default 5)
  -help / -h            this message

et voila un exemple d'exécution :

Voila également l'interface de mes fonctions de test:

$ ./rbt test list
available tests:
  test config                     show configuration
  test hash <s1> <s2> ...         compute hash of strings s1, s2, ...
  test i2c <i1> <i2> ...          compute i2c(i1), i2c(i2), ...
  test h2i <s> <t>                compute h2i(H(s), t)
  test i2i <i1> <t1> ...          compute i2i(i1, t1), i2i(i2, t2), ...
  test time_i2i [N]               compute average time of single i2i call over N calls
  test full_chain <T> <i1> ...    compute (full) chains starting at i1, i2, ...
  test FULL_chain <T> <i1> ...    compute (full, with details) chains starting at i1, i2, ...
  test chain <T> <i1> ...         compute chains starting at i1, i2, ...
  test search <FILENAME> <i>      search the first and last occurences of i in table
  test list                       this list

5. Pour aller plus loin

5.1. Plusieurs tables

Lorsque les tables sont trop grosses, le nombre de collisions augmente, diminuant ainsi la couverture des textes clairs.

Une possibilité est de créer alors plusieurs tables, numérotées de 0 à n-1. La fonction h2i est modifiée pour accepter un paramètre supplémentaire :

    h2i(y, t, n) = (y[0...7] + t + 65536*n) % N

Chaque table est stockée dans un fichier, et la recherche se fait séquentiellement dans la liste des fichiers. Le temps de recherche augmente, mais la couverture aussi...

5.2. Dictionnaire

On peut combiner une attaque arc-en-ciel et une attaque par dictionnaire : la fonction i2c renvoie alors le mot à l'indice n dans le dictionnaire.

Erreurs fréquentes

D'après J.O. Lachaud, voici quelques erreurs qui reviennent souvent dans votre code :

• Mauvaise génération aléatoire de l'indice. Attention, il faut générer un nombre entier aléatoire suffisamment grand, genre 64 bits. Par exemple, random, suivant les architectures ne génère pas forcément un nombre assez grand. Une manière de faire est donc de générer deux nombre aléatoires et de les combiner:

  unsigned long n1 = rand();
  unsigned long n2 = rand();
  uint64 n = ( (uint64) n2 )
             + ( ( (uint64) n1 ) << 32 );
  

• Oubli fréquent de prendre le "modulo N" pour l'indice aléatoire initial.

• Mauvaise transformation d'indice en texte clair. Il faut bien vérifier sur de petits exemples (petits alphabets) que tout se passe bien.

• Mauvaise transformation de l'empreinte en indice (h2i). Le plus simple est d'utiliser les conversions type C qui changent le point de vue sur la mémoire:

  unsigned char t[16];           // empreinte, un grand nombre de 16 octets (pour MD5)
  uint64_t* ptr = (uint64_t*) t; // le même tableau, vu comme un tableau d'entiers 64 bits
  uint64_t i = ptr[0];           // par définition le nombre stocké dans t[0-7].
  

  En Java, cette fonction est souvent mal vérifiée, car elle ne peut être écrite aussi simplement.

• Mauvaise comparaison de chaines (en C, C++ et en Java). Vous comparez très souvent l'adresse des chaines, pas leur valeur. Utilisez equals en Java, strcmp en C, ou string::operator== en C++

• Vérifiez votre nombre de mots N.

• Vérifiez vos tables : elles doivent être triées selon la deuxième colonne et ne doivent pas contenir trop de répétitions/doublons. Si ce n'est pas le cas, vous avez probablement un problème dans la fonction i2i.

• Confusion entre chaines C (terminées par '\0') et chaine C++ avec des conversions dans tous les sens.

• Confusion entre la vision affichable en hexadécimal de l'empreinte (pour MD5, 32 caractères parmi 0123456789abcdef) et l'empreinte elle même (un grand entier sur 16 octets). De fait, souvent la version "affichable" du MD5 est utilisée dans h2i, alors qu'il faut bien la version chiffrée (le grand entier).

• Mauvais paramètre t passé à h2i. Il faut bien faire attention à la cohérence de ce paramètre entre la génération de la table et la recherche pour cracker le mot de passe.

Remarques sur la page (ou le sujet) : contact.
mentions légales

,

Dernière révision: le 21-10-2021 à 11:32.