Cómo Google venció el PoW de kernelCTF con AVX512

• El equipo Crusaders of Rust descubrió un bug de use-after-free en el planificador de paquetes de Linux y desarrolló un exploit
• En la competencia Google kernelCTF, intentaron una optimización de alto rendimiento debido a la necesidad de una solución rápida para el PoW (Proof of Work)
• Con ensamblador propio y optimización SIMD usando instrucciones AVX512IFMA, lograron un rendimiento casi 7 veces más rápido que las implementaciones existentes en Python/GMP y Rust
• Ajustaron en detalle el funcionamiento interno, las operaciones modulares, la gestión de memoria y el uso de registros, reduciendo el tiempo de procesamiento del PoW hasta 0.21 segundos
• Finalmente, tras una entrega exitosa a kernelCTF en el menor tiempo de la historia (3.6 segundos), la política de PoW fue eliminada oficialmente

---

Resumen y propósito

• En mayo de 2025, William Liu y Savy Dicanosa, del equipo Crusaders of Rust, encontraron una vulnerabilidad de use-after-free en Linux y participaron en la competencia kernelCTF de Google
• Este artículo trata sobre el proceso de optimización para resolver rápidamente la verificación PoW (Proof of Work) y así poder enviar antes que otros equipos globales en una competencia por bounty con tiempo limitado

Proceso de envío a kernelCTF y contexto competitivo

• kernelCTF es una competencia en la que, debido a las grandes recompensas, equipos de seguridad especializados de todo el mundo participan apostándolo todo a la automatización de envíos y a la optimización del PoW
• En cada ventana de envío (que se abre cada 2 semanas), solo el equipo más rápido recibe el premio
• Procedimiento de envío:
  • Conectarse al servidor en punto
  • Resolver el PoW, lo que toma varios segundos
  • Esperar el arranque de la VM
  • Ejecutar el código del exploit y obtener la flag
  • Enviar el formulario de Google
• Recientemente hubo incluso un caso exitoso de envío de la flag en 4.5 segundos, pero como solo el PoW y el arranque de la VM ya tomaban 6.5 segundos, mejorar la velocidad del PoW era una tarea indispensable

Análisis del algoritmo PoW (VDF-Sloth) y primera optimización

• El PoW de kernelCTF usa una verifiable delay function basada en cómputo secuencial llamada sloth VDF
  • Para un entero de 1280 bits x, repite operaciones de cuadrado modular e inversión de bits
• Incluso en las implementaciones existentes (Python+gmpy y Rust), la paralelización multinúcleo no ayudaba y GMP ya estaba suficientemente optimizado
• Sin embargo, aprovechando que la operación módulo se basa en el número de Mersenne (2^1279-1), lograron mejorar el rendimiento hasta 1.9~1.4 segundos con una implementación modular manual más rápida en C++

El gran salto a AVX512 y la implementación ultrarrápida basada en SIMD

• Después pusieron la mira en la ISA AVX512 y, en particular, en AVX512IFMA (instrucciones de multiplicación y acumulación de 52 bits)
• Dividieron el número de 1280 bits en limbs de 52 bits para maximizar la aceleración SIMD (25 limbs → uso de 4 registros zmm)
• Repitieron ajustes de bajo nivel como la simetría de la operación modular de cuadrado, máscaras de acumulación, broadcast en memoria, optimización de asignación de registros y comparación sin ramas
• Usando ASM (inline assembly), evitaron el spill/reload ineficiente de registros por parte del compilador y, con optimizaciones de broadcast y enmascarado, llevaron finalmente la velocidad hasta 0.21 segundos

Automatización del envío del PoW y escenario real de la competencia

• En la entrega final, usaron un servidor Google Cloud Zen 5 (región de Ámsterdam) para minimizar también la latencia de red hasta el formulario de Google
• Con un programa de envío automático (parcheando la solicitud POST del formulario de Google y optimizado mediante colaboración interna del equipo), lograron enviar la flag con éxito en 3.6 segundos, el tiempo más corto registrado hasta ahora
• Después, la organización de kernelCTF anunció oficialmente la eliminación de la política de PoW, liberando a los participantes de la carrera de optimización del PoW y permitiendo publicar la técnica

Detalles avanzados de implementación

Optimización de operaciones modulares

• Sustituyeron la operación módulo 2^1279-1 (primo) por unos pocos desplazamientos de bits y operaciones aritméticas básicas, logrando una operación modular mucho más rápida que la de GMP estándar

Squaring de enteros grandes basado en AVX512IFMA

• Usaron las instrucciones de multiplicación-acumulación de 52 bits de AVX512 (vpmadd52luq, vpmadd52huq) para multiplicar y acumular en paralelo grupos de 8 limbs
• Como la estructura es de 25 limbs, la distribuyeron en 4 registros zmm y diseñaron una lógica que minimiza enmascarados/acumulaciones innecesarios

Disposición de datos y uso de registros

• Eliminaron cuellos de botella SIMD con unidades por offset, disposición escalonada de datos y reacomodo entre registros (valignq, broadcast)
• Duplicaron los acumuladores para asegurar el máximo throughput sin esperas ociosas de las unidades de multiplicación
• Incluso la propagación de carry se realizó solo en el mínimo necesario

Automatización final del envío y colaboración

• Organizaron a los miembros del equipo en horario de madrugada para el ataque coordinado, optimizando la ubicación de red y la ejecución del exploit
• En el envío real, automatizaron de extremo a extremo la resolución del PoW, la ejecución del exploit, la inserción de la flag y la solicitud POST al Google Form

Conclusión y significado

• La optimización del PoW de kernelCTF es un trabajo que requiere una comprensión casi anatómica del hardware, desde el nivel de bits hasta la memoria, los registros y las CNN
• Con la desaparición de la política de PoW, el foco de la competencia pasa a ser únicamente la “velocidad pura de red/exploit”
• Este caso muestra el encuentro entre el hacking práctico y la computación de alto rendimiento, y apunta a que tanto las técnicas de optimización algorítmica como el código open source seguirán aportando a la comunidad investigadora

Referencias y apéndice

• Se publicaron por completo el código del algoritmo PoW y las funciones de conversión (GMP <-> arreglo de 52 bits), las operaciones modulares basadas en SIMD y el código ASM afinado
• Aunque es un código “rústico” desarrollado intensivamente durante unas 12 horas para uso inmediato en producción, fue liberado bajo licencia GNU AGPL 3.0
• Para dudas o colaboración relacionada con VDF, se puede contactar por Discord (@forevermilk)

[GN⁺]

Opiniones de Hacker News

• El equipo que ganó con 3.6 segundos y el segundo lugar marcaron 3.73 o 3.74 segundos; da la impresión de que el segundo lugar también optimizó el PoW o incluso pudo haber usado FPGA. Comparado con envíos anteriores con FPGA que tardaban más de 4 segundos, queda la sensación de que habría sido bueno que el autor mencionara que el registro del segundo lugar esta semana también podría ser una marca histórica.

• Da la impresión de que este método es muy parecido al que se usa en implementaciones de RSA optimizadas para AVX-512, porque RSA también requiere operaciones de exponenciación muy grandes. El paper (https://dpitt.me/files/sime.pdf) trata la técnica de windowing y cómo el tamaño de ventana puede ajustarse arbitrariamente. En implementaciones RSA con AVX-512, además se almacenan en una tabla los resultados de multiplicación en el rango [0..2^{window-size}) para usar el resultado en cada ventana. Un ejemplo real puede verse en rsaz-2k-avx512.pl del código de aws-lc.

  • Queda la sensación de que habría servido haber visto esto antes como referencia para el desarrollo. En Zen 5 se esperaría el doble de rendimiento de multiplicación usando registros zmm, y en el código existente los registros de máscara se convierten en GPR, lo cual es ineficiente en Zen 4/5. También surge la duda de si la propagación de carry realmente tiene que hacerse necesariamente de una sola vez. De hecho, el código repite asumiendo que el carry solo ocurre una vez, lo que en la mayoría de los casos ayuda a reducir la latencia. Eso sí, sigue existiendo la posibilidad de ataques de timing por el uso de ramas.

• Sobre la afirmación de que AVX512 estuvo soportado en CPU de consumo a lo largo de varias generaciones, recuerdan que antes de Rocket Lake (11.ª generación) AVX512 solo estaba disponible en procesadores enthusiast, Xeon y algunos móviles. Después de la 12.ª generación y la introducción de núcleos P/E, fue desactivado y desapareció en cuestión de meses. Se deja la predicción de que si AMD tiene éxito con AVX512, Intel volverá a introducirlo. La persona comenta que usa un i9-11900.

  • Los CPU P-core de 12.ª generación ni siquiera soportaban ni anunciaban AVX512, y venía desactivado por defecto. Como el espacio estaba destinado a los E-core, AVX512 no venía implementado en todo el CPU. A lo sumo era posible activar AVX512 en los núcleos restantes mediante el truco de desactivar los E-core en BIOS, pero a cambio había que renunciar a los E-core.
  • En el reciente whitepaper de Intel sobre AVX10 (https://cdrdv2.intel.com/v1/dl/getContent/784343), se plantea AVX de 512 bits como estándar tanto para P-core como para E-core. Al dejar atrás configuraciones limitadas a 256 bits, se anticipa un regreso formal de AVX-512 no solo en servidores sino también en futuros CPU de consumo. Se interpreta como un intento de Intel por seguir a AMD a medida que esta amplía AVX-512.

• Se cuestiona la esencia del torneo CTF: opinan que, en lugar de una competencia por velocidad de envío, sería mejor un esquema donde todos los equipos que envíen la flag dentro de una ventana determinada compartan el premio.

  • Se plantea que ese modelo podría generar un metajuego en el que los participantes no revelen de inmediato la información del exploit y la retengan para rondas posteriores, perjudicando el reporte inmediato. También preocupa el efecto secundario de incentivar competencias poco constructivas, como estrategias sobre el momento del envío.
  • Se menciona que la estructura del metajuego cambiaría y que incluso podría reducir la motivación para participar, aumentando la cantidad de personas que ni siquiera considerarían hacer envíos a kernelCTF.

• Si entendí bien, se trata de un proof of work de 4 segundos y una estructura de pago mensual; surge la duda de si realmente aparecen tantos exploits cada mes como para que exista una competencia tan intensa.

  • El servidor se abría cada dos semanas y el PoW servía para introducir una pequeña demora con el objetivo de evitar solicitudes de conexión excesivas. Los CTF públicos a menudo son tan competitivos que incluso se intentan operaciones parecidas a DDoS. Después, Google eliminó la etapa de proof of work.
  • Se afirma que el mito sobre la seguridad del kernel de Linux en realidad no es más que una ilusión.
  • Este CTF no trataba de ejecución remota de código, sino de exploits de escalada de privilegios, es decir, pasar de usuario normal a root. Los bugs de escalada de privilegios son realmente comunes.

• Es un desafío sorprendente, pero deja la impresión de que la complejidad de los obstáculos para ganar y el ambiente casi ridículo hacen que parezca una máquina de Rube Goldberg, en el sentido divertido de la expresión.

• Si quieren saber más sobre lo relacionado con base-52 mencionado en el artículo, recomiendan ver este post que estuvo caliente hoy (https://news.ycombinator.com/item?id=44132673).

• Comentario de que las matemáticas son geniales.

• Presentan sloth, una VDF (Verifiable Delay Function) usada en el proof of work, que exige una serie de cálculos largos para demostrar el paso del tiempo, mientras que el resultado puede verificarse rápidamente. Como el cálculo es serial, no es posible reducir el tiempo de ejecución usando varios núcleos. Se preguntan si este campo podría convertirse en un nuevo mercado para los fabricantes de CPU, y proponen instrucciones dedicadas para las iteraciones y resultados de sloth, además de funciones de prevención de overclocking a nivel de hardware. También se plantea como idea monitorear el uptime del CPU y firmarlo junto con el challenge. Eso se parece a una noción de proof of stake que permitiría usar productivamente el CPU mientras al mismo tiempo se demuestra la posesión del CPU durante n segundos.

• Surge la duda de cómo la función en Python mostrada en el blog es equivalente a la implementación de PoW de Google; da la impresión de que es difícil de seguir.

  • En el código de Google, exponent = (p + 1) // 4 resulta ser 2^1277. Para elevar un número a un exponente tan enorme, hay que hacer 1277 cuadrados, y la función en Python justamente implementa eso. Si el valor inicial es x, en cada cuadrado se duplica el exponente multiplicativo, y al final se llega a 2^1277, explican.