Intégrité IILes systèmes à clé

publique

6e cours--hiver 2014Louis Salvail

L’intégrité symétrique et asymétrique

L’intégrité symétrique nécessite le partage d’une clé secrète entre l’expéditeur et le destinataire.

Seul le destinataire légitime peut vérifier le CAM d’un message.

Est-il possible de garantir l’intégrité d’un message sans qu’il soit nécessaire de partager une clé secrète et telle que tout le monde puisse la vérifier?

Un système pour l’intégrité avec cette propriété est dit à clé publique aussi appelé intégrité asymétrique ou simplement signatures numériques.

Intégrité à clés publiques

MM’

(M,s)

K

SK(M)

s(M’,s

’)

V(M’,s’)

oui/non

!!!!!!

Signatures numériquesLes signatures numériques assurent l’intégrité à

partir d’une clé publique et d’une clé privée. Un tel système est défini par :

Chaque signataire potentiel connaît une paire de clés (PK,SK) où SK est privée et PK publique.

Un algorithme S qui génère une signature pour le message M à partir de la clé privée SK. La signature est définie par SSK(M).

Un algorithme V qui vérifie une signature s pour M à partir de la clé publique PK de l’expéditeur. C’est-à-dire que

VPK(M,SSK(M))=1,

VPK(M,s)=0 si s≠SSK(M).

Ceci implique que quiconque Ceci implique que quiconque connaissant connaissant PKPK peut vérifier une peut vérifier une

signature.signature.

Pour des signatures sûres

Supposons que les clés d’Obélix sont (PK,SK) où SK est la clé privée et PK est la clé publique permettant de vérifier une signature d’Obélix.

Nous avons :

À partir de PK, il est difficile de trouver SK.

Plus précisément, même après avoir vu plusieurs messages signés, l’adversaire ne peut pas générer un nouveau message avec la signature d’Obélix (ou de qui que ce soit).

Les limites des signaturesComme pour les CAM, les signatures numériques peuvent être attaquées par fouille exhaustive de clés :

Étant donné PK, trouver SK!

Une fois SK trouvée, l’adversaire peut contrefaire des signatures aussi facilement que l’utilisateur légitime.

Comme pour le chiffrement à clé publique, trouver SK à partir de PK peut être accompli beaucoup plus rapidement que par fouille exhaustive.

Les clés doivent donc être beaucoup plus longues que dans le cas symétrique.

Évidemment, pour vérifier une signature, il faut être certain de l’identité de la clé publique PK!!!!

Avantages des signatures sur les CAM

Imaginez Obélix transmettant un message M avec un CAM valide à Astérix.

Astérix peut vérifier que M émane bien d’Obélix en utilisant la clé secrète qu’il partage avec celui-ci.

Astérix ne peut toutefois pas convaincre Panoramix qu’Obélix a vraiment envoyé M.

Du point de vue de Panoramix, Astérix peut très bien être l’auteur de M!!!!

Les signatures numériques permettent à quiconque de vérifier l’origine d’un message M...

Signatures RSA*Le système de chiffrement RSA peut facilement être transformé en un système de signatures numériques (pas sûr!).

Soient (PK,SK)=((N,e), d) les clés publique et privée pour le chiffrement RSA. Le signataire (Obélix) connaît SK tandis que les vérificateurs connaissent PK :

Signature du message M :

Sd(M)= Md mod N = s,

(M,s) est un message avec sa signature.

Vérification que (M,s) provient d’Obélix :

VPK(M,s) = oui, si (se mod N = M),

VPK(M,s) = non, sinon.

ssee mod mod NN = (= (MMdd mod mod NN))ee mod mod NN

= = MMddee mod mod NN= = MM11 mod mod N N..

ssee mod mod NN = (= (MMdd mod mod NN))ee mod mod NN

= = MMddee mod mod NN= = MM11 mod mod N N..

Sûreté des signatures RSA*

Supposons que César veuille faire passer le message M* pour un qui provienne d’Obélix dont la clé publique est PK=(N,e) :

César doit réussir à évaluer

(M*)d mod N où d=e-1 mod φ(N).

Ce qui semble équivalent à trouver SK=d (et c’est supposé difficile) car la factorisation de N est inconnue.

Mais, comme tel, RSA* n’est pas un bon système pour les signatures numériques...

Insécurité des signatures RSA*

Soit PK=(N,e) et SK=d les clés publique et privée pour signatures RSA*.

Voici comment contrefaire une signature sans en avoir vu une seule valide...

César choisit s∈Z*N et pose M*=se mod N

(M*,s) est un message avec une signature valide, car se=M*.

Ceci n’est pas dévastateur, car César n’a pas le contrôle du message qu’il signe... mais ceci est une chose à éviter, car le sens du message produit ne devrait pas être considéré pour déterminer le succès d’une contrefaçon.

attaque attaque ‘‘sans-message’!sans-message’!

attaque attaque ‘‘sans-message’!sans-message’!

Une autre attaque contre les signatures RSA*

Voici une attaque qui permet à César de contrefaire une signature pour un message de son choix à partir de la signature de deux messages choisis :

César veut signer M* pour Obélix dont la clé publique est (N,e).

César choisit W∈Z*N et demande à Obélix de signer :

W et M* W-1 mod N pour obtenir s1 et s2 respectivement,

s=s1*s2 mod N est une signature valide pour M*! Puisque se=(s1 s2)e=s1

e s2e=W M* W-1 = M* W-1W = M*.

Ceci n’est peut-être pas dévastateur, car il faut bien convaincre Obélix de signer deux messages. Néanmoins, un tel comportement est à éviter, car il est difficile de faire des hypothèses sur ce qu’Obélix acceptera de signer.

Attaque àAttaque à‘‘message-choisi’message-choisi’

Attaque àAttaque à‘‘message-choisi’message-choisi’

Le paradigme hache-et-signe

RSA* a été modifié pour éviter les problèmes que nous venons de voir. Bien des versions sont sans preuve formelle de sécurité cependant.

Une méthode générale (qui peut être montrée sûre en idéalisant certaines composantes) est appelée «hache-et-signe» :

Au lieu de signer M, une empreinte de M est signée.

PK=(N,e,H), SK=d, où H est une fonction de hachage cryptographique produisant l’empreinte.

SSK(M) = H(M)d mod N.

VPK(M,s) = oui ssi H(M)=se mod N.

Contrefaçons contre hache-et-signe RSA

Attaque sans-message : La façon naturelle de tenter une telle attaque consiste à choisir s∈Z*N, calculer m=se mod N et trouver M* tel que H(M*)=m. Puisque H est une fonction de hachage cryptographique, cette tâche semble difficile.

Attaque à message choisi : La façon naturelle de tenter l’attaque consiste à chercher trois messages m1,m2,M* tels que H(M*)= H(m1)×H(m2) mod N. Cette tâche semble difficile pour H une fonction de hachage cryptographique.

Avantages de hache-et-signe RSA

hache-et-signe RSA pourrait être démontré sûr si la fonction H était une fonction idéale. Ceci donne une indication que remplacer l’idéale H par une bonne fonction de hachage cryptographique, comme SHA256, devrait résulter en un système sûr.

Un autre avantage de hache-et-signe RSA est qu’il peut être utilisé pour signer des messages de longueur arbitraire puisque les fonctions de hachage cryptographiques acceptent des chaînes de toutes les longueurs.

Signatures numériques dans la pratique?

Est-ce que les signatures numériques peuvent avoir la même valeur que les signatures manuscrites?

Oui, et la législation de bien des pays est prête pour ça mais quelques conditions doivent être satisfaites :

Évidentes : Clés assez longues et rangées en sécurité.

Plus subtiles : Un utilisateur doit pouvoir signaler que sa clé privée a été compromise. Le résultat est que toutes les signatures pouvant être vérifiées avec l’ancienne clé publique doivent être invalidées, même celles qui précèdent le rapport.

Mais alors, il pourrait être dans l’intérêt d’un signataire de signaler une clé privée compromise dans le but d’invalider des signatures effectuées.

Signatures numériques dans la pratique? (II)

Le problème précédent peut être résolu de plusieurs façons. Une d’entre elles :

Faire intervenir un service d’horodatage («timestamp») qui contresigne les documents importants.

Puisque la signature de ce service reste valide même lorsque la clé privée du signataire est compromise, le problème serait résolu.

Une autre solution, presque toujours nécessaire, consiste à demander aux utilisateurs de signer sur papier un code de conduite pour l’utilisation de signatures numériques.

L’utilisateur est responsable de sa clé privée. Il doit signaler si elle est compromise le plus vite possible.

L’utilisateur ne peut plus aussi facilement invalider une signature après une certaine durée.

Ressemble aux règles au Ressemble aux règles au sujet des cartes de sujet des cartes de crédit et banques à crédit et banques à

domicile.domicile.

Ressemble aux règles au Ressemble aux règles au sujet des cartes de sujet des cartes de crédit et banques à crédit et banques à

domicile.domicile.

Y-a-t-il une différence entre un courriel où chaque champ, incluant l’adresse du destinataire, est signé et un autre où seulement le contenu l’est?

Obélix transmet le message «Veux-tu m’épouser» à Falbala.

N’importe qui peut prétendre avoir une offre d’Obélix, même Bellefleur!

Ce qu’une signature numérique atteste

Une signature numérique ne certifie que ce qui Une signature numérique ne certifie que ce qui est signé et rien d’autre!!!!!!est signé et rien d’autre!!!!!!

Une signature numérique ne certifie que ce qui Une signature numérique ne certifie que ce qui est signé et rien d’autre!!!!!!est signé et rien d’autre!!!!!!

Cela semble évident Cela semble évident n’est-ce pas?n’est-ce pas?

Cela semble évident Cela semble évident n’est-ce pas?n’est-ce pas?

De la même façon, un message chiffré signé ne De la même façon, un message chiffré signé ne garantit pas que le signataire connaît le message clair! garantit pas que le signataire connaît le message clair! Il est facile de copier un cryptogramme (transmis par Il est facile de copier un cryptogramme (transmis par

un tiers) pour ensuite le signer! un tiers) pour ensuite le signer!

De la même façon, un message chiffré signé ne De la même façon, un message chiffré signé ne garantit pas que le signataire connaît le message clair! garantit pas que le signataire connaît le message clair! Il est facile de copier un cryptogramme (transmis par Il est facile de copier un cryptogramme (transmis par

un tiers) pour ensuite le signer! un tiers) pour ensuite le signer!

L’intégrité d’une session

Dans bien des cas, l’intégrité d’une session complète doit être attestée pour conclure qu’elle est sûre...

L’intégrité des messages n’est pas une solution suffisante :

Lorsque le message M et un CAM/signature d’Obélix sont reçus, on ne peut que conclure qu’à un certain point Obélix a transmis ce message.

César peut s’amuser à renvoyer le même message d’Obélix avec preuve d’intégrité autant de fois que voulu et à n’importe quel moment...

Attaque par rediteAttaque par redite(«replay attack»)(«replay attack»)

Attaque par rediteAttaque par redite(«replay attack»)(«replay attack»)

Attaques par reditetransférer 2$ chez lesHelvètes

Obélix

transférer 2$ chez lesHelvètes

Obélix

transférer 2$ chez lesHelvètes

Obélix

transférer 2$ chez lesHelvètes

Obélix

Dans bien des situations, un Dans bien des situations, un message doit, en plus d’être message doit, en plus d’être

intègre, être frais!intègre, être frais!

Dans bien des situations, un Dans bien des situations, un message doit, en plus d’être message doit, en plus d’être

intègre, être frais!intègre, être frais!

Protections contre redites (I)

Il y a des façons simples de se prémunir contre les attaques par redite :

Ajout d’un numéro de séquence aux messages, calculer un CAM du message avec le numéro. Incrémenter le numéro.

Permet d’ordonner les messages.

Lourd (impraticable dans biens des cas), possible de ranger que quelques numéros des messages acceptés récemment.

Supposons que seul le dernier numéro de message confirmé n est retenu. Que faire si le prochain message n’a pas le numéro n+1?

Dans certains cas, les messages sont réordonnés et même perdus sans que quiconque n’intervienne.

N’accepter que les messages avec numéro plus grand que n protège contre les redites mais peut aussi ignorer des bons messages qui sont reçus trop tard.

Protections contre redites (II)

Une autre façon de se prémunir contre les redites :

Utiliser l’horodatage avec le message avant de calculer leur CAM/signature.

Peut vérifier que le message n’est pas trop vieux avant d’accepter. Permet d’éliminer les redites dans une certaine mesure.

Nécessite une certaine synchronisation entre l’expéditeur et le destinataire et aussi que les messages soient transmis sans trop de retard.

Il n’est pas utile de ranger les horodatages reçus.

Protections contre redites (III)

Voici une dernière solution :

Utiliser l’interaction...

Le destinataire transmet à l’expéditeur un nombre R jamais utilisé (séquence ou aléatoire).

L’expéditeur transmet un CAM/signature du message avec R.

Protège contre les redites, ne nécessite pas de synchronisation.

Doit s’assurer de ne pas réutiliser un R.

Quand plusieurs connexions simultanées sont actives, les R courants et leurs connexions doivent être mémorisés.

Confidentialité et intégritéDans bien des applications, la confidentialité et l’intégrité sont requises simultanément.

Nous pouvons évidemment satisfaire ces deux conditions en utilisant les techniques que nous avons vues.

Attention, il y a des pièges à éviter :

Dans le cas symétrique, nous voulons calculer le CAM et chiffrer le message+CAM.

Pour ce faire, il faut utiliser des clés différentes. Aucune garantie de sécurité si tel n’est pas le cas.

Il existe des modes de chiffrement offrant les deux propriétés à l’aide d’une seule clé (par exemple OEM).

Dans tous les cas, il est préférable de chiffrer le CAM/signature en plus du message, car le CAM/signature pourrait contenir de l’information sur le message clair.

ConclusionNous avons vu comment garantir l’intégrité dans le modèle à clé publique.

L’intégrité à clé publique peut être vue comme des signatures électroniques. Tout le monde peut vérifier une signature mais pas un CAM.

Signatures et CAM garantissent l’intégrité d’un message, mais pas le moment où le message a été transmis.

Les systèmes à clé publique sont beaucoup moins efficaces que ceux à clé secrète.

Pour que les systèmes à clé publique soient sûrs, la clé publique utilisée doit être authentique...

Signatures ElGamal

Signatures dont la sécurité est basée sur la difficulté d’extraire des logarithmes discrets.

Rarement utilisées, mais la base d’un standard développé par le NIST (DSA).

Il y aussi un système de chiffrement à clé publique basé sur la difficulté de calculer des logarithmes discrets (le chiffrement d’ElGamal).

Les clés pour ElGamal

Les paramètres du système sont :

H un fonction de hachage cryptographique.

p un grand nombre premier.

g un générateur de Zp*.

Choisir x aléatoire dans Zp*.

La clé publique est PK=(p,g,y=gx mod p).

La clé privée est SK=x.

Signatures ElGamal

Soit M le message à signer à partir de x.

Choisir k aléatoire dans Zp* tel que PGCD(k,p-1)=1.

Calculer r = gk mod p.

Calculer s = (H(M)-xr)k-1 (mod p-1).

La signature pour M est (r,s).

VérificationSoit M un message et (r,s) la signature où r = gk mod p et s= (H(M)-xr)k-1 (mod p-1). La clé publique est PK=(p,g,y=gx mod p).

Vérifier que gH(M) = yrrs mod p :

yrrs = (gx)r r(H(M)-xr)/k mod p

= gxr gk(H(M)-xr)/k mod p

= gxr+H(M)-xr mod p = gH(M) mod p

(sécurité) Pour contrefaire une signature, ou bien une collision pour H doit est trouvée ou bien x doit être calculé à partir de y, p et g. Ce sont deux tâches supposées difficiles. Un nouveau k doit être utilisé chaque fois!!

DSADSA signifie Digital Signature Algorithm.

Il s’agit d’un standard (1991) du gouvernement fédéral américain pour les signatures numériques proposé par le NIST.

Gratuit, car rendu disponible par le NIST.

La taille des clés L a été augmentée dès le début. Elle est passée de 1024 à 2048 pour une durée utile qui excède 2010. L=3072 pour une durée utile excédant 2030.

L’algorithme est basé sur le système de signatures d’ElGamal.

Les clés pour DSAIl faut une fonction de hachage cryptographique H comme SHA256 (c.-à-d. 256 bits en sortie).

Choisir un nombre premier aléatoire q avec le même nombre de bits que la sortie de H.

Choisir un nombre premier aléatoire p de L bits de long tel que p-1 est un multiple de q. (un peu compliqué)

Choisir g d’ordre multiplicatif q modulo p. Pour ce faire g=hp-1/q mod p pour 1<h<p-1. La plupart des h vont marcher.

La clé publique est PK=(H,p,q,g, y=gx mod p) où x est aléatoire dans [0..q].

La clé privée est SK=x.

Signature DSA

Générer une valeur k aléatoire dans [1..q-1]

Calculer r=(gk mod p) mod q

s=k-1(H(M)+x*r) mod q.

La signature de M est (r,s).

Vérification

La signature (r,s) est rejetée si ce n’est pas le cas que 0<r,s<q.

Calculer w=s-1 mod q.

Calculer u1 = H(M)*w mod q

Calculer u2 = r*w mod q

Calculer v=(gu1 yu2 mod p) mod q

Accepter ssi r=v.

Ça marche?

r=v => (gk mod p) mod q = (gu1 yu2 mod p) mod q

(gu1 yu2 mod p) mod q=(gH(M)*w mod q yr*w mod q mod p) mod q

= (gH(M)*w mod q gx(r*w mod q) mod p) mod q

= (gw(H(M)+xr) mod q mod p) mod q

= (g(H(M)+xr)/s mod q mod p) mod q

= (gk(H(M)+xr)/(H(M)+xr) mod q mod p) mod q

= (gk mod p) mod q.

ProblèmeVous êtes un consultant pour une compagnie qui offre un accès à une base de données D.

Des utilisateurs différents ont accès à des parties différentes de D. Il est donc important de pouvoir identifier l’utilisateur qui fait une requête pour déterminer ses droits d’accès.

D’autre part, les données de D sont confidentielles. Il est important que d’autres utilisateurs (ou non) ne puissent déterminer les données fournies à un utilisateur pour une de ses requêtes.

Nous supposons que chaque utilisateur A a une clé privée skA tandis que la base de données stocke toutes les clés publiques des utilisateurs. La clé privée skA permet de signer une requête.

Tous les utilisateurs connaissent la clé publique pkD de D. La clé publique pkD permet de chiffrer une requête.

Solution 1 Solution 2

SolutionsD

Astérix, requête R

réponse S

EpkD(R), SskA(EpkD(R)), Astérix

EpkD((R,SskA(R)), Astérix

Quelle solution proposeriez-vous?

La mauvaise solution est la no 1

EpkD(R), SskA(EpkD(R)),A

EpkA’(S)

EpkD(R),

SskC(EpkD(R)),C

EpkC’(S

)

S

S

Est-ce que le problème aurait été le même si des

méthodes symétriques avaient été

utilisées????????

Problème : signature à partir de systèmes à clé publique sans hachage

Voici une proposition pour construire une signature basée sur un système à clé publique sans l’utilisation de fonction de hachage :

Supposons que le destinataire Obélix connaisse la clé publique pkA d’Astérix.

Obélix tire au hasard une clé AES K et transmet EpkA(K) à Astérix. (OAEP peut être utilisé pour chiffrer la clé)

Astérix déchiffre pour obtenir K et transmet le message M avec CBCMACK(M) à Obélix.

Expliquez pourquoi ceci ne peut pas être utilisé comme signature numérique même si le chiffrement à clé publique et CBCMAC sont sûrs...

Contrefaçons

Obélix peut contrefaire des signatures d’Astérix.

Il est difficile de convaincre un tiers de la validité d’une signature, car il faudrait prouver que la clé K n’est connue que d’Astérix (mais Obélix la connaît aussi).

Pour être convaincu qu’une signature ne peut venir que d’Astérix, il faut qu’il possède quelque chose d’unique!

Ce n’est pas le cas du système que nous venons de voir!

RSA

Number

Decimal

digits

Binary

digits

Cash prize

offered

Factored on

Factored by

RSA-100

100 330US$1,0

00[4]

April 1, 1991[5]

Arjen K. Lenstra

RSA-110

110 364US$4,4

29[4]

April 14, 1992[5]

Arjen K. Lenstra and M.S. Manasse

RSA-120

120 397 $5,898[4]

July 9, 1993[6]

T. Denny et al.

RSA-129

[**]

129 426$100

USDApril 26,

1994[5]Arjen K. Lenstra et al.

RSA-130

130 430US$14,

527[4]

April 10, 1996

Arjen K. Lenstra et al.

RSA-140

140 463US$17,

226February

2, 1999Herman te Riele et al.

RSA-150

[*] ?

150 496  April 16,

2004Kazumaro Aoki et al.

RSA-155

155 512 $9,383[4]

August 22, 1999

Herman te Riele et al.

RSA-160

160 530  April 1,

2003Jens Franke et al.,

University of Bonn

RSA-170

[*]

170 563  December

29, 2009D. Bonenberger and M. Krone [***]

RSA-576

174 576$10,000

USDDecember

3, 2003Jens Franke et al.,

University of Bonn

RSA-180

[*]

180 596  May 8,

2010S. A. Danilov and I. A. Popovyan,

Moscow State University[7]

RSA-190

[*]

190 629  November

8, 2010A. Timofeev and I. A. Popovyan

RSA-640

193 640$20,000

USDNovember

2, 2005Jens Franke et al.,

University of Bonn

RSA-200

[*] ?

200 663  May 9,

2005Jens Franke et al.,

University of Bonn

RSA-210

[*]

210 696Septembe

r 26, 2013[8]Ryan Propper

RSA-704

[*]

212 704$30,000

USDJuly 2,

2012Shi Bai, Emmanuel Thomé and

Paul Zimmermann

RSA-220

220 729  

RSA-230

230 762  

RSA-232

232 768  

RSA-768

[*]

232 768$50,000

USDDecember

12, 2009Thorsten Kleinjung et al.

RSA-2048

617 2048$200,000

USD

Certicom ECC ChallengeAbstract

Certicom is pleased to present the Certicom Elliptic Curve Cryptosystem (ECC) Challenge. The first of its kind, the ECC

Challenge has been developed to increase the industry’s understanding and appreciation for the difficulty of the

elliptic curve discrete logarithm problem, and to encourage and stimulate further research in the security analysis of

elliptic curve cryptosystems.It is our hope that the knowledge and experience gained from this Challenge will help confirm comparisons of the

security levels of systems such as ECC, RSA and DSA that have been based primarily on theoretical considerations.

We also hope it will provide additional information to users of elliptic curve public-key cryptosystems in terms of

selecting suitable key lengths for a desired level of security.