II. 2Les protocoles simples

II. 2Les protocoles simples

Sommaire

1. Authentification

2. Signature électronique

3. Certification

1. Authentification

1.1 Principe

1.2 Par clef publique

1.3 Sans apport d’information

1.1 Principe

Virginie veut Vérifierle secret de Paul

Paul peut Prouverqu’il possède un

secret sans le révéler

… que Eve Espionne

par undialogue…

1.2 Par clef publiqueNotations kx : clef publique de x

k’x : clef privée de x

kp

choix d’un défi xy = Ekp

(x)

z = Dk’p (y)

z

vérification z = x

1.3 Sans apport d’information

• La grotte secrète

A

B

C D

1. Virginie se place au point A

2. Paul entre dans la grottejusqu’au point C ou D

3. Virginie va au point B et demande à Paul de sortir soit de C soit de D

4. Si Paul ne peut s’exécuterc’est qu’il n’a pas la clef

Paul prétend pouvoir ouvrirla porte entre C et D maisne veut pas le montrerVirginie veut vérifier ce que luidit Paul

La grotte secrète : le « bluff »

Paul peut sortir du bon côté sans avoir la clef

si tous les choix sont équiprobables, Paul peut « bluffer » Virginie avec p = 1/2

Virginie répète le test n fois

la porte se referme automatiquement après chaque test

Un usurpateur peut « bluffer » Virginie avec p = 1/2n

n = 20 p = 1/220 10-6

Exemple : co-isomorphisme de graphes

G1 = < S ; R1 > G2 = < S ; R2 >

G1 G2 ssi

π : S S | (u,v) R1 (π(u), π(v)) R2

exemple

1

2 4 1

3 4 3

2

G1G2π(G1,G2) = (3, 1, 4, 2)

Complexité

π( G1, G2 ) G1 G2

P

NP

Le protocole

construit π (H, Gi )

G1 & G2construit π (G1, G2)

H

choisit j {1, 2 }équiprobablement j

construit π (H, Gj )π (H, Gj)

vérifie π (H, Gj )

publie garde secret π (G1, G2)

Le « bluff »

• Paul peut toujours construire π (H, Gj)si j = i π (H, Gj ) = π (H, Gi)

pas d’utilisation du secret

si j ≠ i π (H, Gj ) = π (H, Gi ) ° π (Gi, Gj ) utilisation du secret nécessaire

• Un usurpateur peut « bluffer » Virginie, donc construire π (H, Gj), si j = i

• Preuve itérée n fois probabilité d’usurpation = 1/2n

Apport d’information

• Eve peut intercepter la suite des triplets< Hk , jk, πk (Hk, Gjk

) >

• Mais ces triplets peuvent être construits par n’importe quiPreuve

G1 et G2 sont publics

H peut être construit avec π, j et Gj

Les triplets n’apportent aucune information à Eve

2. Signature électronique

2.1 Objectifs et Principe

2.2 Mécanisme

2.3 Formalisation

2.4 Inversion des clefs

2.5 Signature d’un message public

2.6 Signature d’un message secret

2.7 Falsification et Répudiation

2.8 Hachage

2.9 Signatures non reproductibles

2.1 Objectifs et Principe

• Objectifs : empêcher– Falsification– Répudiation– Usurpation

• Principe – Attacher à un message une information

• Indissociable du message• Authentifiant son émetteur• Assurant l’intégrité du message• Vérifiable publiquement• Non reproductible

2.2 Mécanisme

– fonction de signature s = sig (k, x)

– prédicat public de vérification ver (k, x, s) s = sig (k, x)

x ssigk

verk

2.3 Formalisation

< P, K, A ; S ; V >

P textes en clair

K clefs de signature

A signatures

S : P x K A fonction de signature

V : P x K x A { vrai, faux } vérification

2.4 Inversion des clefs

• En-cryptages et Dé-cryptages inversiblesk : clef publique k’ : clef secrète

Dk’ (Ek (M)) = Dk (Ek’ (M)) = M

– Exemple : RSA E = D

2.5 Signature d’un message public

Alice

clef secrète k’a

Bobpublic

ka

x, s y = Dka (s)message : x

vérificationverka

(x, s) =

(x = y )

signatures = sigka

(x) = Ek’a (x)

2.6 Signature d’un message secret

Alice

clef secrète k’a

Bob

clef secrète k’b

publicka kb

y = Ekb (s)

y s = Dk’b (y)

signatures = sigka

(x) = Ek’a (x)

vérificationverka

(x, s) =

(x = Dka (s) )

message : x

2.7 Falsification et Répudiation

• Eve ne peut décrypter y

seul Bob possède k’b

• Bob ne peut falsifier x• Alice ne peut répudier x• Eve ne peut signer x

seule Alice peut produire Ek’a (x)

• Cas d’un message secret– La signature n’est pas publique

2.8 Hachage

• Fonction de hachage cryptographiqueP textes en clairZ empreintesh : P Z fonction de hachage

z = h (x) empreinte de zh : {0, 1}* {0, 1}n

z : longueur fixe h n’est pas injective h-1 n’existe pas attaque des anniversaires possible

Signature d’un message public

Alice

clef secrète k’a

Bobpublich, ka

empreinte : z = h (x)

x, s z = Dka (s)

signatures = sigka

(x) = Ek’a (z)

vérificationverka

(x, s) =

(z = h(x) )

message : x

Falsification et répudiation

• x n’est pas secret• vérification publique

D, ka, h sont publics• Falsification par Bob

Recherche d’un x’ tel que h(x’) = h(x)collision faible

• Répudiation par AliceFabrication de x, x’ tels que h(x’) = h(x)

collision forte

• Eve ne peut signer x

seule Alice peut produire Ek’a (x)

Construction de la fonction de hachage

– h : {0, 1}* {0, 1}n

– on utilise souvent une fonctiong : {0, 1}m {0, 1}n m > n

– on calcule n pour rendre difficile l’attaque des anniversaires

Construction par cryptage

P = C = K = {0, 1}n

E : P x K C

g : {0, 1}n x {0, 1}n {0, 1}n

exemples

g (x, k) = e (x, k) x

g (x, k) = e (x, k) x k

g (x, k) = e (x k, k ) x

g (x, k) = e (x k, k ) x k

Construction de Merkle

g : {0, 1}m {0, 1}n r = m - n > 1

x {0, 1}* l = |x|

u = 0i x |u| mod r = 0 x est complété avec des « 0 » en tête

y = 0j l |y| mod (r-1) = 0 l est complété avec des « 0 » en tête

y = t1 t2 … |ti| = r-1

y est découpé en blocs de longueur r-1

v = 1 w1 1 w2 …« 1 » est ajouté devant chaque bloc

w = u 0r v w est composé de t blocs de longueur r

H est construite inductivement

H0 = 0n

Hi = g (Hi-1 wi) 1 ≤ i ≤ t

h = Ht

Propriétés et exemple

• propriétég résiste aux collisions h résiste aux collisions

• exempler = 4 x = 11101 l = 101

u = 0001 1101

v = 1101

w = 0001 1101 0000 1101 t = 4

h = g ( g ( g ( g (0n 0001)1101)0000)1101)

Taille de l’empreinte

P : textes en clair |P| = m

Z : empreintes |Z| = n

h : P Z fonction de hachage

théorème des anniversaires

m > 2n/2 pr ( x, x’ P x ≠ x’ h(x) = h(x’) ) > 1/2

exemples

n = 40 m > 220 220 s 1s

n = 128 m > 264 264 s 500 000 ans

n = 160 m > 280 280 s 2 AU

Autres constructions

• Basées sur la construction de Merkle MD5 Message-Digest Algorithm (n = 128 bits )

SHA Secure Hash Algorithm (n = 160 bits)

• Basées sur la construction de ElgamalDSS Digital Signature Standard

DSA Digital Signature Algorithmissues de l’algorithme de signature dû à

Taher Elgamal, basé sur le logarithme discret

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

الجمل طاهر Taher Elgamal

(1955)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

2.9 Signature non reproductible

• Objectif : éviter le re-jeu• Méthode : introduction d’un « nonce » (number

once) dans la signature– exemple : compteur, date

N : ensemble des nonces

S : P x K x N A fonction de signature

V : P x K x N x A {vrai, faux } vérification

3. Certification

3.1 Objectif et Principe

3.2 Contenu d’un certificat

3.3 Utilisations

3.1 Objectif et Principe

• Objectif– Association clef publique - identité

– Publication sécurisée de la clef publique

– Contre l’attaque du « man in the middle »

• Principe – Tiers de confiance

• centralisés : autorités de certification CA

• distribués : chaînes de confiance PGP

3.2 Contenu d’un certificat

– Contenu minimum en clair A, kA, n• A : identité de A nom, adresse IP, domaine, etc …

• kA : clef publique de A

• Nonce

– Informations complémentaires• Date de limite de validité

• Type de cryptage utilisant la clef

• Etc …

– Signature du tiers de confiance

3.3 Utilisations

– Enregistrement de la clef publique

– Vérification de l’identité du détenteur d’un secret

– Distribution de clefs de session généralement privées