- Em código criptográfico, a propriedade crucial de tempo constante (constant-time) pode ser quebrada apenas por otimizações do compilador, e um experimento está em andamento para inserir um patch de aviso dentro do LLVM para encontrar padrões de risco
- A “otimização” do compilador pode acelerar parte dos benchmarks, mas muitas vezes os caminhos realmente críticos dependem de intrinsics e assembly, e o custo dos bugs gerados pela otimização se acumula separadamente
- Em junho de 2024, Antoon Purnal confirmou que o código de referência do Kyber, com Clang 15 ou superior e certas opções de otimização, pode ser transformado em desvios condicionais baseados em valores secretos, permitindo ataques de timing
- O TIMECOP 2 inspeciona, dentro do SUPERCOP, os resultados compilados declarados como constantes no tempo, mas há limitações tanto nos comandos suportados pelo Valgrind quanto no fluxo de dados exposto durante a execução real dos testes
- Na prática, a resposta é usar funções como
crypto_{int,uint}{8,16,32,64}.h para impedir que o compilador trate resultados de 1 bit como bool, ou migrar para assembly verificado, linguagens voltadas à segurança ou compiladores dedicados
O vazio de responsabilidade criado pela “otimização” do compilador
- Nos históricos recentes de mudanças de LLVM e GCC, continuam aparecendo “otimização”, testes de “otimização”, correções de testes e correções de bugs de “otimização”
- Mesmo quando um código funcionava bem antes da compilação e muda depois de alterações no compilador, em muitos casos a responsabilidade recai sobre o programador por ter esbarrado em “undefined behavior”
- Esses “language standards” são definidos por autores de compiladores e, no fim, formam uma estrutura em que o código de milhões de programadores assume mais responsabilidade do que as mudanças feitas por um pequeno grupo de autores de compiladores
- Como exemplo em código criptográfico, em vários benchmarks de CPU a implementação
avx2 de kyber768 é cerca de 4 vezes mais rápida do que o código portátil compilado com compiladores “otimizadores”
Limites da medição de desempenho da otimização
- Em 2000, Todd A. Proebsting expressou em Proebsting's Law que “o avanço dos compiladores dobra o poder computacional a cada 18 anos”, concluindo que a contribuição da otimização de compiladores é periférica
- Em 2022, Arseny Kapoulkine resumiu em um benchmark que o LLVM 11 leva o dobro do tempo do LLVM 2.7 para compilar com otimização, enquanto o código executável fica em geral 10 a 20% mais rápido
- As duas discussões deixam passar a medição de desempenho realmente percebida pelos usuários
- Os hotspots onde o desempenho se concentra costumam conter muitos intrinsics e assembly
- O FFmpeg tem 160.000 linhas de assembly em arquivos
.asm e .S
- À medida que computadores e redes processam mais dados, mais tempo real de CPU recai sobre esses hotspots
- O custo de segurança também cresce separadamente nas discussões sobre otimização
- A Deloitte informou que, em 2023, o orçamento de segurança de TI foi 0,5% da receita das empresas
- Junto com o dado de que a receita total das empresas no mundo em 2022 foi de mais de 48 trilhões de dólares, a escala total pode chegar à casa das centenas de bilhões de dólares
- Ainda assim, há a ressalva de que os 0,5% da Deloitte podem ser uma média simples por empresa, e nem todas as empresas responderam à pesquisa
Vazamento por timing e o caso Kyber
- Os problemas de segurança criados por compiladores “otimizadores” incluem não só bugs tradicionais, mas também vazamentos por timing em que informação secreta escapa pelo tempo de execução
- O artigo da EuroS&P 2018, de Laurent Simon, David Chisnall e Ross Anderson, alertou que uma atualização de compilador pode abrir silenciosamente canais de timing em código que antes era seguro
- O exemplo destacado no artigo de 2018 era um código que escolhia entre dois valores com
bool, e esse bool induzia o compilador a gerar saltos condicionais
- Em implementações criptográficas, é prática comum evitar isso removendo
bool de trechos importantes e criando funções separadas de comparação em tempo constante
- O OpenSSL é citado como declarando 37 funções para isso
- O caso de 2015 envolvendo
curve25519-donna e MSVC 2015 é tratado no texto como um mal-entendido
- Na prática, ao compilar para x86 de 32 bits, operações
int64 eram convertidas em chamadas para a biblioteca int64 de 32 bits da Microsoft, llmul.asm
- O vazamento por timing era criado por desvios dependentes de dados em
llmul.asm, e essa biblioteca também deve ser considerada parte de um conceito razoável de código-fonte
- Em junho de 2024, Antoon Purnal confirmou que o código de referência do Kyber pode permitir ataques de timing com Clang 15 ou superior e certas opções de otimização
- A forma problemática era
(-((x>>j)&1))&y, um cálculo que produz y se o bit j de x estiver definido, ou 0 caso contrário
- O Clang transforma o bit em
bool usando uma instrução de teste de bit e então gera um desvio condicional com base nesse bool
- Dentro do LLVM, essa “otimização” é tratada por
combineShiftAnd1ToBitTest em lib/CodeGen/SelectionDAG/DAGCombiner.cpp
- Essa função foi adicionada por Sanjay Patel em setembro de 2019 e depois modificada por várias pessoas
- Há casos parecidos de invasão de limites também no GCC
- Um patch do GCC da ARM, de novembro de 2021, transforma
(-x)>>31 em -(x>0)
- Em abril de 2024, surgiu um alerta a respeito disso
TIMECOP e verificação de tempo constante
- O TIMECOP 2 está embutido no framework de testes criptográficos SUPERCOP e verifica automaticamente, em código compilado declarado como constante no tempo, desvios condicionais derivados de valores secretos
- O escopo da verificação inclui, além de desvios condicionais, índices de array derivados de valores secretos
- O artigo KyberSlash também descreve um patch para verificar divisões derivadas de valores secretos
- O TIMECOP 1 foi uma ferramenta criada por Moritz Neikes ao modificar o SUPERCOP, automatizando a abordagem ctgrind de Adam Langley
- O TIMECOP 2 amplia a abordagem anterior em alguns pontos
- Marca automaticamente saídas do RNG como valores secretos
- Dá suporte a “declassification”
- Dá suporte à especificação de “public inputs”
- É executado em vários núcleos
- O TIMECOP tem limitações claras
- Só consegue lidar com instruções suportadas pelo Valgrind, então para em casos como instruções AMD XOP
- Inspeciona apenas o fluxo de dados visível durante a execução real dos testes
- O trabalho com ferramentas de verificação de comportamento em tempo constante continua, e uma lista de ferramentas relacionadas está em ct-tools
- Uma verificação correspondente à do TIMECOP entrou na suíte de testes do libmceliece e pode se espalhar para outras bibliotecas
Abordagem de reescrita para tempo constante
- Depois de encontrar um trecho de código com tempo variável, é preciso uma forma de reescrevê-lo em tempo constante sem introduzir bugs
- Em uma apresentação de julho de 2024, foram mostradas algumas das funções de tempo constante oferecidas por libmceliece e SUPERCOP
- Os nomes de arquivo são
crypto_{int,uint}{8,16,32,64}.h
- Esses arquivos podem ser copiados para uso em outros projetos
- A função de exemplo
crypto_uint32_bitmod_mask(x,j) produz o mesmo efeito de -((x>>(j&31))&1), mas impede que o compilador enxergue o resultado de 1 bit
- Há também exemplos mais complexos, como
crypto_uint32_max(x,y)
- O artigo de 2018 trata de um tweak para adicionar ao Clang/LLVM a função de tempo constante
__builtin_ct_choose(bool cond, x, y)
- O artigo sugeriu, incorretamente, que essa única função seria suficiente
- Essa função pode até entrar no compilador algum dia, mas pode levar muito tempo até que projetos possam depender dela
- A implementação parece mais frágil do que
crypto_{int,uint}{8,16,32,64}.h
Como evitar o problema com antecedência
- Se testes antes da distribuição de uma biblioteca compilada detectarem vazamentos por timing introduzidos pelo compilador, a distribuição pode continuar usando a versão anterior do compilador enquanto o código é reescrito
- Essa abordagem é uma resposta temporária para continuar mantendo os usuários seguros
- Uma solução é distribuir a biblioteca em assembly
- A apresentação da RWC 2024 Adoption of high-assurance and highly performant cryptographic algorithms at AWS mostra um software rápido de X25519 cuja correção para todas as entradas foi provada
- A implementação foi escrita em assembly em 2 versões para CPUs Intel/AMD de 64 bits e 2 versões para CPUs ARM de 64 bits
- A proposição de correção é um teorema sobre o código de máquina realmente executado pelos usuários, e a prova foi verificada com o provador de teoremas HOL Light
- Ainda assim, em software criptográfico que não chega a esse nível, continua existindo o problema da dificuldade de auditoria de assembly
- Também se busca uma forma rápida de aplicar uma “vacina” contra vazamentos por timing em código escrito em C, C++ e afins
Experimento com o patch clang-vs-clang
x&1 e x>>31 têm em comum o fato de que só admitem dois resultados possíveis
x&1 é 0 ou 1x>>31 de uint32 é 0 ou 1x>>31 de int32 é 0 ou -1
- Essas formas facilitam que quem escreve “otimizações” de compilador coloque o resultado de 1 bit em
bool
- Há a recomendação de sempre compilar com
-fwrapv para que GCC e Clang assumam aritmética em complemento de dois
- Em vez de apenas varrer o código-fonte atrás de
&1, 1&, >>31 etc., foi inserido diretamente um patch no “optimizer” do LLVM para fazer a varredura de outro modo
- O patch parte do commit
68df06a0b2998765cb0a41353fcf0919bbf57ddb do LLVM, encontra &1 e >>31 e emite o seguinte aviso
please take this away before clang does something bad
- Um comando de compilação de exemplo é
clang -Rpass-analysis=clang-vs-clang -O -c x.c
- A função de teste é a seguinte
int sra31(int x)
{
x >>= 31;
return x;
}
- Não é surpreendente que o mesmo aviso se repita
- O compilador continua tentando aplicar “otimizações” até que não haja mais progresso
- A saída de
clang-vs-clang distingue signed de unsigned em shifts
- Essa diferença é importante para reescritas manuais ou automáticas com base em
crypto_{int,uint}{8,16,32,64}.h
- Um dos métodos para automatizar a transformação do código-fonte é o
clang-tidy
- Códigos removidos por
#ifdef ou eliminados antes dessa etapa de “otimização” não geram avisos do clang-vs-clang
Resultados de execução do SUPERCOP e casos encontrados
- O SUPERCOP 20240716 foi executado em um dual EPYC 7742 com
./data-do-biglittle
- O overclocking foi desativado
- A lista de compiladores do SUPERCOP foi ajustada para usar
clang-vs-clang, adicionando -Rpass-analysis=clang-vs-clang à linha clang em okcompilers/{c,cpp}
- Os resultados ficaram prontos depois de 3 horas
- A saída do Clang teve 675.752 linhas no total
- O tamanho bruto foi de 210.786.494 bytes
- O resultado comprimido foi
20240803-fromclang.txt.gz, com 3.595.199 bytes
- A saída contém muito ruído vindo de ramificações de código-fonte baseadas em dados públicos que acabam gerando
&1 dentro do Clang
- Um exemplo claro para alteração preventiva é o seguinte
a0 += (a0>>15)&106;
- Um exemplo que exigiria esforço de parsing de C para ser encontrado por simples varredura de código-fonte é o seguinte
- A macro
ONE8 é definida como ((uint8_t)1)
*pk2^=(((* pk_cp)>>ir)&ONE8)<<jr;
- Exemplos ainda mais difíceis aparecem em macros baseadas em intrinsics AVX2
signmask_x16(x) é definido como _mm256_srai_epi16((x),15)- Isso desloca cada pedaço signed de 16 bits dentro de um vetor de 256 bits em 15 bits para a direita
mask = signmask_x16(sub_x16(x,const_x16((q+1)/2)));
- Esse caso com AVX2 não é prioridade alta
- Para que operações vetoriais virem desvios condicionais, seria preciso compilar com AVX-512 e o compilador ainda tomar a decisão estranha de transformar
bool vetorizado em desvios condicionais bool seriais
- O TIMECOP usa Valgrind, e o Valgrind não suporta AVX-512
- Por enquanto, não se recomenda compilação com AVX-512
int128 e uma direção de resposta mais ampla
- A descoberta mais interessante foi um caso em que shift à direita de 64 bits em
int128 gerou um aviso de >>
- A implementação de
int128 pode internamente usar um shift à direita de 63 bits para descobrir o sinal da palavra superior de 64 bits
- Se o Clang adicionar, como o GCC, suporte para transformar shift à direita de 63 bits em
bool e depois em desvio condicional, muito código com int128 pode de repente se tornar de tempo variável
- Nesse caso, a situação se aproximaria da que o título do artigo de 2015 afirmava, mas desta vez ocorreria mesmo sem
bool explícito no código-fonte
- No nível do código-fonte, a proteção mais simples é evitar a implementação atual de
int128 do compilador e usar funções crypto_int128
crypto_int128, ao contrário de int128 do GCC e do Clang, também pode funcionar em plataformas pequenas de 32 bits
- A ideia de adicionar tipos de dados secretos ao GCC e ao Clang parece boa, mas não está claro como torná-la robusta na estrutura dos dois compiladores
- Há mais expectativa em compiladores projetados desde o início para segurança
- Entre os compiladores voltados à segurança que exigem uma nova linguagem de entrada estão FaCT e Jasmin, em desenvolvimento ativo
- Há preocupação com o tempo de reescrita do código, mas, vendo como os compiladores atuais tratam o código existente, algum tipo de ação será necessário
1 comentários
Opiniões no Hacker News
Não faz sentido chamar de bug do compilador quando um código que contém comportamento indefinido não se comporta como desejado.
É parecido com executar
ddcom argumentos errados, perder os dados e depois dizer que oddtem bug.É difícil dizer que o código-fonte ou o compilador têm bug; o mais correto é ver isso como o padrão C sendo pouco especificado demais, pelo critério do autor, o que cria bugs de segurança em alguns alvos.
No fim, os autores do padrão C não conseguem definir até o comportamento do hardware, apenas a semântica da linguagem; portanto, a área de criptografia inevitavelmente sofre com bugs cuja causa está no hardware.
Uma das vantagens do Rust é limitar possíveis comportamentos indefinidos a blocos
unsafe. Ainda assim, mesmo que Rust tenha definido muitas coisas que em C seriam comportamento indefinido, ao entrar em códigounsafeé muito fácil esbarrar sem querer em comportamentos indefinidos sutis.Um terceiro modelo, que falha silenciosamente e gera código imprevisível, só é útil para autores de compiladores. Esconder-se atrás da especificação não traz benefício para usuários reais.
Essa otimização quebra código que antes funcionava bem. Os autores de compiladores poderiam priorizar compatibilidade retroativa, mas não fazem isso.
Além disso, como essas otimizações nem melhoram de forma significativa o desempenho de código real, é preciso refutar o argumento de que esse trade-off de quebrar código não vale a pena.
Gosto do Bernstein, mas às vezes ele mira na direção errada e fica radical; este texto é um bom exemplo. No fim do texto, ele mesmo meio que admite isso.
Uma grande parte do texto é sobre a questão secundária de quão bons são os ganhos de otimização, e mesmo com dados isso seria um julgamento que depende do caso de uso.
A reclamação central é que compiladores C não levam em conta semânticas que não podem ser expressas pela linguagem, o que não deveria surpreender ninguém.
No final, ele diz “use uma linguagem capaz de expressar a semântica necessária”, e o texto inteiro poderia ter sido substituído por essa única frase.
Uma boa parte disso tem justificativa duvidosa e torna mais difícil escrever programas corretos.
C e C++ não são adequados para escrever algoritmos com garantia de tempo constante.
O padrão quase não tem noção de tempo real, e os compiladores também não oferecem garantias adicionais por meio de extensões.
Mas culpar os desenvolvedores do compilador por isso é mirar no lugar errado.
Em CPUs Intel, seja com
clangou qualquer outra coisa, não é possível gerar código correto em modo de usuário. Para começo de conversa, código correto nem existe.https://www.intel.com/content/www/us/en/developer/articles/t...
Olhando o
DOITMno documento, é simplesmente impossível que uma biblioteca criptográfica em espaço de usuário configure os bits necessários.Uma vez ativado, ele funciona bem também no espaço de usuário; portanto, por exemplo, poderia ser uma flag por processo ativada por uma chamada de sistema
prctl, com o escalonador ajustando oMSRdurante a troca de tarefas.Só pela frase “sempre que possível, autores de compiladores se recusam a assumir responsabilidade pelos bugs que criaram”, é raro ver a credibilidade técnica de um post de blog desmoronar tão rapidamente
Seguindo até o link, trata-se apenas de um ponto bem básico de C: comportamento indefinido não significa que ele produza “um valor arbitrário”
Mesmo havendo comportamento indefinido, muitas vezes o código-fonte é bugado, mas o programa gerado ainda está correto. Mais tarde, quando o autor do compilador adiciona uma nova otimização e, com base naquele comportamento indefinido, gera um programa com bug, começa a disputa sobre responsabilidade
O ponto que não se quer admitir é que a responsabilidade perante o usuário é dividida entre todos os lados. Se uma aplicação CRUD dereferenciou
NULLe, só por isso, a bateria pegou fogo, uma pessoa sensata não culparia apenas o autor da aplicação por ter esquecido uma verificação deNULLCompiladores, sistemas operacionais e fabricantes de hardware também precisam se responsabilizar por produtos projetados de forma irresponsável, e a expressão “comportamento indefinido” no padrão ISO não encerra a questão. Todos os integrantes da cadeia de suprimentos compartilham a responsabilidade de prever como o produto pode ser usado indevidamente e de lidar com isso de forma razoável
Comportamento indefinido existe para entregar valor. É possível criar uma linguagem sem esse tipo de coisa; o motivo de ele existir é a portabilidade e a flexibilidade que dá aos autores de compiladores
O ponto central do texto é se essa flexibilidade vale a pena quando comparada à dificuldade de escrever programas sem comportamento indefinido
O autor entende que o dinheiro perdido com bugs parece ser maior do que o dinheiro economizado com bytecode mais rápido, e que, como os autores de compiladores têm muita influência sobre o que entra nos padrões da linguagem, há pouca disposição para corrigir isso
Como referência, o
clangtem o atributoclang::optnone, que desativa todas as otimizações por função, e o GCC tem o excelente atributognu::optimize, que permite adicionar ou remover otimizações por nome, ou definir o nível de otimização independentemente das flags do compiladorgnu::optimize(0)é parecido com aquela flag doclang. Oclangtambém temclang::no_builtins, que desativa especificamente otimizações dememcpyememsetoptimizedeve ser usado apenas para fins de depuração e não é adequado para código de produção”https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
Tenho alguma simpatia pelos objetivos que o pessoal de criptografia quer, como avaliação em tempo constante e ocultação de valores secretos
Mas compiladores de uso geral não pensam nisso na maior parte do tempo, então parece difícil que isso passe de um hack que funciona na maioria dos casos
Para fazer isso a sério, provavelmente seria necessário um compilador especializado próprio, ou continuar indo para assembly
Algum dia, talvez vejamos o presente como os velhos tempos ruins e já tenhamos saído de C para uma linguagem com muito menos comportamento indefinido
Em C, é fácil demais escrever expressões que compilam, mas cuja intenção o compilador simplesmente não tem como saber
Por exemplo, em Python é possível escrever um código como
result = [something(value) for value in set_object]. Como um objetosetnão tem ordem, fica claro que a ordem de processamento dos itens e a ordem do resultado não importam, e isso abre espaço para muitas otimizações no nível da linguagem sem que o compilador precise adivinhar a intenção do autorCódigo semelhante em outras linguagens com dados imutáveis vai um passo além: como
something(value1)não pode afetarsomething(value2), as execuções podem ocorrer em paralelo, seja em threads ou em processosUma parte considerável da otimização dos compiladores C consiste em olhar padrões de código e encontrar formas de acelerar algo que provavelmente era a intenção do autor. Como C, em comparação com linguagens modernas, tem pouca capacidade de expressar intenção, há liberdade para inferir, mas, para entregar um desempenho decente, é preciso fazer esse tipo de dedução
Ainda assim, pode ser uma bênção disfarçada, como o caso em que o telescópio Hubble precisou de óculos. Ao tentar superar limitações, criaram técnicas excelentes e, depois de corrigido o problema, essas técnicas renderam um desempenho muito maior do que se esperava originalmente. Aplicar otimizações de compiladores C a linguagens que não são C talvez funcione como um superpoder
Basicamente é parecido com comportamento indefinido, mas pode aparecer não como um problema imediato de segurança, e sim como um resultado incorreto. Claro que um resultado incorreto pode levar a um problema de segurança mais tarde
Ao contrário do comportamento indefinido, criar um “sanitizador” que verifique se o código funciona para todas as ordens possíveis de um
seté, na prática, impossívelgcceclangtêm muitos hints de baixo nível que frequentemente não existem em outras linguagens. Há__builtin_expect/__builtin_unpredictable,__builtin_unreachable/__builtin_assume,#pragma clang loop vectorize(assume_safety)/#pragma GCC ivdep, pragmas para desligar o desenrolamento de loops ou a vetorização, ou para escolher valores específicos, entre outrosO que acho que mais falta é uma barreira de otimização que impeça explicitamente o compilador de inferir coisas com base na origem dos valores.
__asm__permite isso em certa medida, mas tem efeitos colaterais indesejados e exige nomes de tipos de registradores específicos de plataformaO potencial de otimizações de alto nível baseadas em intenção também é claro. Penso em coisas como reservar espaço em uma lista dinâmica antes de fazer
pushnvezes em um loop, fundir buscas em hashmap do tipocontains→get→putcom a mesma chave, ou inferir localmente o comportamento de alocação global para eliminar objetos e alocaçõesC fica suficientemente perto do hardware real para que o programador possa simplesmente dizer o que fazer, então o compilador não precisa adivinhar a intenção do programador
As linguagens que implementam esse tipo de otimização de memória costumam ser do tipo Java e, para começo de conversa, têm uma pessimizacão preventiva agressiva, o que cria motivação para fazer essas otimizações. Mesmo assim, essas otimizações não compensam a perda
O ponto é que C também não é grande coisa, mas o outro lado é pior
Se você não gosta da semântica de C, não fique com raiva dos engenheiros de compiladores; use outra linguagem de programação
qhasm. Até mesmo Zig. Essa avaliação vinda dele não é tão surpreendenteÉ um texto interessante, que traz um ponto de vista pouco ouvido. Também vale conferir: https://gavinhoward.com/2023/08/the-scourge-of-00ub/