Quatre milliards de requêtes pour éprouver une ancienne clé RSA

Deux études de Google DeepMind chiffrent le coût de falsifier une signature RSA-1024 et celui de factoriser des clés de même taille.

Quatre milliards de requêtes à un dispositif de signature simulé ont précédé le choix de la cible. Une fois cet accès coupé, les chercheurs de Google DeepMind ont calculé la valeur qui tient lieu de signature dans l’expérience et l’ont vérifiée avec la clé publique. L’équipe a repris un cas RSA de 1 024 bits étudié par Laura Shea et ses coauteurs. Les facteurs de la clé étaient déjà connus. Seul le programme qui simulait le dispositif de signature y avait accès.

Pour obtenir ce résultat, préparation comprise, les tâches retenues ont mobilisé l’équivalent de 391 années sur un cœur de processeur, contre 1 380 dans l’expérience précédente. Le document de travail sur les signatures rapporte un temps CPU divisé par 3,5 sur le même cas, avec une partie du calcul effectuée sur des GPU et comptabilisée séparément. Les 3,2 jours écoulés entre le lancement à grande échelle et la vérification du résultat tiennent surtout au nombre de tâches exécutées en parallèle. En moyenne, quelque 45 000 cœurs travaillaient en même temps. Ce que le dispositif laisse choisir

Une signature numérique sert à vérifier l’origine et l’intégrité d’un document ou d’une mise à jour logicielle. Dans le format étudié, le dispositif complète les données qu’il reçoit avec des octets prédéfinis pour former un bloc de taille fixe. Les chercheurs ont examiné ce que ce format change quand une personne ayant accès à l’interface de signature peut choisir directement une partie du bloc.

Pour une clé de 1 024 bits, si cette personne contrôle environ la moitié du bloc, le calcul devient presque aussi accessible qu’avec une interface qui accepte des données sans format imposé. Si elle ne peut choisir qu’une empreinte de 32 octets, le problème est plus difficile. Pour ce scénario, Pushmeet Kohli estime que la nouvelle méthode divise le coût par environ 1 600 par rapport à la méthode de référence. Ce facteur vient d’une estimation théorique. Les dispositifs qui calculent eux-mêmes l’empreinte du message sortent du modèle étudié. Répartir la préparation entre plusieurs clés

La seconde étude, sur la factorisation, examine le coût de retrouver les deux nombres premiers dont le produit figure dans la clé publique RSA. Connaître ces facteurs permet de reconstituer la clé privée. Dans l’expérience de falsification, il suffisait de calculer une signature pour la cible choisie.

Les auteurs proposent de mutualiser une partie du travail entre plusieurs clés de même taille. Dans leur estimation pour RSA-1024, la préparation coûte autant qu’une factorisation par la méthode classique. Une fois cette étape payée, le coût de chaque clé supplémentaire est environ 30 fois inférieur à celui de la meilleure méthode antérieure pour ce budget. La proposition reste théorique. Pour RSA à 2 048 bits, les deux articles fournissent des estimations de coût. Le calcul mené en laboratoire porte sur 1 024 bits. Qui a fait quoi dans l’expérience

Pour reproduire le calcul sur les signatures, un agent a préparé le plan, fixé les vérifications et contrôlé les résultats. Un autre a écrit le code, lancé les tâches sur le cluster et corrigé les erreurs. Le chercheur a défini l’objectif et donné son accord aux étapes décisives. Dans l’étude sur la factorisation, un agent a élaboré des preuves et un autre les a vérifiées. Les auteurs ont aussi utilisé Lean 4 pour vérifier les identités algébriques et certaines conditions de faisabilité.