Informations sur le parcours

Titre :
Les algorithmes de la cryptographie à bas coût
Profils :
Ingénieur informatique, Enseignant-Chercheur, Etudiant
Thème :
Cryptographie à bas coût
Finalité :
Pratique
Difficulté :
niveau 2
Auteur(s) :
Marc Girault
Mise à jour :
26/03/2007 à 10h13
 

L'AES: un algorithme à bas coût?


L'algorithme Rijndael, conçu par J. Daemon et V. Rijmen, est devenu l'AES (Advanced Encryption Standard) en 2000. Bien que ce ne fût pas spécifié dans le cahier des charges du NIST, une étude récente montre, de façon assez surprenante, qu'il pourrait satisfaire des contraintes de ressources très élevées. Plus précisément, les auteurs de [1] décrivent une implémentation qui nécessiterait seulement 3600 portes logiques, soit beaucoup moins que ce qu'aurait par exemple exigé son prédécesseur le DES (Data Encryption Standard).

Cette performance résulte d'un compromis espace-temps délibérément favorable à l'espace. En contrepartie, le temps d'exécution est assez élevé, sans doute incompatible avec les exigences des protocoles de communication les plus courants. Pour y pallier, une solution consiste à multiplexer les dialogues entre un lecteur et les tags, quand ces derniers sont nombreux à être simultanément présents. Ainsi, chaque tag dispose de plus de temps pour répondre, au détriment d'une complexification des protocoles.

Nul doute que d'autres études vont venir compléter et améliorer ce premier défrichage, et, dans un avenir proche, peut-être amener AES aux portes de la cryptographie à bas coût.





[1] M. Feldhofer, S. Dominikus and J. Wolkerstorfer. Strong authentication for RFID systems using the AES algorithm. In Proc. of CHES‘04, LNCS 3156, pages 357-370, Springer-Verlag, 2004.
 

Fonctions Anti-Clones


Les "Fonctions Anti-Clones" constituent une famille d'algorithmes à très bas coût développée par France Télécom. Les premières versions ont été spécifiées vers le milieu des années 90, afin de lutter préventivement contre la contrefaçon des télécartes. Ces dernières, tout comme les étiquettes RFID, contiennent des puces à logique câblée de très faible puissance de calcul. Plus récemment, d'autres versions ont été mises au point pour des étiquettes RFID, et ont été mises à disposition exclusive de l'encarteur de cartes et tickets sans contact ASK (pour l'une), et du fabricant de composant électroniques STMicroelectronics (pour l'autre). Toutes les versions nécessitent approximativement le même nombre de portes logiques, à savoir 500 seulement. Cela exige un savoir-faire particulier, qui explique que ces fonctions n'aient jamais été divulguées.

Une Fonction Anti-Clone est en réalité un algorithme de MAC, destiné à s'intégrer dans un protocole d'authentification de type défi-réponse : le lecteur envoie un nombre aléatoire à la puce, et cette dernière calcule l'image par la fonction du nombre aléatoire et éventuellement d'autres données. La fonction est paramétrée par une clé secrète, généralement propre à chaque puce. Le lecteur (ou le serveur auquel il est connecté) dispose d'une clé maîtresse, qui lui permet de retrouver la clé secrète de chaque puce. Il peut ainsi exécuter le même calcul qu'elle, et comparer les deux résultats.

L'équivalent allemand des Fonctions Anti-Clones fut inventé par Siemens, à peu près au même moment. Il n'a pas été non plus divulgué. Paradoxalement, le secret de ces fonctions, qu'elles soient d'un bord ou l'autre du Rhin, ne les empêche nullement de figurer parmi les algorithmes les plus déployés au monde. Ceci s'explique par le succès croissant de la téléphonie publique aux quatre coins du globe, parfois masqué par sa tombée en désuétude dans les pays développés. Au Mexique, 250 millions de télécartes sont vendues annuellement. C'est si élevé que l'opérateur national a souhaité en diversifier l'approvisionnement. Ainsi les publiphones sont-ils munis d'un lecteur bi-standard, capable aussi bien d'authentifier une carte allemande qu'une carte française, ce qui suppose une cohabitation parfaitement étanche des deux algorithmes de MAC.
 
 

Cryptographie à bas coût: Autres algorithmes à clé secrète


Suivant la voie tracée par France Télécom et Siemens, d'autres sociétés ont développé pour leurs besoins propres des algorithmes sur mesure qui, dans leur principe, s'apparentent grandement aux Fonctions Anti-Clones évoquées dans la fiche précédente –jusque dans leur caractère secret… Ainsi en est-il, par exemple, des algorithmes Crypto1 de Philips, ou de l'algorithme DST de Texas Instruments.

Ce dernier a connu une notoriété peu enviable, lorsque les RSA Labs et la Johns Hopkins University montrèrent qu'on pouvait le casser [1]. Texas Instruments l'avait implanté dans le but d'authentifier à distance des clés de voiture mais avait commis deux imprudences. Tout d'abord, une partie de l'algorithme était, sinon divulguée, assez facilement accessible. D'autre part, la clé était très courte : 40 bits seulement. La cryptanalyse s'effectua en deux étapes : au cours de la première, grâce à une analyse fine de couples (défi, réponse) observées sur la voie radio, les chercheurs du laboratoire parvinrent à reconstituer l'algorithme dans son intégralité. Ensuite, à l'aide d'un tableau de circuits programmables FPGA, ils entreprirent en s'appuyant sur l'un de ces couples, une recherche exhaustive qui ne tarda pas à révéler la clé. L'histoire ne dit pas s'il y avait une faiblesse dans l'algorithme lui-même, car la petitesse de la clé suffisait à elle seule à la mettre en défaut.


 




[1] S. Bono, M. Green, A. Juels, A. Stubblefield, A. Rubin and M. Szydlo. Security analysis of a cryptographically-enabled RFID device. 14th USENIX Security Symposium, 2005.




 

Algorithme à clé publique: GQ2 (factorisation)


Le schéma GQ2 [1], dû à L. Guillou et J.-J. Quisquater, est un protocole d'authentification de type zero-knowledge à trois passes, dont la sécurité repose sur le problème de la factorisation. Il fait suite au protocole GQ [2], des mêmes inventeurs, qui présente l'avantage d'être basé sur l'identité, mais l'inconvénient de nécessiter des calculs plus lents. Les deux schémas sont décrits dans la norme ISO/IEC 9798-5 [3].

Outre qu'il repose sur le même problème difficile, GQ2 se compare naturellement à RSA en ce que les clés sont semblables. En effet, une clé publique GQ2 est un nombre composé, produit de deux ou trois facteurs premiers qui doivent rester secrets. D'autres entiers entrent en jeu dans ce schéma, mais ils sont de petite taille et peuvent par ailleurs être fixés comme des paramètres du système.

La sécurité de GQ2 est difficile à étudier et est encore aujourd'hui une question partiellement ouverte. Mais pour certains choix de clés et de paramètres, elle peut être réduite au problème de la factorisation, ce qui est un peu mieux que RSA lui-même. Dans ce cas, les facteurs premiers d'un module composé n sont a priori mieux protégés s'ils sont mis en oeuvre dans un protocole GQ2 que dans un protocole RSA.

Par ailleurs, une authentification GQ2 est entre 10 et 40 fois plus rapide qu'une authentification RSA. C'est le grand avantage de cette méthode : elle permet d'authentifier une carte à microprocesseur simple (sans cryptoprocesseur) en moins d'une seconde, sans partager de clé avec cette carte. Et il semble bien qu'elle soit la seule à permettre cela, sauf à recourir à une technique de coupons ou à des mathématiques moins maîtrisées (voir fiches suivantes).

Notons enfin que, comme tous les protocoles d'authentification de cette nature, GQ2 peut facilement être converti en schéma de signature numérique à l'aide de l'heuristique dite de Fiat-Shamir, consistant à simuler les aléas du vérifieur par une fonction de hachage pseudo-aléatoire. Cependant, le temps d'exécution du protocole s'en ressent, car il est très sensible à la taille des (pseudo-)aléas utilisés, laquelle doit être d'au moins 80 bits, sinon 160, dans le cas d'une signature numérique. Les signatures GQ et GQ2 sont sur le point d'être normalisées à l'ISO/IEC [4].





[1] L.C. Guillou and J.-J. Quisquater. Technical report on dynamic authentication comparison of RSA, GQ1 and GQ2. Technical report, France Telecom R&D / University of Louvain, 2001.

[2] L.C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In Proc. of Eurocrypt‘88, LNCS 330, pages 123-128, Springer-Verlag, 1989.

[3] ISO/IEC 9798-5. Information technology – Security techniques – Entity authentication – Part 5 : Mechanisms using zero-knowledge techniques. Publiée le 6 décembre 2004.

[4] ISO/IEC 14888-2. Information technology – Security techniques – Digital signatures with appendix – Part 2 : Integer factorisation based mechanisms. A paraître.

 

Algorithme à clé publique: Schnorr (logarithme discret)


Le schéma de Schnorr [1] est un protocole d'authentification de type zero-knowledge à trois passes, dont la sécurité repose sur le problème du logarithme discret. Une particularité importante de ce schéma est que les tailles de la clé privée et des valeurs transmises par le prouveur sont réduites à leur minimum. L'astuce utilisée pour y parvenir sera reprise par le NIST, lorsqu'il spécifiera le standard fédéral DSA (Digital Signature Algorithm). Le schéma de Schnorr est décrit dans la norme ISO/IEC 9798-5 [2], tandis que le DSA est en cours de normalisation [3].

Dans le schéma de Schnorr, la clé privée est le logarithme discret de la clé publique, et ne peut donc en être déduite si les paramètres sont assez grands. A priori, il ne s'agit pas de cryptographie à bas coût, car le prouveur doit calculer une nouvelle exponentielle à chaque authentification. Cependant, ce calcul ayant lieu au tout début du protocole, il peut être effectué à l'avance et son résultat stocké en mémoire en attendant l'interaction. On parle alors de "précalcul" ou de "coupon". Quand vient l'authentification proprement dite, le prouveur n'a plus qu'à transmettre un coupon non encore utilisé, recevoir le défi du vérificateur, calculer la réponse et le lui transmettre. Le calcul de la réponse est, lui, élémentaire. 

Comme GQ2 et tous les protocoles d'authentification de cette nature, le schéma de Schnorr peut facilement être converti en schéma de signature numérique à l'aide de l'heuristique de Fiat-Shamir. Si le temps d'exécution global du protocole s'en ressent, le recours aux coupons permet néanmoins au signataire de produire sa signature en un temps défiant (presque) toute concurrence.





[1] C.P. Schnorr. Efficient signature generation by smart cards. In Journal of Cryptology, Vol. 4, n° 3, pages 161-174, 1991.

[2] ISO/IEC 9798-5. Information technology – Security techniques – Entity authentication – Part 5 : Mechanisms using zero-knowledge techniques. Publiée le 6 décembre 2004.

[3] ISO/IEC 14888-2. Information technology – Security techniques – Digital signatures with appendix – Part 3 : Discrete logarithm based mechanisms. A paraître.
 

Algorithme à clé publique: GPS (logarithme discret)


Le schéma GPS [1], d'après M. Girault, G. Poupard et J. Stern, est une variante du schéma de Schnorr, qui généralise le domaine d'application de ce dernier à tout groupe mathématique dans lequel le logarithme discret est réputé difficile. De façon inattendue, cette généralisation facilite encore le calcul de la réponse du prouveur, car la réduction modulaire disparaît. Si cette différence n'a guère de conséquence dans la plupart des environnements, elle prend son importance dans les puces à simple logique câblée telles que celles dont sont pourvues les étiquettes radio-fréquence, où chaque porte logique économisée compte. Le schéma GPS a été labellisé en 1999 par le projet européen NESSIE [2]. Il figure également dans la norme ISO/IEC 9798-5 [3] en tant que protocole d'authentification et dans la future norme ISO/IEC 14888-2 en tant que schéma de signature numérique [4].

Les caractéristiques de GPS dépendent du groupe dans lequel on choisit d'effectuer les calculs. S'il s’agit des entiers non nuls modulo p, p premier, alors ce schéma est très proche de celui de Schnorr. En revanche, si l'on porte son choix sur les entiers inversibles modulo n, n composé, alors il se compare plutôt à GQ2 et à RSA. Il existe même une version, appelée GPS2 dans la norme citée ci-dessus, dans laquelle les clés sont semblables à celles de ces deux autres algorithmes : la clé publique est un nombre composé, produit de deux ou trois facteurs premiers qui doivent rester secrets. Enfin, si l'on décide de travailler sur une courbe elliptique, alors on obtient un schéma particulièrement compact, avec des clés de petite taille.





[1] Girault, G. Poupard and J. Stern. On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order. Journal of Cryptology, Vol. 19, N°4, Springer-Verlag ,pages 463 - 488, Autumn 2006.

[2] https://www.cosic.esat.kuleuven.be/nessie/

[3] ISO/IEC 9798-5. Information technology – Security techniques – Entity authentication – Part 5 : Mechanisms using zero-knowledge techniques. Publiée le 6 décembre 2004.

[4] ISO/IEC 14888-2. Information technology – Security techniques – Digital signatures with appendix – Part 2 : Integer factorisation based mechanisms. A paraître.

Algorithme à clé publique: SD (codes correcteurs d'erreurs)


Le schéma SD, dû à Stern [1], est un protocole d'authentification de type zero-knowledge à multiples passes. Il tire son du nom du problème sur lequel sa sécurité est fondée : Syndrome Decoding. Ce problème est central dans la théorie des codes correcteurs d'erreurs, et a été utilisé la première fois à des fins cryptographiques en 1978 par McEliece [2]. Le schéma de chiffrement qui porte son nom utilise les codes dits de Goppa, tandis que SD utilise des codes "aléatoires".

Un attrait important de la théorie des codes correcteurs d'erreurs est que les opérations élémentaires sont extrêmement rapides et faciles à implémenter. Elles se réduisent en effet pour l'essentiel à des multiplications et additions dans de très petits corps finis (typiquement le corps à deux éléments). En revanche, les matrices et vecteurs qu'elle manipule sont généralement de grande taille, ce qui, dans des applications cryptographiques, aboutit à des clés publiques de très grande taille également (typiquement 1 Mbit). Cependant, des recherches très récentes visent à corriger ce défaut [3].

Dans le schéma SD, la clé secrète est un mot binaire de poids très faible w et la clé publique est le syndrome de ce mot dans un code choisi aléatoirement. En d'autres termes, si l'on appelle H une matrice binaire (k-n) choisie au hasard et s la clé secrète de n bits, alors la clé publique v est le mot de k bits obtenu en multipliant H par s. Des valeurs typiques sont : n = 1024, k = 512 et w = 110. Un protocole en trois passes permet au prouveur de montrer sa connaissance de s sans rien en révéler. Cependant, comme un imposteur dispose d'une stratégie pour satisfaire ce protocole avec deux chances sur trois, on réduit sa chance de manière exponentielle en itérant le protocole plusieurs fois.





[1] J. Stern. A new identification scheme based on syndrome decoding. In Advances in Cryptology - Crypto‘93, LNCS 773, pages 13-21, Springer-Verlag, 1993.

[2] R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol., Pasadena, CA, pages 114-116, January 1978.

[3] P. Gaborit. Shorter keys for the McEliece cryptosystem. Proc. of WCC 2005.

Algorithme à clé publique: SFLASH (multivariables)


SFLASH est un schéma de signature numérique appartenant à la famille de la cryptographie dite multivariée (ou multivariable), dû à J. Patarin, N. Courtois et L. Goubin [1]. Cette famille regroupe des algorithmes dont la sécurité repose sur la difficulté de résoudre des systèmes d'équations quadratiques, dont les inconnues appartiennent à de très petits corps finis (typiquement les corps à 2 ou 256 éléments) mais nombreuses. Leur petite taille permet des temps d'exécution très courts. Leur grand nombre permet une sécurité élevée. Cette voie de recherche, initiée par Matsumoto et Imaï en 1988 et popularisée par J. Patarin à la fin du siècle dernier est à l'heure actuelle en pleine effervescence. Une connexion étroite avec la cryptographie symétrique a été mise en évidence, notamment au travers des attaques dites algébriques.

Les opérations à effectuer sont, quand on les compare aux schémas reposant sur l'arithmétique, extrêmement rapides. Moins de soixante millisecondes suffisent à un microprocesseur standard de carte à puce pour produire une signature SFLASH. De plus la signature est remarquablement courte : 259 bits seulement. En revanche, la taille de la clé publique est très élevée (typiquement 120 kbit).

SFLASH possède trois versions, dont la plus légère a été cassée en 2002 par H. Gilbert et M. Minier [2]. Par défaut, le nom SFLASH réfère à la version v2, d'ailleurs la première chronologiquement, et labellisée en 1999 par le projet européen NESSIE [3]. Malheureusement cette version a aussi été cassée, sept ans plus tard [4]. En conséquence, l'algorithme n'est plus recommandable en l'état.





[1] J. Patarin, N. Courtois and L. Goubin. FLASH, a fast multivariate algorithm. In CT-RSA‘01, LNCS 2020, pages 297-307, Springer-Verlag, 2001.

[2] H. Gilbert and M. Minier. Cryptanalysis of SFLASH. In Proc. of Eurocrypt‘02, LNCS 2332, pages 288-298, Springer-Verlag, 2002.

[3] https://www.cosic.esat.kuleuven.be/nessie/

[4] V. Dubois, P.-A. Fouque, A. Shamir and J. Stern. Practical Cryptanalysis of SFLASH. 2006. To be published.

Algorithme à clé publique: NTRU (réseaux euclidiens)


NTRU est initialement un schéma de chiffrement à clé publique dû à J. Hoffstein, J. Pipher et J. H. Silverman [1]. Proposé en 1996, il fit l'effet d'une petite bombe, d'une part en raison de ses performances annoncées, d'autre part parce qu'il illustrait pour la première fois que la théorie des réseaux euclidiens (lattices) pouvait aussi être source de schémas efficaces, et pas seulement de méthodes de cryptanalyse dévastatrices avec l'algorithme LLL (Lenstra-Lenstra-Lovasz). Plus précisément, la sécurité de NTRU est connectée à la difficulté de trouver le plus petit vecteur dans un réseau euclidien de grande dimension.

NTRU utilise des polynômes réduits modulo XN dont les coefficients eux-mêmes réduits modulo un premier q sont volontairement choisis petits afin d'accélérer les calculs. La version utilisant de petites valeurs de N et q fut vite cassée [2], mais si par exemple N = 251 et q = 239, alors le schéma résiste à la cryptanalyse. Des algorithmes de signature ont également été proposés, mais ils ont connu de mauvaises fortunes. Le dernier en date [3] a été sévèrement ébranlé lors de la conférence Eurocrypt 2006 [4].

Les algorithmes NTRU sont normalisés ou en cours de normalisation à l'IEEE [5].





[1] J. Hoffstein, J. Pipher and J. H. Silverman. NTRU : a ring based public key cryptosystem. In Proc. of ANTS III, LNCS 1423, pages 267-288, Springer-Verlag, 1998. First presented at the rump session of Crypto‘96.

[2] D. Coppersmith and A. Shamir. Lattices attacks on NTRU. In Proc. of Eucrocrypt‘97, LNCS 1233, pages 52-61, Springer-Verlag, 1998.
 
[3] J. Hoffstein, J. Pipher and J. H. Silverman. NTRUSIGN : Digital signatures using the NTRU lattice. In Proc. of CT-RSA‘03, LNCS 2612, pages 122-140, Springer-Verlag, 2003.

[4] P.Q. Nguyen and O. Regev. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. In Proceedings of Eurocrypt‘06, LNCS 4004, pages 271-288, Springer-Verlag, 2006.

[5] IEEE P1361.1. Public-key cryptographic techniques based on hard problems over lattices. http://grouper.ieee.org/groups/1363/lattPK/index.html