New Algorithmes à clé secrète Jean-Marc Robert · 2019. 6. 12. · Jean-Marc Robert, ETS Cryptologie - Clé secrète - A08 3 Introduction La cryptologie est la science des messages

CryptologieAlgorithmes à clé secrète

Jean-Marc Robert

Génie logiciel et des TI

Jean-Marc Robert, ETS Cryptologie - Clé secrète - A08 2

Plan de la présentation

◼ Introduction

◼ Science de la cryptologie

◼ Cryptographie à clé secrète

❑ Les principes essentiels

❑ Les notions importantes

◼ Conclusions


Introduction

◼ La cryptologie est la science des messages secrets et des

codes chiffrés utilisés traditionnellement par les militaires et

les gouvernements.

◼ Depuis l’avènement des transactions électroniques, la

cryptologie c’est démocratisée.

❑ Banques

❑ Internet

❑ …


Cryptologie

◼ Cryptographie

❑ Ensemble des principes, méthodes et techniques dont l'application

assure le chiffrement et le déchiffrement des données, afin d'en

préserver la confidentialité et l'authenticité.

◼ Cryptanalyse

❑ Ensemble des méthodes et procédés de décryptage visant à rétablir en

clair un cryptogramme, sans connaissance préalable de la clé de

chiffrement.

Jean-Marc Robert, ETS

Un peu d’histoire

◼ Tatouage sur la tête rasée d'un esclave. Secret caché par les cheveux repoussés!

◼ Scytale de Sparte (vers 500 av. J.-C.)

5◼Chamseddine Talhi, ÉTS

http://fr.wikipedia.org/wiki/Fichier:Skytale.png


Cryptographie – Objectifs

◼ Le but de la cryptographie est de développer des procédés

permettant à deux personnes de communiquer tout en

protégeant leurs messages.

❑ Préserver la confidentialité des messages.

❑ Vérifier l’intégrité des messages.


Cryptographie – Principes de Kerckhoffs

1° Le système doit être matériellement, sinon mathématiquement,

indéchiffrable ;

2° Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient

tomber entre les mains de l’ennemi ;

3° La clef doit pouvoir en être communiquée et retenue sans le secours de

notes écrites, et être changée ou modifiée au gré des correspondants ;

4° Il faut qu’il soit applicable à la correspondance télégraphique ;

5° Il faut qu’il soit portatif, et que son maniement ou son fonctionnement

n’exige pas le concours de plusieurs personnes ;

6° Enfin, il est nécessaire, vu les circonstances qui en commandent

l’application, que le système soit d’un usage facile, ne demandant ni

tension d’esprit, ni la connaissance d’une longue série de règles à observer.

Auguste Kerckhoffs, « La cryptographie militaire », Journal des sciences militaires, vol. IX, Janvier 1883.


Cryptographie à clé secrète (ou symétrique)

◼ Méthode permettant à deux personnes possédant une clé

secrète commune de s’échanger des messages de façon

sécurisée.

◼ La confidentialité des messages dépend de la confidentialité

de cette clé et de la robustesse de l’algorithme utilisé.


Cryptographie – Complexité

◼ La capacité d’un algorithme cryptographique à résister à des

attaques de cryptanalyse repose essentiellement sur

❑ L’algorithme choisi

❑ La confidentialité de la clé

❑ Le nombre de clés potentielles

◼ La longueur de la clé

❑ Entropie de la clé


Cryptographie – Définitions

Texte en clair: Texte d'origine, immédiatement intelligible et

pouvant donc être exploité directement, sans recours au

déchiffrement. (Plaintext)

Chiffrement: Opération par laquelle est substitué, à un texte en

clair, un texte inintelligible, inexploitable pour quiconque ne

possède pas la clé permettant de le ramener à sa forme

initiale. (Encryption)

Texte en clairDéchiffrementCryptogrammeChiffrementTexte en clair


Cryptographie – Définitions

Cryptogramme (ou texte chiffré): Message rendu inintelligible

grâce au chiffrement, qui ne peut être compris et utilisé que

par les seules personnes en possession de la clé permettant de

le déchiffrer. (Ciphertext)

Déchiffrement: Opération inverse d'un chiffrement réversible,

permettant à une personne autorisée, en possession de la clé,

de rétablir en clair un cryptogramme. (Decryption)

Texte en clairDéchiffrementCryptogrammeChiffrementTexte en clair


Cryptanalyse

◼ Afin de briser un code secret et d’obtenir ainsi les textes en

clair, l’attaquant a diverses possibilités:

❑ Attaques passives: par écoute électronique, l’attaquant obtient copie de

tous les textes chiffrés échangés entre les intervenants.

❑ Attaques actives: l’attaquant joue un rôle actif lors du protocole et peut

altérer ou détruire des messages.


Cryptanalyse – Types d’attaques

◼ Cryptogrammes seuls

❑ L’attaquant ne possède qu’une copie des cryptogrammes échangés.

◼ Textes en clair connus

❑ L’attaquant possède plusieurs paires (texte en clair, cryptogramme).

◼ Textes en clair choisis

❑ L’attaquant possède plusieurs paires (texte en clair, cryptogramme) dont

il a choisi le texte en clair.

◼ Cryptogrammes choisis

❑ L’attaquant choisit plusieurs cryptogrammes dont il obtient le texte en

clair correspondant.


Cryptanalyse – Types d’attaques (fin?)

◼ Réinsertion (replay)

❑ L’attaquant réinsère des messages dans la communication.

◼ Mesures indirectes (side channel attacks)

→ L’algorithme cryptographique doit être mis en œuvre dans le monde

physique.

❑ L’attaquant utilise des mesures indirectes pour obtenir la clé.

◼ Consommation de courant

◼ Émanations électromagnétiques


erqmrxuyrlflyrwuhsuhplhufubswrjudpph

bonjourvoicivotrepremiercryptogramme

◼ Algorithme: Décaler chaque lettre de X positions.

◼ Clé: X = +3

❑ a→d,b→e,c→f, …

◼ Problème: Lorsque l’algorithme est connu, il est facile d’essayer

toutes les 25 clés possibles.

L’algorithme de chiffrement de Jules César.

Cryptographie à clé secrète



fxcaxmrkxegekxzrwiwmbewlwgrouzxdrtllw

bonjourvoicivotredeuxiemecryptogramme

◼ Algorithme: Remplacer chaque lettre par une autre lettre.

◼ Clé: permutation

◼ Même si l’algorithme est connu, il est impossible d’essayer les

26!-1 clés possibles c.-à-d. 403291461126605635583999999.

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

t f g i w y d q e a s n l c x u h r v z m k j b o p


Substitution monoalphabétique

◼ Les deux méthodes précédentes appartiennent aux systèmes de

substitution monoalphabétique.

❑ Dans un texte en clair, une lettre est toujours substituée par la même

lettre.

◼ Si le texte est suffisamment long, il est possible de trouver la

substitution en analysant la fréquence des lettres.

❑ Donc, le texte en clair peut être retrouvé à partir du cryptogramme seul.

Même si le nombre de clés est grand,

cette méthode n’est pas acceptable.


Fréquences – langue française

E 17.67 O 5.34 B 0.80

S 8.23 D 3.60 H 0.64

A 7.68 C 3.32 X 0.54

N 7.61 P 3.24 Y 0.21

T 7.30 M 2.72 J 0.19

I 7.23 Q 1.34 Z 0.07

R 6.81 V 1.27 K 0.00

U 6.05 G 1.10 W 0.00

L 5.89 F 1.06

Pourcentage de la

fréquence des lettres


Substitution monoalphabétique

◼ Cryptanalyse: Langue Française

Fréquences des bigrammes sur 10 000 bigrammes 21

◼Chamseddine Talhi, ÉTS

ES 305 TE 163 OU 118 EC 100 EU 89 EP 82

LE 246 SE 155 AI 117 TI 98 UR 88 ND 80

EN 242 ET 143 EM 113 CE 98 CO 87 NS 79

DE 215 EL 141 IT 112 ED 96 AR 86 PA 78

RE 209 QU 134 ME 104 IE 94 TR 86 US 76

NT 197 AN 30 IS 103 RA 92 UE 85 SA 75

ON 164 NE 124 LA 101 IN 90 TA 85 SS 73

ER 163

SS 73M

M20 AA 3

EE 66 RR 17 UU 3

LL 66 PP 16 II 2

TT 29 FF 10 GG 1

NN 24 CC 8



cqqnpwuzpkfmwqwvfvusjulingfvzrurhtdqng

bonjourvoicivotretroisiemecryptogramme

◼ Algorithme: Additionner à chaque lettre la lettre de la clé.

◼ Clé: abcd

❑ abcdabcdabcdacbdacbdacbdabcdacbdabcdab

Le chiffre de Vigenère – Blaise Vigenère 1523-1596.


Substitution polyalphabétique

◼ Le chiffre de Vigenère appartient aux systèmes de substitution

polyalphabétique.

❑ Dans un texte en clair, une lettre est substituée par une autre lettre

dépendant de sa position dans le texte.

◼ Si le texte est suffisamment long, il est possible de trouver les

substitutions en découpant le texte selon la longueur

présumée de la clé puis en analysant les fréquences des

lettres.


Même si le nombre de clés est grand,

cette méthode n’est pas acceptable.


Masque jetable – One-time pad

◼ Les principales faiblesses des systèmes de substitution polyalphabétique classiques sont:

❑ La taille de la clé ❑ Le fait que la clé soit réutilisée.

◼ Pour pallier ce problème, il «suffit» d’avoir un algorithme polyalphabétique dont

❑ la clé est aussi longue que le message à chiffrer,

❑ la clé est nouvelle pour chaque nouveau message.

◼ Transférer le problème de transmettre un message chiffré à celui de transmettre une clé de façon sécurisée.

❑ Avec quelle clé chiffrer la clé???

iii KMC =


Transposition

ujoonbiivcorqroetveraitupreycmmroagtem

bonjourvoicivotrequatriemecryptogramme

◼ Algorithme: Permuter les lettres selon une permutation fixe.

◼ Clé: 123456 → 642531

◼ Si le texte est suffisamment long, il est possible de trouver les

transpositions en découpant le texte selon la longueur présu-

mée de la clé puis en analysant les diverses permutations.



Cryptographie à clé secrète – Temps moderne

◼ En 1945, Claude Shannon définissait les bases théoriques de la

cryptographie moderne.

❑ Par exemple, le seul système cryptographique parfaitement sécurisé est

l’algorithme du masque jetable.

◼ En 1976, l’agence de normalisation américaine développait un

algorithme de chiffrement qui a été grandement utilisé depuis:

❑ DES – Data Encryption Standard

◼ En 2002, l’agence de normalisation américaine récidivait avec un

nouvel algorithme:

❑ AES – Advanced Encryption Standard


Algorithme DES 1976 – Utilisation

◼ Chiffrement de messages

❑ Entre deux intervenants partageant une même clé de chiffrement.

◼ Authentification de messages

❑ Entre deux intervenants partageant une même clé d’authentification.

→ Bien que le même algorithme, il ne faut jamais mélanger les

fonctionnalités et l’usage de clés.

→ Règle: Une clé pour chaque fonctionnalité.


Algorithme DES – chiffrement

Cryptogramme - 64 bits

Texte - 64 bits

Algorithme DESClé - 56 bits


Algorithme DES – Détails

Substitutions

Transpositions


Chiffrement par blocs

◼ Le chiffrement par blocs consiste à découper le message en

blocs de bits et de chiffrer chacun de ces blocs.

❑ ECB – Electronic Code Book

❑ CBC – Cipher Block Chaining


Chiffrement DES – ECB (Electronic Code Book)

Objectif: Chiffrer un message arbitrairement long avec la boîte

noire DES chiffrant 64 bits.

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

Texte en clair

Cryptogramme


Source :https://fr.wikipedia.org/wiki/Mode_d%27op%C3%A9ration_(cryptographie)

Cryptologie - Clé secrète - A08 32


Chiffrement DES – CBC (Cipher Block Chaining)

Objectif: Chiffrer un message arbitrairement long avec la boîte

noire DES chiffrant 64 bits sans qu’il puisse être manipulé.

64 bits

DESClé

64 bits 64 bits 64 bits64 bits

Texte en clair

Cryptogramme

64 bits

DESClé

xor

64 bits

DESClé

xor

64 bits

DESClé

xor

Chiffrement


Source :https://fr.wikipedia.org/wiki/Mode_d%27op%C3%A9ration_(cryptographie)

Cryptologie - Clé secrète - A08 34


Chiffrement DES – CTR (Counter Mode)

Compteur

Output

DESClé

incrémenter

à chaque bloc

Séquence: Ek(Cnt) | Ek(Cnt+1) | Ek(Cnt+2) …

◼ Envoyer avec le premier bloc.

❑ Nonce

Séquence de clé

Bloc de cryptogramme

Bloc de textexor


Algorithme DES – authentification

Code d’authentification – 32 bits

Texte – sans restriction

Algorithme DESClé - 56 bits


DES – Message Authentication Code (MAC)

Objectif: Calculer une empreinte permettant au destinataire de

vérifier que le message n’a pas été altéré et qu’il provient bien

de la source présumée.

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

64 bits

64 bits

DESClé

Texte en clair

xorxorxor

Le MAC est les 32 premiers bits du résultat


Autres algorithmes

◼ Triple DES (3DES)

❑ Pour chaque bloc de 64 bits de message, trois itérations sont nécessaires:

◼ Chiffrer avec K1, Déchiffrer avec K2, Chiffrer avec K1 (112 bits de clé)

◼ Chiffrer avec K1, Déchiffrer avec K2, Chiffrer avec K3 (168 bits de clé)

◼ IDEA – International Data Encryption Algorithm

❑ Chiffrement en blocs dont la longueur des blocs est de 64 bits et la

longueur de la clé est de 128 bits.

◼ Blowfish

❑ Chiffrement en blocs dont la longueur des blocs est de 64 bits et la

longueur de la clé peut être aussi grande que 448 bits.


Triple DES

64 bits

64 bits

K1 E

DK2

EK1

64 bits

64 bits

K1 E

DK2

EK3


AES – Audiences publiques

◼ Au début des années 2000, le NIST américain a tenu des

audiences publiques afin de définir le nouveau standard.

◼ Le candidat retenu en 2002: Rijndael:

◼ Trois versions:

❑ Chiffrement de blocs de 128 bits avec une clé de 128 bits

◼ 10 itérations


◼ 12 itérations


◼ 14 itérations

Jean-Marc Robert, ETS 41◼Chamseddine Talhi, ÉTS

◼ Problème des clés secrètes

◼ 2 personnes => 1 clé

◼ N personnes => n * (n-1)/2 clés

◼ 100 personnes => 4,950 clés

◼ 1,000personnes => 499,500 clés

◼ Pour chaque 10 personnes en plus

on a besoin de 100 clés en plus!

◼Adapté de: http://www.cryptool-online.org/

http://www.cryptool-online.org/


Conclusions

◼ La cryptographie est un outil essentiel afin de s’assurer de la

confidentialité, l’authenticité et de l’intégrité des actifs

informationnels.

◼ Règle d’or #1 : ne jamais développer un nouvel algorithme

cryptographique. Utiliser ceux qui sont disponibles depuis un

certain temps. Older is better.

◼ Règle d’or #2: avant de déployer une solution cryptographique, il

faut comprendre l’architecture de sécurité et son implémentation:

❑ Confiance en qui?

❑ Gestion des clés adéquate (génération, entreposage, rotation, …)

❑ Implémentation logicielle et ses vulnérabilités


Terminologie et définitions

Les définitions en italique ainsi que les termes français

proviennent de grand dictionnaire terminologique de

l’Office de la langue française du Québec.

(http://www.oqlf.gouv.qc.ca/ressources/gdt.html)

http://www.oqlf.gouv.qc.ca/ressources/gdt.html


Supplémentaires


Output


Chiffrement DES – CFB (Cipher Feedback Mode)

Input

DES

Séquence de clé

Clé

Vecteur

initial

Séquence: Ek(IV) | Ek(Ek(IV) M1) | Ek(Ek(Ek(IV) M1) M2) …

◼ Toujours le même – défaut.


Bloc de textexor


Chiffrement DES – OFB (Output Feedback Mode)

Input

Output

DESClé

Vecteur

initial

Séquence: Ek(IV) | Ek(Ek(IV)) | Ek(Ek(Ek(IV))) …


Séquence de clé


Bloc de textexor


Chiffrement continu – Stream cipher

◼ Le chiffrement continu chiffre un bit du message à la fois dès que

celui-ci est disponible.

◼ Ce type de méthode génère une séquence qui est « additionnée »

au message pour produire le cryptogramme.

❑ La fonction ou-exclusif est utilisée.

Texte en clair Cryptogramme

Générateur

01001110110011001101

xor

Clé


Chiffrement continu

◼ Longue période avant que la séquence ne contienne des patrons

répétitifs.

◼ La séquence est statistiquement imprévisible.

◼ La séquence est statistiquement non biaisée.

❑ Autant de 0 que de 1.

◼ La séquence ne dépend pas de la clé de façon linéaire.

❑ Il est difficile de trouver les bits de la clé en fonction de la séquence.


Autres algorithmes

◼ RC4

❑ Chiffrement continu avec des clés de longueur variable.

❑ L’algorithme de chiffrement continu le plus utilisé.

◼ RC5

❑ Chiffrement en blocs dont le nombre d’itérations, la longueur de la clé

et des blocs peuvent être paramétrés.

Documents

New Algorithmes à clé secrète Jean-Marc Robert · 2019. 6. 12. · Jean-Marc Robert, ETS Cryptologie - Clé secrète - A08 3 Introduction La cryptologie est la science des messages