INFO910 : cryptologie

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

Automne 2019

• Consignes

  • Langage de programmation

• Liens utiles

• Introduction

  • Idée du compromis temps-mémoire

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

  • 1.1. Initialisation

    • Fonctions d'empreintes

  • 1.2. Indices et empreintes

  • 1.3. Indices et textes clairs

  • 1.4. Table arc-en-ciel

    • Chaines d'indices

    • Table

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

• 3. Finitions

• 4. Pour aller plus loin

  • 4.1. Plusieurs tables

  • 4.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.

   Pour tester les fonctions intermédiaires, j'ajoute en général une fonctionnalité test qui permet de lancer différentes fonctions de test. (Pour les questions 2.2, 4, 5, etc.)

3. Votre code (Python, C, Java) 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.

4. 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'inclue 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) demande de nombreux calculs. Les exemples demandés dans le TP restent de taille raisonnable, mais un langage compilé reste de loin préférable.

Pour information, avec ma version du programme (en C) la création des tables pour la question 12 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%). -

Je vous conseille d'utiliser C ou C++.

Liens utiles

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

• le sujet du même TP des années précédentes (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, une amélioration par Philippe Oeschslin.

Introduction

Idée du compromis temps-mémoire

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.

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'on les a 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 première méthode, celle ci nécessite de sauvegarder un tableau de taille N et de faire un précalcul assez long. 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.

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

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

1.1. Initialisation

Une fonction de hachage H transforme une suite arbitraire d'octets en un nombre fixe d'octets (8 pour LM hash, 16 pour MD5, 20 pour SHA1, etc.).

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

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

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

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

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

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

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

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

#include <openssl/des.h>
#ifdef _WIN32
#pragma comment(lib, "libeay32.lib")
#endif
void setup_DES_key(unsigned char key_56[], DES_key_schedule* ks)
{
    DES_cblock key;
    key[0] = key_56[0];
    key[1] = (key_56[0] << 7) | (key_56[1] >> 1);
    key[2] = (key_56[1] << 6) | (key_56[2] >> 2);
    key[3] = (key_56[2] << 5) | (key_56[3] >> 3);
    key[4] = (key_56[3] << 4) | (key_56[4] >> 4);
    key[5] = (key_56[4] << 3) | (key_56[5] >> 5);
    key[6] = (key_56[5] << 2) | (key_56[6] >> 6);
    key[7] = (key_56[6] << 1);
    DES_set_key(&key, ks);
}

static unsigned char magic[] = { 0x4B, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25 };

void hash_LM(char* c, unsigned char* H)
{
    int i;
    for (i = strlen(c); i < 7; i++)
        c[i] = 0;
    DES_key_schedule ks;
    setup_DES_key((unsigned char*)_clear, &ks);
    DES_ecb_encrypt((DES_cblock*)magic, (DES_cblock*)H, &ks, DES_ENCRYPT);
}

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

fonction de hash : MD5
taille min = 4
taille max = 5
alphabet = abcdefghijklmnopqrstuvwxyz
taille alphabet = 26
N = 12338352

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

1.3. Indices et textes clairs

La fonction {0, ..., N-1} → TextesClairs, appelée i2c est une bijection. Dans le cas où alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", taille_min = taille_max = 4, on peut prendre

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

Attention, si taille_min = 4 et taille_max = 6, on aura par exemple

0 -> AAAA
1 -> AAAB
...
456975 -> ZZZZ
456976 -> AAAAA
456977 -> AAAAB
...
12338351 -> ZZZZZ

    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    taille_min = 4
    taille_max = 5

    142678997 -> "Salut"

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

  min size = 4
  max size = 5
  alphabet = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

  chaine de taille 1: 1 ... 1
  chaine de taille 2: 1 ... 48955774
  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
min size = 5
max size  = 5
alphabet = abcdefghijklmnopqrstuvwxyz
length = 26
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

2. 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);

3. Finitions

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

  Available commands:
    hash <S>
              compute hash of given string
    time [n]
              time the i2i function on n calls (default 1000000)
    bruteforce <H>
              brute force the given hash
    info <M> <T>
              compute some information about corresponding rainbow table
    table <M> <T> <FILENAME>
              create the corresponding rainbow table
    table <FILENAME> [LIMIT]
              display some information about the table from given file
    crack <H> <FILENAME>
              crack the given hash with the rainbow tables
    test ...
              development tests

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

  $ ./rbt --md5  --size=5 table 10000 10000 TABLE
  >>> creating table 0 (for i=0; i<1; i += 1)
  >>> creating chain 1310 of 10000 (13.09000%), ETA: 13 s
  >>> creating chain 2700 of 10000 (26.99000%), ETA: 10 s
  >>> creating chain 4084 of 10000 (40.83000%), ETA: 8 s
  >>> creating chain 5471 of 10000 (54.70000%), ETA: 6 s
  >>> creating chain 6858 of 10000 (68.57000%), ETA: 4 s
  >>> creating chain 8242 of 10000 (82.41000%), ETA: 2 s
  >>> creating chain 9627 of 10000 (96.26000%), ETA: 0 s
  >>> sorting table

  $ wc -c TABLE
  160054 TABLE

  $ ./rbt crack 4A82A984ABEB41E09765F66CC26EF518 TABLE
  trying to crack 4A82A984ABEB41E09765F66CC26EF518 with table from file TABLE (1 / 1)
  >>> currently checking chains of length 9690 (3.10031%)
  >>> currently checking chains of length 8734 (12.66127%)
  >>> currently checking chains of length 8174 (18.26183%)
  >>> currently checking chains of length 7698 (23.02230%)
  >>> nb_err = 2748
  >>> crack succesful:
  miaou

4. Pour aller plus loin

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

4.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 change 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 09-10-2019 à 11:04.