Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Sécurité Informatique Cryptographie et cryptanalyse October 17, 2018 Houcemeddi

Sécurité Informatique Cryptographie et cryptanalyse October 17, 2018 Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn École Nationale d’Ingénieurs de Carthage ENI-CARTHAGE Université Carthage Tunisie 1 Plan de cour Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 2 Cryptographie Principe et classiﬁcation Principe Cryptographie: Transformer un texte clair pour en cacher le sens Classiﬁcation ▶Selon le nombre de clés à utiliser: ▶Une seul clé, cryptosystème à clé privée (symétrique) ▶2 clés ou cryptosystème à clé publique (asymétrique) ▶Selon le type d’opérations: ▶substitution ▶transposition ▶produit des deux ▶Selon la façon dont le texte clair est traité: ▶Bloc ▶ﬂux (stream cipher) Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 3 Cryptographie Terminologie Terminologie basique ▶Plaintext : le message original ▶Ciphertext : le message chiffré ▶chiffrement ou cryptage : le processus de conversion du plaintext vers le ciphertext ▶déchiffrement ou décryptage : le processus de conversion du ciphertext vers le plaintext ▶cryptographie : l’étude des méthodes de cryptage (science des messages secrets) ▶cryptanalyse : l’étude des techniques pour casser les algorithmes de chiffrement ▶Cryptologie : la cryptographie et la cryptanalyse Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 4 Cryptographie Cryptage symètrique Modèle de cryptage symètrique ▶Aussi connu comme cryptage conventionnel ou cryptage à clé secrète. ▶c’était le seul type de cryptage jusqu’à invention du cryptage asymétrique ds les années 70. ▶reste comme même le cryptage le plus répandu des deux Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 5 Cryptanalyse Principe Principe ▶Son objectif est de retrouver la clé secrète pas simplement le plaintext ▶brute force attack (attaque à force brute) : ▶essayer toutes les combinaisons (sur une ciphertext pour le déchiffrer) de la clé jusqu’à trouver la bonne ▶En moyenne, il faut essayer au moins la moitié des clés disponibles pour arriver à casser un cryptosystème. ▶cryptanalytic attack : plus intelligente, exploite une connaissance sur l’algorithme et la manière dont le plaintext est traité. Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 6 Cryptanalyse Protocole d’attaque cryptographique general Collecte d’informations : faiblesses théoriques Observation ou action :Étape "on-line" connecté à la cible. ▶Ciphertext-only attack(COA) ▶Known-plaintext attack(KPA) ▶Chosen-plaintext attack(CPA) ▶Chosen-ciphertext attack(CCA) Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 7 Cryptanalyse Protocole d’attaque cryptographique general Collecte d’informations : faiblesses physiques Attaques par canal auxiliaire : Side Channel Attack ▶Mesure du temps de cryptage/décryptage : étude du temps mis pour effectuer certaines opérations ▶Fuites électromagnétiques : émet des rayonnements qui varient selon les opérations effectuées ▶Analyse du Comportement du processeur lors du calcul : bruit acoustique ▶Analyse de la consommation d’énergie : Une consommation accrue indique un calcul important et peut donner des renseignements sur la clé Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 8 Cryptanalyse Protocole d’attaque cryptographique general Analyse, déduction et exploitation ▶Étape "off-line" : Analyse & Déduction ▶Attaque à force brute : essayer toutes les clés possibles pour retrouver un texte en clair à partir du cryptogramme ▶Attaque statistique : Estimer la fréquence d’apparition des lettres dans un texte ▶Attaque algébrique : trouver des représentations équivalentes du cryptosystème, exploiter des linéarités existantes. ▶Cryptanalyse linéaire : approximation linéaire de l’algorithme de chiffrement, augmenter le nombre de couples pour améliorer l’approximation. ▶Cryptanalyse différentielle : étudier la manière dont les différences entre les entrées affectent les différences de leurs sorties pour découvrir des vulnérabilités. ▶Exploitation : Estimation de la clé et Déchiffrement de tous les cryptogrammes. Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 9 Cryptanalyse Protocole d’attaque cryptographique general Exemple: Brute force attack Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 10 Cryptographie classique Algorithmes de substitution CESAR ▶Consiste à remplacer les lettres du plaintext par d’autres lettres ou symboles ou bits. ▶le plus connu est l’algorithme de Cesar : remplacer chaque lettre par celle qui la suit apres trois positions ds l’alphabet ▶L ’alphabet est enroulé de sorte que la lettre qui suit Z est A ▶ex : plain : meet me after the toga party cipher : PHHW PH DIWHU WKH WRJD SDUWB CESAR: modèlisation mathématique ▶l’alg peut etre exprimé comme : c = E(3, p) = (p + 3)mod26 ▶le decalage peut etre généralisé à n’importe quel nombre k : c = E(k, p) = (p + k)mod26 ▶si k ∈[1, 25], alors le déchiffrement est : p = D(k, c) = (c −k)mod26 Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 11 Cryptographie classique Algorithmes de substitution CESAR: Brute force attack Brute force attack sur Cesar : essayer toute les 26 combinaisons Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 12 Cryptographie classique Algorithmes de substitution Monoalphabetic cipher ▶consiste a remplacer chaque lettre arbitrairement (pas simple décalage) ▶la clé est de longueur 26 : ▶Plain : a b c d e f g h i j k l m n o p q r s t u v w x y z ▶Cipher : D K V Q F I B J W P E S C X H T M Y A U O L R G Z N ▶exemple : Plaintext : if we wish to replace letters Ciphertext : WI RF RWAJ UH YFTSDVF SFUUFYA Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 13 Cryptographie classique Monoalphabetic cipher Sécurité du crypto monoalphabetique ▶On a un total de 26! = 4 × 1026 clés possibles, mais on peut le casser par analyse de fréquence : Al-Kindy ▶Le langage humain est très redondant, ex ds le msg "th lrd s m shphrd shll nt wnt" les lettres de cette façon ne sont pas ordinaire en anglais ▶En anglais la lettre "E" est la plus utilisée, suivie par : "T,R,N,I,O,A,S" ▶les lettres comme "Z,J,K,Q,X" sont rares en utilisation. ▶il ya des doublets ou des triplets qui sont plus répondu que d’autres. Fréquences des lettres en anglais Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 14 Cryptographie classique Monoalphabetic cipher Sécurité du crypto monoalphabetique: Exemple de cryptanalyse ▶etant donné un ciphertext :UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXU DBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYE- POPDZSZUFPOMBZWPF UPZHMDJUDTMOHMQ ▶On compte la fréquence de chaque lettre ds le ciphertext ▶On peut deviner que P et Z sont e et t ▶On peut deviner que ZW est th et donc ZWP est the ▶la séquence ZWSZ est remplacé par th*t, on peut deviner que S est a ▶on continu avec la technique essai-erreur-essai, on trouve le plaintext : "it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow" Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 15 Cryptographie classique Playfair Principe ▶L ’algorithme le plus connu qui crypte plusieurs lettres en même temps ▶traite les diagrammes (2 lettres) comme unité et la converti en diagramme ciphertext. ▶basé sur une matrice 5 × 5 utilisant un mot clé ▶inventé par le Britannique Sir Charles Wheatstone en 1854 ▶utilisé par l’armée Britannique en W.W.I et par l’USA et ses alliés durant la guerre W.W.II Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 16 Cryptographie classique Playfair Matrice Playfair ▶copier les lettres du mots clé dans la matrice (sans duplication) ▶completer le reste de la matrice par les lettres manquantes ▶les lettres I et J sont traités comme une seule lettre ▶ex : en utulisant le mot clé MONARCHY Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 17 Cryptographie classique Playfair Cryptage Playfair ▶opérer sur des diagrammes de lettres (2 lettres) à chaque fois ▶cas particulier : si diagramme de même lettres, séparer par des lettres spéciales ex : x. par exemple : balloon est traité comme ba lx lo on ▶Si plaintext dans la même ligne : remplacer par les lettres de droite. Ex1 pq est remplacé par qs. Ex2 ar est remplacé par RM. ▶Si plaintext dans la même colonne : remplacer par les lettres en-dessous. ex mu est remplacé par CM ▶sinon, remplacer par lettre en même ligne qu’elle et même colonne que l’autre lettre du plaintext. ex hs est remplacé par BP. ex2 ea devient IM ou JM Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 18 Cryptographie classique Playfair Sécurité de Playfair ▶Sécurité amélioré puisque il ya en tout 26 × 26 = 676 diagrammes ▶on a besoin d’une analyse fréquentielle sur 676 unité et non plus sur 26 comme le monoalphabetique ▶donc l’alphabet du ciphertext est aussi énorme ▶il peut être cassé si on connaît une centaine de plaintext/ciphertext Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 19 Cryptographie classique Playfair fréquence des lettres Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 20 Cryptographie classique Algorithmes poly-alphabètique Avantages ▶améliore la sécurité en combinant plusieurs algorithme mono-alphabetiques ▶rende la cryptanalyse plus difﬁcile avec augmentation d’alphabets et une distribution fréquentielle plus platte ▶utilise une clé pour choisir quel alphabet mono-alphabetique à utiliser pour chaque lettre du plaintext ▶répéter du début si la ﬁn de la clé est atteinte Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 21 Cryptographie classique Algorithmes poly-alphabètique Vigenère ▶l’algorithme poly-alphabetique le plus simple : algorithmes de Cesar muliples ▶la clé est constitué de caractères K = k1k2...kd ▶la ième lettre de la clé spéciﬁe le ième algorithme de Cesar à utiliser ▶repeter des le debut chaque d lettres du plaintext Houcemeddine HERMASSI houcemeddine.hermassi@enit.rnu.tn | Sécurité Informatique 1 22 Cryptographie classique Algorithmes poly-alphabètique Vigenère: Exemple ▶écrire le plaintext ▶écrire la clé et uploads/Science et Technologie/ presentation-secinfo2-houcem.pdf