Criptoanálise diferencial

Criptoanálise diferencial é uma forma geral de criptoanálise aplicável principalmente a cifras de bloco, mas também a cifras de fluxo e funções hash criptográficas. No sentido mais amplo, é o estudo de como as diferenças na entrada de informações podem afetar a diferença resultante na saída. No caso de uma cifra de bloco, refere-se a um conjunto de técnicas para rastrear diferenças através da rede de transformação, descobrindo onde a cifra apresenta comportamento não aleatório e explorando tais propriedades para recuperar a chave secreta (chave criptográfica).

História

A descoberta da criptoanálise diferencial é geralmente atribuída a Eli Biham e Adi Shamir no final dos anos 80, que publicaram uma série de ataques contra várias cifras de bloco e funções de hash, incluindo uma fraqueza teórica no Data Encryption Standard (DES). Foi observado por Biham e Shamir que o DES era surpreendentemente resistente à criptoanálise diferencial, mas pequenas modificações no algoritmo o tornariam muito mais suscetível.

Em 1994, um membro da equipe original do IBM DES, Don Coppersmith, publicou um artigo afirmando que a criptoanálise diferencial era conhecida pela IBM já em 1974 e que a defesa contra a criptoanálise diferencial era um objetivo do projeto. De acordo com o autor Steven Levy, a IBM descobriu a criptoanálise diferencial por conta própria, e a NSA aparentemente estava bem ciente da técnica. A IBM manteve alguns segredos, como explica Coppersmith: “Após discussões com a NSA, foi decidido que a divulgação das considerações do projeto revelaria a técnica de criptoanálise diferencial, uma técnica poderosa que poderia ser usada contra muitas cifras. Isso, por sua vez, enfraqueceria a vantagem competitiva dos Estados Unidos sobre outros países no campo da criptografia." Dentro da IBM, a criptoanálise diferencial era conhecida como o "T-ataque" ou "Ataque de cócegas".

Embora o DES tenha sido projetado tendo em mente a resistência à criptoanálise diferencial, outras cifras contemporâneas provaram ser vulneráveis. Um dos primeiros alvos do ataque foi a cifra de bloco FEAL. A versão original proposta com quatro rodadas (FEAL-4) pode ser quebrada usando apenas oito textos simples escolhidos, e mesmo uma versão de 31 rodadas de FEAL é suscetível ao ataque. Em contraste, o esquema pode criptoanalisar o DES com um esforço da ordem de 2⁴⁷ textos claros escolhidos.

Mecânica de ataque

A criptoanálise diferencial é geralmente um ataque de texto simples escolhido, o que significa que o atacante deve ser capaz de obter cifratextos para algum conjunto de textos claros de sua escolha. Há, no entanto, extensões que permitiriam um texto simples conhecido ou até mesmo um ataque apenas cifrado. O método básico usa pares de texto simples relacionados por uma constante diferença. A diferença pode ser definida de várias maneiras, mas a operação eXclusive OR (XOR) é habitual. O atacante então computa as diferenças dos cifratextos correspondentes, esperando detectar padrões estatísticos em sua distribuição. O par resultante de diferenças é chamado de um diferencial. Suas propriedades estatísticas dependem da natureza das caixas S usadas para criptografia, de modo que o atacante analisa diferenciais (? ? x,? ? Sim.)(Delta _{x},Delta _{y})} Onde?

? ? Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =S(x⊕ ⊕ ? ? x)⊕ ⊕ S(x)Não. Delta _{y}=S(xoplus Delta _{x})oplus S(x)}

Na forma mais básica de recuperação de chave por meio de criptoanálise diferencial, um invasor solicita os textos cifrados para um grande número de pares de texto simples e assume que o diferencial é válido por pelo menos r − 1 rodadas, onde r é o número total de rodadas. O atacante então deduz quais chaves de rodada (para a rodada final) são possíveis, assumindo que a diferença entre os blocos antes da rodada final é corrigida. Quando as chaves redondas são curtas, isso pode ser obtido simplesmente descriptografando exaustivamente os pares de texto cifrado uma rodada com cada chave redonda possível. Quando uma chave de rodada foi considerada uma chave de rodada potencial consideravelmente mais frequentemente do que qualquer outra chave, ela é considerada a chave de rodada correta.

Para qualquer cifra em particular, a diferença de entrada deve ser cuidadosamente selecionada para que o ataque seja bem-sucedido. Uma análise interna do algoritmo é realizada; o método padrão é traçar um caminho de diferenças altamente prováveis através dos vários estágios de criptografia, denominado característica diferencial.

Desde que a criptoanálise diferencial se tornou de conhecimento público, ela se tornou uma preocupação básica dos projetistas de cifras. Espera-se que novos projetos sejam acompanhados de evidências de que o algoritmo é resistente a esse ataque e muitos, incluindo o Padrão de Criptografia Avançada, provaram ser seguros contra o ataque.

Ataque em detalhe

O ataque se baseia principalmente no fato de que um determinado padrão de diferença de entrada/saída ocorre apenas para determinados valores de entradas. Normalmente o ataque é aplicado essencialmente aos componentes não lineares como se fossem um componente sólido (geralmente são na verdade tabelas de consulta ou S-boxes). Observando a diferença de saída desejada (entre duas entradas de texto simples escolhidas ou conhecidas) sugere possíveis valores de chave.

Por exemplo, se um diferencial de 1 => 1 (implicando uma diferença no bit menos significativo (LSB) da entrada leva a uma diferença de saída no LSB) ocorre com probabilidade de 4/256 (possível com a função não linear na cifra AES, por exemplo) então por apenas 4 valores (ou 2 pares) de entradas é esse diferencial possível. Suponha que temos uma função não linear onde a chave é XOR'ed antes da avaliação e os valores que permitem o diferencial são {2,3} e {4,5}. Se o invasor enviar os valores de {6, 7} e observar a diferença de saída correta, isso significa que a chave é 6 ⊕ K = 2 ou 6 ⊕ K = 4, significando que a chave K é 2 ou 4.

Em essência, para uma função não linear de n bits, seria ideal buscar o mais próximo possível de 2^{−(n − 1)} para alcançar uniformidade diferencial. Quando isso acontece, o ataque diferencial requer tanto trabalho para determinar a chave quanto simplesmente forçar a chave bruta.

A função não linear AES tem uma probabilidade diferencial máxima de 4/256 (a maioria das entradas, no entanto, são 0 ou 2). O que significa que, em teoria, pode-se determinar a chave com metade do trabalho da força bruta, no entanto, o ramo alto do AES impede que qualquer trilha de alta probabilidade exista em várias rodadas. Na verdade, a cifra AES seria igualmente imune a ataques diferenciais e lineares com uma função não linear muito mais fraca. A ramificação incrivelmente alta (contagem de S-box ativa) de 25 sobre 4R significa que em 8 rodadas nenhum ataque envolve menos de 50 transformações não lineares, o que significa que a probabilidade de sucesso não excede Pr[ataque] ≤ Pr[melhor ataque em S-box]⁵⁰. Por exemplo, com o atual S-box AES não emite nenhum diferencial fixo com uma probabilidade maior que (4/256)⁵⁰ ou 2⁻³⁰⁰ que é muito menor que o necessário limite de 2⁻¹²⁸ para uma cifra de bloco de 128 bits. Isso teria permitido espaço para um S-box mais eficiente, mesmo que fosse 16 uniforme, a probabilidade de ataque ainda seria de 2⁻²⁰⁰.

Não existem bijeções para entradas/saídas de tamanho uniforme com uniformidade 2. Eles existem em campos ímpares (como GF(2⁷)) usando cubagem ou inversão (existem outros expoentes que também podem ser usados). Por exemplo, S(x) = x³ em qualquer campo binário ímpar é imune à criptoanálise diferencial e linear. Isso é em parte porque os projetos MISTY usam funções de 7 e 9 bits na função não linear de 16 bits. O que essas funções ganham em imunidade a ataques diferenciais e lineares, elas perdem para ataques algébricos. Ou seja, eles são possíveis de descrever e resolver por meio de um solucionador SAT. Isso é em parte porque o AES (por exemplo) tem um mapeamento afim após a inversão.

Tipos especializados

• Cripanálise diferencial de ordem superior
• Criptoanálise diferencial truncada
• Criptoanálise diferencial impossível
• Ataque de Boomeran