Fundamentos da criptoanálise diferencial

A criptoanálise diferencial (Biham e Shamir, 1990) é um ataque de texto claro escolhido que analisa como as diferenças em pares de textos claros se propagam por uma cifra. Ao encontrar diferenças de entrada que produzem diferenças de saída previsíveis com alta probabilidade, o atacante recupera bits da chave estatisticamente.

Para cifras baseadas em XOR: diferença ΔX = X XOR X'. Para cifras baseadas em adição: diferença ΔX = X - X' mod 2^n. As diferenças por XOR são mais comuns, pois o XOR com a chave comuta com a operação XOR (os efeitos do escalonamento da chave se cancelam nos pares diferenciais).

Um par diferencial (P, P') tem diferença de entrada ΔP = P XOR P'. Após a criptografia: (C, C'), com diferença de saída ΔC = C XOR C'. Um diferencial útil é ΔP → ΔC com alta probabilidade p, o que significa que muitos pares (P, P') com diferença ΔP produzem a diferença de saída ΔC.

A DDT (Tabela de Distribuição Diferencial) contabiliza, para cada diferença de entrada Δx e diferença de saída Δy, quantas entradas x satisfazem S(x) XOR S(x XOR Δx) = Δy. Dividindo por 2^n, obtém-se a probabilidade. Uma S-box boa tem valor máximo da DDT igual a 2 (probabilidade 1/2^{n-1}), sem diferenciais fortes.

Para uma cifra de bloco com r rodadas: encontre uma sequência ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}, na qual cada transição de rodada tenha uma probabilidade conhecida. Multiplique as probabilidades entre as rodadas: a probabilidade total é p = p1 * p2 * ... * p_{r-1}. O ataque usa 2/p pares para recuperar a chave da última rodada.

Com um diferencial de r-1 rodadas de alta probabilidade: colete N = 2/p pares de textos claros. Para cada candidata a chave da última rodada K': descriptografe ambos os textos cifrados em uma rodada, aplique XOR aos resultados e verifique se a diferença corresponde a ΔU_{r-1}. A K' correta corresponde a aproximadamente N/2 casos; as chaves incorretas, a aproximadamente N/2^{bit_size} casos.

A S-box do AES é o inverso multiplicativo sobre GF(2^8), seguido de uma transformação afim. O valor máximo da sua DDT é 4 (de 256), resultando em uma probabilidade diferencial ≤ 4/256 = 1/64 por S-box. O AES tem 4 S-boxes por rodada, mas o projeto Wide Trail garante que as trilhas diferenciais completas fiquem abaixo de 2^{-100}.

O projeto Wide Trail de Joan Daemen (usado no AES/Rijndael): defina o número de ramificação B de MixColumns. Qualquer trilha diferencial não trivial ao longo de uma rodada ativa ≥ B S-boxes. 4 rodadas × 4 S-boxes por rodada garantem ≥ 25 S-boxes ativas → probabilidade < 2^{-100}.

Os diferenciais truncados especificam apenas parte da diferença (por exemplo, quais colunas estão ativas, mas não os valores exatos das diferenças). Isso permite ataques a mais rodadas, nas quais os diferenciais completos são fracos demais. São usados contra o AES com número reduzido de rodadas, SERPENT e outras cifras SPN.

Um diferencial impossível é um par (ΔP, ΔC) que nunca pode ocorrer para nenhuma chave. Qualquer chave que associe um par observado (P, P') a essa diferença é eliminada. Ao coletar pares suficientes, todas as chaves incorretas são eliminadas, restando a chave correta.

O ataque bumerangue (Wagner, 1999) combina dois diferenciais curtos em um ataque adaptativo de texto claro/texto cifrado escolhido. Ele divide a cifra em duas metades, cada uma com um diferencial curto de alta probabilidade, permitindo atacar mais rodadas do que qualquer diferencial isolado permitiria.

Qual é a finalidade da Tabela de Distribuição Diferencial (DDT) na criptoanálise?

A criptoanálise diferencial explora a propagação de diferenças de entrada→saída com alta probabilidade. O AES resiste a ela por meio de sua S-box otimizada para a DDT e do projeto Wide Trail. Próximo: criptoanálise linear e tabelas de aproximação.