Side-Channel Attack Against RSA Key Generation Algorithms

Auteurs : Aurélie Bauer (ANSSI), Eliane Jaulmes (ANSSI), Victor Lomné (ANSSI), Emmanuel Prouff (ANSSI), Thomas Roche (ANSSI)
Présenté par Victor Lomné lors de CHES 2014 (23 au 26 septembre à Busan, Corée du Sud)

De nombreuses applications fonctionnant sur des systèmes embarqués nécessitent la génération de paramètres secrets pendant la durée de vie du produit. Dans ce contexte ouvert, plusieurs travaux ont montré que les algorithmes de génération de clefs sont vulnérables aux attaques par canaux auxiliaires. C’est en particulier le cas de la génération de facteurs premiers pour l’algorithme de signature RSA. Jusqu’à présent, la menace a été démontrée sur des implémentations naïves dont le flot d’opérations dépend des données secrètes, et une contremesure simple (et bien connue) consiste à supprimer cette dépendance.

Dans cet article, nous proposons une nouvelle attaque qui rend cette stratégie de défense inefficace et met en défaut des recommandations d’implémentations présentes dans les standards ANSI X9.31 et FIPS 186-4.
Dans une seconde partie de l’article, l’efficacité de l’attaque est analysée pour différentes spécifications de la génération de clefs. Des expériences sont également présentées contre une implémentation sur carte à puce.

L’article se conclut sur une discussion quant aux contremesures possibles à notre attaque et aboutit à la conclusion principale suivante : les algorithmes de génération de nombres premiers doivent éviter l’utilisation d’un crible de nombres premiers combiné avec un processus déterministe générant les nombres premiers à partir d’une graine aléatoire.