Criptoanálise linear e tabelas de aproximação

A criptoanálise linear (Matsui, 1993) é um ataque de texto claro conhecido que encontra aproximações lineares (XOR de bits específicos) de uma cifra que se mantêm com probabilidade p ≠ 1/2. Usando muitos pares de texto claro e texto cifrado, o viés estatístico revela bits da chave.

Uma aproximação linear para uma S-box: a soma de bits de entrada selecionados XOR a soma de bits de saída selecionados = 0 (mod 2) com probabilidade p. É expressa como: P[a·x XOR b·y = 0] = 1/2 + ε, em que a,b são máscaras de bits e ε é o viés (|ε| >> 0 é desejável).

A LAT contabiliza, para cada máscara de entrada a e máscara de saída b, o número de entradas x em que (a·x) XOR (b·S(x)) = 0. Subtraia 2^{n-1} para obter o viés. Uma S-box boa tem |max_bias| = 1 (probabilidade 1/2 ± 1/2^{n/2}), sendo o mais uniforme possível.

Para aproximações lineares independentes em várias rodadas, os vieses se multiplicam: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Cada aproximação de rodada reduz pela metade o viés efetivo. Após muitas rodadas, o viés total se aproxima de 0, exigindo exponencialmente mais pares para ser detectado.

Para atacar uma cifra de r rodadas: encontre uma trilha linear ε ao longo de r-1 rodadas. Colete N = 1/ε^2 textos claros conhecidos. Para cada byte candidato da chave da última rodada k': faça a descriptografia parcial da última rodada por XOR e verifique se a aproximação linear se mantém mais de N/2 vezes. A k' correta apresenta o viés correto.

Matsui atacou o DES de 16 rodadas em 1993 usando uma aproximação linear de 14 rodadas com viés 2^{-21.4}. Foram necessários 2^{43} textos claros conhecidos. Recuperou 26 bits da chave na fase 1; os 30 restantes foram encontrados por busca exaustiva. Foi o primeiro ataque prático mais rápido que a força bruta contra o DES completo.

A S-box do AES tem entrada máxima da LAT |ε| = 4/256 = 1/64 por S-box. A Estratégia Wide Trail limita a quantidade de S-boxes ativas em qualquer trilha de 4 rodadas a ≥ 25. O viés total é ≤ (1/64)^{25/2} ≈ 2^{-75}. São necessários 2^{150} textos claros conhecidos, o que é inviável.

Diferencial: pares de textos claros conhecidos/escolhidos; explora diferenças de saída. Linear: textos claros conhecidos; explora aproximações lineares estatísticas. Ambos são ataques de texto claro escolhido na prática. Ambos são critérios de projeto: as S-boxes precisam resistir aos dois (máximo baixo da DDT E máximo baixo da LAT).

Use várias aproximações lineares simultaneamente para reduzir a complexidade dos dados. Nyberg e Leander ampliaram o método de Matsui: combinar M aproximações reduz a quantidade de dados por um fator log(M). Aplicado ao PRESENT, SIMON e outras cifras leves.

Aproximação linear aplicada a cifras de fluxo: encontre a correlação entre o fluxo de chave e uma função linear da saída do LFSR. Essa correlação, se diferente de zero, permite recuperar a chave mais rapidamente que por busca exaustiva. Ela inspirou o projeto de funções de combinação não lineares em cifras de fluxo.

A criptoanálise integral (Knudsen-Wagner): escolha um conjunto de textos claros em que determinados bytes assumam todos os 256 valores, enquanto os demais permaneçam fixos. Após várias rodadas, o XOR de todas as saídas em determinadas posições é 0 (balanceado). Explora a estrutura do AES e quebra o AES com número reduzido de rodadas de forma eficiente.

O que o lema da acumulação afirma sobre a combinação de aproximações lineares?

A criptoanálise linear encontra aproximações lineares com viés nas S-boxes. O AES resiste por meio de sua S-box otimizada para a LAT e da Estratégia Wide Trail. Matsui quebrou o DES com 2^43 textos claros conhecidos usando uma trilha de 14 rodadas. Próximo: ataques de aniversário e descoberta de colisões.