Como vencer o PoW do kernelCTF do Google com AVX512

• A equipe Crusaders of Rust queria enviar um exploit para o CVE-2025-38001 no escalonador de pacotes do Linux, mas, por causa da estrutura de ordem de chegada do kernelCTF, o fator decisivo acabou sendo reduzir o PoW mais do que o próprio bug
• O processo de envio seguia 12:00 UTC conexão, cerca de 4 s de PoW, cerca de 2,5 s para boot da VM, execução do exploit e envio no Google Form, e o recorde anterior de 4,5 s expôs esse gargalo
• O PoW alvo era o VDF “sloth”, um cálculo serial que repetia quadrados modulares em 2^1279 - 1 sobre inteiros de 1280 bits, então era difícil reduzi-lo apenas aumentando a quantidade de núcleos de CPU/GPU
• Após cair para 1,9 s com GMP/C++ e redução modular de Mersenne, e para cerca de 1,4 s com linkagem estática e -march=native, a equipe usou o fused multiply-add inteiro de 52 bits do AVX512IFMA para reduzir o tempo para cerca de 0,21 s em um Ryzen 9950X
• Em 16 de maio de 2025, a equipe enviou a flag em 3,6 s usando um servidor Google Cloud Zen 5 e um caminho otimizado de envio por POST, e em 28 de maio o kernelCTF anunciou a remoção do PoW

---

Corrida contra o tempo: o problema era enviar mais rápido que o bug

• Em maio de 2025, William Liu e Savy Dicanosa, da equipe Crusaders of Rust, descobriram o bug use-after-free CVE-2025-38001 no escalonador de pacotes do Linux e desenvolveram um exploit
  • William encontrou o bug enquanto fazia fuzzing no Linux para sua dissertação de mestrado
  • Savy reduziu o tempo de execução do exploit para cerca de 0,55 s
• O kernelCTF do Google abria uma janela de envio a cada duas semanas ao meio-dia UTC, e apenas a primeira equipe a explorar o servidor e enviar a flag no Google Form recebia a recompensa
• O envio sempre seguia a mesma sequência
  • conectar ao servidor do kernelCTF às 12:00:00 UTC
  • resolver o proof of work, cerca de 4 s
  • esperar o boot da instância, cerca de 2,5 s
  • enviar e executar o exploit
  • enviar a flag no Google Form
• A recompensa esperada era de US$ 51.000
  • recompensa base de US$ 21.337
  • bônus de estabilidade de execução de US$ 10.000
  • bônus de bug 0-day de US$ 20.000

O recorde anterior revelou o gargalo do PoW

• Na janela de envio de 2 de maio de 2025, o primeiro envio aconteceu 4,5 s depois do meio-dia
• Só o PoW de cerca de 4 s somado ao boot da VM de cerca de 2,5 s já exigiria 6,5 s, então o registro de 4,5 s não batia com a conta simples
• Por causa de características de arredondamento no código do servidor do kernelCTF, a instância de VM na prática iniciava às 11:59:59, eliminando a contradição temporal
• Ainda assim, o timestamp de geração da flag mostrava que a equipe vencedora resolveu o PoW em menos de 1 s
• Se uma equipe concorrente tivesse usado FPGA, um PoW abaixo de 1 s poderia ser possível
  • FPGA é hardware customizado capaz de executar tarefas específicas muito rapidamente
  • não é adequado para tarefas de uso geral, e tem custo alto e programação difícil

sloth VDF: um PoW que quase não paraleliza

• O PoW do kernelCTF era um verifiable delay function (VDF) chamado “sloth”
• VDF é um primitivo criptográfico que prova a passagem do tempo por meio de um cálculo serial longo, enquanto a verificação da prova é relativamente rápida
• Como o cálculo em si é serial, é difícil reduzir o tempo apenas adicionando mais núcleos de CPU ou GPU
• O loop central a ser otimizado tinha a seguinte estrutura
  • difficulty=7337
  • em cada repetição de difficulty, executar 1277 vezes x = (x * x) % (2 ** 1279 - 1)
  • depois inverter o bit menos significativo de x
• A implementação de referência do Google usava gmpy em Python, que é um binding Python para GMP
  • GMP é uma biblioteca de inteiros multiprecisão com kernels de soma e multiplicação implementados em assembly para cada plataforma

Primeira otimização com base em GMP

• A primeira otimização explorou o fato de 2^1279 - 1 ser um número de Mersenne para fazer a redução modular
  • o produto intermediário de 2560 bits era dividido entre os 1279 bits baixos e os bits altos, que então eram somados
  • se o resultado fosse maior ou igual ao módulo, bastava subtrair uma vez, substituindo a operação %
• Para reduzir o overhead de FFI do Python, a solução foi portada para C++, e essa versão executava em 1,9 s em um MacBook Pro M1
• William compilou a libgmp localmente com -march=native e fez linkagem estática, chegando a cerca de 1,4 s em um notebook Intel Ice Lake
• Um solver com otimização semelhante escrito em Rust usava a mesma técnica de Mersenne, mas levava cerca de 2,4 s
• Depois, também testaram FLINT, mas o desempenho ficou quase igual ao do GMP

Reescrevendo o quadrado de inteiros grandes com AVX512IFMA

• AVX512 é uma extensão da ISA x86 da Intel que aumenta a quantidade e a largura dos registradores vetoriais e adiciona predição por máscara e várias novas instruções
  • a Intel desativou o suporte a AVX512 em CPUs cliente a partir de Alder Lake
  • no segmento de servidores o suporte continuou, e a AMD implementou AVX512 tanto em CPUs de consumo quanto de servidor nas arquiteturas Zen 4 e Zen 5
• O ponto central foi o AVX512IFMA
  • vpmadd52luq: soma a metade baixa de uma multiplicação de 52 bits em um acumulador de 64 bits
  • vpmadd52huq: soma a metade alta de uma multiplicação de 52 bits em um acumulador de 64 bits
• Essas instruções calculam as partes baixa e alta de uma multiplicação 52×52→104 bits e acumulam o resultado em registradores vetoriais
• O Zen 5 tinha caminho de dados de 512 bits, então conseguia despachar duas dessas instruções por ciclo de clock
• A base natural era 2^52, e o inteiro de 1280 bits era representado por 25 limbs de 52 bits
  • um registrador zmm de 512 bits pode conter 8 limbs
  • o valor completo cabe em 4 registradores zmm

Organização da multiplicação e redução de Mersenne

• O quadrado de 1280 bits foi implementado elevando ao quadrado 25 limbs de 52 bits para gerar um resultado intermediário de 50 limbs
• A simetria do quadrado foi usada para quase reduzir pela metade o número de multiplicações necessárias
  • componentes diagonais ai^2
  • termos cruzados 2 * ai * aj para i < j
• No cálculo dos termos cruzados, uma janela deslizante de 8 limbs consecutivos era multiplicada por um único limb multiplicador para reduzir operações de shuffle
• Com merge masking do AVX512, multiplicações que não fariam parte da soma final não eram acumuladas
• A redução modular era feita somando os 1279 bits altos aos 1279 bits baixos
  • como os elementos do acumulador podiam passar de 2^52 - 1, a propagação de carry era adiada para depois da soma
  • decidir se o resultado era maior ou igual a 2^1279 - 1 equivalia a verificar se o 1280º bit era 1
  • subtrair 2^1279 - 1 era equivalente a limpar o 1280º bit e somar 1 ao limb menos significativo
• No estágio final ainda restava uma possibilidade muito pequena de overflow
  • se o último limb fosse exatamente 2^52 - 1, seria necessária propagação de carry
  • para PoWs aleatórios, a probabilidade foi estimada em cerca de 2 em 2 bilhões por execução e acabou sendo ignorada

Micro-otimizações: de 0,45 s para 0,21 s

• A primeira versão com AVX512IFMA processava o PoW em cerca de 0,45 s em um Ryzen 9950X alugado
• Como as instruções multiply-add tinham latência de 4 ciclos e podiam iniciar duas por ciclo, eram necessários pelo menos 8 acumuladores para saturar a unidade de multiplicação
  • antes havia apenas 7 acumuladores
  • a solução foi usar 7 acumuladores para a metade baixa e 7 para a metade alta, 14 no total, e combinar tudo no fim
  • essa mudança reduziu o tempo para cerca de 0,32 s
• GCC e clang, ao desenrolar o loop, geravam vbroadcastsd zmm, m64, e a alocação de registradores ficava sem registradores vetoriais, causando spill e reload na stack
  • com assembly inline, forçaram vpmadd52luq/vpmadd52huq a usar memory broadcast operand
  • em vez de colocar o limb multiplicador em um registrador vetorial separado, ele era lido da memória e replicado em todos os elementos do vetor
  • esse broadcast load era tratado pela unidade de load, sem consumir recursos da ALU vetorial
  • nessa etapa, o tempo caiu para cerca de 0,23 s
• Armazenar inteiros alinhados na memória e depois formar a janela com loads desalinhados causava store-forwarding stall
  • com valignq, eles passaram a emular loads desalinhados dentro dos registradores zmm, reduzindo acessos à memória
  • o tempo final do PoW ficou em cerca de 0,21 s

Resultado do envio em 16 de maio de 2025

• A equipe preparou o envio final às 4:30 da manhã PST de 16 de maio de 2025
• Para reduzir a latência, usou um servidor Google Cloud Zen 5 na Holanda, geograficamente próximo do servidor que recebia os envios do Google Form
• Minutos antes do envio, interceptaram e registraram uma requisição POST do Google Form usando uma flag fictícia
  • Bryce Casaje e Larry Yuan projetaram e otimizaram o programa de envio do formulário
  • Max Cai também ajudou no desenvolvimento e no envio
• Às 5:00, o servidor conectou ao kernelCTF, resolveu o PoW, executou o exploit otimizado de Savy e inseriu a flag na requisição POST para enviá-la
• O resultado foi um envio em 3,6 s, o mais rápido da história do kernelCTF até então
• Os operadores do kernelCTF confirmaram a elegibilidade para a recompensa no mesmo dia

Remoção do PoW e publicação do solver final

• Em 28 de maio de 2025, o operador do kernelCTF koczkatamas anunciou a remoção do PoW
• Com o fim do PoW, a disputa por slot passou a depender principalmente do tempo de execução do exploit e da latência de rede
• Essa mudança permitiu competir em igualdade com equipes especializadas mesmo sem conhecimento de FPGA ou de otimizações com assembly inline
• O código do solver final foi resultado de cerca de 12 horas de trabalho entre 14 e 15 de maio de 2025 e foi publicado sob GNU AGPL 3.0
• Um exemplo de build era gcc main.c -O3 -march=znver5 -masm=intel -lgmp

[GN⁺]

Comentários do Hacker News

• Conteúdo excelente. Essa abordagem é muito parecida com implementações de RSA otimizado para AVX-512, porque RSA também precisa fazer exponenciação com números muito grandes
  Este artigo[1] trata de como o RSA faz windowing e também inclui uma fórmula que mostra que o tamanho da janela pode ser arbitrário. Implementações de RSA com AVX-512 ainda armazenam em uma tabela os resultados de multiplicação no intervalo [0..2^{window-size}) e, para cada janela, pegam esse resultado da tabela[2] e fazem apenas shifts/rearranjos

  1. https://dpitt.me/files/sime.pdf (hospedado no meu domínio porque foi retirado de um periódico)

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

  • Interessante. Eu deveria ter visto isso enquanto desenvolvia. Aquele código se beneficiaria de mais uma versão, por exemplo para Zen 5, e usando registradores zmm parece que a vazão de multiplicação poderia dobrar
    Além disso, ele move registradores de máscara para registradores de uso geral por causa das operações aritméticas, o que não é ideal no Zen 4/5. Separadamente, também fico curioso se realmente é preciso propagar o carry de uma vez só. No meu código, assumi que o carry ocorre apenas uma vez e, se necessário, volto em um loop, reduzindo a latência no caso comum. Mas, com branches, pode haver problemas de ataque de timing
  • dpitt.me/files/sime.pdf também pode ser colocado no archive.org: https://archive.org/download/sime_20250531/sime.pdf

• A parte “apesar de [AVX512] ter sido suportado em CPUs de consumidor por várias gerações” soa um pouco estranha
  Antes do Rocket Lake (11ª geração), AVX-512 existia apenas em CPUs entusiastas de alto nível, CPUs Xeon e alguns processadores móveis, e é meio discutível chamar processadores móveis de CPUs de consumidor. Na 12ª geração, por causa da arquitetura com núcleos de desempenho/eficiência, ele foi desativado nesses núcleos alguns meses depois e não apareceu de novo. Ainda assim, se a AMD tiver algum sucesso com AVX-512, acho provável que a Intel o reintroduza. Para constar, ainda uso um Intel i9-11900

  • É por aí mesmo. O white paper atualizado de AVX10[1] da Intel, de alguns meses atrás, também parece confirmar isso. Ele diz explicitamente que AVX de 512 bits se tornará padrão tanto nos P-cores quanto nos E-cores, e que eles sairão das configurações somente de 256 bits
    Isso parece um forte sinal de que AVX-512 voltará de verdade não só em servidores, mas também em futuras CPUs de consumidor com E-cores. Provavelmente para alcançar a adoção mais ampla de AVX-512 pela AMD

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

  • CPUs de 12ª geração com núcleos de desempenho nem sequer anunciavam suporte a AVX512 e ele não vinha ativado por padrão
    Como os núcleos de eficiência não incluíam AVX512 por questões de área, a CPU inteira era considerada sem suporte a AVX512. Só era possível usar um comportamento peculiar de algumas opções de BIOS para desligar os núcleos de eficiência e ativar AVX512 no restante da CPU, ao custo de abrir mão dos E-cores

• O recorde vencedor foi 3,6 segundos, mas o segundo lugar fez 3,73 segundos, ou 3,74 segundos se arredondado para o mesmo número de casas do recorde. Então será que o segundo lugar também otimizou a prova de trabalho ou usou FPGA?
  O autor disse que submissões anteriores, mesmo descritas como baseadas em FPGAs caros, passavam de 4 segundos. Então é possível que o segundo lugar daquela semana tenha sido a segunda submissão mais rápida de todos os tempos; acho que teria havido algum comentário sobre isso

  • Na imagem aparece dupe. Provavelmente a equipe do post original tentou fazer submissões paralelas com várias contas

• Impressionante, mas parece uma otimização para o alvo errado. CTF não deveria virar uma disputa de operação de submissão
  Acho que seria melhor para todos se todas as equipes que enviassem a flag dentro da janela de submissão dividissem o prêmio

  • Essa estrutura também incentiva a não reportar exploits imediatamente e ficar segurando eles. Se não conseguiu desta vez, a equipe pode mirar na próxima submissão; mesmo sem brincadeiras com o timing da submissão, há incentivo para segurar
    Então, na prática, ela pode incentivar ativamente o comportamento “errado”
  • Isso viraria outro metagame. Não pensei muito a fundo, mas parece provável que, no fim, as pessoas percam o ânimo e parem até de considerar submissões ao kernelCTF
  • Concordo, mas praticamente todo CTF tem esse tipo de elemento

• Se entendi direito, há uma prova de trabalho de 4 segundos, e o prêmio é pago uma vez por mês
  Existem mesmo tantos exploits assim para as pessoas competirem todo mês?

  • O servidor abria a cada duas semanas. A prova de trabalho era um mecanismo para deixar a conexão um pouco mais lenta e reduzir o incentivo a fazer spam com o máximo possível de tentativas de conexão
    CTF público é difícil. No fim, algumas equipes acabam se comportando de forma parecida com DDoS enquanto correm até a linha de chegada. Depois, o Google removeu a etapa de prova de trabalho
  • Isso não é execução remota de código, mas sim um exploit de elevação local de privilégios, ou seja, do usuário comum para root. Bugs de elevação de privilégio são extremamente comuns
  • O mito da segurança do kernel Linux é literalmente só um mito

• Conteúdo incrível, mas, olhando os obstáculos que é preciso superar para vencer este desafio, parece uma comédia. É uma verdadeira máquina de Rube Goldberg

• Se quiser saber mais sobre a representação em base 52 mencionada neste texto, vale ver outro post que está hoje na front page: https://news.ycombinator.com/item?id=44132673

• Uma observação pequena: linkagem estática não faz inlining; ela só remove o overhead da PLT. Quem aumenta as oportunidades de inlining é o LTO

• Não entendo por que fazem isso como uma competição. Por que não simplesmente recompensar cada exploit único?

  • Porque o chefe quer um orçamento rigidamente fixo para operar um programa legal desses. A justificativa de um programa assim é, pelo menos em parte, medir tendências de exploits e mitigações, não comprar bugs
    E o Linux tem tantos bugs que, se começarem a pagar por todo 0-day, a coisa sai do controle. O Google chegou a fazer uma promoção por tempo limitado, sem competição, para as pessoas descarregarem bugs acumulados; quando aceitaram todos os 0-days, as submissões explodiram. Ao mesmo tempo, eles não querem irritar a comunidade, então a estrutura ficou assim

• É meio deprimente que, depois de todo esse tempo, especialistas ainda consigam tomar uma máquina Linux em 3 segundos