Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 31-01-2014 à 07:41.
Le TP est à rendre, avant le jeudi 19 décembre à 23h59...
Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier prenom-nom.c contenant votre programme. Ce fichier sera utilisable directement avec les autres fichiers fournis pour le TP.
Le non-respect de cette consigne risque de me mettre de mauvaise humeur...
Attention, le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :
Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :
-Wall -Werror -Wextra -pedantic -std=c99,
./FMS) ne devra pas provoquer d'erreur.
« RC4 » peut-être vu comme un générateur pseudo-aléatoire pour crypter 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.
RC4 comporte deux phases :
1 ≤ t ≤ 256 octets,
En pseudo C, si on note "cle" la clé, et "t" sa taille :
KSA: (* Key Scheduling Algorithm *) for(i = 0; i < 256; i++) etat.P[i] = i j = 0 for(i = 0; i < 256; i++) j = (j + etat.P[i] + cle[i % t]) % 256 etat.P[i] <-> etat.P[j] (* échange *) etat.i = 0 etat.j = 0
et
PRGA: (* Pseudo Random Generator Algorithm *) etat.i = (etat.i + 1) % 256 etat.j = (etat.j + etat.P[etat.i]) % 256 etat.P[etat.i] <-> etat.P[etat.j]; (* échange *) return etat.P[ (etat.P[etat.i] + etat.P[etat.j]) % 256]
Programmez une fonction
void code_RC4_drop(char *K, char *M, int n)
qui affiche les octets, en hexadécimal (format "%02X" pour printf), du codage de la chaîne M avec la clé K.
L'argument "n" sera le nombre d'octets initiaux qu'on jette lors de la génération. (Autrement dit, on attend "n" octets générés avant de commencer à coder.) On appelle parfois ce codage "RC4-drop[n]".
estimation du temps : 30 minutes
typedef unsigned char byte;
c" de type "char" en valeur de type "byte", il faut faire un "cast" : "(byte) c".
M et K sont des chaines de caractères. Pour obtenir leur taille, vous devez utiliser la fonction strlen (après un #include <string.h>).
int main(int argc, char *argv[]) { if (argc != 4) { printf("RC4-drop[n], utilisation : %s cle message n\n", argv[0]); exit(-1); } code_RC4(argv[1], argv[2], atoi(argv[3])); return 0; }
code_RC4 directement à partir de la ligne de commande :
$ ./rc4_drop-n cle message 17 La clé est "cle" et le message clair est "message" Les 17 premières étapes seront ignorées. Le code obtenu est : 484EB4A859834E
K" correspond à la colonne "Key", l'argument "M" à la colonne "Plaintext" et l'argument "n" prend la valeur 0. Le résultat codé doit être égal à la colonne "Ciphertext".
Pour récupérer l'archive contenant les fichiers pour la suite du TP, remplacez tp3.html dans l'url du TP par TP3/tp3-XXXXXXXXXXXXXX.tar, où XXXXXXXXXXXXXX est le codage RC4 de "info528" en utilisant la clé "WEP" et en jetant les 1234 premiers octets du générateur pseudo-aléatoire. (Argument "n" à 1234 donc.) Attention, les chiffres hexadécimaux sont en majuscules (printf("%02X",o)).
L'archive du TP contient un répertoire info528-TP3 qui contient les fichiers :
Makefile : n'oubliez pas de changer la variable NOM
tp3.h : le fichier d'entêtes
rc4.c : les fonctions pour utiliser RC4
FMS.c : le fichier qui contient la fonction principale pour tester vos fonctions
lucien-tartempion.c un fichier squelette que vous devrez compléter.
Le WEP ("Wired Equivalent Privacy") crypte chaque paquet en utilisant deux clés :
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 crypté.
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 message décodé pour retrouver le début de la suite pseudo-aléatoire, et donc de pouvoir décoder tous les messages de taille inférieure.
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 relativement faible de paquets cryptés.
Le principe général (vu en cours) est le suivant :
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).
Si on fait suffisamment de prédictions, on observera un biais : une valeur sera prédite plus souvent que les autres. C'est probablement le premier octet de la clé secrète.
On peut recommencer, sauf qu'on a maintenant un octet connu de plus : les 3 octets des vecteurs d'initialisation et un octet de la clé secrète.
Détails de l'attaque :
Si on connaît les "0 ≤ n < 13" premiers octets de la clé WEP,
IV (avant le paquet crypté),
o (en faisant le XOR du premier octet crypté avec 0xaa),
3+n premières étapes du KSA,
IV est un vecteur d'initialisation faible :
P[1] < 3+n"
P[1] + P[P[1]] == 3+n"
prediction = P'[o] - j - P[3+n]", où "P'[o]" est la position de o (premier octet généré par le PRGA) dans la permutation P.
Si non, on passe au paquet suivant.
On garde la prediction qui apparaît le plus souvent, et on cherche l'octet suivant jusqu'à avoir trouvé tous les octets de la clé WEP.
Pour éviter d'avoir à récupérer des paquets réseaux, nous allons programmer l'attaque en génèrant l'information nécessaire pour l'attaque (et seulement cette information). Pour cela, il suffit de pouvoir récupérer le premier octet généré par RC4 à partir de la clé WEP (secrète) et d'un vecteur d'initialisation arbitraire.
Le code fournit utilise deux constantes définies globalement :
taille_cle_RC4 pour la taille des clés utilisées par RC4 lors du cryptage WEP (valeur par défaut : 16)
taille_IV pour la taille des vecteurs d'initialisation utilisés (valeur par défaut : 3)
Il y a également une constante octet *cle_WEP pour le tableau d'octets de la clé WEP. Sa taille vaut taille_cle_RC4-taille_IV. Cette constante sert uniquement à tester vos prédictions : vous ne pouvez en aucun cas l'utiliser dans votre programme de recherche de clé.
Le code fournit contient un fichier "rc4.c" qui permet
void init_WEP_RC4(octet *IV)",
octet RC4_PRGA(void)".
La fonction principale est contenue dans le fichier FMS.c. Elle permet de lancer votre fonction predit_octet avec les arguments adéquats :
--taille-cle=..." permet de modifier la valeur de taille_cle_RC4 (valeur par défaut : 16)
--taille-IV=..." permet de modifier la valeur de taille_IV (valeur par défaut : 3)
--nb-IV=..." permet de spécifier combien de vecteurs d'initialisations doivent être observés avant de faire une prédiction pour un octet de la clé. Attention : si vous n'observez pas suffisamment de vecteurs d'initialisations, votre prédiction a de forte chance d'être incorrecte...
--nb-IV-faibles=..." permet de spécifier combien de vecteurs d'initialisation faibles doivent être observés avant de faire une prédiction pour un octet de la clé. Attention, si vous demandez trop de vecteurs d'initialisation faibles, la prédiction sera très lente.
--cle=".. .. .. .."" permet de spécifier la valeur de cle_WEP pour tester votre programme sur une clé connue à l'avance. Attention, la clé doit être donnée en hexadécimal avec des séparateurs entre les octets.
--nb-tests=..." permet de spécifier combien de clés vous voulez essayer de prédire. Le programme tirera autant de clés WEP aléatoirement et essaiera de les prédire. Cette option est incompatible avec "--cle".
--verbose" ou "-v" permet d'afficher des messages d'information pendant l'éxécution. Cet argument peut être répété en permet d'incrémenter une constante globale "verbose". Utilisez cette constante pour controler la quantité d'information que vous voulez afficher. (Reportez-vous à la fonction main dans le fichier FMS.c pour des exemples d'utilisation.)
Voici un exemple d'appel au programme sur la ligne de commandes :
$ ./FMS --taille-IV=4 --taille-cle=7 --cle="12 34 56" --nb-IV-faibles=300 -vvv Pour l'octet n=0 : ...................................................................... .......................................................................................... .......................................................................................... .................................................. - il a eu 300 vecteurs d'initialisation faibles sur 6498079 vecteurs testés. (0.004617%) - l'octet le plus fréquent est 12. Il apparaît 12 fois (4.00%). Pour l'octet n=0 : ...................................................................... .......................................................................................... .......................................................................................... .................................................. - il a eu 300 vecteurs d'initialisation faibles sur 2326398 vecteurs testés. (0.012895%) - l'octet le plus fréquent est 34. Il apparaît 20 fois (6.67%). Pour l'octet n=0 : ...................................................................... .......................................................................................... .......................................................................................... .................................................. - il a eu 300 vecteurs d'initialisation faibles sur 2653570 vecteurs testés. (0.011306%) - l'octet le plus fréquent est 56. Il apparaît 21 fois (7.00%). OK, clé = 12 34 56
La fonction principale appelle la fonction predit_octet_multiple pour deviner chacun des octets de la clé WEP. Cette fonction doit appeler la fonction predit_octet_simple qui prend en arguments :
Elle doit verifier si le vecteur d'initialisation est faible, et si oui, faire une prédiction sur l'octet approprié de la clé WEP. (Voir les détails de l'attaque.)
Regardez le code actuel de predit_octet_multiple et insérer un appel approprié à predit_octet_simple.
Programmez ensuite la fonction predit_octet_simple :
/********************************************************************** * teste un vecteur d'initialisation : * * - "IV" est le vecteur en question * * - "o_rc4" est le premier octet généré par RC4 avec "IV" * * - "n" est l'octet de la clé que l'on recherche * * - "cle_partielle" est la clé partielle que l'on a déjà calculée * * * * La fonction renvoie 1 si le vecteur était faible, et dans ce cas, * * la prédiction correspondante se trouve dans le dernier paramètre * * "prediction". * **********************************************************************/ int predit_octet_simple(octet *IV, octet o_rc4, int n, octet *cle_partielle, octet *prediction)
Si on ne spécifie pas les options --nb-IV-faibles et --nb-IV, les vecteurs d'initialisation seront de la forme { 3+n, 255, X }, pour X = 0, 1, ... 255. Ces vecteurs sont presque tous faibles.
Commencez par tester uniquement avec ces vecteurs car c'est beaucoup plus rapide.
Pour tester : en ajoutant quelques affichages, j'obtiens :
$ ./FMS --taille-cle=4 --cle="12" -vvvv Pour l'octet n=0 : Le vecteur (03, FF, 00) est faible. La prédiction pour l'octet 0 de la clé WEP est "E8". Le vecteur (03, FF, 01) est faible. La prédiction pour l'octet 0 de la clé WEP est "EF". Le vecteur (03, FF, 02) est faible. La prédiction pour l'octet 0 de la clé WEP est "79". Le vecteur (03, FF, 03) est faible. La prédiction pour l'octet 0 de la clé WEP est "E9". Le vecteur (03, FF, 04) est faible. La prédiction pour l'octet 0 de la clé WEP est "6C". ... ... Le vecteur (03, FF, FB) n'est pas faible. Le vecteur (03, FF, FC) n'est pas faible. ...
Complètez le code de la fonction predit_octet_multiple pour garder l'octet prédit le plus souvent. Il faudra ajouter les variables / structures de données nécessaires...
/********************************************************************** * devine le "n"-ième octet de la clé (en supposant qu'on connaît les * * n-1 octets précédents) en essayant tous les vecteurs * * d'initialisations faibles. * * L'argument "cle_wep_partielle" contient le début de la clé (octets * * 0 à "n"-1, non compris). * * La fonction ne modifie pas les "n"-1 premières valeurs de * * "cle_wep_partielle". * * * * L'argument "nb_IV_faibles_total" est le nombre de vecteurs faibles * * à considérer. * * L'argument "nb_IV_total" est le nombre total de vecteurs à tester. * * * * La fonction s'arrête quand l'une des deux bornes est atteinte. * * * * Si les 2 bornes sont nulles, on utilise alors uniquement la * * famille de vecteurs {3+n, 255, ...}. * * * * La fonction renvoie "n" si l'opération c'est bien passée. Dans ce * * cas, l'octet "n"-1 de "cle_wep_partielle" est positionné à sa * * valeur. * * * * La fonction renvoie "-1" en cas de problème. La "n"-ième valeur de * * "cle_wep_partielle" est alors quelconque. * **********************************************************************/ int predit_octet_multiple(int n, octet *cle_wep_partielle, int nb_IV_faibles, int nb_IV_total)
Pour tester :
./FMS --taille-cle=4 --cle="12" -vvvv
On teste uniquement les vecteurs de la forme {n+3,255,...}
Pour l'octet n=0 : ......................................................................
..........................................................................................
..........................................................................................
....
Table de fréquences (*_* = plus fréquent)
00 1 | 20 1 | 40 1 | 60 2 | 80 1 | a0 3 | c0 0 | e0 2 |
01 0 | 21 0 | 41 2 | 61 0 | 81 1 | a1 1 | c1 1 | e1 0 |
02 2 | 22 0 | 42 0 | 62 2 | 82 0 | a2 1 | c2 0 | e2 5 |
03 0 | 23 0 | 43 0 | 63 0 | 83 1 | a3 1 | c3 2 | e3 0 |
04 0 | 24 1 | 44 0 | 64 0 | 84 1 | a4 1 | c4 0 | e4 1 |
05 1 | 25 2 | 45 2 | 65 2 | 85 1 | a5 0 | c5 1 | e5 0 |
06 3 | 26 1 | 46 1 | 66 0 | 86 0 | a6 2 | c6 1 | e6 2 |
07 0 | 27 2 | 47 2 | 67 1 | 87 0 | a7 0 | c7 1 | e7 3 |
08 1 | 28 0 | 48 1 | 68 1 | 88 1 | a8 1 | c8 0 | e8 2 |
09 0 | 29 0 | 49 1 | 69 2 | 89 1 | a9 1 | c9 2 | e9 1 |
0a 0 | 2a 1 | 4a 0 | 6a 0 | 8a 1 | aa 1 | ca 0 | ea 0 |
0b 0 | 2b 1 | 4b 2 | 6b 1 | 8b 1 | ab 0 | cb 3 | eb 2 |
0c 1 | 2c 0 | 4c 1 | 6c 1 | 8c 1 | ac 3 | cc 0 | ec 3 |
0d 0 | 2d 1 | 4d 2 | 6d 1 | 8d 0 | ad 0 | cd 1 | ed 0 |
0e 1 | 2e 2 | 4e 0 | 6e 0 | 8e 2 | ae 0 | ce 0 | ee 1 |
0f 3 | 2f 2 | 4f 2 | 6f 2 | 8f 1 | af 0 | cf 0 | ef 3 |
10 0 | 30 2 | 50 3 | 70 1 | 90 0 | b0 0 | d0 1 | f0 0 |
11 1 | 31 0 | 51 0 | 71 2 | 91 0 | b1 0 | d1 1 | f1 0 |
*12 14*| 32 1 | 52 1 | 72 3 | 92 2 | b2 1 | d2 0 | f2 0 |
13 1 | 33 0 | 53 2 | 73 0 | 93 4 | b3 0 | d3 1 | f3 2 |
14 0 | 34 1 | 54 1 | 74 1 | 94 0 | b4 2 | d4 2 | f4 2 |
15 0 | 35 2 | 55 0 | 75 1 | 95 1 | b5 0 | d5 1 | f5 0 |
16 2 | 36 1 | 56 0 | 76 3 | 96 1 | b6 1 | d6 0 | f6 2 |
17 1 | 37 1 | 57 0 | 77 2 | 97 2 | b7 1 | d7 3 | f7 1 |
18 1 | 38 2 | 58 1 | 78 0 | 98 0 | b8 0 | d8 3 | f8 1 |
19 0 | 39 1 | 59 0 | 79 2 | 99 2 | b9 2 | d9 0 | f9 1 |
1a 1 | 3a 0 | 5a 1 | 7a 2 | 9a 1 | ba 0 | da 1 | fa 2 |
1b 0 | 3b 0 | 5b 3 | 7b 1 | 9b 1 | bb 1 | db 2 | fb 1 |
1c 0 | 3c 1 | 5c 0 | 7c 1 | 9c 0 | bc 0 | dc 0 | fc 3 |
1d 1 | 3d 1 | 5d 1 | 7d 0 | 9d 0 | bd 2 | dd 1 | fd 1 |
1e 1 | 3e 2 | 5e 0 | 7e 0 | 9e 0 | be 0 | de 0 | fe 2 |
1f 0 | 3f 1 | 5f 1 | 7f 0 | 9f 0 | bf 0 | df 0 | ff 0 |
- il a eu 254 vecteurs d'initialisation faibles sur 256 vecteurs testés. (99.218750%)
- l'octet le plus fréquent est 12. Il apparaît 14 fois (5.51%).
OK, clé = 12
{ 3+n, 255, X } ?
Vous pouvez récupérer ici et là deux fichiers objets contenant le code compilé de rc4.c avec une clé secrète. Les seules différences avec rc4.c sont :
cle_wep est statique (donc inaccessible à partir d'un autre fichier)
nouvelle_cle_wep_aleatoire() produit toujours la même clé
Écrivez une petite fonction principale dans un fichier craque.c qui essaie de récupérer les deux clés secrètes. Mettez-les en commentaire en haut de votre fichier nom-prenom.c. (Pas besoin de m'envoyer votre fichier "craque.c".)
Votre fichier craque.c devra contenir :
int main () { octet cle_partielle[13]; // tableau pour reconstruire la clé WEP secrète nouvelle_cle_WEP_aleatoire(); // on initialise la clé WEP (avec la clé secrète) //... // on fait ensuite des appels à "predit_octet_multiple" //... }
Vous pourrez controler le nombre de vecteurs d'initialisation (ou le nombre de vecteurs d'initialisation faibles) à tester avec les arguments nb_IV_total et nb_IV_faibles_total.
Pour ceux qui sont sur une architecture 64 bits, voir plutôt ici et là.
Précisez quels types de vecteurs faibles vous avez considéré (vecteurs faibles généraux, ou uniquement de la forme {3+n, 255, X}) et combien ont été nécessaires.
Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 31-01-2014 à 07:41.