Analyzing Linear Layers in Related-Differential Cryptanalysis

Resumo Técnico: Análise de Camadas Lineares em Criptanálise Diferencial Relacionada

Declaração do Problema
Em cifras de bloco baseadas em SPN (ex.: AES), a camada de difusão linear é tipicamente implementada usando matrizes de Distância Máxima Separável (MDS) para garantir números de ramo ótimos e resistência contra criptanálise diferencial e linear clássica. No entanto, trabalhos recentes de Daemen e Rijmen (2009) e Bardeh e Rijmen (2022) revelaram que matrizes MDS podem ainda exibir estruturas "diferenciais relacionadas". Essas estruturas permitem a construção de características diferenciais relacionadas que podem ser exploradas em ataques, como o ataque de recuperação de chave de 7 rodadas no AES-128. Embora estudos anteriores tenham identificado diferenciais relacionados em instâncias específicas (ex.: matrizes circulares 4×4, matrizes involutórias 3×3), uma compreensão sistemática de quais estruturas de camada linear evitam ou admitem inerentemente esses diferenciais permanece incompleta. Este artigo investiga as condições sob as quais camadas lineares sobre corpos finitos evitam diferenciais relacionados, visando identificar classes de matrizes que são inerentemente resistentes a este vetor específico de criptanálise.

Metodologia
Os autores empregam uma abordagem algébrica teórica sobre corpos finitos de característica 2 ($\mathbb{F}_{2^m}$). A metodologia envolve:

1. Definição de Diferenciais Relacionados: Utilizando as definições de Daemen e Rijmen, onde dois diferenciais $(u, Mu)$e$(v, Mv)$ são "relacionados" se o par de entrada $(u, v)$ e o par de saída $(Mu, Mv)$ satisfazem a condição $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ para todas as coordenadas.
2. Análise Estrutural: Investigando a relação entre propriedades da matriz (status MDS, simetria, estrutura circular) e a existência de pares diferenciais relacionados não triviais.
3. Decomposição Polinomial: Para matrizes circulares, os autores mapeiam as operações da matriz para multiplicação polinomial no anel quociente $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$. Eles decompõem o polinômio de transformação com base na aritmética modular dos expoentes (módulo 2, 3 e 4) para construir pares específicos de diferenças de entrada que produzem diferenças de saída relacionadas.
4. Enumeração Caso a Caso: Para o caso $3 \times 3$, os autores utilizam a decomposição de qualquer matriz MDS em uma forma representativa $M = D_1 M_1 D_2$ (onde $D_i$ são diagonais e $M_1$ é um representante específico). Eles analisam sistematicamente todos os padrões possíveis de peso de Hamming de tripletos de diferença de entrada $(u, v, u \oplus v)$ para derivar condições algébricas necessárias e suficientes para a ausência de diferenciais relacionados.

Principais Contribuições e Resultados

1. Necessidade da Propriedade MDS:
   O artigo prova que a propriedade MDS é uma condição necessária para evitar diferenciais relacionados. Especificamente, o Teorema 2 demonstra que toda matriz não-MDS admite pelo menos um par não trivial de diferenciais relacionados. Isso restringe o espaço de busca para camadas lineares resistentes estritamente à classe de matrizes MDS.

2. Vulnerabilidade de Matrizes Simétricas:
   Os autores estabelecem que a simetria em dimensões ímpares é uma vulnerabilidade inerente. O Teorema 4 prova que toda matriz MDS simétrica de ordem ímpar admite diferenciais relacionados. Este resultado exclui amplas famílias de construções, incluindo matrizes MDS baseadas em Cauchy do Tipo 2 e matrizes circulares à esquerda de ordem ímpar (Corolários 2 e 3), pois são inerentemente simétricas e, portanto, vulneráveis.

3. Vulnerabilidade de Matrizes Circulares:
   O artigo fornece uma caracterização abrangente para matrizes circulares. Ao analisar as propriedades modulares da ordem da matriz $n$, os autores provam no Teorema 5 que uma matriz MDS circular de ordem $n$ admite diferenciais relacionados sempre que $n \not\equiv \pm 2 \pmod{12}$. Isso generaliza descobertas anteriores para os casos $3 \times 3$ e $4 \times 4$, identificando uma ampla classe de ordens vulneráveis.

4. Caracterização Completa de Matrizes $3 \times 3$:
   Revisitando o caso $3 \times 3$, os autores derivam uma caracterização algébrica completa. O Teorema 7 fornece um conjunto explícito de 15 restrições polinomiais necessárias e suficientes sobre os parâmetros de uma matriz MDS representativa $3 \times 3$. Se qualquer uma dessas 15 condições for atendida, a matriz admite diferenciais relacionados; se nenhuma for atendida, a matriz é resistente.

   • O artigo observa que caracterizações anteriores (ex.: por Otal et al.) estavam incompletas.
   • Usando esta caracterização, os autores calculam o número exato de matrizes MDS $3 \times 3$ sobre vários corpos finitos ($\mathbb{F}_{2^m}$) que não possuem diferenciais relacionados, demonstrando que o conjunto de matrizes resistentes é um subconjunto estrito de todas as matrizes MDS (Tabela I).

Significado e Alegações
O artigo alega fornecer uma investigação sistemática dos pré-requisitos estruturais para resistir à criptanálise diferencial relacionada. Seu significado principal reside em:

• Estabelecer Limites: Provar que a propriedade MDS por si só é insuficiente para resistência e que propriedades estruturais específicas (simetria de ordem ímpar, ordens circulares específicas) garantem vulnerabilidade.
• Refinar Critérios de Projeto: Oferecer um conjunto concreto e verificável de 15 restrições algébricas para matrizes $3 \times 3$, permitindo que projetistas verifiquem exaustivamente ou construam matrizes resistentes nesta dimensão.
• Orientar Construção Futura: Ao identificar que matrizes não-MDS são inerentemente vulneráveis e que muitas construções simétricas comuns falham, o trabalho direciona pesquisas futuras para a construção de matrizes MDS que sejam tanto assimétricas (ou simétricas de ordem par) quanto satisfaçam as restrições algébricas específicas derivadas para resistência.

Os autores concluem que, embora o caso $3 \times 3$ esteja totalmente caracterizado, estender esses resultados para matrizes $4 \times 4$ e construir matrizes MDS leves e eficientes sem diferenciais relacionados permanecem desafios abertos. Eles também notam que os casos não resolvidos para matrizes circulares (onde $n \equiv \pm 2 \pmod{12}$) apresentam uma conjectura para futura prova.