Cómo Google kernelCTF PoW fue superado con AVX512

• El equipo Crusaders of Rust quería enviar un exploit para CVE-2025-38001 en el scheduler de paquetes de Linux, pero por la estructura de “el primero en llegar” de kernelCTF, el punto decisivo terminó siendo acortar el PoW más que el bug en sí
• El proceso de envío seguía esta secuencia: conectarse a las 12:00 UTC, resolver un PoW de unos 4 segundos, esperar el arranque de una VM de unos 2.5 segundos, ejecutar el exploit y enviar un Google Form; el récord previo de 4.5 segundos dejaba claro el cuello de botella
• El PoW objetivo era una VDF “sloth”, un cálculo serial que repetía cuadrados modulares sobre un entero de 1280 bits con módulo 2^1279 - 1, así que no era fácil acelerarlo simplemente agregando más núcleos de CPU o GPU
• Con GMP/C++ y reducción modular de Mersenne lo bajaron a 1.9 s, luego a unos 1.4 s con enlace estático y -march=native, y después lo recortaron hasta unos 0.21 s en un Ryzen 9950X usando el fused multiply-add de enteros de 52 bits de AVX512IFMA
• El 16 de mayo de 2025 el equipo envió la flag en solo 3.6 segundos usando un servidor Zen 5 de Google Cloud y una ruta de envío POST optimizada; el 28 de mayo kernelCTF anunció la eliminación del PoW

---

La condición de carrera: el problema era enviar más rápido que el bug

• En mayo de 2025, William Liu y Savy Dicanosa, del equipo Crusaders of Rust, descubrieron el bug use-after-free CVE-2025-38001 en el scheduler de paquetes de Linux y desarrollaron un exploit
  • William encontró el bug mientras hacía fuzzing de Linux para su tesis de maestría
  • Savy redujo el tiempo de ejecución del exploit hasta unos 0.55 segundos
• Google kernelCTF abría una ventana de envío cada dos semanas al mediodía UTC, y solo el primer equipo en explotar el servidor y enviar la flag por Google Form recibía la recompensa
• El envío siempre seguía el mismo orden
  • Conectarse al servidor de kernelCTF a las 12:00:00 UTC
  • Resolver el proof of work, alrededor de 4 segundos
  • Esperar a que arranque la instancia, alrededor de 2.5 segundos
  • Subir y ejecutar el exploit
  • Enviar la flag por Google Form
• La recompensa esperada era de $51,000
  • Recompensa base de $21,337
  • Bono de $10,000 por estabilidad de ejecución
  • Bono de $20,000 por bug 0-day

El récord de envío anterior dejó en evidencia el cuello de botella del PoW

• En la ventana de envío del 2 de mayo de 2025, el primer envío llegó 4.5 segundos después del mediodía
• Solo el PoW de unos 4 segundos y el arranque de VM de unos 2.5 segundos ya sumaban 6.5 segundos, así que el registro de 4.5 segundos no cuadraba con una cuenta simple
• Por una característica de redondeo en el código del servidor de kernelCTF, la instancia de VM en realidad arrancaba a las 11:59:59, así que la contradicción temporal desaparecía
• Aun así, la marca de tiempo de generación de la flag mostraba que el equipo ganador resolvió el PoW en menos de 1 segundo
• Si el equipo rival usó un FPGA, eso podría haber hecho posible un PoW de menos de 1 segundo
  • Un FPGA es hardware personalizado capaz de ejecutar ciertas tareas muy rápido
  • No es ideal para trabajo de propósito general, y su precio y dificultad de programación son altos

sloth VDF: un PoW que no se paraleliza bien

• El PoW de kernelCTF era una función de retardo verificable (VDF) llamada “sloth”
• Una VDF es un bloque criptográfico que prueba que pasó cierto tiempo mediante un cálculo serial largo, mientras que la prueba del resultado puede verificarse relativamente rápido
• Como el cálculo en sí es serial, es difícil reducir su tiempo de ejecución aunque se agreguen más núcleos de CPU o GPU
• El loop central a optimizar tenía esta estructura
  • difficulty=7337
  • En cada iteración de difficulty se ejecutaba 1277 veces x = (x * x) % (2 ** 1279 - 1)
  • Después se invertía el bit menos significativo de x
• La implementación de referencia de Google usaba gmpy desde Python, y gmpy es un binding de Python para GMP
  • GMP es una librería de enteros de precisión múltiple que implementa kernels de suma y multiplicación en ensamblador para cada plataforma

Primera optimización basada en GMP

• La primera optimización aprovechó que 2^1279 - 1 es un número de Mersenne para hacer la reducción modular
  • El producto intermedio de 2560 bits se dividía en los 1279 bits bajos y los bits altos, y luego se sumaban
  • Si el resultado era mayor o igual que el módulo, se restaba una vez para reemplazar la operación %
• Para reducir la sobrecarga del FFI de Python, lo movieron a C++, y esta versión corría en 1.9 segundos en una MacBook Pro con M1
• William compiló libgmp localmente con -march=native y la enlazó estáticamente, bajándolo a unos 1.4 segundos en una laptop Intel Ice Lake
• Un solver con optimización similar escrito en Rust usaba la misma técnica de Mersenne, pero tardaba unos 2.4 segundos
• Después también probaron FLINT, pero su velocidad fue casi igual a la de GMP

Reescribiendo el cuadrado de enteros grandes con AVX512IFMA

• AVX512 es una extensión de la ISA x86 de Intel que aumenta la cantidad y el ancho de los registros vectoriales, y agrega predicación por máscara y varias instrucciones nuevas
  • Intel desactivó el soporte de AVX512 en CPUs cliente a partir de Alder Lake
  • En servidores el soporte continuó, y AMD implementó AVX512 tanto en CPUs de consumo como de servidor con Zen 4 y Zen 5
• La clave fue AVX512IFMA
  • vpmadd52luq: suma la mitad baja de una multiplicación de 52 bits a un acumulador de 64 bits
  • vpmadd52huq: suma la mitad alta de una multiplicación de 52 bits a un acumulador de 64 bits
• Estas instrucciones calculan las partes baja y alta de una multiplicación de 52×52→104 bits y las acumulan en registros vectoriales
• Zen 5 tiene una ruta de datos de 512 bits, así que podía iniciar dos de estas instrucciones por ciclo de reloj
• La base natural era 2^52, y el entero de 1280 bits se representaba con 25 limbs de 52 bits
  • Un registro zmm de 512 bits puede contener 8 limbs
  • El valor completo cabe en 4 registros zmm

Organización de la multiplicación y reducción de Mersenne

• El cuadrado de 1280 bits se implementó elevando al cuadrado los 25 limbs de 52 bits para producir un resultado intermedio de 50 limbs
• Aprovecharon la simetría del cuadrado para reducir casi a la mitad la cantidad de multiplicaciones necesarias
  • Términos diagonales ai^2
  • Términos cruzados 2 * ai * aj para i < j
• En el cálculo de los términos cruzados usaron una ventana deslizante de 8 limbs consecutivos multiplicada por un solo limb multiplicador para reducir shuffles
• Con el merge masking de AVX512 evitaron acumular multiplicaciones que no iban a formar parte de la suma final
• La reducción modular se hacía sumando los 1279 bits altos sobre los 1279 bits bajos
  • Como los elementos del acumulador podían superar 2^52 - 1, la propagación de carry se postergaba hasta después de la suma
  • Determinaban si el resultado era mayor o igual que 2^1279 - 1 verificando si el bit 1280 era 1
  • Restar 2^1279 - 1 equivale a limpiar el bit 1280 y sumar 1 al limb menos significativo
• En la etapa final quedaba una posibilidad de overflow muy pequeña
  • Si el último limb era exactamente 2^52 - 1, hacía falta propagar carry
  • Para PoW aleatorios, estimaron esa probabilidad en unas 2 entre 2 mil millones por ejecución y la ignoraron

Microoptimizaciones: de 0.45 s a 0.21 s

• La primera versión con AVX512IFMA resolvía el PoW en unos 0.45 segundos en un Ryzen 9950X rentado
• Las instrucciones multiply-add tienen una latencia de 4 ciclos y se pueden iniciar dos por ciclo, así que hacían falta al menos 8 acumuladores para saturar la unidad de multiplicación
  • Antes solo tenían 7 acumuladores
  • Cambiaron a 7 acumuladores para la mitad baja y 7 para la mitad alta, 14 en total, y los combinaron al final
  • Ese cambio lo redujo a unos 0.32 segundos
• GCC y clang, al desenrollar el loop, generaban vbroadcastsd zmm, m64, y durante la asignación de registros faltaban registros vectoriales, causando stack spill y reload
  • Con ensamblador en línea forzaron que vpmadd52luq/vpmadd52huq usaran un memory broadcast operand
  • Así, el limb multiplicador se leía desde memoria y se replicaba a todos los elementos del vector sin guardarlo en un registro vectorial aparte
  • Ese broadcast load no consume recursos de la vector ALU, sino que lo maneja la unidad de carga
  • En esta etapa lo bajaron a unos 0.23 segundos
• Guardar enteros alineados en memoria y luego formar la ventana con cargas desalineadas causaba un store-forwarding stall
  • Usaron valignq para simular cargas desalineadas dentro de registros zmm y reducir accesos a memoria
  • El tiempo final del PoW quedó en unos 0.21 segundos

Resultado del envío del 16 de mayo de 2025

• El equipo preparó el envío final a las 4:30 a. m. PST del 16 de mayo de 2025
• Para reducir latencia, usaron un servidor Zen 5 de Google Cloud en Países Bajos, cerca geográficamente del servidor que recibía el Google Form
• Minutos antes del envío interceptaron y registraron la solicitud POST del Google Form con una flag de prueba
  • Bryce Casaje y Larry Yuan diseñaron y optimizaron el programa de envío del formulario
  • Max Cai también ayudó con el desarrollo y el envío
• A las 5:00, el servidor se conectó al servidor de kernelCTF, resolvió el PoW, ejecutó el exploit optimizado por Savy e insertó la flag en la solicitud POST para enviarla
• El resultado fue un envío de 3.6 segundos, el más rápido en la historia de kernelCTF hasta ese momento
• Los operadores de kernelCTF confirmaron ese mismo día que la recompensa calificaba

Eliminación del PoW y publicación del solver final

• El 28 de mayo de 2025, el operador de kernelCTF koczkatamas anunció la eliminación del PoW
• Sin PoW, la competencia por el slot pasó a centrarse en el tiempo de ejecución del exploit y la latencia de red
• Con este cambio, ya se puede competir en las mismas condiciones que los equipos especializados sin necesidad de FPGA ni conocimientos de optimización con ensamblador en línea
• El código del solver final fue el resultado de unas 12 horas de trabajo entre el 14 y 15 de mayo de 2025, y se publicó bajo GNU AGPL 3.0
• Un ejemplo de compilación era gcc main.c -O3 -march=znver5 -masm=intel -lgmp

[GN⁺]

Opiniones en Hacker News

• Excelente contenido. Este enfoque es muy parecido a una implementación de RSA optimizada con AVX-512, porque RSA también tiene que hacer operaciones con exponentes enormes.
  Este paper[1] trata sobre cómo RSA hace windowing e incluye una fórmula que muestra que el tamaño de la ventana puede ser arbitrario. La implementación de RSA con AVX-512 además guarda en una tabla los resultados de multiplicación en el rango [0..2^{window-size}) y, para cada ventana, saca ese resultado de la tabla[2] y solo hace desplazamientos/reordenamientos.

  1. https://dpitt.me/files/sime.pdf (lo alojé en mi dominio porque lo saqué de una revista)

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

  • Interesante. Debería haber visto esto cuando estaba desarrollando. A ese código le vendría bien, por ejemplo, otra versión para Zen 5, y con registros zmm parece que el throughput de multiplicación podría duplicarse.
    Además, está moviendo registros de máscara a registros de propósito general por las operaciones aritméticas, lo cual no es óptimo en Zen 4/5. Por separado, también me pregunto si realmente es necesario propagar el acarreo de una sola vez. En mi código asumí que el acarreo ocurre solo una vez y, si hace falta, vuelvo en un loop, reduciendo así la latencia del caso común. Aunque si hay ramificaciones, podría aparecer un problema de ataques de timing.
  • dpitt.me/files/sime.pdf también se puede subir a archive.org: https://archive.org/download/sime_20250531/sime.pdf

• La parte de “aunque [AVX512] se ha soportado durante varias generaciones en CPUs de consumo” suena un poco rara.
  Antes de Rocket Lake (11.ª generación), AVX-512 solo estaba en CPUs para entusiastas de gama alta, CPUs Xeon y algunos procesadores móviles, y llamar “CPU de consumo” a los procesadores móviles es discutible. En la 12.ª generación, por la arquitectura de núcleos de rendimiento/eficiencia, se desactivó en esos núcleos unos meses después y no volvió a aparecer. Aun así, si AMD tiene cierto éxito con AVX-512, creo que es muy probable que Intel lo reintroduzca. Como referencia, todavía uso un Intel i9-11900.

  • Es la dirección correcta. El white paper actualizado de AVX10[1] de Intel, de hace unos meses, parece confirmarlo. Dice explícitamente que AVX de 512 bits será estándar tanto en los núcleos P como en los núcleos E, y que se alejarán de las configuraciones solo de 256 bits.
    Esto parece una señal fuerte de que AVX-512 volverá en serio no solo a servidores, sino también a futuras CPUs de consumo con núcleos E. Probablemente intenten ponerse al día con la adopción más amplia de AVX-512 por parte de AMD.

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

  • Las CPUs de 12.ª generación con núcleos de rendimiento ni siquiera anunciaban soporte para AVX512 desde el principio, y tampoco venía activado por defecto.
    Como los núcleos de eficiencia no incluían AVX512 por cuestiones de área, toda la CPU se consideraba sin soporte para AVX512. Solo se podía aprovechar un comportamiento peculiar de algunas opciones de BIOS para apagar los núcleos de eficiencia y activar AVX512 en la CPU restante, pagando el precio de renunciar a los núcleos E.

• El récord ganador fue de 3.6 segundos, pero el segundo lugar hizo 3.73 segundos; redondeado a la misma cantidad de cifras que el récord ganador, sería 3.74 segundos. Entonces, ¿también habría que pensar que el segundo lugar optimizó la prueba de trabajo o usó FPGA?
  El autor dijo que el envío anterior, pese a estar basado en FPGA caro, tardaba más de 4 segundos. Entonces existía la posibilidad de que el segundo lugar de esa semana fuera el segundo envío más rápido de la historia; me habría esperado que mencionara algo al respecto.

  • En la imagen dice dupe. Probablemente el equipo del post original intentó enviar en paralelo con varias cuentas.

• Es impresionante, pero parece que están optimizando lo equivocado. Un CTF no debería convertirse en una pelea por la operación de los envíos.
  ¿No sería mejor para todos que todos los equipos que manden la flag dentro de la ventana de envío se repartan el premio?

  • Este tipo de estructura también hace que la gente retenga exploits en vez de reportarlos de inmediato. Si no cobraron esta vez, tienen un incentivo para guardarlos y apuntar al próximo envío, incluso sin juegos con el timing de los envíos.
    Así que, en la práctica, podría incentivar activamente el comportamiento “equivocado”.
  • Eso se convertiría en otro metajuego. No lo he pensado a fondo, pero parece muy probable que, al final, la gente pierda motivación y deje de considerar enviar cosas a kernelCTF.
  • Es cierto, pero en la práctica casi todos los CTF tienen algún elemento de esto.

• Si entiendo bien, hay una prueba de trabajo de 4 segundos y el premio se paga una vez al mes.
  ¿De verdad hay tantos exploits como para que la gente compita todos los meses?

  • El servidor se abría cada dos semanas. La prueba de trabajo era un mecanismo para hacer un poco más lenta la conexión y reducir el incentivo de spammear la mayor cantidad posible de solicitudes de conexión.
    Un CTF público es difícil. Al final, algunos equipos terminan comportándose de forma parecida a un DDoS mientras corren hacia la meta. Más tarde, Google eliminó la etapa de prueba de trabajo.
  • Esto no es ejecución remota de código, sino un exploit de escalada local de privilegios, es decir, pasar de usuario normal a root. Los bugs de escalada de privilegios son de lo más común.
  • El mito de la seguridad del kernel de Linux es literalmente solo un mito.

• Es un contenido impresionante, pero los obstáculos que hay que superar para ganar este desafío se leen casi como comedia. De verdad parece una máquina de Rube Goldberg.

• Si quieren saber más sobre la representación en base 52 mencionada en este artículo, también vale la pena ver otro post de la portada de hoy: https://news.ycombinator.com/item?id=44132673

• Un detalle menor: el enlace estático no hace inlining; solo elimina el overhead de PLT. Lo que aumenta las oportunidades de inlining es LTO.

• No entiendo por qué lo hacen competitivo. ¿No podrían simplemente pagar por cada exploit único?

  • Porque para operar un programa así de genial, su jefe quiere un presupuesto estrictamente fijo. La justificación de este tipo de programa, al menos en parte, no es comprar bugs, sino medir tendencias en exploits y técnicas de mitigación.
    Además, Linux tiene tantos bugs que, si empiezan a pagar por todos los 0-day, se vuelve incontrolable. Google en algún momento hizo una promoción por tiempo limitado, sin competencia, para que la gente sacara a la luz los bugs que tenía acumulados, y cuando reconocieron todos los 0-day, los envíos se dispararon. Al mismo tiempo, no quieren enfadar a la comunidad, así que terminaron con esta estructura.

• Es un poco deprimente que, después de tantos años, los expertos puedan tomar control de una máquina Linux en solo 3 segundos.