Introduction to (Modern) Cryptanalysis
Maxime Bombar
Lecture 1 1 / 28
Introduction and Preliminaries
Quelques mots de présentation
• Maxime Bombar
[Link]@[Link]
• Bureau 382, bâtiment A33 - IMB
• TODO: Site Web du Cours
Il n’y a pas de questions stupides !
Lecture 1 2 / 28
Organisation du Cours
• CM les Mardis de 14h à 15h20 - A29 / Salle 104
• TD/TP de 15h30 à 18h20 - A28 / Salle 009
• TP en SageMath: Objectif, amusez vous dans ces TPs.
• Du contrôle continu: 50% de la note
• Challenges de cryptanalyse ou DS de mi semestre.
• Projet (implémentation) en seconde moitié de semestre.
• Un examen final (3h) en décembre, sur papier: 50% de la note.
Lecture 1 3 / 28
Attention: Modification d’Emploi du Temps
• A priori, pas de cours le Mardi 10 Septembre.
• Décalé au Vendredi 13 (à confirmer ...)
Lecture 1 4 / 28
Lectures Complémentaires (Librement Accessibles)
A. Canteaut - Lecture Notes on Cryptographic Boolean Functions
A. Canteaut - Lecture Notes on ECC and their Applications to Symmetric Crypto
D. Boneh, V. Shoup - A Graduate Course in Applied Cryptography
C. Swenson - Modern Cryptanalysis: Techniques for Advanced Code Breaking.
Des notes sur la théorie de l’information: Par exemple E. Berardini, G. Zémor.
Le poly de l’an dernier : G. Castagnos - Cryptanalyse
Lecture 1 5 / 28
Autres Lectures Complémentaires
G. Zémor - Cours de Cryptographie
D. Vergnaud - Exercices et Problèmes de Cryptographie
A. Joux - Algorithmic Cryptanalysis
Lecture 1 6 / 28
Objectifs du Cours
• Culture générale des techniques modernes en cryptanalyse.
• Développer la capacité de lire de véritables articles de recherche
→ Visitez [Link].
• Mettre en application ces techniques sur de la crypto “de la vraie vie”
• Dans ce cours (TP)
• Dans vos stages
• Dans vos futurs jobs: Recherche ou entreprise (ou les deux, cf Ciffre)
• Mises en garde:
• N’implémentez pas votre propre crypto vous même (mais cryptanalyse OK).
• Plus efficace ne signifie pas forcément plus sûr.
Lecture 1 7 / 28
Essence de la Cryptographie
Confidentialité
Buts de la
Authenticité Intégrité
cryptographie
Essence de la Cryptographie
Confidentialité
Buts de la
Authenticité Intégrité
cryptographie
Cryptanalyse: Menacer n’importe quelle de ces propriétés.
Lecture 1 8 / 28
Cryptologie
Cryptographie: Cryptanalyse:
Design de systèmes Attaques de systèmes
Cryptologie
Lecture 1 9 / 28
Cryptologie
Cryptanalyse:
Cryptographie:
Attaques de systèmes
Design de systèmes
Cryptologie
Lecture 1 9 / 28
Cryptologie
Cryptanalyse:
Attaques de systèmes
Cryptographie:
Design de systèmes
Crypto
symmétrique
Cryptologie
Lecture 1 9 / 28
Réussir en Cryptanalyse (dans la vraie vie)
• La cryptanalyse, c’est difficile.
• Nécessite
• Du temps et de la persévérance
• De l’intuition
• De la pratique
• De la chance
• C’est probabiliste.
Lecture 1 10 / 28
Parfois aussi, une question de perspectives
Lecture 1 11 / 28
Parfois aussi, une question de perspectives
Lecture 1 11 / 28
Parfois aussi, une question de perspectives
Lecture 1 11 / 28
Contenu du cours (tentative)
• Chiffrement par blocs • Cryptanalyse Linéaire
• Chiffrement par flot • Cryptanalyse Différentielle
• Fonctions de hachage • Cryptanalyse Algébrique
• Réduction de réseaux ?
Attaques sur crypto asymétrique:
• Fuite d’information dans les signatures ?
Lecture 1 12 / 28
Outils Mathématiques
Probabilités Algèbre générale Algèbre
Théorie de l’info Groupes, anneaux, corps Linéaire
Mathématiques de la
Cryptanalyse
Complexité Théorie des nombres Algèbre Commutative
Algorithmic Design Géométrie Algébrique Modules, Polynômes
(multivariés)
Lecture 1 13 / 28
Principe de Kerckhoffs
• L’algorithme du cryptosystème ne doit pas être secret.
→ Le cryptanalyste connaît l’algorithme.
• Seule la clé doit être secrète.
→ La clé détermine une instance particulière du cryptosys-
tème.
Auguste Kerckhoffs
(1835-1903)
Lecture 1 14 / 28
Types de Cryptanalyse
Clair Connu
Chiffré Seul
Retrouve la clé à partir de couples (clair, chiffré).
Retrouve la clé ou le clair
Exemples: Recherche exhaustive, Enigma.
Clairs connus Aléatoires
Retrouve la clé à partir de couples (clair, chiffré),
mais où clair est aléatoire.
Canaux Auxiliaires Cryptanalyse
Utilise de l’information supplémentaire quantique
(consommation énergétique, injection de fautes...) Shor, Grover
cf: UE Cartes à Puces cf: UE Algo Arithmétiques
Lecture 1 15 / 28
Rappel: Chiffrement Symétrique
Formellement, couple (E , D)
E :M×K →C
et
D :C×K →M
telle que
DK (EK (m)) = m
Recherche Exhaustive: attaque à clair connu
Attaquant connaît (m, c) et calcule DK (c) pour toutes les clés K jusqu’à DK (c) = m.
Si |K| = 2n , recherche exhaustive réussi avec en moyenne O (2n−1 ) essais (Exercice).
Lecture 1 16 / 28
Grandes Familles de Chiffrement Symétriques
Une sécurité uniquement estimée par la cryptanalyse.
• Chiffrement par substitutions
• Chiffrement par blocs (AES)
• Chiffrement par transpositions
• Chiffrement par flot (ChaCha20)
Cryptanalyse: analyse fréquentielle,
Cryptanalyse: Linéaire,
et autres outils statistiques
Différentielle, Algébrique
(voir TD).
Cryptographie historique Cryptographie moderne
Lecture 1 17 / 28
Ne pas oublier
• Fonctions de Hachage
• Cryptanalyse
• Contre-mesures
Lecture 1 18 / 28
Rappel: Chiffrement à Clé Publique
• Attaque sur les messages - Retrouver
le texte clair uniquement à partir des
données publiques.
• Attaque sur les clés - Retrouver
une clé secrète à partir des données
publiques.
• Idéalement: repose sur des problèmes bien étudiés (Hypothèse Calculatoire)
Sécurité Réductioniste (cf UE Crypto Avancée).
• Cryptanalyse et réductions sont deux faces d’une même pièce.
Lecture 1 19 / 28
Shannon Theory of Secrecy
Chiffrement Inconditionnellement Sûr ?
Peut-on construire un chiffrement
de sorte que les chiffrés soient
indépendants des messages?
Quelle information sur le message
est contenue dans le chiffré ?
Claude Shannon
(1916-2001)
Lecture 1 20 / 28
Rappel: Entropie d’une variable aléatoire
Soit X une variable aléatoire à valeurs dans un ensemble fini X .
Entropie
def X
H(X ) = − PX (X = x ) log PX (X = x ) avec 0 × ∞ = 0.
x ∈X
L’entropie de X est maximale lorsque X est uniformément distribuée, et on a alors
H(X ) = log |X |.
L’entropie mesure le degré d’incertitude de la variable aléatoire.
Lecture 1 21 / 28
Entropie Conditionnelle et Information Mutuelle
Soient X , Y deux variables aléatoires à valeurs dans des ensembles finis X et Y.
Entropie Conditionnelle
def X
H(X | Y ) = − P(X = x , Y = y ) log P(X = x | Y = y )
x ,y
Information Mutuelle
def
I(X , Y ) = H(X ) − H(X | Y )
H(X | Y ) mesure l’incertitude résiduelle que l’on a sur X étant donnée Y .
Lecture 1 22 / 28
Système de Chiffrement au Sens de Shannon
Shannon propose une abstraction de système de chiffrement.
Un système de chiffrement pour une variable
aléatoire M (le message) est un couple de
variables aléatoires (K , C ) (respectivement
La seconde condition signifie que
la clé et le chiffré) tel que
le déchiffrement est toujours unique.
• M et K sont indépendantes.
• H(M|K , C ) = 0
Lecture 1 23 / 28
Chiffrement Parfait
Definition
Un chiffrement (K , C ) pour un message M est dit
parfait lorsque I(M; C ) = 0 ou de manière équivalente
H(M|C ) = H(M).
Dit autrement, la connaissance d’un chiffré n’apporte aucune information sur la valeur
du message original.
Lecture 1 24 / 28
Un exemple Pertinent: le Chiffrement de Vernam
Alias: Masque jetable (One-Time Pad)
Dans le chifrement One-Time Pad, M, K, C sont identifiés à un même groupe abélien G.
Pour une clé K ∈ G, et un message M ∈ G, le chiffré est
def
C = EK (M) = M + K .
Prop. Le One-Time Pad est un chiffrement parfait.
Lecture 1 25 / 28
Condition pour un Chiffrement Parfait
Théorème de Shannon pour le Chiffrement
Si (K , C ) est un chiffrement parfait pour un message M, alors
H(K ) ⩾ H(M)
Preuve: H(M) = H(M | C ) puisque le chiffrement est parfait
⩽ H((M, K )|C )
= H(K | C ) + H(M | (K , C )) règle de la chaîne.
= H(K | C ) chiffrement au sens de Shannon.
⩽ H(K ).
Lecture 1 26 / 28
Cryptographie en Pratique
• Pour G = (Z/2Z)n , la condition d’entropie implique que la clé doit être au-moins
aussi longue que le message pour avoir un chiffrement parfait.
• En pratique, un adversaire est limité en ressources.
• Comment estimer la sécurité d’un cryptosystème, étant donné cette limitation ?
Lecture 1 27 / 28
Cryptographie en Pratique
• Pour G = (Z/2Z)n , la condition d’entropie implique que la clé doit être au-moins
aussi longue que le message pour avoir un chiffrement parfait.
• En pratique, un adversaire est limité en ressources.
• Comment estimer la sécurité d’un cryptosystème, étant donné cette limitation ?
→ Sécurité calculatoire et Cryptanalyse !
Remarque: Le One-Time Pad est utilisé en cryptographie dans le partage de secrets
par exemple.
Remarque 2: Sécurité parfaite ne veut pas dire résistance à la cryptanalyse: OTP est
vulnérable à une attaque à clairs connus.
Lecture 1 27 / 28
Séance Prochaine: Chiffrement par flot
Idée: Remplacer une clé aléatoire, par une clé Pseudo-aléatoire.
Lecture 1 28 / 28