Como vencer o PoW do kernelCTF do Google com AVX512

• A equipe Crusaders of Rust encontrou um bug de use-after-free no escalonador de pacotes do Linux e desenvolveu um exploit
• Na competição Google kernelCTF, por causa da necessidade de uma solução rápida de PoW (Proof of Work), tentou otimizações de alto desempenho
• Com assembly próprio e otimização SIMD usando instruções AVX512IFMA, alcançou desempenho quase 7 vezes mais rápido que as implementações existentes em Python/GMP e Rust
• Ajustando minuciosamente princípio de funcionamento, operações modulares, gerenciamento de memória e uso de registradores, reduziu o tempo de processamento do PoW para 0,21 s
• Por fim, fez uma submissão bem-sucedida ao kernelCTF no menor tempo da história (3,6 s), após o que a política de PoW foi oficialmente abolida

---

Visão geral e objetivo

• Em maio de 2025, William Liu e Savy Dicanosa, da equipe Crusaders of Rust, encontraram uma vulnerabilidade de use-after-free no Linux e participaram da competição kernelCTF do Google
• Este texto trata do processo de otimização para resolver rapidamente a verificação de PoW (Proof of Work) e, assim, enviar a submissão antes de outras equipes globais em uma disputa com bounty limitado

Processo de submissão no kernelCTF e contexto competitivo

• O kernelCTF é uma competição em que equipes profissionais de segurança do mundo todo participam com tudo, automatizando submissões e otimizando o PoW por causa das grandes recompensas
• A cada janela de submissão (aberta a cada 2 semanas), apenas a equipe mais rápida recebe o prêmio
• Procedimento de submissão:
  • conectar ao servidor no horário exato
  • resolver o PoW, o que leva alguns segundos
  • esperar o boot da VM
  • executar o código de exploit e obter a flag
  • enviar o formulário do Google
• Recentemente houve até um registro de envio da flag em 4,5 s, mas como só o PoW e o boot da VM já levavam 6,5 s, melhorar a velocidade de resolução do PoW era uma tarefa essencial

Análise do algoritmo de PoW (VDF-Sloth) e a primeira otimização

• O PoW do kernelCTF usa a sloth VDF, uma verifiable delay function baseada em operações sequenciais
  • para um inteiro x de 1280 bits, repete operações de quadrado modular e inversão de bits
• Mesmo nas implementações existentes (Python + gmpy e Rust), paralelização em múltiplos núcleos não ajudava, e o GMP já estava suficientemente otimizado
• Ainda assim, aproveitando que a operação de módulo era baseada no número de Mersenne (2^1279-1), conseguiram melhorar o desempenho para 1,9~1,4 s com uma implementação manual de módulo em C++ mais rápida

A grande virada para AVX512 e a implementação ultrarrápida baseada em SIMD

• Depois disso, a atenção foi para a ISA AVX512 e, dentro dela, especialmente para AVX512IFMA (instruções de multiplicação e acumulação de 52 bits)
• O número de 1280 bits foi dividido em limbs de 52 bits para maximizar a aceleração por SIMD (25 limbs → uso de 4 registradores zmm)
• Repetiram ajustes de baixo nível como simetria da operação de quadrado modular, máscaras de acumulação, broadcast de memória, otimização de alocação de registradores e comparações sem branch
• Usando ASM (inline assembly), impediram spill/reload ineficiente de registradores por parte do compilador e, com otimizações de broadcast e masking, elevaram a velocidade final para 0,21 s

Automação da submissão do PoW e cenário real da competição

• Na submissão final, usaram um servidor Zen 5 no Google Cloud (região de Amsterdã) para minimizar também a latência de rede até o formulário do Google
• Com um programa de submissão automática (patch no POST do formulário do Google e otimizações com colaboração interna da equipe), conseguiram enviar a flag com sucesso em 3,6 s, o menor tempo já registrado
• A equipe do kernelCTF anunciou oficialmente o fim da política de PoW, encerrando a corrida por otimizações de PoW e permitindo a divulgação da técnica

Detalhes avançados de implementação

Otimização de operações modulares

• A operação módulo 2^1279-1 (primo) foi substituída por alguns shifts de bits e operações aritméticas básicas, alcançando uma operação modular muito mais rápida que a do GMP padrão

Squaring de bigint com base em AVX512IFMA

• Usando as instruções AVX512 de multiplicação e acumulação de 52 bits (vpmadd52luq, vpmadd52huq), fizeram multiplicação e acumulação paralela de blocos de 8 limbs
• Como a estrutura tem 25 limbs, ela foi distribuída por 4 zmm, com uma lógica desenhada para minimizar masking e acumulações desnecessárias

Layout de dados e uso de registradores

• Resolveram gargalos de SIMD com unidades por offset, layout de dados em escada e reorganização entre registradores (valignq, broadcast)
• Dobrar o número de acumuladores garantiu throughput máximo sem espera ociosa da unidade de multiplicação
• Até a propagação de carry (carry propagation) foi executada apenas no mínimo necessário

Automação final da submissão e colaboração

• Distribuição de membros da equipe na madrugada para atingir a campanha, além de otimizações de localização de rede e execução do exploit
• Na submissão real, houve automação consistente do início ao fim: resolução do PoW, execução do exploit, inserção da flag e requisição POST ao Google Form

Conclusão e significado

• A otimização do PoW do kernelCTF exigiu um entendimento quase anatômico do hardware, do nível de bits até memória, registradores e CNN
• Com o fim da política de PoW, o foco da competição passou a ser apenas a velocidade pura de rede/exploit
• Este caso mostra o encontro entre hacking prático e computação de alto desempenho e sugere que, no futuro, o know-how de otimização de algoritmos e o código open source continuarão contribuindo para a comunidade de pesquisa

Referências e apêndice

• Todo o código do algoritmo de PoW e das funções de conversão (GMP <-> arranjo de 52 bits), além das operações modulares baseadas em SIMD e do código de tuning em ASM, foi publicado
• Embora seja um código “bruto”, desenvolvido intensivamente ao longo de cerca de 12 horas para uso real, ele foi aberto sob a licença GNU AGPL 3.0
• Dúvidas ou colaboração relacionada a VDF podem ser tratadas via Discord (@forevermilk)

[GN⁺]

Comentários no Hacker News

• A equipe vencedora registrou 3,6 segundos, e o 2º lugar marcou 3,73 ou 3,74 segundos; fica a impressão de que o 2º colocado também fez otimização de PoW ou talvez tenha usado FPGA. Em comparação com envios antigos de FPGA que passavam de 4 segundos, teria sido bom se o autor tivesse mencionado que o resultado do 2º lugar nesta semana também pode ter sido um recorde histórico.

• Fica a impressão de que este método é muito parecido com o usado em implementações de RSA otimizadas para AVX-512, porque o RSA também exige operações de exponenciação muito grandes. O artigo (https://dpitt.me/files/sime.pdf) trata da técnica de windowing e do fato de que o tamanho da janela pode ser ajustado arbitrariamente. Nas implementações de RSA com AVX-512, há ainda o detalhe de armazenar os resultados da multiplicação em uma tabela no intervalo [0..2^{window-size}) para usar o resultado em cada janela. Um exemplo real pode ser visto em rsaz-2k-avx512.pl no código do aws-lc.

  • Fica o lamento de que, se tivesse visto esse material antes, ele poderia ter servido de referência no desenvolvimento. No Zen 5, espera-se o dobro de throughput de multiplicação com o uso de registradores zmm. No código atual, os registradores de máscara são convertidos em GPR, o que é ineficiente no Zen 4/5. Também fica a dúvida se a propagação de carry realmente precisa acontecer toda de uma vez. Na prática, o código assume que o carry ocorre só uma vez e repete isso, o que na maioria dos casos ajuda a reduzir a latência. Por outro lado, continua existindo a possibilidade de ataque de timing por causa do branch.

• Sobre a afirmação de que o AVX512 foi suportado em CPUs de consumo ao longo de várias gerações, a lembrança é de que, antes do Rocket Lake (11ª geração), o AVX512 só estava disponível em processadores entusiastas, Xeon e alguns modelos móveis. Depois da 12ª geração e da introdução de núcleos P/E, ele foi desativado e desapareceu em poucos meses. Fica a previsão de que, se a AMD tiver sucesso com AVX512, a Intel vai adotá-lo de novo; a pessoa comenta que usa um i9-11900.

  • As CPUs P-core da 12ª geração nem sequer davam suporte oficial ou faziam propaganda de AVX512, e ele vinha desativado por padrão. Por causa do espaço ocupado pelos E-cores, o AVX512 não foi incluído no chip como um todo. No máximo, era possível recorrer a um truque de BIOS para desativar os E-cores e ativar AVX512 nos demais núcleos, mas ao custo de abrir mão dos E-cores.
  • No whitepaper recente da Intel sobre AVX10 (https://cdrdv2.intel.com/v1/dl/getContent/784343), a empresa apresenta AVX de 512 bits como padrão tanto para P-cores quanto para E-cores. Ao abandonar a configuração limitada a 256 bits, isso sinaliza que o AVX-512 pode voltar de verdade não só a servidores, mas também a futuras CPUs de consumo. A interpretação é que a Intel está correndo atrás da expansão do AVX-512 pela AMD.

• Há dúvidas sobre a própria natureza da competição CTF: em vez de uma corrida pela velocidade do envio, seria melhor um modelo em que todas as equipes que enviassem a flag dentro de uma janela definida compartilhassem o prêmio.

  • Levanta-se a possibilidade de que esse modelo crie um metajogo no qual os participantes não divulgariam imediatamente as informações do exploit, guardando-as para tentar as rodadas seguintes, o que atrapalharia o reporte imediato. Também há preocupação com efeitos colaterais como competição pouco construtiva baseada em estratégia de timing de envio.
  • Menciona-se que a estrutura do metajogo mudaria e que isso poderia até reduzir a motivação para participar, aumentando o número de pessoas que nem considerariam enviar algo ao kernelCTF.

• Se entendi direito, trata-se de um proof of work de 4 segundos com pagamentos mensais; fica a curiosidade se realmente surgem tantos exploits por mês a ponto de haver essa competição acirrada.

  • O servidor abria a cada duas semanas, e o PoW servia para introduzir um pequeno atraso com o objetivo de evitar requisições excessivas. CTFs públicos às vezes ficam tão intensos que há tentativas parecidas com DDoS. Depois, o Google removeu a etapa de proof of work.
  • Afirma-se que o mito da segurança do kernel Linux, na prática, não passa de fantasia.
  • Este CTF não era sobre execução remota de código, mas sobre exploits de escalonamento de privilégios (de usuário comum para root). Bugs de escalonamento de privilégios são realmente muito comuns.

• É um desafio impressionante, mas a complexidade dos obstáculos para vencer e o clima meio absurdo chamam atenção; surge a comparação divertida com uma máquina de Rube Goldberg.

• Para quem quiser saber mais sobre a parte de base-52 mencionada no texto, recomendam este post que esteve em alta hoje (https://news.ycombinator.com/item?id=44132673).

• Comentário de que matemática é legal.

• Apresentação do sloth, uma VDF (Verifiable Delay Function) usada no proof of work, que exige uma sequência longa de cálculos para provar a passagem do tempo, enquanto o resultado pode ser verificado rapidamente. Como o cálculo é serial, não dá para reduzir o tempo de execução usando vários núcleos. Surge a curiosidade sobre se essa área poderia se tornar um novo mercado para fabricantes de CPU. Também se propõe adicionar instruções dedicadas para as iterações do sloth e seus resultados, além de um recurso de hardware contra overclock, e se sugere a ideia de monitorar o uptime da CPU e assinar isso junto com o desafio. Isso se parece com um conceito de proof of stake em que a CPU continua sendo usada em produção, mas ao mesmo tempo prova a posse da CPU por n segundos.

• Fica a dúvida de como a função em Python mostrada no blog é equivalente à implementação de PoW do Google; parece difícil de acompanhar.

  • No código do Google, exponent = (p + 1) // 4 é igual a 2^1277. Para elevar um número a um expoente tão gigantesco, seria preciso fazer 1277 quadraturas, e a função em Python realmente implementa isso. Se o valor inicial é x, a cada quadratura a multiplicação dobra, e no final chega-se a 2^1277 delas; é esse o princípio explicado.