Partial Number Theoretic Transform Masking in Post-Quantum Cryptography (PQC) Hardware: A Security Margin Analysis

Título: Análise de Margem de Segurança em Mascaramento Parcial de Transformada Numérica Teórica (NTT) em Hardware de Criptografia Pós-Quântica (PQC)

1. O Problema

Com a padronização dos algoritmos de criptografia pós-quântica ML-KEM (FIPS 203) e ML-DSA (FIPS 204) em 2024, a segurança de canais laterais de aceleradores de hardware tornou-se uma preocupação crítica. A Transformada Numérica Teórica (NTT) é a operação central nestes algoritmos, mas o mascaramento completo de todas as suas camadas em hardware impõe um custo de área de silício proibitivo.

Como resposta, projetistas adotaram estratégias de mascaramento parcial. O exemplo analisado é o Adams Bridge, um acelerador de hardware para a raiz de confiança Caliptra. O design protege apenas a primeira camada da Transformada Numérica Inversa (INTT) e multiplicações ponto a ponto com mascaramento booleano de primeira ordem, dependendo de embaralhamento (shuffling) e argumentos de espaço de busca para proteger as camadas restantes. Os autores do design afirmam que essa abordagem oferece margens de segurança extremamente altas (complexidade de ataque de $2^{88}$ para ML-DSA e $2^{132}$ para ML-KEM), tornando a exploração "inteiramente impraticável".

O problema central deste artigo é avaliar se essas alegações de segurança resistem a uma análise rigorosa baseada na literatura de canais laterais e em validações empíricas, especialmente considerando que a maior parte da computação (85-87%) permanece desprotegida por mascaramento.

2. Metodologia

Os autores empregaram uma abordagem híbrida combinando análise teórica, verificação formal e validação empírica baseada em simulação de RTL (Register-Transfer Level):

• Análise de Evidências Estruturada: Revisão de mais de 30 artigos publicados, classificando cada afirmação com um nível de confiança epistêmica (Proven, Literature-Supported, Extrapolation, Speculative) e origem (Software/Hardware).
• Verificação RTL: Análise do código-fonte RTL publicamente disponível do Adams Bridge para verificar a implementação real do mecanismo de embaralhamento (Random Start Index - RSI).
• Pipeline de Ataque SASCA (Soft Analytical Side-Channel Attack): Desenvolvimento de um pipeline de ataque que utiliza:
  • Extração de vazamento de sinal (SNR) via simulação RTL.
  • Construção de grafos de fatores (Factor Graphs) da estrutura NTT.
  • Aplicação de Propagação de Crença (Belief Propagation - BP) para explorar dependências algébricas entre as camadas.
  • Análise de sensibilidade de retículos (Lattice) para recuperação de chaves.
• Ablação de Camadas: Experimentos exaustivos (500+ tentativas) variando quais camadas são observadas para determinar as condições necessárias para a convergência do BP.
• Verificação Formal: Uso de solucionadores SMT (Z3 e CVC5) para verificar matematicamente as fundações algébricas das alegações de segurança.

3. Principais Contribuições

1. Desmistificação do Embaralhamento RSI: A análise do RTL confirmou que o Adams Bridge utiliza um esquema de Random Start Index (RSI) com hierarquia de dois níveis, gerando apenas 6 bits de entropia por camada (64 ordenações possíveis), em vez da permutação aleatória completa ($64! \approx 2^{296}$ ordenações) assumida nos argumentos de segurança dos projetistas.
2. Redução do Espaço de Busca Algébrico: Demonstrou-se que a estrutura da borboleta Gentleman-Sande (GS) na INTT impõe restrições algébricas que reduzem os graus de liberdade independentes, diminuindo o espaço de busca por borboleta de $2^{46}$ (ML-DSA) e $2^{96}$ (ML-KEM) para valores significativamente menores.
3. Metodologia de Auditoria de Margem de Segurança: Proposição de um framework reutilizável que combina verificação RTL, proveniência de evidências (SW/HW) e cenários de sensibilidade para avaliar qualquer acelerador NTT parcialmente mascarado.
4. Validação Empírica de Propagação de Crença (BP): Primeira validação em escala completa (7 camadas, 256 coeficientes) de que o BP pode recuperar 100% dos coeficientes secretos em grafos de fatores NTT, superando limitações de análises anteriores em subgrafos menores.
5. Hierarquia de Contra-medidas: Identificação de que o mascaramento da camada de entrada (L1) cria uma barreira estrutural intransponível, enquanto o mascaramento de "lacunas estratégicas" (3 camadas consecutivas do meio) oferece proteção baseada em custo de traço.

4. Resultados Chave

• Gap de Margem de Segurança: Sob as suposições mais fortes favoráveis à defesa (cenário B), as margens de segurança efetivas caem para:
  • ML-DSA: $2^{59} - 2^{63}$ (uma redução de $2^{25}$ a $2^{29}$ em relação à estimativa dos projetistas de $\approx 2^{88}$).
  • ML-KEM: $2^{61} - 2^{65}$ (uma redução de $2^{67}$ a $2^{71}$ em relação à estimativa de $\approx 2^{132}$).
  • Nota: Em cenários mais agressivos (favoráveis ao atacante), as margens podem cair para $2^{15}-2^{27}$.
• Gap de 37 Bits (Ataque Modelo): O pipeline de ataque SASCA demonstrou uma redução de 37 bits na complexidade de enumeração (de $2^{46}$ para $2^9$) independentemente do ganho do BP. Isso ocorre porque o ataque SASCA elimina a enumeração por coeficiente, substituindo-a pela enumeração das ordenações de embaralhamento (RSI), que é trivialmente enumerável (512 execuções).
• Eficácia do Embaralhamento RSI: O RSI é muito mais fraco que uma permutação aleatória completa. Com viés de posição moderado, o custo de ataque cai drasticamente, tornando o embaralhamento quase ineficaz contra ataques de canal lateral perfilados.
• Convergência do BP e Topologia: A recuperação de chaves via BP depende da topologia das camadas observadas, não apenas do número de camadas.
  • Barreira Estrutural (NC1): Se a camada de entrada (L1) não for observada, a informação é estruturalmente desconectada (MI $\approx$ 0), tornando a recuperação impossível independentemente do número de traços.
  • Lacunas Estratégicas: Observar camadas espaçadas uniformemente (ex: L1, L3, L5, L7) é muito mais eficiente do que camadas consecutivas.
• Recuperação Total: Em simulações perfiladas com ruído Gaussiano, o BP alcançou 100% de recuperação de coeficientes para ML-KEM com $SNR \times N = 3.000$, confirmando que a informação necessária está presente nos traços e pode ser extraída.

5. Significado e Implicações

• Risco de Subinvestimento: A análise revela que a estratégia de mascaramento parcial do Adams Bridge, baseada em argumentos de espaço de busca e embaralhamento RSI, oferece uma margem de segurança significativamente menor do que o projetado. Para uma raiz de confiança de silício com ciclo de vida de décadas, essa erosão de margem é crítica.
• Embaralhamento não é Substituição: O estudo reforça que o embaralhamento deve ser um complemento ao mascaramento, não um substituto. A dependência exclusiva de embaralhamento em 87% da computação da INTT cria uma superfície de ataque vulnerável a ataques algébricos (SASCA).
• Recomendações de Design:
  1. Mascaramento Prioritário da Camada L1: É a medida mais eficaz, criando uma barreira estrutural que nenhum aumento no número de traços pode superar.
  2. Mascaramento de Lacuna Estratégica: Mascarar 3 camadas consecutivas do meio (ex: L3-L5) cria uma lacuna de observação que derrota ataques de BP em orçamentos de traço moderados, oferecendo uma solução intermediária de custo (43% do custo do mascaramento total).
  3. Validação Empírica Necessária: A comunidade precisa realizar ataques SASCA em hardware real (FPGA) para confirmar se as margens de simulação RTL se mantêm no silício físico, considerando ruídos e filtragem de energia.

Conclusão: O artigo não afirma que o Adams Bridge é inseguro em todos os cenários de implantação, mas demonstra que as alegações de segurança dos projetistas são otimistas e não suportadas pela literatura atual de canais laterais. A estratégia atual depende de suposições não comprovadas sobre o poder do embaralhamento RSI e a independência das camadas, criando um risco real de subproteção para infraestruturas críticas.