TP3 : RC4 et le WEP

info-607 : mathématiques pour l'informatique

Hivers 2020

• Consignes

  • Liens utiles

• 1. Chiffrement avec RC4

• 2. WEP et RC4

  • Introduction

  • 2.1. Générateur de paquets WEP

    • Format des données générées

  • 2.2. Attaque de Fluhrer, Mantin et Shamir

    • Vecteurs faibles

    • Attaque sur la clé complète

    • Vérification

    • Amélioration

Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier prenom-nom.c contenant votre programme.

Attention, le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

1. l'architecture de votre programme (code découpé en fonctions etc.),

2. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),

3. la présence de commentaires aux endroits appropriés,

4. la présence de documentation pour vos fonctions.

Attention, les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

• chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,

• votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=gnu99 -O3,

• une exécution du programme principal « à vide » (./craque) ne devra pas provoquer d'erreur.

Liens utiles

• page wikipedia sur RC4.

1. Chiffrement avec RC4

« RC4 » peut-être vu comme un générateur pseudo-aléatoire qui permet de chiffrer un flot de données sur le modèle du « bloc-notes à usage unique » : chaque octet du flot de données est combiné (avec un XOR) avec l'octet correspondant de RC4. On ne connait pas, à ce jours, d'attaque générale pour RC4. (Voir https://en.wikipedia.org/wiki/RC4#Security pour des détails sur d'autres attaques.)

RC4 comporte deux phases :

1. initialisation à partir d'une clé de taille 0 ≤ t ≤ 256 octets (le "key scheduling algorithm"),

2. génération d'octets aléatoires (le "pseudo random generator algorithm").

En pseudo C, si on note cle la clé, et t sa taille :

/* KSA: Key Scheduling Algorithm */
/* L'état est constitué des variables P (tableau de 256 octets), index_i et index_j (entiers). */
  for(i = 0; i < 256; i++)
    P[i] = i;

  j = 0;
  for(i = 0; i < 256; i++) {
    j = (j + P[i] + cle[i % t])  %  256;
    P[i]  <->  P[j];    /* échange */
  }
  index_i = 0;
  index_j = 0;

et

/* PRGA: Pseudo Random Generator Algorithm */
  index_i = (index_i + 1)  %  256;
  index_j = (index_j + P[index_i])  %  256;
  P[index_i]  <->  P[index_j];  /* échange */
  octet_aleatoire = P[ (P[index_i] + P[index_j])  %  256];

Le PRGA est exécuté autant de fois qu'il faut d'octets aléatoire...

void code_RC4_drop(byte *cle, int taille_cle, char *message, int n)

2. WEP et RC4

Introduction

Le WEP ("Wired Equivalent Privacy") chiffre chaque paquet en utilisant deux clés :

1. la clé WEP, sur 40 ou 104 bits, càd sur 5 ou 13 octets,

2. une "clé" temporaire, ou vecteur d'initialisation sur 24 bits, càd sur 3 octets.

Chaque paquet est codé avec RC4 en utilisant la concaténation "vecteur d'initialisation @ clé WEP" (sur 8 ou 16 octets donc) comme clé. Le vecteur d'initialisation est envoyé en clair avec le paquet chiffré.

Pour décoder, on récupère le vecteur d'initialisation, concatène la clé WEP derrière et décode avec RC4.

De cette manière, on ne peut décoder que si on possède la clé WEP, et on utilise quand même des clés (en général) différentes pour chaque paquet. (C'est important, car sinon, il suffirait d'un paquet décodé pour retrouver le début de la suite pseudo-aléatoire, et donc de pouvoir décoder tous les paquets de taille inférieure.)

2.1. Générateur de paquets WEP

Pour éviter d'avoir à récupérer des paquets réseaux, nous allons générer l'information nécessaire pour l'attaque (et seulement cette information) avec un programme spécifique (fourni). Ce programme génèrera des suites constituées du premier octets RC4 ainsi que le vecteur d'initialisation utilisé. Ces informations sont disponibles dans chaque WEP. (Voir plus haut.) Notez que l'attaque n'a besoin que du premier octet généré par RC4, et jamais des octets suivants.

La clé WEP utilisée pourra être choisie au lancement du générateur, ou bien être tirée aléatoirement.

Ce code est contenu dans le fichier generate_WEP.c, qui est compilé automatiquement par le fichier Makefile fourni.

$ make
gcc -Wall -Wextra -pedantic -std=gnu99  -O3 -Wno-unused-variable generate_WEP.c -o generate
...

Pour l'utiliser, les options sont les suivantes :

$ ./generate -h

Usage : ./generate [options]

  --key_size=<N>, -l<N>
      taille en octets de la clé WEP aléatoire (défaut : 13)
  --IV_size=<N>, -i<N>
      taille en octets des vecteurs d'initialisation (défaut : 3)
  --key="<KEY>", -K"KEY"
      utilise la clé donnée en argument sous la forme
      ".. .. .. .." (en hexadécimal)
  --easy, -e
      utilise les vecteurs d'initialisation (n+3, 255, ...)
      (implique une taille d'IV de 3)
  --tube=<FILENAME>, -t<FILENAME>
      spécifie le nom du tube à utiliser (défaut: data_WEP)
  --increment, -I
      les vecteurs d'initialisations sont simplement incrémentés
  --show_key, -s
      affiche la clé utilisée
  --help, -h
      affiche ce message

Lorsque le générateur est lancé, il est possible de lui demander d'afficher la clé WEP qu'il utilise en lui envoyant le signal SIGUSR1. La ligne de commande correspondante est affiché par le générateur au lancement.

Format des données générées

Le programme generate crée un "tube" (fichier spécial) appelé data_WEP et le remplit avec des paquets d'octets. Chaque paquet est constitué de plusieurs parties :

1. les octets du vecteur d'initialisation (il y en a IV_size),

2. le premier octet généré par RC4 avec ce vecteur d'initialisation et la clé WEP cherchée (il y en a seulement un),

3. un octet 0x00 pour marquer la fin du paquet. Votre programme devra essayer de retrouver la clé en récupérant des paquets d'octets dans ce tube.

La fonction principale du fichier lucien_tartempion.c ouvre ce tube avec l'appel système open et stocke le descripteur de fichier correspondant dans une variable globale tube_fd. Vous pouvez donc y lire des données avec l'appel système read. Vous pouvez consulter la page de manuel (man 2 read) pour l'utilisation de cet appel système.

$ killall generate

int get_data(byte *IV, byte *b_rc4);

$ killall generate
$ ./generate --increment --key="01 02 03 04 05 06 07 08 09 0a 0b 0c 0d"
Pour afficher la clé, vous pouvez utiliser la commande
   $ kill -s SIGUSR1 32508

  $ ./crack -T 7

  QUELQUES TESTS
  ==============

  fonction get_data
  -----------------
  affichage des 10 premiers paquets :

  paquet  1 : 00 00 01  =>  6d
  paquet  2 : 00 00 02  =>  05
  paquet  3 : 00 00 03  =>  df
  paquet  4 : 00 00 04  =>  5c
  paquet  5 : 00 00 05  =>  45
  paquet  6 : 00 00 06  =>  88
  paquet  7 : 00 00 07  =>  15

2.2. Attaque de Fluhrer, Mantin et Shamir

En 2001, Fluhrer, Mantin et Shamir ont montré que l'utilisation de RC4 pour WEP rendait la clé facilement craquable. Il suffit de récupérer un nombre raisonnable de paquets chiffrés.

Le principe général (vu en cours) est le suivant.

1. On récupère des paquets chiffrés avec leurs vecteur d'initialisation (envoyé en clair).

2. Le premier octet de chaque paquet est le "SNAP header" (subnetwork access protocol) qui vaut 0xaa pour le WEP. On peut donc en déduire le premier octet généré par RC4 avec la clé constituée du vecteur d'initialisation (connu) et la clé WEP (inconnue).

3. Lorsque certaines conditions sont vérifiées, on fait une prédiction sur le premier octet de la clé secrète en utilisant le vecteur d'initialisation et le premier octet généré.

Lorsque suffisamment de prédictions ont été faites, on observera un biais : une valeur est prédite plus souvent que les autres. Ça sera le premier octet de la clé secrète.

On peut recommencer, avec un octet connu supplémentaire : les 3 octets des vecteurs d'initialisation et un octet de la clé secrète.

Le code fournit (fichier lucien-tartempion.c) utilise des variables globales que vous ne devrez pas modifier. Leurs valeurs sont choisies en donnant des options sur la ligne de commande. Les plus importantes sont :

• key_size pour la taille des clés WEP utilisées (5 ou 13, mais votre code devra fonctionner avec d'autres valeurs),

• IV_size pour la taille des vecteurs d'initialisation utilisés (3, mais votre code devra fonctionner avec d'autres valeurs).

Vecteurs faibles

int weak(int n, byte *key, byte b_rc4, byte *prediction);

Attaque sur la clé complète

Écrivez la fonction suivante (voir détails de l'attaque)

int crack_WEP(byte* cle_WEP);

qui permet de deviner tous les octets d'une clé WEP en cherchant des vecteurs d'initialisation faibles.

Vous devrez pour ceci faire plusieurs prédictions pour chaque octet de la clé, et ne garder que la plus fréquente.

Le nombre de prédictions à faire pour chaque octet de la clé dépend des deux variables expected_weak_IV et expected_IV :

• expected_IV donne le nombre total de vecteurs d'initialisation à regarder pour chaque octet, indépendamment du faite qu'ils soient faibles ou pas,

• expected_weak_IV donne le nombre de vecteurs faibles à regarder pour chaque octet.

Votre fonction arrêtera de faire des prédictions dès qu'une de ces variables est atteinte.

La valeur de retour devra être le nombre d'octets de la clé.

N'oubliez pas, d'afficher l'avancement de votre fonction. Vous pouvez par exemple utiliser la variable globale VERBOSE pour ajuster le niveau de détails.

Voici par exemple une exécution de mon programme avec VERBOSE = 2 (option -vv sur la ligne de commandes). Chaque . affiché correspond à un vecteur faible trouvé.

Pour vos messages de débogage, la fonction DEBUG s'utilise comme printf mais avec un premier argument supplémentaire : le niveau de détails à partir duquel le message est effectivement affiché.

Attention, cle_WEP ne contient que la partie fixe de la clé alors que la fonction weak prend en argument la clé complète (partie variable + partie fixe). Il faut donc déclarer une nouvelle variable pour contenir la clé complète.

estimation du temps : 45 minutes

Vérification

int check_byte(byte* cle_WEP);

  byte K[] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d};
  if (check_byte(K) == 1) {
      ...
  }

Amélioration

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

,

Dernière révision: le 19-02-2020 à 16:02.