Sécurisation de la Multiplication sur des Corps Finis


L’article, écrit en collaboration avec des chercheurs de l’ENS et de Thales a été présenté à l’occasion de la conférence CRYPTO 2017. Ces travaux apportent une amélioration notable de l’efficacité des contremesures basées sur le partage de secret pour le cas des multiplications définies sur des corps finis.

L’exécution d’algorithmes cryptographiques dans des systèmes embarqués tels que ceux des cartes à puces, des téléphones mobiles ou des automobiles est sensible à des attaques « par analyse de canaux auxiliaires ».

Celles-ci exploitent le comportement physique du matériel (temps d’exécution, rayonnement électromagnétique, consommation de courant) pour retrouver de l’information sur les secrets manipulés par les algorithmes. Afin de contrer de telles attaques, il est nécessaire de protéger les implémentations avec des contremesures dédiées.

Parmi ces dernières, les techniques utilisant les principes de partage de secrets introduits par Shamir (le S de RSA) dans les années 70 sont les plus répandues et leur efficacité a fait ses preuves. Malheureusement, leur complexité est importante et leur utilisation implique souvent une augmentation importante du temps d’exécution et/ou de la consommation de mémoire : essentiellement l’augmentation est quadratique en le gain de sécurité.

L’article présenté propose une amélioration notable de l’efficacité des contremesures, basées sur le partage de secret est proposée pour le cas des multiplications définies sur des corps finis. Une caractérisation algébrique de la résistance de ces circuits dans un modèle de sécurité classique est introduite, et une nouvelle caractérisation algébrique pour la non-interférence (une notion de sécurité plus forte) est proposée. Deux constructions génériques atteignant la propriété de non-interférence sont présentées. Ces constructions permettent une réduction significative du nombre d’aléas et d’opérations nécessaires pour effectuer la multiplication dans un corps fini. Enfin, ces constructions sont instanciées dans des cas pratiques afin d’illustrer leurs bonnes performances dans des implémentations réalistes.

L’efficacité de cette amélioration est argumentée à l’aide d’une analyse formelle poussée et est illustrée par des tests en simulation et en pratique. Sous certaines hypothèses raisonnables, il est montré que la complexité en temps de calcul croit à présent linéairement avec le gain en sécurité (au lieu de quadratiquement).

 

Ces travaux sont co-écrits par Sonia Belaïd (Thales Communications & Security), Fabrice Benhamouda (IBM Research), Alain Passelegue (UCLA), Emmanuel Prouff (ANSSI), Adrian Thillard (ANSSI), et Damien Vergnaud (ENS). Ils ont été présentés lors la conférence CRYPTO 2017.

 

  • pdf

    Private Multiplication over Finite Fields

    530.14 Ko