Comment Google a battu le PoW kernelCTF avec AVX512

 (anemato.de)
2 points par GN⁺ 2025-05-31 | 1 commentaires | Partager sur WhatsApp
  • L’équipe Crusaders of Rust voulait soumettre un exploit pour CVE-2025-38001 dans le packet scheduler de Linux, mais en raison du modèle « premier arrivé, premier servi » de kernelCTF, l’enjeu décisif est devenu la réduction du PoW plutôt que le bug lui-même
  • Le processus de soumission enchaînait connexion à 12:00 UTC, environ 4 s de PoW, environ 2,5 s de démarrage de VM, exécution de l’exploit, puis soumission via Google Form ; le record de 4,5 s du round précédent révélait le goulot d’étranglement
  • Le PoW ciblé était un VDF « sloth » : un calcul sériel répétant une exponentiation modulaire par 2^1279 - 1 sur un entier de 1280 bits, difficile à accélérer simplement en ajoutant des cœurs CPU/GPU
  • Après être passés à 1,9 s avec GMP/C++ et une réduction modulaire de Mersenne, puis à environ 1,4 s avec un linkage statique en -march=native, ils ont utilisé le fused multiply-add entier 52 bits d’AVX512IFMA pour descendre à environ 0,21 s sur Ryzen 9950X
  • Le 16 mai 2025, l’équipe a soumis le flag en 3,6 s avec un serveur Google Cloud Zen 5 et un chemin de soumission POST optimisé ; le 28 mai, kernelCTF a annoncé la suppression du PoW

Condition de course : le problème était de soumettre plus vite, pas seulement de trouver le bug

  • En mai 2025, William Liu et Savy Dicanosa, de l’équipe Crusaders of Rust, ont découvert un bug use-after-free CVE-2025-38001 dans le packet scheduler de Linux et développé un exploit
    • William a trouvé le bug en fuzzant Linux pour son mémoire de master
    • Savy a réduit le temps d’exécution de l’exploit à environ 0,55 s
  • kernelCTF de Google ouvrait une fenêtre de soumission toutes les deux semaines à midi UTC, avec une structure où seule l’équipe soumettant en premier le flag sur Google Form après avoir exploité le serveur était récompensée
  • La soumission suivait toujours le même ordre
    • connexion au serveur kernelCTF à 12:00:00 UTC
    • résolution du proof of work, environ 4 s
    • attente du démarrage de l’instance, environ 2,5 s
    • upload et exécution de l’exploit
    • soumission du flag sur Google Form
  • La prime attendue était de 51 000 $
    • récompense de base : 21 337 $
    • récompense pour la fiabilité d’exécution : 10 000 $
    • récompense pour bug 0-day : 20 000 $

Le record précédent révélait le goulot d’étranglement du PoW

  • Lors de la fenêtre de soumission du 2 mai 2025, la première soumission est arrivée 4,5 s après midi
  • Le PoW d’environ 4 s et le démarrage de VM d’environ 2,5 s nécessitant déjà 6,5 s à eux deux, ce record de 4,5 s ne collait pas à un calcul simple
  • En raison du comportement d’arrondi du code serveur de kernelCTF, l’instance VM démarrait en réalité à 11:59:59, ce qui supprimait la contradiction temporelle
  • Malgré cela, le timestamp de génération du flag montrait que l’équipe gagnante avait résolu le PoW en moins d’une seconde
  • Si l’équipe concurrente utilisait un FPGA, un PoW sous la seconde pouvait être possible
    • un FPGA est un matériel personnalisé capable d’exécuter très rapidement des tâches spécifiques
    • il n’est pas adapté aux tâches généralistes, et son coût comme sa difficulté de programmation sont élevés

sloth VDF : un PoW qui se parallélise mal

  • Le PoW de kernelCTF était une fonction de délai vérifiable (VDF) appelée « sloth »
  • Une VDF est une primitive cryptographique qui prouve l’écoulement du temps par un long calcul sériel, tandis que la preuve du résultat reste relativement rapide à vérifier
  • Le calcul lui-même étant sériel, il est difficile de réduire le temps d’exécution en ajoutant des cœurs CPU ou GPU
  • La boucle centrale à optimiser avait la structure suivante
    • difficulty=7337
    • à chaque itération de difficulté, effectuer 1277 fois x = (x * x) % (2 ** 1279 - 1)
    • puis inverser le bit de poids faible de x
  • L’implémentation de référence de Google utilisait gmpy en Python, gmpy étant un binding Python vers GMP
    • GMP est une bibliothèque d’entiers multiprécision dont les kernels d’addition et de multiplication spécifiques à chaque plateforme sont implémentés en assembleur

Première optimisation basée sur GMP

  • La première optimisation consistait à exploiter le fait que 2^1279 - 1 est un nombre de Mersenne pour la réduction modulaire
    • diviser le produit intermédiaire de 2560 bits entre les 1279 bits de poids faible et les bits de poids fort, puis les additionner
    • si le résultat est supérieur ou égal au modulus, le soustraire une fois, ce qui remplace l’opération %
  • Pour réduire l’overhead de la FFI Python, le code a été porté en C++, et cette version s’exécutait en 1,9 s sur un M1 MacBook Pro
  • William a compilé libgmp localement avec -march=native et l’a liée statiquement, descendant à environ 1,4 s sur un laptop Intel Ice Lake
  • Un solveur optimisé similaire écrit en Rust utilisait la même technique de Mersenne, mais prenait environ 2,4 s
  • FLINT a ensuite aussi été testé, mais sa vitesse était presque identique à celle de GMP

Réécrire la mise au carré de grands entiers avec AVX512IFMA

  • AVX512 est une extension de l’ISA x86 d’Intel qui augmente le nombre et la largeur des registres vectoriels, et ajoute la prédication par masques ainsi que plusieurs nouvelles instructions
    • Intel a désactivé la prise en charge d’AVX512 sur ses CPU clients à partir d’Alder Lake
    • côté serveurs, la prise en charge a continué, et AMD a implémenté AVX512 sur les CPU grand public comme serveurs avec Zen 4 et Zen 5
  • La clé était AVX512IFMA
    • vpmadd52luq : ajoute la moitié basse d’un produit 52 bits à un accumulateur 64 bits
    • vpmadd52huq : ajoute la moitié haute d’un produit 52 bits à un accumulateur 64 bits
  • Ces instructions calculent les parties basse et haute d’un produit 52×52→104 bits et les accumulent dans un registre vectoriel
  • Zen 5 dispose d’un chemin de données 512 bits, ce qui lui permettait de lancer deux de ces instructions par cycle
  • La base naturelle était 2^52, et un entier de 1280 bits était représenté par 25 limbs de 52 bits
    • un registre zmm de 512 bits peut contenir 8 limbs
    • la valeur complète tient dans 4 registres zmm

Agencement des multiplications et réduction de Mersenne

  • La mise au carré d’un entier de 1280 bits a été implémentée en élevant au carré 25 limbs de 52 bits pour produire un résultat intermédiaire de 50 limbs
  • La symétrie du carré a permis de réduire presque de moitié le nombre de multiplications nécessaires
    • composantes diagonales ai^2
    • termes croisés 2 * ai * aj pour i < j
  • Pour les termes croisés, une fenêtre glissante de 8 limbs consécutifs était multipliée par un seul limb multiplicateur afin de réduire les shuffles
  • Le merge masking d’AVX512 servait à éviter d’accumuler les multiplications qui ne contribuaient pas à la somme finale
  • La réduction modulaire s’effectuait en ajoutant les 1279 bits de poids fort aux 1279 bits de poids faible
    • comme les éléments de l’accumulateur pouvaient dépasser 2^52 - 1, la propagation des retenues était différée après l’addition
    • le fait que le résultat soit supérieur ou égal à 2^1279 - 1 était déterminé par la présence d’un bit 1280 à 1
    • soustraire 2^1279 - 1 revient à effacer le 1280e bit et à ajouter 1 au limb de poids faible
  • Il restait une très faible possibilité d’overflow à la dernière étape
    • si le dernier limb vaut exactement 2^52 - 1, une propagation de retenue est nécessaire
    • pour un PoW aléatoire, la probabilité d’occurrence a été estimée à environ 2 sur 2 milliards par exécution, et ignorée

De 0,45 s à 0,21 s grâce aux micro-optimisations

  • La première version AVX512IFMA traitait le PoW en environ 0,45 s sur un Ryzen 9950X loué
  • Les instructions multiply-add ont une latence de 4 cycles et peuvent être lancées à raison de 2 par cycle ; il fallait donc au moins 8 accumulateurs pour saturer les unités de multiplication
    • auparavant, il n’y avait que 7 accumulateurs
    • la méthode a été changée pour utiliser 7 accumulateurs pour la moitié basse et 7 pour la moitié haute, soit 14 accumulateurs au total, puis les combiner à la fin
    • ce changement a permis de descendre à environ 0,32 s
  • GCC et clang déroulaient la boucle en générant vbroadcastsd zmm, m64, et l’allocation de registres manquait de registres vectoriels, entraînant des stack spills et des reloads
    • de l’assembleur inline a forcé vpmadd52luq/vpmadd52huq à utiliser un memory broadcast operand
    • le limb multiplicateur n’était plus placé dans un registre vectoriel séparé, mais lu depuis la mémoire et dupliqué vers tous les éléments vectoriels
    • ce broadcast load est traité par la load unit sans utiliser de ressources d’ALU vectorielle
    • à cette étape, le temps est descendu à environ 0,23 s
  • Stocker l’entier aligné en mémoire puis créer la fenêtre avec des chargements non alignés provoquait un store-forwarding stall
    • valignq a été utilisé pour simuler des chargements non alignés à l’intérieur des registres zmm, réduisant les accès mémoire
    • le temps final du PoW est devenu environ 0,21 s

Résultat de la soumission du 16 mai 2025

  • L’équipe a préparé la soumission finale le 16 mai 2025 à 4:30 PST
  • Elle a réduit la latence en utilisant un serveur Google Cloud Zen 5 aux Pays-Bas, géographiquement proche du serveur de soumission Google Form
  • Quelques minutes avant la soumission, elle a intercepté et enregistré une requête POST Google Form avec un flag factice
    • Bryce Casaje et Larry Yuan ont conçu et optimisé le programme de soumission du Form
    • Max Cai a également contribué au développement et à la soumission
  • À 5:00, le serveur s’est connecté au serveur kernelCTF, a résolu le PoW, exécuté l’exploit optimisé de Savy, puis inséré le flag dans la requête POST et l’a envoyée
  • Le résultat a été une soumission en 3,6 s, alors la plus rapide de l’histoire de kernelCTF
  • Les opérateurs de kernelCTF ont confirmé l’éligibilité à la prime le jour même

Suppression du PoW et publication du solveur final

  • Le 28 mai 2025, l’opérateur kernelCTF koczkatamas a annoncé la suppression du PoW
  • Une fois le PoW supprimé, la compétition pour les slots s’est déplacée vers le temps d’exécution de l’exploit et la latence réseau
  • Ce changement a permis de concourir à armes égales avec les équipes spécialisées, même sans FPGA ni expertise en optimisation d’assembleur inline
  • Le code du solveur final est le résultat d’environ 12 heures de travail les 14 et 15 mai 2025, et a été publié sous licence GNU AGPL 3.0
  • L’exemple de build était gcc main.c -O3 -march=znver5 -masm=intel -lgmp

À lire aussi

1 commentaires

 
GN⁺ 2025-05-31
Commentaires sur Hacker News

  • Super contenu. Cette approche ressemble beaucoup à une implémentation de RSA optimisée pour AVX-512, puisque RSA doit lui aussi effectuer des exponentiations avec de très grands exposants.
    Cet article[1] explique comment RSA utilise le fenêtrage, et contient aussi une formule montrant que la taille de fenêtre peut être arbitraire. L’implémentation RSA AVX-512 stocke en plus dans une table les résultats de multiplications dans l’intervalle [0..2^{window-size}), puis, pour chaque fenêtre, récupère ce résultat dans la table[2] et ne fait que des décalages/réarrangements.

    1. https://dpitt.me/files/sime.pdf (hébergé sur mon domaine, car il vient d’une revue)

    2. https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...

    • Intéressant. J’aurais dû voir ça pendant le développement. Ce code gagnerait par exemple à avoir une version supplémentaire pour Zen 5, et avec les registres zmm, le débit des multiplications pourrait apparemment être doublé.
      Il déplace aussi les registres de masque vers des registres généraux pour les opérations arithmétiques, ce qui n’est pas optimal sur Zen 4/5. À part ça, je me demande s’il est vraiment nécessaire de propager la retenue en une seule fois. Dans mon code, j’ai supposé qu’il n’y aurait qu’une seule retenue et je repasse dans une boucle si nécessaire, afin de réduire la latence dans le cas courant. Cela dit, s’il y a des branchements, cela peut poser un problème d’attaque temporelle.
    • dpitt.me/files/sime.pdf peut aussi être envoyé sur archive.org : https://archive.org/download/sime_20250531/sime.pdf

  • Le passage « malgré la prise en charge de [AVX512] sur les CPU grand public depuis plusieurs générations » est un peu étrange.
    Avant Rocket Lake (11e génération), AVX-512 n’était présent que sur les CPU haut de gamme pour passionnés, les CPU Xeon et certains processeurs mobiles, et il est discutable de qualifier ces processeurs mobiles de CPU grand public. Sur la 12e génération, à cause de l’architecture avec cœurs performance/efficacité, il a été désactivé sur ces cœurs quelques mois plus tard et n’est pas réapparu. Cela dit, si AMD obtient un certain succès avec AVX-512, je pense qu’Intel a de bonnes chances de le réintroduire. Pour référence, j’utilise encore un Intel i9-11900.

    • C’est bien la tendance. Le livre blanc AVX10[1] mis à jour par Intel il y a quelques mois semble aussi le confirmer. Il précise que l’AVX 512 bits deviendra standard à la fois sur les cœurs P et E, et qu’Intel s’éloignera des configurations limitées à 256 bits.
      Cela ressemble à un signal fort indiquant qu’AVX-512 revient vraiment, non seulement sur les serveurs, mais aussi sur les futurs CPU grand public avec cœurs E. Probablement pour rattraper l’adoption plus large d’AVX-512 par AMD.

      [1] - https://cdrdv2.intel.com/v1/dl/getContent/784343 (PDF)

    • Les CPU de 12e génération dotés de cœurs performance n’annonçaient de toute façon pas la prise en charge d’AVX512 et ne l’activaient pas par défaut.
      Comme les cœurs efficacité n’intégraient pas AVX512 pour des raisons de surface, l’ensemble du CPU était considéré comme ne le prenant pas en charge. Il était seulement possible d’exploiter le comportement particulier de certaines options de BIOS pour désactiver les cœurs efficacité et activer AVX512 sur le CPU restant, au prix de renoncer aux cœurs E.

  • Le record gagnant était de 3,6 secondes, mais la deuxième place était à 3,73 secondes, soit 3,74 secondes si l’on aligne sur le même nombre de chiffres significatifs que le record. Faut-il donc considérer que le deuxième avait lui aussi optimisé la preuve de travail, ou utilisé un FPGA ?
    L’auteur disait que les soumissions précédentes basées sur des FPGA coûteux dépassaient quand même 4 secondes. Il est donc possible que la deuxième place de cette semaine-là ait été la deuxième soumission la plus rapide de tous les temps ; on pourrait s’attendre à ce qu’il en dise quelque chose.

    • L’image indique dupe. L’équipe de l’article original a probablement essayé de soumettre en parallèle depuis plusieurs comptes.

  • Impressionnant, mais on dirait que l’optimisation porte sur la mauvaise chose. Un CTF ne devrait pas devenir une bataille d’exploitation du processus de soumission.
    Ne serait-il pas préférable pour tout le monde que toutes les équipes ayant envoyé le flag dans la fenêtre de soumission se partagent la récompense ?

    • Ce genre de structure incite aussi à garder un exploit sous le coude au lieu de le signaler immédiatement. Si l’on n’a pas gagné cette fois, on est incité à attendre la prochaine soumission ; même sans jeux sur le timing, il y a une incitation à temporiser.
      Donc, dans les faits, cela peut activement encourager le « mauvais » comportement.
    • Ce serait simplement un autre métajeu. Je n’y ai pas réfléchi en profondeur, mais il me semble probable qu’au final les gens se démotivent et cessent même d’envisager de soumettre à kernelCTF.
    • C’est vrai, mais en pratique presque tous les CTF comportent ce genre d’éléments.

  • Si j’ai bien compris, il y a une preuve de travail de 4 secondes, et les récompenses sont versées une fois par mois.
    Y a-t-il vraiment autant d’exploits pour que des gens se livrent concurrence chaque mois ?

    • Le serveur ouvrait toutes les deux semaines. La preuve de travail servait à ralentir un peu les connexions pour réduire l’incitation à spammer autant de requêtes de connexion que possible.
      Un CTF public, c’est difficile. Au final, certaines équipes adoptent un comportement proche du DDoS pour franchir la ligne d’arrivée. Par la suite, Google a supprimé l’étape de preuve de travail.
    • Ce n’est pas une exécution de code à distance, mais un exploit d’élévation de privilèges locale, c’est-à-dire le passage d’un utilisateur standard à root. Les bugs d’élévation de privilèges sont extrêmement courants.
    • Le mythe de la sécurité du noyau Linux n’est justement qu’un mythe.

  • Excellent contenu, mais les obstacles à franchir pour gagner ce challenge se lisent comme une comédie. On dirait vraiment une machine de Rube Goldberg.

  • Si vous voulez en savoir plus sur la représentation en base 52 mentionnée dans cet article, un autre post en une aujourd’hui vaut le détour : https://news.ycombinator.com/item?id=44132673

  • Petit pinaillage, mais le lien statique ne permet pas l’inlining ; il supprime seulement le surcoût de la PLT. C’est le LTO qui augmente les possibilités d’inlining.

  • Je ne comprends pas pourquoi ils organisent une compétition. Ne pourraient-ils pas simplement récompenser chaque exploit unique ?

    • Parce que le responsable qui finance ce programme génial veut un budget strictement fixe. La justification d’un tel programme tient au moins en partie à mesurer les tendances des exploits et des techniques de mitigation, plutôt qu’à acheter des bugs.
      Et Linux a tellement de bugs que si l’on commence à payer pour tous les 0-day, cela devient incontrôlable. Google a déjà mené une promotion limitée dans le temps, sans compétition, pour pousser les gens à vider leurs stocks de bugs ; lorsqu’ils ont accepté tous les 0-day, les soumissions ont explosé. En même temps, ils ne veulent pas fâcher la communauté, d’où cette structure.

  • C’est un peu déprimant qu’après toutes ces années, des experts puissent prendre le contrôle d’une machine Linux en 3 secondes.