Direction de recherche : Jean-Charles FAUGÈRE
Co-encadrement : RENAULT Guénaël

Méthodes algébriques pour l'analyse de sécurité des implantations d'algorithmes Cryptographiques

Le 10ème problème de Hilbert, consistant à trouver les solutions entières d'équations polynomiales, est un problème crucial en cryptanalyse. Si ce dernier a été prouvé indécidable, Coppersmith publia en 1996 une méthode basée sur la réduction de réseaux permettant de trouver efficacement l'ensemble des petites solutions de certaines équations polynomiales. De nombreuses applications de cette méthode ont vu le jour dans le domaine de la cryptanalyse de chiffrements à clé publique, notamment lorsque le cryptosystème est exécuté sur un système embarqué et qu'une partie de la clé secrète est dévoilée par la réalisation d'attaques physiques sur le dispositif. Dans ce contexte, nous proposons une attaque physique sur le schéma de signature RSA en mode CRT où une application de la méthode de Coppersmith permet de compléter l'information obtenue par l'attaque physique. Nous proposons également un nouvel algorithme déterministe basé sur la méthode de Coppersmith pour factoriser les entiers de la forme $N=p^rq^s$ en temps polynomial lorsque $r$ ou $s$ sont suffisamment grands.

Enfin, si les applications de la méthode de Coppersmith sont nombreuses, en pratique, du fait que les réseaux euclidiens à réduire soient gigantesques, les petites solutions ne peuvent être retrouvées que jusqu'à une borne qui est plus petite que la borne théorique annoncée. Aussi, une autre contribution de cette thèse consiste en la proposition de deux méthodes permettant une accélération du temps d'exécution de l'algorithme de Coppersmith. Lorsque les deux méthodes sont combinées, le nouvel algorithme s'effectue des centaines de fois plus rapidement pour des paramètres typiques, permettant ainsi dans de nombreux cas d'atteindre la borne théorique.

Soutenance : 16/07/2015

Membres du jury :

STEHLE Damien (ENS Lyon) [Rapporteur]
GUTIERREZ Jaime (Université de Cantabria) [Rapporteur]
FAUGÈRE Jean-Charles (INRIA, UPMC, CNRS, LIP6)
RENAULT Guénaël (INRIA, UPMC, CNRS, LIP6)
CORON Jean-Sébastien (Université du Luxembourg)
NGUYEN Phong (INRIA, ENS Ulm)
GRAILLAT Stef (UPMC, CNRS, LIP6)

Publications 2013-2016

• 2016
  • J.‑S. Coron, J.‑Ch. Faugère, G. Renault, R. Zeitoun : “Factoring $N=p^r q^s$ for Large $r$ and $s$”, RSA Conference Cryptographers' Track, Topics in Cryptology – CT-RSA 2016, San Francisco, United States (2016)
  • J.‑S. Coron, A. Greuet, E. Prouff, R. Zeitoun : “Faster Evaluation of SBoxes via Common Shares”, Lecture Notes in Computer Science, vol. 9813, Cryptographic Hardware and Embedded Systems – CHES 2016, Santa Barbara, CA, United States, pp. 498-514, (Springer) (2016)
  • A. Battistello, J.‑S. Coron, E. Prouff, R. Zeitoun : “Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme”, Lecture Notes in Computer Science, vol. 9813, Cryptographic Hardware and Embedded Systems – CHES 2016, Santa Barbara, CA, United States, pp. 23-39, (Springer) (2016)
• 2015
  • R. Zeitoun : “Méthodes algébriques pour l’analyse de sécurité des implantations d’algorithmes Cryptographiques”, soutenance de thèse, soutenance 16/07/2015, direction de recherche Faugère, Jean-Charles, co-encadrement : Renault, Guénaël (2015)
• 2014
  • J. Bi, J.‑S. Coron, J.‑Ch. Faugère, Phong Q. Nguyen, G. Renault, R. Zeitoun : “Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences”, PKC 2014 - 17^th IACR International Conference on Practice and Theory of Public-Key Cryptography, vol. 8383, Lecture Notes in Computer Science, Buenos Aires, Argentina, pp. 185-202, (Springer) (2014)
• 2013
  • G. Barbu, A. Battistelllo, G. Dabosville, Ch. Giraud, G. Renault, S. Renner, R. Zeitoun : “Combined Attack on CRT-RSA. Why Public Verification Must Not Be Public?”, PKC 2013 - Public-Key Cryptography, vol. 7778, Lecture Notes in Computer Science, Nara, Japan, pp. 198-215, (Springer) (2013)