Comment battre le PoW de kernelCTF de Google avec AVX512

 (anemato.de)
2 points par GN⁺ 2025-05-31 | 1 commentaires | Partager sur WhatsApp
  • L’équipe Crusaders of Rust a découvert un bug de type use-after-free dans l’ordonnanceur de paquets Linux et a développé un exploit
  • Dans le cadre du concours Google kernelCTF, elle a tenté une optimisation hautes performances en raison de la nécessité d’une solution PoW (Proof of Work) rapide
  • Grâce à une optimisation SIMD et assembleur maison exploitant les instructions AVX512IFMA, elle a obtenu des performances près de 7 fois supérieures aux implémentations existantes en Python/GMP et Rust
  • En peaufinant en détail le fonctionnement interne, les opérations modulaires, la gestion mémoire et l’utilisation des registres, elle a réduit le temps de traitement du PoW à 0,21 seconde
  • Au final, l’équipe a effectué une soumission réussie à kernelCTF en un temps record de 3,6 secondes, après quoi la politique PoW a été officiellement supprimée

Vue d’ensemble et objectif

  • En mai 2025, William Liu et Savy Dicanosa de l’équipe Crusaders of Rust ont découvert une vulnérabilité de type use-after-free dans Linux et ont participé au concours kernelCTF de Google
  • Cet article traite du processus d’optimisation visant à résoudre le PoW (Proof of Work) le plus vite possible afin de soumettre plus rapidement que les autres équipes mondiales dans une compétition bounty à temps limité

Processus de soumission à kernelCTF et contexte concurrentiel

  • kernelCTF est un concours auquel participent des équipes de sécurité professionnelles du monde entier, motivées par de grosses primes, et qui misent énormément sur l’automatisation des soumissions et l’optimisation du PoW
  • À chaque fenêtre de soumission (ouverte toutes les deux semaines), seule l’équipe la plus rapide reçoit la récompense
  • Procédure de soumission :
    • se connecter au serveur à l’heure exacte
    • résoudre un PoW qui prend plusieurs secondes
    • attendre le démarrage de la VM
    • exécuter le code d’exploit et obtenir le flag
    • soumettre le formulaire Google
  • Récemment, un flag avait même été soumis avec succès en 4,5 secondes, mais comme le PoW et le démarrage de la VM prennent déjà 6,5 secondes à eux seuls, l’amélioration de la vitesse de résolution du PoW était devenue indispensable

Analyse de l’algorithme PoW (VDF-Sloth) et première optimisation

  • Le PoW de kernelCTF utilise une verifiable delay function fondée sur des calculs séquentiels appelée sloth VDF
    • pour un entier x de 1280 bits, elle répète des opérations de carré modulaire et inversion de bits
  • Dans les implémentations existantes (Python+gmpy et Rust), la parallélisation multi-cœur était déjà inutile et GMP était déjà suffisamment optimisé
  • Cependant, en exploitant le fait que l’opération modulo repose sur un nombre de Mersenne (2^1279-1), l’équipe a réussi à améliorer les performances jusqu’à 1,9~1,4 seconde avec une implémentation modulaire manuelle plus rapide en C++

Changement de cap vers AVX512IFMA et implémentation ultra-rapide basée sur SIMD

  • Ensuite, l’équipe s’est tournée vers l’ISA AVX512, et plus particulièrement vers AVX512IFMA (instructions de multiplication et accumulation sur 52 bits)
  • Le nombre de 1280 bits a été découpé en limbs de 52 bits afin de maximiser l’accélération SIMD (25 limbs → utilisation de 4 registres zmm)
  • En exploitant la symétrie de l’opération de carré modulaire ainsi qu’en répétant des optimisations de bas niveau sur les masques d’accumulation, le broadcast mémoire, l’affectation des registres et les comparaisons sans branchement, l’équipe a affiné l’implémentation
  • L’usage d’ASM (assembleur inline) a permis d’éviter les inefficacités du compilateur liées aux spill/reload de registres, et les optimisations de broadcast et de masquage ont finalement ramené le temps à 0,21 seconde

Automatisation de la soumission du PoW et scénario réel de compétition

  • Pour la soumission finale, l’équipe a utilisé un serveur Google Cloud Zen 5 (région d’Amsterdam) afin de minimiser aussi la latence réseau jusqu’au formulaire Google
  • Grâce à un programme de soumission automatisée (patch de requêtes POST vers le formulaire Google, optimisé via la collaboration interne de l’équipe), elle a soumis le flag avec succès en 3,6 secondes, un record absolu
  • Les organisateurs de kernelCTF ont ensuite annoncé officiellement la suppression de la politique PoW, mettant fin à la course à l’optimisation du PoW et permettant enfin la publication des techniques employées

Détails avancés de l’implémentation

Optimisation des opérations modulaires

  • Les opérations modulo 2^1279-1 (premier) ont été remplacées par quelques décalages de bits et opérations arithmétiques, ce qui a permis des opérations modulaires bien plus rapides que GMP standard

Big integer squaring basé sur AVX512IFMA

  • Utilisation des instructions AVX512 d’accumulation de multiplications sur 52 bits (vpmadd52luq, vpmadd52huq) pour effectuer en parallèle la multiplication et l’accumulation par groupes de 8 limbs
  • Comme la structure comporte 25 limbs, elles sont réparties sur 4 zmm, avec une logique pensée pour minimiser les masquages et accumulations inutiles

Disposition des données et utilisation des registres

  • Suppression des goulets d’étranglement SIMD grâce à des unités par offset, une disposition des données en escalier et des réagencements entre registres (valignq, broadcast)
  • Doublement des accumulateurs afin d’obtenir le meilleur throughput sans attente des unités de multiplication
  • La propagation de retenue (carry propagation) n’est effectuée qu’au strict minimum nécessaire

Automatisation finale de la soumission et collaboration

  • Répartition des membres de l’équipe aux heures de nuit pour frapper au bon moment, avec optimisation de la position réseau et de l’exécution de l’exploit
  • Lors de la soumission réelle, l’ensemble du flux — résolution du PoW, exécution de l’exploit, insertion du flag et requête POST vers Google Form — a été automatisé de bout en bout

Conclusion et portée

  • L’optimisation du PoW de kernelCTF est un travail qui exige une compréhension anatomique du matériel, depuis le niveau bit jusqu’à la mémoire, aux registres et aux CNN
  • Avec la disparition de la politique PoW, la compétition se recentre uniquement sur la vitesse pure du réseau et de l’exploit
  • Ce cas illustre la rencontre entre hacking en conditions réelles et calcul haute performance, et montre aussi comment le savoir-faire en optimisation algorithmique et le code open source pourront continuer à contribuer à la communauté de recherche

Références et annexe

  • Le code complet de l’algorithme PoW, les fonctions de conversion (GMP <-> tableau 52 bits), les opérations modulaires basées sur SIMD et le code d’optimisation ASM ont tous été publiés
  • Il s’agit d’un code « brut », développé de manière intensive sur environ 12 heures puis déployé en conditions réelles, mais publié en open source sous licence GNU AGPL 3.0
  • Pour toute question ou collaboration autour des VDF, il est possible de contacter Discord(@forevermilk)

À lire aussi

1 commentaires

 
GN⁺ 2025-05-31
Commentaires sur Hacker News

  • L’équipe gagnante a terminé en 3,6 secondes, et la 2e place a affiché 3,73 ou 3,74 secondes ; cela laisse penser que le 2e a lui aussi optimisé le PoW ou a peut-être utilisé un FPGA. Comparé aux anciennes soumissions FPGA au-delà de 4 secondes, certains regrettent que l’auteur n’ait pas mentionné que le score de la 2e place cette semaine pouvait lui aussi être un record historique.

  • Cette méthode donne l’impression d’être très proche de celle utilisée dans les implémentations RSA optimisées pour AVX-512, puisque RSA exige lui aussi des opérations d’exponentiation très importantes. L’article (https://dpitt.me/files/sime.pdf) traite des techniques de fenêtrage et du fait que la taille de fenêtre peut être ajustée arbitrairement. Un point supplémentaire dans les implémentations RSA AVX-512 est que les résultats de multiplication sont stockés dans une table sur l’intervalle [0..2^{window-size}) afin d’utiliser le résultat à chaque fenêtre ; un exemple concret est visible dans rsaz-2k-avx512.pl du code aws-lc.

    • Certains regrettent de ne pas avoir vu ce type de contenu plus tôt, car cela aurait pu aider au développement. Sur Zen 5, ils s’attendent à un débit de multiplication doublé grâce à l’utilisation des registres zmm. Dans le code existant, les registres de masque sont convertis en GPR, ce qui est inefficace sur Zen 4/5. Ils s’interrogent aussi sur la nécessité d’une propagation de retenue en une seule fois ; en pratique, le code suppose qu’une retenue ne se produit qu’une fois et boucle là-dessus, ce qui aide généralement à réduire la latence. En revanche, cela laisse subsister un risque d’attaque temporelle dû aux branches.

  • À propos de l’affirmation selon laquelle AVX512 a été pris en charge sur plusieurs générations de CPU grand public, certains se souviennent qu’avant Rocket Lake (11e génération), AVX512 n’était disponible que sur les puces enthusiast, Xeon et quelques processeurs mobiles. Après la 12e génération et l’introduction des cœurs P/E, il a été désactivé puis a disparu en quelques mois. Ils prédisent que si AMD réussit avec AVX512, Intel le réintroduira ; l’un d’eux utilise actuellement un i9-11900.

    • Les CPU 12e génération à cœurs P ne prenaient même pas officiellement en charge AVX512 et ne le mettaient pas en avant ; il était désactivé par défaut, l’espace des cœurs E empêchant son intégration sur l’ensemble du CPU. Au mieux, il était possible, via une astuce BIOS, de désactiver les cœurs E puis d’activer AVX512 sur les autres cœurs, au prix de l’abandon des cœurs E.
    • Le récent livre blanc Intel sur AVX10 (https://cdrdv2.intel.com/v1/dl/getContent/784343) présente désormais l’AVX 512 bits comme standard à la fois sur les cœurs P et E, rompant avec les configurations limitées au 256 bits. Cela est interprété comme le signe d’un vrai retour d’AVX-512, non seulement côté serveur mais aussi sur les futurs CPU grand public, Intel cherchant à suivre l’extension d’AVX-512 chez AMD.

  • Certains remettent en cause la nature même du CTF : au lieu d’une course à la vitesse de soumission, ils estiment qu’il vaudrait mieux que toutes les équipes soumettant le flag dans une fenêtre donnée se partagent la récompense.

    • D’autres soulignent qu’un tel système pourrait pousser les participants à ne pas divulguer immédiatement leurs informations d’exploit et à les conserver pour les tours suivants, créant un méta-jeu qui nuirait au signalement immédiat. Ils craignent aussi des effets pervers, comme une compétition non constructive autour de la stratégie de timing des soumissions.
    • Il est également mentionné que cela changerait la structure du méta-jeu et pourrait au contraire réduire la motivation à participer, au point que davantage de personnes renonceraient à envisager une soumission à kernelCTF.

  • Si la compréhension est bonne, il s’agissait d’un proof of work de 4 secondes avec une structure de paiement mensuelle ; certains se demandent donc s’il apparaît chaque mois autant d’exploits, dans une concurrence aussi intense.

    • Le serveur ouvrait toutes les deux semaines, et le PoW visait à introduire un léger délai pour éviter un excès de requêtes de connexion ; les CTF publics sont parfois suffisamment disputés pour susciter des opérations proches du DDoS. Google a ensuite supprimé l’étape de proof of work.
    • Certains affirment que le mythe autour de la sécurité du noyau Linux n’est en réalité qu’une illusion.
    • Ce CTF concernait non pas une exécution de code à distance, mais un exploit d’élévation de privilèges (passage d’un utilisateur ordinaire à root) ; les bugs d’élévation de privilèges sont réellement fréquents.

  • Défi impressionnant, mais la complexité des obstacles pour gagner et l’atmosphère presque absurde marquent les esprits ; quelqu’un compare cela à une machine de Rube Goldberg.

  • Pour en savoir plus sur ce qui est dit dans le texte à propos de base-52, recommandation de consulter ce billet très discuté aujourd’hui (https://news.ycombinator.com/item?id=44132673).

  • Réaction simple : les maths, c’est génial.

  • Présentation de sloth, une VDF (Verifiable Delay Function) utilisée dans le proof of work : elle exige une longue série de calculs pour prouver l’écoulement du temps, tandis que le résultat peut être vérifié rapidement. Le calcul étant sériel, il est impossible de réduire le temps d’exécution en mobilisant plusieurs cœurs. Certains se demandent si ce domaine pourrait devenir un nouveau marché pour les fabricants de CPU ; ils proposent des instructions dédiées pour les itérations et résultats de sloth, ainsi qu’une protection matérielle contre l’overclocking. Une autre idée consiste à surveiller l’uptime du CPU puis à le signer avec le challenge, ce qui permettrait d’utiliser le CPU en production tout en prouvant sa possession pendant n secondes, dans une logique proche d’un proof of stake.

  • Certains se demandent comment la fonction Python du blog est équivalente à l’implémentation PoW de Google, car cela ne semble pas facile à suivre.

    • Dans le code de Google, exponent = (p + 1) // 4 vaut 2^1277, ce qui signifie que pour élever un nombre à un exposant aussi immense, il faut effectuer 1277 opérations de mise au carré ; la fonction Python implémente précisément cela. Si la valeur initiale est x, chaque carré double effectivement l’exposant, et on finit avec 2^1277, ce qui explique le principe.