Cours6_AttaqueContreCourplage

Attaques par canaux cachés

contre la cryptographie à base de couplage

Nadia El Mrabet

GREYC−LMNO−Université de Caen, France

Ecole � Code et Cryptographie �, ENSIAS de Rabat−MAROC,Semaine du 8 au 14 mars 2010.

1 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

2 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

3 / 57

Suite des festivitésLes couplages dans tout leur état

Dé�nition mathématiques des couplages (Ca c'est fait !)

Exemple et calcul de couplages (Ca c'est fait !)

Optimisation des couplages Mathématiques et Arithmétique (Ca c'estpresque fait ! )

Attaques par canaux cachés : SPA, attaque par faute, DPA (Ca c'estfait !)

Application au couplage

Perspective de la recherche à base de couplage.

4 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

5 / 57

Outline

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

6 / 57

Qu'est ce qu'un couplage ?Propriétés

Soient G1, G2 et G3 trois groupes abéliens �nis. Un couplage est uneapplication :

e : (G1,+)× (G2,+)→ (G3,×)

Véri�ant les propriétés :

Non dégénérescence : ∀P ∈ G1 6= {0} ,∃Q ∈ G2 t.q. e(P,Q) 6= 1

Bilinéarité : ∀P,P ′ ∈ G1, ∀Q ∈ G2, e(P + P ′,Q) = e(P,Q).e(P ′,Q)

Conséquences

∀j ∈ Z, e(jP,Q) = e(P,Q)j = e(P, jQ)

7 / 57

Qu'est ce qu'un couplage ?Propriétés

Soient G1, G2 et G3 trois groupes abéliens �nis. Un couplage est uneapplication :

e : (G1,+)× (G2,+)→ (G3,×)

Véri�ant les propriétés :

Non dégénérescence : ∀P ∈ G1 6= {0} ,∃Q ∈ G2 t.q. e(P,Q) 6= 1

Bilinéarité : ∀P,P ′ ∈ G1, ∀Q ∈ G2, e(P + P ′,Q) = e(P,Q).e(P ′,Q)

Conséquences

∀j ∈ Z, e(jP,Q) = e(P,Q)j = e(P, jQ)

7 / 57

Qu'est ce qu'un couplage ?Propriétés

Soient G1, G2 et G3 trois groupes abéliens �nis. Un couplage est uneapplication :

e : (G1,+)× (G2,+)→ (G3,×)

Véri�ant les propriétés :

Non dégénérescence : ∀P ∈ G1 6= {0} ,∃Q ∈ G2 t.q. e(P,Q) 6= 1

Bilinéarité : ∀P,P ′ ∈ G1, ∀Q ∈ G2, e(P + P ′,Q) = e(P,Q).e(P ′,Q)

Conséquences

∀j ∈ Z, e(jP,Q) = e(P,Q)j = e(P, jQ)

7 / 57

Cryptologie à base de couplages

Le problème du logarithme discret

dans G1 consiste à retrouver l'entier a avec la donnée de P ∈ G1 et aP .Soit Q un point de G2 :

e(aP,Q) = e(P,Q)a.

Cryptanalyse

La propriété de bilinéarité des couplages a permis de transférer le problèmedu logarithme discret depuis une courbe elliptique en un problème delogarithme discret sur un corps �ni. Il s'agit des attaques de MOV 93 etFrey Rück 94.

8 / 57

Cryptologie à base de couplages

Le problème du logarithme discret

dans G1 consiste à retrouver l'entier a avec la donnée de P ∈ G1 et aP .Soit Q un point de G2 :

e(aP,Q) = e(P,Q)a.

Cryptanalyse

La propriété de bilinéarité des couplages a permis de transférer le problèmedu logarithme discret depuis une courbe elliptique en un problème delogarithme discret sur un corps �ni. Il s'agit des attaques de MOV 93 etFrey Rück 94.

8 / 57

Cryptologie à base de couplages

Cryptographie

les couplages ont permis la construction de protocoles originaux et lasimpli�cation de protocoles cryptographiques existants.

L'échange de Di�e Hellman à trois (Joux 2001)

La cryptographie basée sur l'identité (Boneh et Franklin 2001)

Les schémas de signature courte (Boneh, Lynn, Shacham 2001)

Exemple

Construction d'une clé pour un échange basé sur l'identité entre Alice etBob.

9 / 57

Cryptologie à base de couplages

Cryptographie

les couplages ont permis la construction de protocoles originaux et lasimpli�cation de protocoles cryptographiques existants.

L'échange de Di�e Hellman à trois (Joux 2001)

La cryptographie basée sur l'identité (Boneh et Franklin 2001)

Les schémas de signature courte (Boneh, Lynn, Shacham 2001)

Exemple

Construction d'une clé pour un échange basé sur l'identité entre Alice etBob.

9 / 57

Cryptographie basée sur l'identitéEchange de clé sécurisée entre Alice et Bob

10 / 57

Cryptographie basée sur l'identitéEchange de clé sécurisée entre Alice et Bob

10 / 57

Cryptographie basée sur l'identitéEchange de clé sécurisée entre Alice et Bob

10 / 57

Cryptographie basée sur l'identitéEchange de clé sécurisée entre Alice et Bob

10 / 57

Les couplages utilisés en cryptologie

Le couplage de Weil,

le couplage de Tate,

le couplage η,

le couplage Ate et Twisted Ate.

sont les couplages les plus utilisés en cryptologie.

Les couplages de Weil, de Tate, Ate et Twisted Ate sont construits sur lemême modèle.Ils partagent la même étape centrale pour leur calcul.

11 / 57

Les couplages utilisés en cryptologie

Le couplage de Weil,

le couplage de Tate,

le couplage η,

le couplage Ate et Twisted Ate.

sont les couplages les plus utilisés en cryptologie.

Les couplages de Weil, de Tate, Ate et Twisted Ate sont construits sur lemême modèle.Ils partagent la même étape centrale pour leur calcul.

11 / 57

Outline

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

12 / 57

Construction des couplagesDonnées

A�n de calculer un couplage, nous avons besoin de :

Soit E une courbe elliptique sur un corps K :E (K) :=

{(x , y) ∈ K×K, y2 = x3 + ax + b, avec a, b ∈ K

}∪ P∞.

Figure: Courbe elliptique dans le plan réel

La courbe elliptique est munie d'une loi d'addition.13 / 57

Courbe elliptiqueLoi de groupe - Addition

14 / 57

Courbe elliptiqueLoi de groupe - Addition

14 / 57

Courbe elliptiqueLoi de groupe - Addition

14 / 57

Courbe elliptiqueLoi de groupe - Doublement

15 / 57

Courbe elliptiqueLoi de groupe - Doublement

15 / 57

Courbe elliptiqueLoi de groupe - Doublement

Par convention nous noterons [r ]P = P + P + . . .+ P︸ ︷︷ ︸r fois

.

15 / 57

Construction des couplagesDonnées

A�n de calculer un couplage, nous avons besoin de :

Soit E une courbe elliptique sur un corps K ⊃ Fp, a et b ∈ Fp :

E (K) :={

(x , y) ∈ K×K, y2 = x3 + ax + b}∪ {P∞}.

r un nombre premier divisant card(E (Fp)),

ainsi que l'ensemble : E [r ] ={P ∈ E (Fp), [r ]P = P∞

}.

Le degré de plongement k : le plus petit entier tel que r |(pk − 1) ;

Si k > 1 alors E [r ] ⊂ E (Fpk ).

La fonction de Miller notée fr ,P qui admet :

le point P comme zéro d'ordre r

le point [r ]P comme pôle.

16 / 57

Construction des couplagesDonnées

A�n de calculer un couplage, nous avons besoin de :

Soit E une courbe elliptique sur un corps K ⊃ Fp, a et b ∈ Fp :

E (K) :={

(x , y) ∈ K×K, y2 = x3 + ax + b}∪ {P∞}.

r un nombre premier divisant card(E (Fp)),

ainsi que l'ensemble : E [r ] ={P ∈ E (Fp), [r ]P = P∞

}.

Le degré de plongement k : le plus petit entier tel que r |(pk − 1) ;

Si k > 1 alors E [r ] ⊂ E (Fpk ).

La fonction de Miller notée fr ,P qui admet :

le point P comme zéro d'ordre r

le point [r ]P comme pôle.

16 / 57

Construction des couplagesDonnées

A�n de calculer un couplage, nous avons besoin de :

Soit E une courbe elliptique sur un corps K ⊃ Fp, a et b ∈ Fp :

E (K) :={

(x , y) ∈ K×K, y2 = x3 + ax + b}∪ {P∞}.

r un nombre premier divisant card(E (Fp)),

ainsi que l'ensemble : E [r ] ={P ∈ E (Fp), [r ]P = P∞

}.

Le degré de plongement k : le plus petit entier tel que r |(pk − 1) ;

Si k > 1 alors E [r ] ⊂ E (Fpk ).

La fonction de Miller notée fr ,P qui admet :

le point P comme zéro d'ordre r

le point [r ]P comme pôle.

16 / 57

Construction des couplagesDonnées

A�n de calculer un couplage, nous avons besoin de :

Soit E une courbe elliptique sur un corps K ⊃ Fp, a et b ∈ Fp :

E (K) :={

(x , y) ∈ K×K, y2 = x3 + ax + b}∪ {P∞}.

r un nombre premier divisant card(E (Fp)),

ainsi que l'ensemble : E [r ] ={P ∈ E (Fp), [r ]P = P∞

}.

Le degré de plongement k : le plus petit entier tel que r |(pk − 1) ;

Si k > 1 alors E [r ] ⊂ E (Fpk ).

La fonction de Miller notée fr ,P qui admet :

le point P comme zéro d'ordre r

le point [r ]P comme pôle.

16 / 57

Construction des couplagesLe couplage de Tate

Soit P ∈ E (Fp)[r ], Q ∈ E (Fpk )/rE (Fpk ) et k le degré de plongement de lacourbe relativement à r .

Le couplage de Tate est l'application :

eT : E (Fp)[r ]× E (Fpk )/rE (Fpk )→ F∗pk

(P,Q)→ fr ,P(Q)pk−1

r

17 / 57

Construction des couplagesLe couplage de Tate

Soit P ∈ E (Fp)[r ], Q ∈ E (Fpk )/rE (Fpk ) et k le degré de plongement de lacourbe relativement à r .

Le couplage de Tate est l'application :

eT : E (Fp)[r ]× E (Fpk )/rE (Fpk )→ F∗pk

(P,Q)→ fr ,P(Q)pk−1

r

17 / 57

Outline

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

18 / 57

L'égalité de MillerLa fonction fr,P

Le calcul des couplages nécessite la construction d'une fonction rationnellefr ,P pour r un entier naturel.Cette fonction admet le point P comme zéro d'ordre r et le point [r ]Pcomme pôle.

Victor Miller a établi l'égalité :

fi+j ,P = fi ,P × fj ,P ×l[i ]P,[j]P

v[i+j]P

Cette égalité nous permet de construire une suite de fonction admettant lepoint [i ]P comme pôle pour i allant de 1 à r .

19 / 57

L'égalité de MillerExemple

Nous voulons calculer f5,P en utilisant sa décomposition binaire :5 = (101)2

et un algorithme de doublement et addition :

Nous partons de i = 1,

Le deuxième bit de 5 est 0 :

i := 2× i ⇒ i = 2

Le troisième bit de 5 est 1 :

i := 2× i ⇒ i = 4

i := i + 1 ⇒ i = 5

Sur ce modèle, nous allons calculer f5,P en utilisant l'égalité de Miller et ladécomposition binaire de 5.

20 / 57

L'égalité de MillerExemple

Nous voulons calculer f5,P en utilisant sa décomposition binaire :5 = (101)2

et un algorithme de doublement et addition :

Nous partons de i = 1,

Le deuxième bit de 5 est 0 :

i := 2× i ⇒ i = 2

Le troisième bit de 5 est 1 :

i := 2× i ⇒ i = 4

i := i + 1 ⇒ i = 5

Sur ce modèle, nous allons calculer f5,P en utilisant l'égalité de Miller et ladécomposition binaire de 5.

20 / 57

L'égalité de MillerExemple

Nous voulons calculer f5,P en utilisant sa décomposition binaire :5 = (101)2

et un algorithme de doublement et addition :

Nous partons de i = 1,

Le deuxième bit de 5 est 0 :

i := 2× i ⇒ i = 2

Le troisième bit de 5 est 1 :

i := 2× i ⇒ i = 4

i := i + 1 ⇒ i = 5

Sur ce modèle, nous allons calculer f5,P en utilisant l'égalité de Miller et ladécomposition binaire de 5.

20 / 57

L'égalité de MillerExemple

Soit f1,P qui vaut 1 par construction des fonctions fi ,P et i = 1.

i := 2i (i = 2)

f2,P = f1,P × f1,P ×lP,Pv[2]P

f2,P =lP,Pv[2]P

i := 2i (i = 4)

f4,P = f2,P × f2,P ×l[2]P,[2]P

v[4]P

f4,P = f 22,P ×l[2]P,[2]P

v[4]P

i := i + 1 (i = 5)

f5,P = f4,P ×l[4]P,P

v[5]P

f5,P =

((lP,P

v[2]P

)2

×l[2]P,[2]P

v[4]P

)×

l[4]P,P

v[5]P

21 / 57

L'égalité de MillerExemple

Soit f1,P qui vaut 1 par construction des fonctions fi ,P et i = 1.

i := 2i (i = 2)

f2,P = f1,P × f1,P ×lP,Pv[2]P

f2,P =lP,Pv[2]P

i := 2i (i = 4)

f4,P = f2,P × f2,P ×l[2]P,[2]P

v[4]P

f4,P = f 22,P ×l[2]P,[2]P

v[4]P

i := i + 1 (i = 5)

f5,P = f4,P ×l[4]P,P

v[5]P

f5,P =

((lP,P

v[2]P

)2

×l[2]P,[2]P

v[4]P

)×

l[4]P,P

v[5]P

21 / 57

L'égalité de MillerExemple

Soit f1,P qui vaut 1 par construction des fonctions fi ,P et i = 1.

i := 2i (i = 2)

f2,P = f1,P × f1,P ×lP,Pv[2]P

f2,P =lP,Pv[2]P

i := 2i (i = 4)

f4,P = f2,P × f2,P ×l[2]P,[2]P

v[4]P

f4,P = f 22,P ×l[2]P,[2]P

v[4]P

i := i + 1 (i = 5)

f5,P = f4,P ×l[4]P,P

v[5]P

f5,P =

((lP,P

v[2]P

)2

×l[2]P,[2]P

v[4]P

)×

l[4]P,P

v[5]P

21 / 57

Calcul des couplagesL'algorithme de Miller renvoie fr,P(Q)

Data: r = (rN . . . r0)2,P ∈ G1 ⊂ E (Fp)[r ]

Result: [r ]PT ← P

for i = N − 1 to 0 do

T ← [2]T

if ri = 1 then

T ← T + P

end

end

return T = [r ]P

22 / 57

Calcul des couplagesL'algorithme de Miller renvoie fr,P(Q)

Data: r = (rN . . . r0)2,P ∈ G1 ⊂ E (Fp)[r ] et

Q ∈ G2 ⊂ E (Fpk )[r ]Result: fr ,P(Q) ∈ G3 ⊂ F∗

pk

T ← P , f1 ← 1, f2 ← 1for i = N − 1 to 0 do

T ← [2]T

f1 ←− f12 × ld (Q)

f2 ←− f22 × vd (Q)

if ri = 1 then

T ← T + P

f1 ←− f1 × la(Q)f2 ←− f2 × va(Q)

end

end

returnf1f2

23 / 57

Calcul des couplagesL'algorithme de Miller renvoie fr,P(Q)

Data: r = (rN . . . r0)2,P ∈ G1 ⊂ E (Fp)[r ] et

Q ∈ G2 ⊂ E (Fpk )[r ]Result: fr ,P(Q) ∈ G3 ⊂ F∗

pk

T ← P , f1 ← 1, f2 ← 1for i = N − 1 to 0 do

T ← [2]Tf1 ←− f1

2 × ld (Q)f2 ←− f2

2 × vd (Q)if ri = 1 then

T ← T + P

f1 ←− f1 × la(Q)f2 ←− f2 × va(Q)

end

end

returnf1f2

23 / 57

Calcul des couplagesL'algorithme de Miller renvoie fr,P(Q)

Data: r = (rN . . . r0)2,P ∈ G1 ⊂ E (Fp)[r ] et

Q ∈ G2 ⊂ E (Fpk )[r ]Result: fr ,P(Q) ∈ G3 ⊂ F∗

pk

T ← P , f1 ← 1, f2 ← 1for i = N − 1 to 0 do

T ← [2]Tf1 ←− f1

2 × ld (Q)f2 ←− f2

2 × vd (Q)if ri = 1 then

T ← T + P

f1 ←− f1 × la(Q)f2 ←− f2 × va(Q)

end

end

returnf1f2

23 / 57

Calcul des couplagesL'algorithme de Miller renvoie fr,P(Q)

Data: r = (rN . . . r0)2,P ∈ G1 ⊂ E (Fp)[r ] et

Q ∈ G2 ⊂ E (Fpk )[r ]Result: fr ,P(Q) ∈ G3 ⊂ F∗

pk

T ← P , f1 ← 1, f2 ← 1for i = N − 1 to 0 do

T ← [2]Tf1 ←− f1

2 × ld (Q)f2 ←− f2

2 × vd (Q)if ri = 1 then

T ← T + P

f1 ←− f1 × la(Q)f2 ←− f2 × va(Q)

end

end

returnf1f2

23 / 57

Outline

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

24 / 57

La sécurité des couplages

Niveau de sécurité en bits 80 128 192 256Nombre minimal de bits de r 160 256 384 512Nombre minimal de bits de pk 1 024 3 072 7 680 15 360

Table: Niveau de sécurité

25 / 57

Implantation des couplages sur courbes elliptiques

Soit Mp le coût d'une multiplication dans Fp, Spk celui d'un carré et Mpk

celui d'une multiplication dans Fpk .

L'algorithme de Miller nécessite

N = [log2(r)] + 1 itérations

la complexité de l'étape de doublement est8Sp + (12 + 4k)Mp + 2Spk + 2Mpk

la complexité de l'étape d'addition est6Sp + (20 + 3k)Mp + 2Spk + 2Mpk

A�n d'améliorer l'e�cacité du calcul du couplage, nous pouvons :

réduire le nombre d'additions et de multiplications dans Fpk .

améliorer l'arithmétique dans Fpk .

26 / 57

Implantation des couplages sur courbes elliptiques

Soit Mp le coût d'une multiplication dans Fp, Spk celui d'un carré et Mpk

celui d'une multiplication dans Fpk .

L'algorithme de Miller nécessite

N = [log2(r)] + 1 itérations

la complexité de l'étape de doublement est8Sp + (12 + 4k)Mp + 2Spk + 2Mpk

la complexité de l'étape d'addition est6Sp + (20 + 3k)Mp + 2Spk + 2Mpk

A�n d'améliorer l'e�cacité du calcul du couplage, nous pouvons :

réduire le nombre d'additions et de multiplications dans Fpk .

améliorer l'arithmétique dans Fpk .

26 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

27 / 57

Calcul d'un couplage dans IBCLes données

On considère :

q nombre premier ou puissance d'un nombre premier

E courbe elliptique d'équation : y2 = x3 + ax + b, a et b ∈ Fq

P ∈ E (Fq) l'entrée secrète lors des calculs : P est privé.

Q ∈ E (Fqk ) l'entrée connue lors des calculs : Q est public.

28 / 57

Coordonées a�nesL'équation et la cible

L'équation de ld en coordonnées a�nes est :

ld (xQ , yQ) = yQ − λ(xQ − xT )− yT

L'attaque porte sur la di�érence (xQ − xT ) à la première itération del'algorithme de Miller.Avec :

T = P = (xP , yP) que l'on cherche.

Q public que l'on fait varier à volonté.

Illustration

xQi. . . 0 1 0

xP − ? 1 0 1(xQi− xP) ? 1 0 1

29 / 57

Coordonnées a�nesSchéma d'attaque

m point Qi ∈ G2(⊂ E (Fqk )) sont choisis (500 < m < 10000 )

Les j − 1 bits de poids faibles de xP sont connus

1 Récupérer les courbes Ci pour i = 0 . . .m2 Supposer (xP)j = 1

I Si (xQi− xP)

j= 0 mettre Ci dans S0

I Si (xQi− xP)

j= 1 mettre Ci dans S1

3 Calculer les moyennes C0 et C1 des paquets S0 et S14 Calculer la di�érence ∆ = C1 − C0

I Si la courbe ∆ présente un ou des pics de consommation, alors

(xP)j = 1I Sinon (xP)j = 0

5 on obtient ainsi le j eme bit de xP .

30 / 57

Coordonnées a�nesSchéma d'attaque

ld (xQ , yQ) = yQ − λ(xQ − xT )− yT

Une fois obtenue la valeur de xP , on utilise l'équation de la courbepour trouver yP .

L'équation de la courbe donne au plus deux valeurs de yP .

y2 = x3 + ax + b

En essayant les deux valeurs lors d'une exécution de l'algorithme deMiller, on peut déterminer la bonne.

31 / 57

Coordonnées projectivesL'équation et les cibles

L'équation de ld est :

ld (xQ , yQ) = Z 2yQ − (3X 2 + aZ 2)(xQZ − X )− YZ

L'attaque porte en premier lieu sur le produit xQZ , puis sur la di�érence(xQZ − X ), toujours sur la première itération où :

T = P = (XP ,YP ,ZP) en coordonnées projectives

Q = (xQ , yQ) en coordonnées a�nes

Rappel

T = (XT ,YT ,ZT ) est équivalent à T = (XT

ZT, YT

ZT, 1) pour ZT 6= 0

32 / 57

Coordonnées projectivesSchéma d'attaque

m point Qi ∈ G2(⊂ E (Fqk )) sont choisis

Les j − 1 bits de poids faibles de ZP sont connus

1 Récupérer les courbes Ci pour i = 0 . . .m2 Supposer (ZP)j = 1

I Si (ZP × xQi)j

= 0 mettre Ci dans S0I Si (ZP × xQi

)j

= 1 mettre Ci dans S1

3 Calculer les moyennes C0 et C1 des paquets S0 et S14 Calculer la di�érence ∆ = C1 − C0

I Si la courbe ∆ présente un ou des pics de consommation, alors

(ZP)j = 1I Sinon (ZP)j = 0

5 on obtient ainsi le j eme bit de ZP .

33 / 57

Coordonnées projectivesSchéma d'attaque

ld (xQ , yQ) = Z 2yQ − (3X 2 + aZ 2)(xQZ − X )− YZ

Une fois obtenue la valeur de ZP , on réitère le procédé pour retrouverla valeur de XP via l'opération (xQZ − X ).

L'équation de la courbe donne au plus deux valeurs de YP .

Y 2 = X 3 + aXZ 2 + bZ 3

En essayant les deux valeurs lors d'une exécution de l'algorithme deMiller, on peut déterminer la bonne.

34 / 57

Coordonnées jacobiennesL'équation et les cibles

L'équation de ld est :

ld (Q) = Z3Z2yQ − 2Y 2 − (3X 2 − aZ 4)(xQZ

2 − X )

L'attaque porte en premier lieu sur le produit xQZ 2, puis :

soit sur la di�érence (xQZ2 − X )

soit sur le calcul de Z3Z2yQ = 2YZ × Z 2 × yQ

sachant que :

T = P = (XP ,YP ,ZP) en coordonnées jacobiennes, et Z3 = 2YTZT .

Q = (xQ , yQ) en coordonnées a�nes

Rappel

T = (XT ,YT ,ZT ) est équivalent à T = (XT

Z2T

, YT

Z3T

, 1) pour ZT 6= 0

35 / 57

Coordonnées jacobiennesSchéma d'attaque

Le schéma est le même qu'en coordonnées projectives :

ld (Q) = Z3Z2yQ − 2Y 2 − (3X 2 − aZ 4)(xQZ

2 − X )

Il s'agit d'abord de retrouver Z 2P , ce qui nous donne deux possiblités

pour ZP .

Ensuite, avec ces deux possiblités on réitère le procédé pour trouverles deux valeurs de YP associées.

En�n, pour trouver XP , on se sert de l'équation de la courbe :

Y 2 = X 3 + aXZ 3 + Z 6

� Ou alors avec Z 2P on retrouve XP via la di�érence (xQZ

2 − X )

� Puis retrouver YP à l'aide de l'équation de la courbe.

36 / 57

Coordonnées jacobiennesSchéma d'attaque

Le schéma est le même qu'en coordonnées projectives :

ld (Q) = Z3Z2yQ − 2Y 2 − (3X 2 − aZ 4)(xQZ

2 − X )

Il s'agit d'abord de retrouver Z 2P , ce qui nous donne deux possiblités

pour ZP .

Ensuite, avec ces deux possiblités on réitère le procédé pour trouverles deux valeurs de YP associées.

En�n, pour trouver XP , on se sert de l'équation de la courbe :

Y 2 = X 3 + aXZ 3 + Z 6

� Ou alors avec Z 2P on retrouve XP via la di�érence (xQZ

2 − X )

� Puis retrouver YP à l'aide de l'équation de la courbe.

37 / 57

Implémentation

Nous avons utilisé un environnement de simulation pour mettre en placel'attaque DPA. Cet environnement a été proposé par Di Natale, Flottes etRouzeire, il simule la consommation électrique d'un circuit en synthétisantles transistors et transition liées à l'exécution de l'algorithme.L'environnement exécute aussi l'attaque DPA. Nous avons obtenu parexemple les courbes suivantes :

38 / 57

Conclusion

L'algorithme de Miller est vulnérable à l'attaque DPA

Vulnérabilité des couplages basés sur l'algorithme de Miller

Nous venons de voir que quelque soit le positionnement du secret lors d'uncalcul de couplage nous pouvons le retrouver.La conséquence directe est que tous les couplages : le couplage de Weil, deTate, Ate et Twisted Ate sont vulnérables à l'attaque DPA.

39 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

40 / 57

Outline

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

41 / 57

Attaques par canaux cachées

Lors d'un protocole basé sur l'identité l'attaquant connait :

l'algorithme de couplage utilisé,

le nombre d'itérations (N = [log2(r)] + 1).

Le secret est l'un des arguments du couplage.

Le secret n'in�uence ni le temps d'exécution ni le nombre d'itérationsde l'algorithme.

42 / 57

Attaques par canaux cachés

Les attaques par canaux cachés utilisent les failles matérielles del'implantation pour récupérer des informations sur le secret utilisé.

Les attaques par injection de fautes consistent à perturber l'exécutiond'un algorithme par exemple par des émissions lasers.

La première attaque par injection de fautes contre un cryptosystème àbase de couplage à été introduite en 2006 par Page et Vercauterencontre l'algorithme de Duursma et Lee.

Nous étudions la vulnérabilité de l'algorithme de Miller confronté àune attaque par injection de fautes.

43 / 57

Attaques par canaux cachés

Les attaques par canaux cachés utilisent les failles matérielles del'implantation pour récupérer des informations sur le secret utilisé.

Les attaques par injection de fautes consistent à perturber l'exécutiond'un algorithme par exemple par des émissions lasers.

La première attaque par injection de fautes contre un cryptosystème àbase de couplage à été introduite en 2006 par Page et Vercauterencontre l'algorithme de Duursma et Lee.

Nous étudions la vulnérabilité de l'algorithme de Miller confronté àune attaque par injection de fautes.

43 / 57

Attaques par canaux cachés

Les attaques par canaux cachés utilisent les failles matérielles del'implantation pour récupérer des informations sur le secret utilisé.

Les attaques par injection de fautes consistent à perturber l'exécutiond'un algorithme par exemple par des émissions lasers.

La première attaque par injection de fautes contre un cryptosystème àbase de couplage à été introduite en 2006 par Page et Vercauterencontre l'algorithme de Duursma et Lee.

Nous étudions la vulnérabilité de l'algorithme de Miller confronté àune attaque par injection de fautes.

43 / 57

Description de l'attaque par injection de fautes

Nous supposons que le couplage est utilisé lors d'un protocole decryptographie basée sur l'identité.

Le secret est le point P , premier argument lors du calcul du couplagee(P,Q).

Le second paramètre du couplage Q est connu et maitrisé parl'attaquant.

Objectif de l'attaque par injection de fautes

L'attaque consiste à faire varier le nombre d'itérations durant l'exécution del'algorithme de Miller, ceci a�n d'obtenir les résultats de deux exécutionsdont le nombre d'itérations soient consécutifs : τ et τ + 1 itérations pourτ ∈ {1, . . . ,N}.Nous notons Fτ,P(Q) et Fτ+1,P(Q) les deux résultats de ces itérations.

44 / 57

Description de l'attaque par injection de fautes

Nous supposons que le couplage est utilisé lors d'un protocole decryptographie basée sur l'identité.

Le secret est le point P , premier argument lors du calcul du couplagee(P,Q).

Le second paramètre du couplage Q est connu et maitrisé parl'attaquant.

Objectif de l'attaque par injection de fautes

L'attaque consiste à faire varier le nombre d'itérations durant l'exécution del'algorithme de Miller, ceci a�n d'obtenir les résultats de deux exécutionsdont le nombre d'itérations soient consécutifs : τ et τ + 1 itérations pourτ ∈ {1, . . . ,N}.Nous notons Fτ,P(Q) et Fτ+1,P(Q) les deux résultats de ces itérations.

44 / 57

Description de l'attaque par injection de fautes

Cible de l'attaque

Nous modi�ons le registre mémoire contenant l'entier N déterminant lenombre d'itérations exécutées par l'algorithme de Miller à l'aide d'émissionlaser.

Principe de l'attaque

Nous procédons à plusieurs exécutions de l'algorithme de Miller enmodi�ant aléatoirement à chaque exécution ce registre.

Ce bombardement laser modi�e le nombre d'exécutions e�ectuées ; endénombrant les cycles d'horloge nous pouvons retrouver le nombred'itérations faites.

Nous recommençons l'opération jusqu'à obtenir deux nombred'itérations consécutifs notés τ et τ + 1.

45 / 57

Description de l'attaque par injection de fautes

Cible de l'attaque

Nous modi�ons le registre mémoire contenant l'entier N déterminant lenombre d'itérations exécutées par l'algorithme de Miller à l'aide d'émissionlaser.

Principe de l'attaque

Nous procédons à plusieurs exécutions de l'algorithme de Miller enmodi�ant aléatoirement à chaque exécution ce registre.

Ce bombardement laser modi�e le nombre d'exécutions e�ectuées ; endénombrant les cycles d'horloge nous pouvons retrouver le nombred'itérations faites.

Nous recommençons l'opération jusqu'à obtenir deux nombred'itérations consécutifs notés τ et τ + 1.

45 / 57

Description de l'attaque par injection de fautes

Cible de l'attaque

Nous modi�ons le registre mémoire contenant l'entier N déterminant lenombre d'itérations exécutées par l'algorithme de Miller à l'aide d'émissionlaser.

Principe de l'attaque

Nous procédons à plusieurs exécutions de l'algorithme de Miller enmodi�ant aléatoirement à chaque exécution ce registre.

Ce bombardement laser modi�e le nombre d'exécutions e�ectuées ; endénombrant les cycles d'horloge nous pouvons retrouver le nombred'itérations faites.

Nous recommençons l'opération jusqu'à obtenir deux nombred'itérations consécutifs notés τ et τ + 1.

45 / 57

Description de l'attaque par injection de fautes

Probabilité de réussite

Nous cherchons à tirer deux entiers consécutifs pris aléatoirement parmi N.

Ce problème est similaire au paradoxe des anniversaires.Nous pouvons calculer la probabilité de réussite de cet évènement.

Exemple

Pour un nombre r de taille 256 bits,il su�t de 15 tirages pour obtenir deux nombres consécutifs pris parmi 256entiers avec une probabilité supérieure à 0, 5 ;et de 26 pour obtenir une probabilité supérieure à 0, 9.

46 / 57

Description de l'attaque par injection de fautes

Probabilité de réussite

Nous cherchons à tirer deux entiers consécutifs pris aléatoirement parmi N.Ce problème est similaire au paradoxe des anniversaires.Nous pouvons calculer la probabilité de réussite de cet évènement.

Exemple

Pour un nombre r de taille 256 bits,il su�t de 15 tirages pour obtenir deux nombres consécutifs pris parmi 256entiers avec une probabilité supérieure à 0, 5 ;et de 26 pour obtenir une probabilité supérieure à 0, 9.

46 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Nous notons Fτ,P(Q) le résultat de la τ -ième itération et Fτ+1,P(Q) celuide la τ + 1-ième.

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

permet de retrouver des informations sur le

secret utilisé.

A la τ -ième étape, T = [j ]P dans l'algorithme de Miller

Nous notons [j ]P = (Xj ,Yj ,Zj) le point secret et Q = (xQ , yQ)l'entrée connue lors du calcul de e(P,Q).

En écrivant les équations nous obtenons l'expression de R suivante :

Z2jZj2yQ − 2Yj

2 − (3Xj2 − aZj

4)(xQZj2 − Xj).

La connaissance du développement formel de R et de sa valeur, nouspermet de construire un système en les coordonnées de [j ]P .

47 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Nous notons Fτ,P(Q) le résultat de la τ -ième itération et Fτ+1,P(Q) celuide la τ + 1-ième.Le rapport R =

Fτ+1,P(Q)Fτ,P(Q)2

permet de retrouver des informations sur le

secret utilisé.

A la τ -ième étape, T = [j ]P dans l'algorithme de Miller

Nous notons [j ]P = (Xj ,Yj ,Zj) le point secret et Q = (xQ , yQ)l'entrée connue lors du calcul de e(P,Q).

En écrivant les équations nous obtenons l'expression de R suivante :

Z2jZj2yQ − 2Yj

2 − (3Xj2 − aZj

4)(xQZj2 − Xj).

La connaissance du développement formel de R et de sa valeur, nouspermet de construire un système en les coordonnées de [j ]P .

47 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Nous notons Fτ,P(Q) le résultat de la τ -ième itération et Fτ+1,P(Q) celuide la τ + 1-ième.Le rapport R =

Fτ+1,P(Q)Fτ,P(Q)2

permet de retrouver des informations sur le

secret utilisé.

A la τ -ième étape, T = [j ]P dans l'algorithme de Miller

Nous notons [j ]P = (Xj ,Yj ,Zj) le point secret et Q = (xQ , yQ)l'entrée connue lors du calcul de e(P,Q).

En écrivant les équations nous obtenons l'expression de R suivante :

Z2jZj2yQ − 2Yj

2 − (3Xj2 − aZj

4)(xQZj2 − Xj).

La connaissance du développement formel de R et de sa valeur, nouspermet de construire un système en les coordonnées de [j ]P .

47 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Nous notons Fτ,P(Q) le résultat de la τ -ième itération et Fτ+1,P(Q) celuide la τ + 1-ième.Le rapport R =

Fτ+1,P(Q)Fτ,P(Q)2

permet de retrouver des informations sur le

secret utilisé.

A la τ -ième étape, T = [j ]P dans l'algorithme de Miller

Nous notons [j ]P = (Xj ,Yj ,Zj) le point secret et Q = (xQ , yQ)l'entrée connue lors du calcul de e(P,Q).

En écrivant les équations nous obtenons l'expression de R suivante :

Z2jZj2yQ − 2Yj

2 − (3Xj2 − aZj

4)(xQZj2 − Xj).

La connaissance du développement formel de R et de sa valeur, nouspermet de construire un système en les coordonnées de [j ]P .

47 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Le système est :

YjZ3j = λ2

Z 2j (X 2

j − Z 4j ) = λ1

3Xj(X2j − Z 4

j ) + 2Y 2j = λ0.

où nous connaissons les valeurs de λ0, λ1 et λ2 dans Fp.

La résolution de ce système nous permet d'exprimer les inconnues Xj et Yj

en fonction de Zj .Cela nous permet de construire une équation de degré 12 admettant Zjcomme solution.

(λ20 − 9λ21)Z 12 − (4λ0λ22 + 9λ31)Z 6 + 4λ41 ≡ 0 mod p

48 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Le système est :

YjZ3j = λ2

Z 2j (X 2

j − Z 4j ) = λ1

3Xj(X2j − Z 4

j ) + 2Y 2j = λ0.

où nous connaissons les valeurs de λ0, λ1 et λ2 dans Fp.

La résolution de ce système nous permet d'exprimer les inconnues Xj et Yj

en fonction de Zj .Cela nous permet de construire une équation de degré 12 admettant Zjcomme solution.

(λ20 − 9λ21)Z 12 − (4λ0λ22 + 9λ31)Z 6 + 4λ41 ≡ 0 mod p

48 / 57

Le rapport R =Fτ+1,P(Q)Fτ,P(Q)2

Le système est :

YjZ3j = λ2

Z 2j (X 2

j − Z 4j ) = λ1

3Xj(X2j − Z 4

j ) + 2Y 2j = λ0.

où nous connaissons les valeurs de λ0, λ1 et λ2 dans Fp.

La résolution de ce système nous permet d'exprimer les inconnues Xj et Yj

en fonction de Zj .Cela nous permet de construire une équation de degré 12 admettant Zjcomme solution.

(λ20 − 9λ21)Z 12 − (4λ0λ22 + 9λ31)Z 6 + 4λ41 ≡ 0 mod p

48 / 57

Conclusion

[ISA'09]

L'algorithme de Miller est vulnérable à une attaque par injection de fautes.

Vulnérabilité des couplages basés sur l'algorithme de Miller

Le couplage de Weil est directement sensible à cette attaque.

Les couplages de Tate et Ate sont construits sur le même modèle :

eT (P,Q) = (fr ,P(Q))pk−1

r .Cette exponentiation pourrait être une contre mesure à l'attaque parfaute,mais il est existe des méthodes comme les attaques par scan quipeuvent rendre possible l'attaque par injection de fautes contre cescouplages.

49 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

50 / 57

Quelles contremesures peut on proposer ?

Attaque DPA : souvent des techniques de masquages

Utiliser les coordonnées Jacobiennes ou projective et tirer partie del'homogénéïté.

⇒ ∀λ ∈ N?(X : Y : Z ) ≡ (λ2X : λ3Y : λZ )

Utiliser la bilinéarité des couplages

⇒ ∀λ ∈ N? : e(P,Q) = e([λ]P, [ 1λ ]Q)

⇒ ∀λ ∈ N? : e(P,Q) = e([λ]P,Q)1λ

51 / 57

Quelles contremesures peut on proposer ?

Attaque DPA : souvent des techniques de masquages

Utiliser les coordonnées Jacobiennes ou projective et tirer partie del'homogénéïté.

⇒ ∀λ ∈ N?(X : Y : Z ) ≡ (λ2X : λ3Y : λZ )

Utiliser la bilinéarité des couplages

⇒ ∀λ ∈ N? : e(P,Q) = e([λ]P, [ 1λ ]Q)

⇒ ∀λ ∈ N? : e(P,Q) = e([λ]P,Q)1λ

51 / 57

Quelles contremesures peut on proposer ?

Attaque par faute

Les mêmes que pour l'attaque DPA

Utilisation d'une horloge asynchrone

52 / 57

Quelles contremesures peut on proposer ?

Attaque par faute

Les mêmes que pour l'attaque DPA

Utilisation d'une horloge asynchrone

52 / 57

Plan de la présentation

1 Résumé des épisodes précédents

2 Cryptologie à base de couplageDé�nition et propriétés des couplagesConstruction et exemple de couplagesCalcul des couplagesAspect arithmétique de la cryptographie à base de couplages

3 Attaque DPA

4 Attaque par fauteDé�nition d'une attaque par injection de fautes

5 Contremesure

6 Conclusion et perspectives

53 / 57

Conclusion

Nous venons de découvrir les deux axes des travaux e�ectués durant cettethèse :

performance de l'arithmétique des couplages,

étude de la sécurité des protocoles à base de couplage.

54 / 57

Contribution de la thèsePlan du mémoire

1 Arithmétique des couplages

Comparaison des complexités des couplages de Weil et de Tate[SPIE'07 avec J.C. Bajard]

2 Bases adaptées aux couplages [ACISP'09 avec C. Nègre]3 Cas spéci�que des courbes de degré de plongement k = 15

Étude complète du calcul d'un couplage sur cette famille de courbe[En cours avec S.Ionica et N. Guillermin]

4 Attaques par canaux cachés5 Attaque di�érentielle par consommation de courant

Attaque DPA contre l'algorithme de Miller [PRIME'09 avecG.DiNatale et M.L. Flottes]

6 Attaque par injection de fautes [ISA'09]

55 / 57

Contribution de la thèsePlan du mémoire

1 Arithmétique des couplages

Comparaison des complexités des couplages de Weil et de Tate[SPIE'07 avec J.C. Bajard]

2 Bases adaptées aux couplages [ACISP'09 avec C. Nègre]3 Cas spéci�que des courbes de degré de plongement k = 15

Étude complète du calcul d'un couplage sur cette famille de courbe[En cours avec S.Ionica et N. Guillermin]

4 Attaques par canaux cachés5 Attaque di�érentielle par consommation de courant

Attaque DPA contre l'algorithme de Miller [PRIME'09 avecG.DiNatale et M.L. Flottes]

6 Attaque par injection de fautes [ISA'09]

55 / 57

Contribution de la thèsePlan du mémoire

1 Arithmétique des couplages

Comparaison des complexités des couplages de Weil et de Tate[SPIE'07 avec J.C. Bajard]

2 Bases adaptées aux couplages [ACISP'09 avec C. Nègre]3 Cas spéci�que des courbes de degré de plongement k = 15

Étude complète du calcul d'un couplage sur cette famille de courbe[En cours avec S.Ionica et N. Guillermin]

4 Attaques par canaux cachés5 Attaque di�érentielle par consommation de courant

Attaque DPA contre l'algorithme de Miller [PRIME'09 avecG.DiNatale et M.L. Flottes]

6 Attaque par injection de fautes [ISA'09]

55 / 57

Contribution de la thèsePlan du mémoire

1 Arithmétique des couplages

Comparaison des complexités des couplages de Weil et de Tate[SPIE'07 avec J.C. Bajard]

2 Bases adaptées aux couplages [ACISP'09 avec C. Nègre]3 Cas spéci�que des courbes de degré de plongement k = 15

Étude complète du calcul d'un couplage sur cette famille de courbe[En cours avec S.Ionica et N. Guillermin]

4 Attaques par canaux cachés5 Attaque di�érentielle par consommation de courant

Attaque DPA contre l'algorithme de Miller [PRIME'09 avecG.DiNatale et M.L. Flottes]

6 Attaque par injection de fautes [ISA'09]

55 / 57

Contribution de la thèsePlan du mémoire

1 Arithmétique des couplages

Comparaison des complexités des couplages de Weil et de Tate[SPIE'07 avec J.C. Bajard]

2 Bases adaptées aux couplages [ACISP'09 avec C. Nègre]3 Cas spéci�que des courbes de degré de plongement k = 15

Étude complète du calcul d'un couplage sur cette famille de courbe[En cours avec S.Ionica et N. Guillermin]

4 Attaques par canaux cachés5 Attaque di�érentielle par consommation de courant

Attaque DPA contre l'algorithme de Miller [PRIME'09 avecG.DiNatale et M.L. Flottes]

6 Attaque par injection de fautes [ISA'09]

55 / 57

Perspectives

Arithmétique des couplages

Recherche de courbes elliptiques adéquates.

Optimisation de l'arithmétique des corps �nis.

Implémentation e�cace de l'arithmétique des corps �nis.

Implantation de couplages e�cace en software et hardware.

Sécurité des couplage

Implantation de l'attaque par fautes.

Implantation des contre mesures proposées aux attaques par canauxcachées.

Attaque d'implantation protégée par les contre mesures de Coron.

Voir si les couplages sont vulnérables à d'autres attaques.

56 / 57

Perspectives

Arithmétique des couplages

Recherche de courbes elliptiques adéquates.

Optimisation de l'arithmétique des corps �nis.

Implémentation e�cace de l'arithmétique des corps �nis.

Implantation de couplages e�cace en software et hardware.

Sécurité des couplage

Implantation de l'attaque par fautes.

Implantation des contre mesures proposées aux attaques par canauxcachées.

Attaque d'implantation protégée par les contre mesures de Coron.

Voir si les couplages sont vulnérables à d'autres attaques.

56 / 57

MERCI POUR VOTRE

ATTENTION

ET SURTOUT VOTRE ACCUEIL ! !

57 / 57