TP3 : RC4 et le WEP

info-602 : mathématiques pour l'informatique

Hivers 2022

• Consignes

  • Liens utiles

• Prélimiaires : chiffrement avec RC4

• 1. WEP et RC4

  • Utilisation du code

  • 1.1. Générateur de paquets WEP

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

  • 1.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 fichier rc4_drop-n.c (pour la question 1) et un fichier prenom-nom.c pour les questions suivantes.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

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

• votre fichier devra s'appeler "nom.c",

• 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 qui sont définies dans le fichier Makefile. (Vous pouvez également ajouter les options -Wno-unused-parameter -Wno-unused-function.)

Liens utiles

• page wikipedia sur RC4,

• l'archive contenant le code du TP (uniquement pour les questions 2 -- 6).

Prélimiaires : 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(byte *Cle, int taille_cle, byte *Message, int taille_message, int n);

1. WEP et RC4

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

Utilisation du code

1. Le code fourni contient une fonction main dans un fichier main.c que vous ne devez pas modifier. Cette fonction permet de lancer le programme compilé depuis la ligne de commande.

2. Votre code devra être écrit dans le fichier severus-snape.c. (Sauf les tests, qui seront dans tests-severus-snape.c.)

3. Une des options disponibles est -T qui permet d'exécuter la fonction perform_tests du fichier test-severus-snape.c. La fonction fournie gère un ou deux tests. À vous de l'étendre de manière pertinente.

4. Le code définit une fonction DEBUG qui s'utilise comme la fonction printf. Elle a simplement un premier argument supplémentaire qui permet de contrôler l'affichage :

   • si cet argument est à 0, le message est toujours affiché,

   • si cet argument est à 1, le message est seulement affiché si le programme est lancé avec l'option -v,

   • si cet argument est à 2, le message est seulement affiché si le programme est lancé avec l'option -vv,

   • etc.

Voila un exemple d'exécution :

$ make
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function WEP_generator.c -o WEP_generator
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function -c -o correction.o correction.c
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function -c -o tests-correction.o tests-correction.c
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function -c -o main.o main.c
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function correction.o tests-correction.o main.o -o crack
$ 
$ ./WEP_generator &
[1] 353878
$ Pour afficher la clé, vous pouvez utiliser la commande
   $ kill -s SIGUSR1 353878

$ ./crack -h
Usage : ./crack [options]

  --key_size=N, -lN
      taille en octets de la clé WEP aléatoire (défaut : 13)
  --IV_size=N, -iN
      taille en octets des vecteurs d'initialisation (défaut : 3)
  --tube=FILENAME, -tFILENAME
      spécifie le nom du tube à utiliser (défaut: data_WEP)
  --expected_weak_IV=N, -nN
      spécifie le nombre de vecteurs faibles à regarder pour prédire un octet de la clé
  --expected_IV=N, -NN
      spécifie le nombre de vecteurs à regarder pour prédire un octet de la clé
  --nb_tests=N
      spécifie le nombre de tests à faire sur des nouveaux paquets après avoir trouvé une clé
lorsque les premières prédictions ne fonctionnent pas
  --verbose, -v
      augmente le niveau de détails de débogage
  --test, -T
      lance uniquement la fonction de test avec les arguments de la ligne de commandes
  --help, -h
      affiche ce message
$ 
$ ./crack -T get_data 10


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

paquet  1 : c3 c5 e4  =>  0a 49
paquet  2 : a0 f7 cb  =>  87 f5
paquet  3 : 63 88 48  =>  fc fc
paquet  4 : 6b 2f 0f  =>  a7 cc
paquet  5 : 14 9a 1a  =>  d2 e3
paquet  6 : b9 80 59  =>  cc 7b
paquet  7 : 2e a2 1b  =>  0a f9
paquet  8 : 03 82 88  =>  63 48
paquet  9 : 9c 47 69  =>  df 77
paquet 10 : 0b 44 23  =>  20 35
$

1.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 une séquence de

• un vecteur d'initialisation

• les 2 octets générés par RC4 avec la clé complète.

Ces informations sont disponibles dans chaque paquet WEP. (Voir plus haut.) L'attaque n'a besoin que du premier octet généré par RC4 (ou parfois des 2 premiers).

La clé WEP utilisée pourra être choisie au lancement du générateur. Par défaut, elle est tirée aléatoirement.

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

$ make
gcc -Wall -std=gnu99 -Wextra -pedantic -Werror -O3 -Wno-unused-parameter -Wno-unused-function WEP_generator.c -o WEP_generator
...

Pour l'utiliser, les options sont les suivantes :

$ ./WEP_generator -h

Usage : ./WEP_generator [options]

  --key_size=N, -lN
      taille en octets de la clé WEP aléatoire (défaut : 13)
  --IV_size=N, -iN
      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, -tFILENAME
      spécifie le nom du tube à utiliser (défaut: data_WEP)
  --file=FILENAME, -fFILENAME
      spécifie le nom du fichier à utiliser (défaut: data_WEP)
  --nb_packets=N, -nN
      spécifie le nombre de paquets à générer (défaut: 10000000)
  --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 en exécution, 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 WEP_generator crée un "tube" (fichier spécial) appelé data_WEP et le remplit avec des paquets d'octets à la demande. Chaque paquet est constitué de plusieurs parties :

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

2. les 2 premiers octets générés par RC4 avec ce vecteur d'initialisation et la clé WEP cherchée,

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 severus-snape.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.

int get_data(byte *IV, byte *o1, byte *o2);

$ killall WEP_generator
$ ./WEP_generator --increment --key="01 02 03 04 05 06 07 08 09 0a 0b 0c 0d"
clé utilisée: 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 get_data 8
  fonction get_data
  -----------------
  affichage des 8 premiers paquets :

  paquet  1 : 00 00 01  =>  6d 0f
  paquet  2 : 00 00 02  =>  05 34
  paquet  3 : 00 00 03  =>  df ef
  paquet  4 : 00 00 04  =>  5c e2
  paquet  5 : 00 00 05  =>  45 5c
  paquet  6 : 00 00 06  =>  88 cd
  paquet  7 : 00 00 07  =>  15 42
  paquet  8 : 00 00 08  =>  04 13

1.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 severus-snape.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 o1, byte o2, 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 (valeur par défaut : 6000000),

• expected_weak_IV donne le nombre de vecteurs faibles à regarder pour chaque octet (valeur par défaut : 200).

Votre fonction arrêtera de faire des prédictions dès qu'une de ces variables est atteinte. Si une des 2 valeurs est négative (ou nulle), il faudra l'ignorer complètement.

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

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.

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

L'outils aircrack-ng implémente de nombreuses améliorations à l'attaque de Fluhrer, Mantin et Shamir. Le plus important est de détecter d'autres formes de vecteurs faibles. En voici quelques exemples, avec les prédictions correspondantes :

attaque	condition	prédiction	taux de réussite
FMS	P[1]<n et P[1]+P[P[1]]==n	Pi[o1]-j-P[n]	5%
A_s13	P[1]==n et o1==n	Pi[0]-j-P[n]	13%
A_u13_1	P[1]==n et o1==1-n	Pi[o1]-j-P[n]	13%
A_u13_2	P[n]==n et P[1]==0	1-j-P[n]	13%
A_u13_3	P[n]==n et P[1]==o1 et P[1]==1-n	1-j-P[n]	13%
A_u5_1	P[1]==n (et o1!=1-n et o1!=n) et Pi[o1] < n et Pi[Pi[o1]-n]!=1	Pi[Pi[o1]-n]-j-P[n]	5%
A_u5_2	Pi[o1]==2 et P[n]==1	1-j-P[n]	5%
A_u5_3	P[n]==n et P[1]>=-n et P[1]==Pi[o1]-n et Pi[o1]!=1	1-j-P[n]	5%

Il existe d'autres conditions et prédictions qui utilisent les 2 premiers octets o1 et o2 générés par RC4 :

attaque	condition	prédiction	taux de réussite
A_s3	P[1]!=2 et P[2]!=0 et P[1]+P[2]<n et P[P[1]+P[2]]+P[2]==n et Pi[o2]!=1 et Pi[o2]!=2 et Pi[o2]!=P[1]+P[2]	Pi[o2]-j-P[n]	3%
A_u15	P[2]!=0 et o2==0 et P[n]==0	2-j-P[n]	15%
A_s5_2	P[1]>n et P[1] + P[2]==n et o2==P[1] et p!=1 et p!=2 (avec p=Pi[P[1]-P[2]])	p-j-P[n]	5%
A_s5_3	P[1]>n et P[1]+P[2]==n et o2!=P[1] et Pi[o2]!=1 et Pi[o2]!=2	Pi[o2]-j-P[n]	5%
A_4_s13	n==4 et P[1]==2 et o2==0	Pi[0]-j-P[n]	13%
A_4_u5_4	n>4 et P[1]==2 et P[4]+2==n et Pi[o2]!=1 et Pi[o2]!=4	Pi[o2]-j-P[n]	5%

(voir les fichiers aircrack-ng.h et aircrack-ng.c)

Implémentez (certaines de) ces améliorations et décrivez comment vous gérez les différents taux de réussite.

Vérifiez expérimentalement, que les prédictions fonctionnent...

Avec toutes ces améliorations, le temps de calcul (et le nombre de paquets à considérer) est environ divisé par 5 !

Attention, le mode --easy n'est plus utilisable lorsque vous ajoutez ces attaques.

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

,

Dernière révision: le 16-02-2022 à 11:53.