Detalhes

Categoria: Criptoanálise

Atualização: Domingo, 14 Junho 2009 17:18

Autor: vovó Vicki

Acessos: 10934

Em 1990, Eli Biham e Adi Shamir introduziram a noção da criptoanálise diferencial, um método totalmente novo. Usando esta técnica, os autores encontraram um ataque de texto claro escolhido (chosen-plaintext) contra o DES, mais eficiente do que o da força bruta.

A criptoanálise diferencial procura por pares de texto claro e pares de texto cifrado, ou seja, o ataque examina pares de texto cifrado cujos pares de texto claro correspondentes apresentem determinadas diferenças. Os dois textos claros podem ser escolhidos ao acaso, mas precisam satisfazer determinadas condições, apesar do criptoanalista não precisar conhecer seus valores.

Certas diferenças nos pares de texto claro têm uma grande probabilidade de reaparecerem nos pares do texto cifrado resultante. Estas diferenças são chamadas de características. Por exemplo, se a diferença entre dois textos claros for 0080 8200 6000 000 (em hexadecimal), então após três rodadas, ignorando a permutação inicial do DES, a probabilidade desta diferença aparecer nos dois textos cifrados resultantes continuar sendo 0080 8200 6000 000 é de (1/16)² ou 5%.

Três etapas de características do DES com probabilidade de 0.05

A criptoanálise diferencial usa estas características para atribuir probabilidades a chaves possíveis e, eventualmente, localizar a chave mais provável, mas é preciso ressaltar que o método usa um ataque estatístico e pode falhar em algumas raras ocasiões.

Este ataque funciona no DES e em outros algoritmos semelhantes com caixas S (S-boxes) constantes porque depende essencialmente da estrutura das caixas S. Acontece que as caixas S do DES foram otimizadas para resistir à criptoanálise diferencial. Os detalhes matemáticos desta abordagem vão além da proposta deste texto, mas podem ser encontrados nos trabalhos:

• E. Biham e A. Shamir, "Differential Cryptanalysis of DES-like Cryptosystems" Advances in Cryptology - CRYPTO '90 Proceedings, Berlim: Springer-Verlag, 1991, pp. 2-21
• E. Biham e A. Shamir, "Differential Cryptanalysis of DES-like Cryptosystems" Journal of Cryptology, v.4, n.1, 1991, pp. 3-72
• E. Biham e A. Shamir, "Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI, and Lucifer" Advances in Cryptology - CRYPTO '91 Proceedings, Berlim: Springer-Verlag, 1992, pp. 156-171
• E. Biham e A. Shamir, "Differential Cryptanalysis of the Full 16-Round DES" Advances in Cryptology - CRYPTO '92 Proceedings, Berlim: Springer-Verlag, 1993

Os resultados são mais do que interessantes. A tabela a seguir apresenta um resumo do ataque contra o DES com diversas rodadas:

O texto conhecido funciona com o DES em qualquer um dos seus modos de operação - ECB, CBC, CFB e OFB - com a mesma complexidade.

O DES pode ser melhorado aumentando-se o número de interações. A criptoanálise diferencial (com texto claro escolhido) do DES com 17 ou 18 etapas demora praticamente o mesmo tempo que o de uma procura exaustiva. Com 19 etapas, a procura exaustiva é mais rápida do que a criptoanálise diferencial.

Observações finais

Existem algumas aspectos que precisam ser destacados. O primeiro é que este ataque é principalmente teórico porque o tempo enorme e a quantidade de dados necessária para montar um ataque torna-o inacessível para a maioria das pessoas. Só para se ter uma idéia, para obter os dados necessários para o ataque gasta-se cerca de 3 anos para cifrar um fluxo de dados a 1.5 Mbits/segundo de texto claro escolhido. Em segundo lugar, este é um ataque com texto claro escolhido. A criptoanálise diferencial também funciona como um ataque a um texto claro conhecido, mas é preciso "escarafunchar" todos os pares de texto claro/texto cifrado até encontrar os que possam ser usados.

Para o DES com 16 etapas completas, este tipo de ataque é ligeiramente menos eficiente do que o da força bruta (o ataque da criptoanálise diferencial precisa de 2^55.1 operações enquanto a força bruta precisa de 2⁵⁵ operações). O consenso é que, quando implementado adequadamente, o DES resiste a uma criptoanálise diferencial. E aí surgem as perguntas: Porque o DES é tão resistente à criptoanálise diferencial? Porque as caixas S foram otimizadas para dificultar ao máximo este ataque? Porque existem apenas as etapas necessárias e não mais do que isto? A resposta é: porque os projetistas do DES já conheciam a criptoanálise diferencial. Don Coppersmith, da IBM, disse o seguinte num newsgroup da IBM:

Nós [o grupo IBM] já conhecíamos a criptoanálise diferencial desde 1974. Este é o motivo pelo qual o DES resistiu a este tipo de ataque. Projetamos as caixas S e a permutação para que este ataque fosse neutralizado. Todos estes anos ficamos calados a respeito do assunto porque sabíamos que a criptoanálise diferencial é muito poderosa e porque queríamos que ela não fosse descoberta e usada (tanto em projetos, quanto em ataques). Agora que a técnica se tornou conhecida, achamos que chegou a hora de contar a nossa versão da história.

Adi Shamir desafiou Coppersmith a revelar que não havia encontrado qualquer ataque melhor do que este, mas Coppersmith preferiu ficar em silêncio.

Referência bibliográfica

• Bruce Schneier, "Applied Cryptography" John Wiley & Sons, Inc, 1994