Introduction à la Cryptographie

Généralités et concepts de base

• La cryptographie est omniprésente, assurant la sécurité des communications, le cryptage des fichiers, la protection du contenu et l'authentification des utilisateurs.

Sécurité des communications

• La navigation web est sécurisée par TLS (Transport Layer Security).
• Les communications sans fil utilisent des protocoles comme IEEE802.11i, WPA2, GSM et Bluetooth.

Cryptage de fichiers sur le disque

• Des outils comme EFS, TrueCrypt et BitLocker servent à crypter les fichiers stockés sur un disque.

Protection de contenu

• Des technologies comme CSS et AACS protègent le contenu des DVD et Blu-ray.

Définition de la cryptographie et de la cryptanalyse

• Cryptographie et cryptanalyse proviennent du grec: "Kruptos" signifiant cacher et "logos" signifiant science.
• Cryptographie est l'art de concevoir des cryptosystèmes dans le but de sécuriser des communications.
• Un cryptosystème est un mécanisme qui assure les services de sécurité nécessaires.
• Cryptanalyse est l'art de casser les cryptosystèmes.

Objectifs de la cryptographie

• Deux notions de base caractérisent la cryptographie, premièrement l'établissement une clé et deuxièmement une communication sécurisée.
• Elle vise à parer aux attaques passives telles que l'espionnage.
• Elle vise à parer aux attaques actives telles que l'usurpation d'identité (de l'émetteur ou du récepteur), l'altération des données (modification du message) et la répudiation du message (l'émetteur nie l'envoi).

Services de la sécurité

• Confidentialité : Assurer que l'information ne soit accessible qu'aux personnes autorisées.
• Intégrité : Garantir que l'information ne subisse pas d'altérations frauduleuses.
• Authentification : Vérifier l'identité de l'émetteur d'un message.
• Non-répudiation : Empêcher une partie de nier un acte ou un engagement.

Points clés à retenir sur la cryptographie

• La cryptographie est un outil puissant qui forme la base de nombreux mécanismes de sécurité.
• Elle n'est pas la solution à tous les problèmes de sécurité.
• Elle est fiable si elle est mise en œuvre et utilisée correctement.
• Il existe de nombreux cryptosystèmes ad hoc qui sont vulnérables.

Historique de la cryptographie avant l'ère de la technologie

• La scytale était un des premiers outils de cryptographie.
• Le cryptogramme de César fut un autre système ancien.
• Parmi les méthodes de chiffrement, on retrouve le chiffrement par substitution, le chiffrement de Vigenère, le chiffrement de Hill et le chiffrement de Vernam.

La scytale

• La scytale est un instrument de transposition utilisé pour le chiffrement.
• Un message crypté avec une scytale ressemble à: KTMIOILMDLONKRIIRGNOHGWT

Le cryptogramme de César

• Jules César, chef des armées romaines autour de 100 avant J.-C., utilisait un cryptogramme basé sur un décalage des lettres.
• Le chiffrement consiste en un décalage circulaire des lettres de l'alphabet.
• Le déchiffrement est un décalage dans le sens inverse.
• L'espace de clés est l'ensemble des décalages possibles, soit 26 options (0 à 25).
• La sécurité est faible car toutes les clés peuvent être testées manuellement.
• Exemple : ATTAQUE AU MATIN devient DWWDTXH DX PDXLQ avec un décalage de 3.

Chiffrement par substitution

• Se base sur l'association de chaque lettre de l'alphabet à une autre, sans règle générale.
• Exemple : ATTAQUE AU MATIN devient DAADECV DC WDASI selon une substitution définie.
• Le déchiffrement nécessite l'application des substitutions inverses.
• L'avantage est un grand espace de clés.
• L'inconvénient est une clé longue constituée de 26 lettres.
• Malgré le grand nombre de clés, le déchiffrement reste aisé.
• Le nombre de clés est égal à 26!, soit environ 4.10^26.
• Une machine testant 1 000 000 de clés par seconde prendrait 12 millions d'années.
• La faiblesse est qu'une même lettre est toujours cryptée de la même manière.
• La cryptanalyse exploite les fréquences d'apparition des lettres dans la langue française.

Cryptanalyse de la substitution de lettres

• On peut déchiffrer un message en utilisant les fréquences d'apparition des lettres en français.
• La clé de chiffrement ULOIDTGKXYCRHBPMZJQVWNFSAE peut être déduite en analysant la fréquence des lettres cryptées.

Le chiffrement de Vigenère

• Il utilise une correspondance entre les lettres et des nombres (A=0, B=1, ..., Z=25).
• Le chiffrement se fait par addition des lettres, par exemple J + W = F (9 + 22 mod 26 = 5).
• Exemple: l'addition sur les lettres du mot "CRYP" donne QFSH

Le chiffrement de Vernam (1917)

• Il s'agit d'un chiffrement de Vigenère qui est sûr si la clé est aussi longue que le message, utilisée une seule fois et purement aléatoire.
• En pratique, il n'est jamais utilisé, car l'échange de la clé est aussi délicat que le message, la création de la clé est difficile (clé aléatoire) et la gestion de la clé est complexe.

Le chiffrement de Hill

• Basé sur une correspondance entre chaque lettre et un nombre (A=0, B=1, ..., Z=25).
• Le processus consiste à considérer des blocs de lettres consécutives, et à utiliser une matrice pour chiffrer le message.
• La matrice en représente la clé de chiffrement.
• Par exemple, une matrice 2x2 peut agir sur des vecteurs de longueur 2.
• La formule de chiffrement est: (𝑐1= 𝑎.𝑚1+ 𝑐. 𝑚2, 𝑐2= 𝑏.𝑚1+ 𝑑. 𝑚2), modulo 26.
• Avec l'exemple (17,4) × 𝑀 = (C1=173+421=135 mod 26=5, C2=175+48=117 mod 26=13), le couple de lettres RE devient le couple (F,N).

Cryptographie moderne

• Elle s'appuie sur les principes de Kerckhoffs.
• Elle est marquée par l'âge de la technique et le codage de l'information.
• Elle met l'accent sur le cryptage à clé.

Cryptanalyse du chiffrement par transposition

• Déterminer si une substitution n'a pas été utilisée.
• Une analyse statistique des caractères suffit à déterminer si les caractères ont été substitués, les statistiques fréquentielles du texte sont identiques à celles d'un texte en clair.
• S'il n'y a pas une substitution, une transposition a été employée.
• Ensuite, il faut faire une hypothèse sur le nombre de colonnes utilisées pour réaliser la transposition.
• Les codes de transposition modifient l'ordre des caractères, contrairement aux codes de substitution qui les cachent.

Renforcer la force des chiffrements

• Avec l'arrivée de l'ordinateur, les méthodes traditionnelles de substitution/transposition sont devenues obsolètes, car elles ne résistent pas au traitement informatique.
• La combinaison de substitution et de transposition permet de faire subir aux caractères du « texte en clair » une substitution suivie de plusieurs opérations de transposition.
• Il faut changer très souvent les paramètres de ces combinaisons.
• Le but est de rendre l'apparence du cryptogramme la plus « aléatoire » possible.

Principes de Kerckhoffs

• Auguste Kerckhoffs (1835-1903) était un cryptologue militaire néerlandais.
• En 1883, il a énoncé les principes de base de la cryptographie moderne dans un article intitulé « La cryptographie militaire ».
• L'important est de distinguer un système d'écriture chiffrée pour des échanges momentanés et une méthode de cryptographie durable.
• Les utilisateurs devraient pouvoir modifier leurs conventions et ne jamais conserver d'objets ou écrits susceptibles d'aider l'ennemi.

L'âge de la technique

• Alan Mathison Turing (1912-1954), mathématicien britannique, a été un pionnier de l'informatique et de l'intelligence artificielle.
• L'armée allemande a remporté de nombreuses victoires au début de la Seconde Guerre mondiale grâce à la machine Enigma.
• Turing a conçu le Kolossus, une machine électronique pour décrypter les messages allemands.
• La cryptographie a joué un rôle majeur de 1939 à 1945, avec les alliés cassant le code Enigma des allemands.

Chiffrement de Vernam

• Le chiffrement de Vernam est basé sur une opération XOR entre le message et la clé.
• Chiffré = Message XOR Clé
• Le déchiffrement se fait par une opération XOR similaire : Message = Chiffré XOR Clé

Le cryptage à clé

• Le chiffrement moderne repose sur l'utilisation d'un algorithme public et d'une clé.
• Il correspond à la cryptographie moderne selon les principes de Kerckhoffs.
• Auparavant, les algorithmes étaient simples, mais utilisaient des clés longues, maintenant, des algorithmes sophistiqués et complexes sont utilisés avec des clés courtes.

Chiffrement symétrique

• Le chiffrement par blocs (DES, IDEA, AES…) et les calculs dans le corps de Galois GF(28) sont courants.
• La force d'un mot de passe est un aspect important.

Approche théorique du chiffrement symétrique

• Il repose sur une formule mathématique, où Cryptogramme = Fonction(Message, clé).
• Le message peut être récupéré avec Message = Fonction_inverse(Cryptogramme, clé).
• La plupart des codes utilisés sont rapides et s'appliquent à un fort débit de données.
• Le chiffrement symétrique repose sur l'échange d'un secret (les clés).
• La gestion des clés nécessite que chaque paire d'interlocuteurs partage une clé unique, ce qui implique N*(N-1)/2 clés pour N interlocuteurs.

Chiffrement symétrique: Blocs et flux

• Dans le chiffrement par blocs, les messages sont découpés en blocs: DES (64 bits, clé de 56 bits), IDEA (64 bits, clé de 128 bits), AES (128 bits, clé de 128 bits).
• Dans le chiffrement par flots, les messages sont traités comme un flux de données, RC4 (chiffrement octet par octet), A5.

Chiffrement à clé symétrique par bloc

• Le principe est de couper le message en blocs de même taille qui sont encryptés un par un et finalement concaténés.
• Il existe quatre modes d'opération : ECB (Electronic CodeBook), CBC (Cipher-Block Chaining), CFB (Cipher Feedback), OFB (Output Feedback).

Chiffrement par bloc : ECB (Electronic CodeBook)

• Fonctionnement : (M → M₁, ..., Mᵢ, ... ) → (E) → Clé C ← (· C₁, ..., Cᵢ, ...) et au déryptage C → (· C₁, ..., Cᵢ, ...) → E⁻¹ → Clé M ← (· M₁, ..., Mᵢ, ...)
• Avantages : Simplicité et intégrité des blocs indépendante.
• Inconvénients : Expose le format des données, "usure" de la clé.

Chiffrement par bloc : CBC (Cipher-Block Chaining)

• Fonctionnement : M → (· M₁, ..., Mᵢ, ...) + (E → Clé ` IV, C₁, ..., Cᵢ, ... C ← (· C₁, ..., Cᵢ, ...) et au déryptage C → (·(· C₁, ..., Cᵢ, ...) → E⁻¹ → Clé E (IV), C₁, ..., Cᵢ, ... M ← (· M₁, ..., Mᵢ, ...) +
• IV est un vecteur d'initialisation public.
• Avantage : Plus sûr et presque aussi rapide que EBC.
• Inconvénient : Si le bloc Cᵢ est corrompu, alors on ne peut pas décoder Cᵢ₊₁.

Exemples de chiffrements par bloc

• DES, IDEA, Blowfish, AES, et Serpent sont des algorithmes de chiffrement par bloc.
• Ils diffèrent par la taille des blocs, la taille de la clé, l'année de création et les inventeurs.

Diagrammes de Feistel

• Les algorithmes à clé secrète cherchent à tendre vers la perfection, en cryptographie, c'est l'aléatoire : il faut que le message codé paraisse aussi aléatoire que possible, pour limiter au minimum les risques d'une attaque par analyse du texte chiffré, de ses redondances, etc.
• On crypte le message w ∈ {0,1}²ˡ avec 2 rondes
• On utilise deux fonctions clé : f₁ : {0,1}ˡ → {0,1}ˡ et f₂ : {0,1}ˡ → {0,1}ˡ

Formalisme des diagrammes de Feistel

• Application de rondes de cryptage et de décryptage avec des fonctions déterminées.
• Il existe un exemple de cryptage avec deux rondes.
• La sortie est définie par des équations spécifiques impliquant les fonctions et les entrées.

D.E.S. (Data Encryption Standard)

• En 1973, le NBS (National Bureau of Standards) a lancé un appel pour la création d'un algorithme de chiffrement.
• IBM a conçu (Lucifer) en 1971 par Horst Feistel.
• Modifié par la NSA (National Security Agency), il est devenu DES.
• Le message est décomposé en blocs de 64 bits, qui sont chiffrés un par un.
• L'algorithme utilise une clé de 56 bits.
• Il repose sur des décalages, des opérations « ou exclusif » et de transposition/recopie.
• Ces opérations sont faciles à réaliser par un processeur.

D.E.S. (Data Encryption Standard) : Codage

• Expansion de la clé: 16 fonctions f1,…, f16 sont construites à partir de la clé par des permutations sur 4 bits (S-boîtes).
• Application du schéma de Feistel avec un bloc de 64 bits et une permutation sur 64 bits fixée.

Cryptanalyse contre le D.E.S.

• Recherche exhaustive (attaque par force brute): On essaie toutes les clés possibles soit 256 ≈ 7 · 1016, soit 2,3 années/machine pour un test de 1 000 000 000 clés par seconde.
• En 1998, le EFF (Electronic Frontier Foundation) a construit pour environ $250,000 une machine spécialisée qui casse une clé D.E.S. en moins de deux jours.
• Le protocole Triple D.E.S. consiste à appliquer trois fois le protocole D.E.S. avec trois clés différentes et, bien que désormais obsolète avec l'arrivée de A.E.S., est toujours considéré comme sûr.

AES. (Advanced Encryption Standard)

• Début d'offre par le NIST (National Institute of Standards and Technology) le 2 janvier 1997.
• AES: Appel d'offre international pour faire face aux clés trop courtes du DES donc la cryptanalyse part recherche exhaustive devient possible.
• Algorithme plus efficace que le triple DES, avec des clés de 128, 192 ou 256 bits et des blocs plus grands.
• Blocs de 128 bits et des clés de 128, 192 ou 256 bits.

Détails concernant le Advanced Encryption Standard (AES)

• Une quinzaine de candidats sont proposés pour la première étape du concours : CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish.
• Les cinq finalistes inclus : MARS, RC6, Rijndael, Serpent, Twofish.
• Rijndael de Vincent Rijmen et Joan Daemen (Belges) a remporté le concours AES et entrait dans un processus de standardisation officielle le 2 octobre 2000 et a été approuvé dans le standard FIPS PUB 197 le 26 novembre 2001 par le NIST.
• Les critères de sélection définie par le NIST étant la sécurité et le cout de son implémentation.
• AES est un algorithme de chiffrement non Feistel existant en trois versions 10, 12 et 14 tours (ronds):
• Le clés des chacune des déclinaison taille de clés (128, 192 ou 256 bits).
• Les sous-clés de tours (round keys) font 128 bits.

Composants de l'AES

• State est un tableau 2D d'octets de 4×4.
• En entrée du block, il y a les octets Bo, B1, B2 jusqu'à B15.
• Les opérations de transformations se font ensuite.
• Ensuite, il est découpé sous forme d'état.

Transformation du Bloc à State

• Les octets rentrent dans le bloc.
• Si est la valeur de State à un instant initial, chaque octet entre est transformé à l'aide de la formule mod 4, ( i / 4)

AES : Transformations dans les rounds

• Structure de chaque Round dans le processus de chiffrement (SubBytes, ShiftRows, MixColumns, AddRoundKey).
• Un AddRoundKey est appliquée avant le 1er Round. La 3ème transformation est omise dans le dernier Round.

Transformation SubBytes

• Elle est non linéaire, appliquée indépendamment à chacun des octets de la matrice State en utilisant une table de substitution (S-Box).

Transformation ShiftRows()

• Processus de permutation cyclique des octets sur les lignes de l'état.
• Le décalage des octets correspond à l'indice de la ligne examinée.

Transformation MixColumns().

• Transformation appliquée à un état colonne après colonne.
• C'est une transformation linéaire : un produit matriciel utilisant les 4 octets d'une colonne.

Transformation AddRoundKey()

• Correspond à l'ajout de la clé de ronde (ou de la clé lors de la ronde initiale) à l'état considéré (l'addition étant prise au sens ou exclusif)
• Pour l'implémentation XOR XOR | 0 1
• -- | - - 0 | 0 1 1 | 1 0

Calcul dans GF(28)

• Chaque élément de GF (28) est un polynôme de degrés 7 : a7.x7 + a6.x6 + a5.x5 + a4.x4 + a3.x3 + a2.x2 + a1.x + a0
• Les coefficients aᵢ sont représentés dans GF(2) (Z2)
• Un élément de GF (28), peut être représenté par une chaine de bits de longueur 8.
• La multiplication par A*{02} se traduit en A’ *02 = la logique à un décalage

Force d'un mot de passe

• C'est un moyen pour un identifiant prouver son authenticité
• L'entité prouve ses crédentiels pour se certifier "mot de passe" auprès du vérificateur pour ensuite recevoir les droit d'accès associé à son compte.
• La force du mot de passe se calcule par la longeur multiplié par le nombre de caractères possibles.