Crypto et sécurité de l’information

Si plaintext ds la même ligne : remplacer par les lettres de droite.

Ex1 pq est remplacé par qs. Ex2 ar est remplacé par RM.

Si plaintext ds 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

15 / 79

Sécurité de Playfair

Algorithme 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

16 / 79

fréquence des lettres

Algorithme Playfair

17 / 79

Algorithmes poly-alphabetiques

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

18 / 79

Algorithmes poly-alphabetiques

Polyalphabetic Ciphers

Alg de substitution poly-alphabetique

améliore la sécurité en combinant plusieurs alg

mono-alphabetiques

rende la cryptanalyse plus difficile 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 fin de la clé est atteinte

19 / 79

Algorithmes poly-alphabetiques

Vigenère

l’alg poly-alphabetique le plus simple : algs de Cesar muliples

la clé est constitué de caractères K = k1k2 . . . kd

la ième lettre de la clé spécifie le ième alg de Cesar à utiliser

repeter des le debut chaque d lettres du plaintext

20 / 79

Algorithmes poly-alphabetiques

Exemple Vigenère

écrire le plaintext

écrire la clé et la répéter sur la longueur du plaintext

utiliser chaque lettre de la clé comme clé de Cesar

chiffrer chaque lettre indépendamment des autres

ex: clé = deceptive

21 / 79

Algorithmes poly-alphabetiques

Autokey cipher

voulant une clé aussi longue que le message

vigenère propose l’autokey

clé est préfixé au message pour générer une nouvelle clé

connaissant la clé basique, on peut déchiffrer les premières lettres

peut etre cassé par analyse fréquentielle

ex: clé: deceptive

22 / 79

Algorithmes poly-alphabetiques

Vernam cipher

utilise une clé aussi longue que le plaintext

inventé par un ingénieur AT&T Gilbert Vernam en 1918

23 / 79

Algorithmes poly-alphabetiques

One time Pad

Amélioration de Vernam proposé par l’officier de l’armée, Joseph

Mauborgne

Utiliser une clé aléatoire qui est aussi longue que le message de

sorte que la clé n’a pas besoin d’être répétée

La Clé est utilisée pour chiffrer et déchiffrer un seul message, puis

elle est jeté

Chaque nouveau message nécessite une nouvelle clé de la

même longueur que le nouveau message

Ce cryptosystème est incassable

problèmes dans la production et la distribution sécurisée de la clé

Non pratique: reste utilisé ds les communications top-secrets et

très coûteuses (teleph rouge entre Moscow et Washington)

24 / 79

Les algorithmes de transposition

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

25 / 79

Les algorithmes de transposition

Transposition

Transposition= permutation

Chiffrer le message en réarrangeant l’ordre des lettres du plaintext

le plaintext et le ciphertext ont même occurence (fréquence) des

lettres

26 / 79

Les algorithmes de transposition

Fail hence cipher

La transposition la plus simple

plaintext est écrit en séquences de diagonales

on le lit ligne par ligne

pour chiffrer le message "meet me after the toga party" avec "Rail

hence" de profondeur(nb de lignes) 2 :

ciphertext est : MEMATRHTGPRYETEFETEOAAT

27 / 79

Les algorithmes de transposition

Raw Transposition Cipher

Transposition plus complexe

écrire le plaintext sous forme de rectangle, ligne par ligne

ciphertext : lire le message colonne par colonne, mais permuter

l’ordre des colonnes

l’ordre de la lecture des colonnes est donc la clé

28 / 79

Les algorithmes de transposition

Product ciphers

Les algorithmes de substitutions ou transposition ne sont pas sécurisés

à cause de l’analyse fréquentielle

donc envisager d’utiliser plusieurs alg à la suite pour rendre la

cryptanalyse plus difficile.

exemple répéter la permutation du texte précédent avec la même clé (ou

même avec une autre clé):

on peut voir l’effet de la double permutation comme ceci:

avant permutation :

après la première permutation :

après la deuxième permutation :

29 / 79

C’est le concept des algorithmes de cryptage moderne

Algorithmes de cryptage Moderne

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

30 / 79

Algorithmes de cryptage Moderne

Algorithmes de chiffrement par bloc, et par flux

en anglais: block ciphers et stream ciphers

block ciphers traitent le plaintext bloc par bloc, chcun est

chiffré/déchiffré (ex: DES et AES)

stream ciphers traitent le plaintext bit par bit (ou octect par octect)

lors de cryptage/decryptge (ex: viginère, vernam)

majorité des algorithmes modernes sont des blocks ciphers

31 / 79

Algorithmes de cryptage Moderne

32 / 79

Algorithmes de cryptage Moderne

Stream ciphers

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

33 / 79

Algorithmes de cryptage Moderne

Stream ciphers

Stream cipher : Vernam cipher

utilise une clé aussi longue que le plaintext

inventé par un ingénieur AT&T Gilbert Vernam en 1918

34 / 79

Algorithmes de cryptage Moderne

Stream ciphers

One time Pad

Amélioration de Vernam proposé par l’officier de l’armée, Joseph

Mauborgne

Utiliser une clé aléatoire qui est aussi longue que le message de

sorte que la clé n’a pas besoin d’être répétée

La Clé est utilisée pour chiffrer et déchiffrer un seul message, puis

elle est jeté

Chaque nouveau message nécessite une nouvelle clé de la

même longueur que le nouveau message

Ce cryptosystème est incassable

problèmes dans la production et la distribution sécurisée de la clé

Non pratique: reste utilisé ds les communications top-secrets et

très coûteuses (teleph rouge entre Moscow et Washington)

35 / 79

Algorithmes de cryptage Moderne

Block ciphers

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

36 / 79

Algorithmes de cryptage Moderne

Block ciphers

fonctions réversibles et irréversibles

Un alg à chiffrement par bloc prend n bits du plaintext et le

transforme en n bits de ciphertext

il y a 2n combinaisons possibles de plaintext

le Cryptage doit être reversible

chaque bloc du plaintext produit un bloc du ciphertext diffèrent

(bijectivité)

il ya 2n transformations possibles

37 / 79

Algorithmes de cryptage Moderne

Block ciphers

modèle d’un block cipher

38 / 79

Algorithmes de cryptage Moderne

Block ciphers

les tables du bloc cipher exemple

39 / 79

Algorithmes de cryptage Moderne

Block ciphers

Claude Shannon et les alg de substitution-permutation

Shannon a introduit l’idée des réseaux de

substitution-permutation (S-P) en 1949

c’est la base de tout les alg de cryptage moderne

les réseaux S-P sont basés sur deux critère:

substitution (S-box)

Permutation(P-box)

Ceci fourni les critères de confusion et de diffusion du plaintext et

de la clé sur le ciphertext

40 / 79

Algorithmes de cryptage Moderne

Block ciphers

Confusion et diffusion

Deux termes introduits par Shanon qui constituent les critères de

base d’un algorithme de cryptage

Son but était de concevoir des cryptosystèmes qui résistent

l’analyse statistique

confusion: Rend la relation entre le ciphertext et la clé aussi

complexe que possible (apparence aléatoire)

diffusion: Chaque bit du plaintext affecte tous les bits du ciphertext

(avalanche)

41 / 79

Plan

Exemple : DES

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

42 / 79

Exemple : DES

Structure et fonctionnement

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

43 / 79

DES

Exemple : DES

Structure et fonctionnement

Data Encryption standard (DES) est le standard de cryptage

recommandé par NIST (National Institute of Standards and

Technologies) en 1977.

l’alg de cryptage le plus utilisé jusqu’à 2001 (l’arrivée de AES par

NIST aussi)

L’alg de DES est appelé DEA (Data Encryption Algorithm)

Le plaintext est chiffré en 64-bit blocs en utilisant une clé de taille

56 bit

l’alg transforme un bloc de 64-bit du plaintext à un bloc de 64-bit

du ciphertext

Les mêmes étapes, avec la même clé, conduisent au décryptage

44 / 79

DES

Exemple : DES

Structure et fonctionnement

45 / 79

Initial permutation (IP) de DES

Exemple : DES

Structure et fonctionnement

ex: A la sortie de IP:

ds la pos 1 =⇒ entrée 58;

ds la pos 2 =⇒ entrée 50;

ds la pos 64 =⇒ entrée 7

A la sortie de IP−1 :

1 est lu depuis la pos 58

2 est lu depuis la pos 50

64 est lu depuis la pos 7

46 / 79

Structure d’une ronde DES

Exemple : DES

Structure et fonctionnement

47 / 79

Structure d’une ronde DES

Exemple : DES

Structure et fonctionnement

Deux moitiés L et R de taille 32-bits chacune

Structure de Feistel est comme suit :

Li = Ri−1

Ri = Li−1 ⊕ F (Ri−1, Ki )

F prend la moitié R de 32-bit et la clé intermédiaire de 48-bit et

fait comme suit:

Expansion de R à 48-bits en utilisant la permutation E

L’ajouter à la clé intermédiaire par XOR

La faire passer à travers 8 S-box pour avoir le résultat de 32-bits

Finalement la permuter en utilisant une permutation P

48 / 79

Les fonction de permutation E et P

Exemple : DES

Structure et fonctionnement

49 / 79

Structure d’une ronde DES: F(R,K)

Exemple : DES

Structure et fonctionnement

50 / 79

Les 8 S-box

Exemple : DES

Structure et fonctionnement

chaque S-box transforme 6-bits à 4-bits

Pour chaque entrée de chaque S-box :

les bits 1 et 6 (bits extérieurs) sélectionne une ligne parmi 4.

les bits 2-5 (bits intérieurs) sont substitués par la sortie

correspondante ds la ligne choisie

le résultat est 8 lots de 4-bit: ça fait 32-bits en tout

la sélection de la ligne dépend du plaintext et de la clé

exemple 48 bits –> 32 bits: S(18 09 12 3d 11 17 38 39) =

5fd25e03

Sbox1: 0x18 : 011000 –> ligne n◦0 et colonne n◦ 12 : 5 = 0x5

Sbox2: 0x09 : 001001 –> ligne n◦1 et colonne n◦ 4 colonne :

15=0xf

Sbox8: 0x39 : 111001 –> ligne n◦3 et colonne n◦ 12 : 3 = 0x3

51 / 79

Les 8 S-box: (1-4)

Exemple : DES

Structure et fonctionnement

52 / 79

Les 8 S-box: (5-8)

Exemple : DES

Structure et fonctionnement

53 / 79

DES Key schedule

Exemple : DES

Structure et fonctionnement

Key schedule : préparation des clés intermédiaires (des 16

rondes) à partir de la clé originale de 56-bits

Permutation initiale de la clé (PC1) qui sélectionne 56-bits (parmi

64) en 2 moitiés de 28-bits

16 stages qui consistent à:

"Rotation circulaire à gauche" de chaque moitié de 1 ou 2 bits en

fonction de la fonction de rotation K

sélectionner 24 bits de chaque moitié et la permuter par (PC2) pour

être l’entrée de la fonction F.

54 / 79

DES Key schedule

Exemple : DES

Structure et fonctionnement

55 / 79

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

Plan

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

56 / 79

Sécurité de DES

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

taille de l’espace clé 256 = 7.2 × 1016

une machine à 109 déchiffrement/s peut le casser en 1.125 année

une machine à 1013 déchiffrement/s peut le casser en 1 heure

l’AES-128 avec la même vitesse, la machine reste 5.3 × 1017

années

plusieurs attaques sur DES :

differential cryptanalysis

linear cryptanalysis

related key attack

Le besoin de trouver une alternative de DES devient nécessaire

57 / 79

Cryptage multiple avec DES

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

DES est devenu vulnérable à la brute force attack

Alternative: crypter plusieurs fois avec des clés différentes

Options :

Double DES: n’est pas très performant

Triple DES (3DES) avec deux clés: brute force 2112

Triple DES avec trois clés : brute force 2168

58 / 79

Double encryption

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

clé de taille 2 × 56 = 112

espace clé de 2112.

il faut donc essayer en moyenne 2111 pour le casser en brute force

attaque plus intelligente: Meet-in-the-middle attack

59 / 79

Meet-in-the-middle attack

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

Double cryptage DES : C = E(K2, E(K1, P))

soit X = E(K1, P) = D(K2, C)

supposons que l’adversaire connaît 2 paires P/C : (Pa, Ca) et

(Pb, Cb)

chiffrer Pa en utilisant toutes les possibilités 256 de la clé K1 pour

avoir les possibilités de X

Enregistrer les valeurs possibles de X ds un tableau avec leurs clés

correspondantes K1

Déchiffrer Ca en utilisant toutes les possibilités 256 de la clé K2

Pour chaque résultat du décryptage, vérifier avec les valeurs du

tableau

S’il y a correspondance, Prenez les valeurs correspondantes de K1

et K2. Et vérifier si Cb = E(K2, E(K1, Pb)), alors accepter les clés.

Avec deux paires de P/C, la probabilité de succès est 1

Cette attaque est de complexité 2 × 256 qui est très inférieur à

complexité brute force attack 2112

60 / 79

Cryptage Triple

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

2 clés : 112 bits

3 clés : 168 bits

Pourquoi E-D-E ? Pour être compatible avec DES simple:

C = E(K1, D(K1, E(K1, P)))

3DES a été adopté par plusieurs application internet: PGP,

S/MIME

61 / 79

AES

Exemple : DES

Amélioration sur DES jusqu’à utilisation d’AES

Advanced encryption standard est le nouveau alg de cryptage

adopté par NIST crée en 2001 (Rijandael)

Taille block: 128-bit (possibilité d’autres tailles)

taille clé: 128, 192, 256 bits

rondes: 10, 12, 14 dépend de la clé

XOR avec clés intermédiaires, Substitutions avec des S-box,

mixage avec l’arithmétique du corps de Galois

Largement utilisé dans les communications sécurisés en réseaux

Considéré comme sécurisée jusqu’à ce moment.

62 / 79

Plan

Modes de cryptage par bloc

1 Algorithmes de substitution

2 Monoalphabetic Cipher

3 Algorithme Playfair

4 Algorithmes poly-alphabetiques

5

Les algorithmes de transposition

6 Algorithmes de cryptage Moderne

Stream ciphers

Block ciphers

7 Exemple : DES

Structure et fonctionnement

Amélioration sur DES jusqu’à utilisation d’AES

8 Modes de cryptage par bloc

63 / 79

Modes de cryptage par bloc

Modes de cryptage par bloc

NIST SP 800-38A definiti 5 modes de cryptages

ECB: Electronic codebook Book Mode

CBC: cipher block chaining Mode

CFB: cipher FeedBack Mode

OFB: Output FeedBack Mode

CTR : Counter Mode

il y a ceux qui sont orientés bloc et ceux qui sont orienté flux

Ceci est pour couvrir une large variété d’application ds la vie réelle

ces modes peuvent être appliqués sur n’importe quel algorithme

de bloc

64 / 79

ECB

Modes de cryptage par bloc

Le plaintext est divisé en blocs qui seront cryptés

chaque block constitue une valeur qui sera substitué par cryptage

comme un dictionnaire, d’où le nom (dictionnaire=codebook)

Chaque bloc est crypté indépendamment des autres blocs :

Ci = EK (Pi )

Application: transmission sécurisée de messages courts

65 / 79

ECB

Modes de cryptage par bloc

66 / 79

Avantages et limitations de ECB

Modes de cryptage par bloc

Les répétitions dans le plaintext sont montrés aussi dans le

ciphertext (peu de confusion)

Non efficace pour les images : trop de redondance, trop de

répétitions donc image peut rester visible après cryptage

La faiblesse est dans l’indépendance dans le cryptage des

différents blocs

Utilisation principale est le cryptage de plaintext très court

Image originale

Image cryptée (AES) en mode ECB

67 / 79

CBC

Modes de cryptage par bloc

Le plaintext est divisé en blocs

ces blocs seront liés durant le cryptage

chaque bloc du ciphertext est lié avec le bloc du plaintext

correspondant et les bloc ciphertext précédents

utilise un vecteur d’initialisation pour commencer le cryptage:

Ci = EK (Pi XOR Ci−1)

C−1 = IV

Application: Le cryptage de données en vrac (de grande

redondance); Authentification (CMAC)

68 / 79

CBC

Modes de cryptage par bloc

69 / 79

Avantages et limitations de CBC

Modes de cryptage par bloc

chaque bloc du ciphertext dépend de tous les blocs qui le

précèdent

n’importe quel changement affecte tous les blocs du ciphertext qui

le suivent

CBC a besoin d’un IV pour l’initialisation:

l’IV doit être connu de l’émetteur et récepteur

S’il est transmis en clair, un adversaire peut changer les bits du

premier bloc et changer IV pour compenser ce changement.

Donc IV doit être soit fixe

soit envoyé crypté en mode ECB avant de traiter le plaintext

70 / 79

Les modes de cryptage en bloc orientés flux

Modes de cryptage par bloc

Les modes de bloc chiffre tout le bloc

dans certaines application, on pourra avoir besoin d’operer sur

des tailles plus petites

application dans le cryptage du flux multimédia (temps réel)

convertir les alg de bloc en alg de flux

CFB

OFB

CTR

l’idée est d’utiliser les alg de blocs sous forme de générateur de

séquences pseudo-aléatoires

71 / 79

CFB

Modes de cryptage par bloc

Le message est traité comme un flux de bits

le message est ajouté à la sortie du l’alg de bloc

le résultat est retourné (feed-back) à l’étage précédent (d’où le

nom)

le standard permet plusieurs tailles de blocs (1; 8; 64; 128; etc)

pour être feed-back

notés CFB-1, CFB-8, CFB-64, CFB-128

le cryptage est comme suit:

Ci = Pi XOR EK (Ci−1)

C−1 = IV

Applications: cryptage du flux (temps réel), Authetification

72 / 79

CFB

Modes de cryptage par bloc

73 / 79

Avantages et limitations de CFB

Modes de cryptage par bloc

CFB est approprié si les données arrivent en bits ou octets

approprié pour le mode en flux

Noter que dans le cryptage et le décryptage, les deux opèrent

avec le bloc de chiffrement EK

l’erreur (s’il y en a) peut se propager dans plusieurs blocs après le

bloc erroné

74 / 79

OFB

Modes de cryptage par bloc

Le message est traité comme flux de bits

la sortie du cryptage est ajouté au message

la sortie est ensuite retourné (Output feed-back) à l’entrée de

l’étage suivant (d’où le nom)

le feedback est indépendant du message (plaintext)

il peut être calculé auparavant

Oi = EK (Oi−1)

Ci = Pi XOR Oi

O−1 = IV

Utilisation: Cryptage de flux dans un canal bruité

75 / 79

OFB

Modes de cryptage par bloc

76 / 79

Avantages et Limitations de OFB

Modes de cryptage par bloc

OFB a besoin d’un IV qui doit être unique pour chaque utilisation

si l’IV est réutilisé, l’adversaire peut retrouver les sorties

Les erreurs ne se propagent pas

émetteur et récepteur doivent être en synchronisation

77 / 79

CTR

Modes de cryptage par bloc

un nouveau mode similaire à OFB mais chiffre un compteur au

lieu de la sortie

doit avoir une clé différente et une valeur de compteur différente

pour chaque message

Oi = EK (i)

Ci = Pi XOR Oi

Utilisation: Cryptage dans les réseaux haut débit

78 / 79

CTR

Modes de cryptage par bloc

79 / 79