Como o DES foi quebrado

O DES tem 2^56 chaves possíveis, o que equivale a aproximadamente 72 quatrilhões (72.057.594.037.927.936) de chaves. Embora isso pareça enorme, trata-se de um espaço finito que pode ser pesquisado sistematicamente com poder computacional suficiente.

O esgotamento de chaves (força bruta) exige, em média, testar metade do espaço de chaves antes de encontrar a chave correta. Para DES, isso significa cerca de 2^55 tentativas de descriptografia, cada uma exigindo algumas operações no hardware moderno.

Em 1997, a RSA Data Security ofereceu um prêmio de US$ 10.000 por quebrar uma mensagem criptografada com DES. Rocke Verser coordenou um esforço de computação distribuída em dezenas de milhares de computadores conectados à internet.

Após 96 dias de busca, a chave foi encontrada. O texto simples era "A criptografia forte torna o mundo um lugar mais seguro." O esforço demonstrou que o DES podia ser quebrado, embora isso exigisse meses e uma coordenação em grande escala.

A Fundação da Fronteira Eletrônica construiu a Deep Crack por US$ 250.000 em 1998. Ela continha 1.856 ASICs personalizados, cada um capaz de testar 2,5 milhões de chaves DES por segundo, dando à Deep Crack uma taxa combinada de mais de 90 bilhões de chaves por segundo.

A Deep Crack podia esgotar todo o espaço de chaves do DES em cerca de 9 dias, em média. Isso provou que um adversário determinado, com um investimento de US$ 250.000, poderia quebrar o DES em menos de duas semanas.

No DES Challenge II-1 (fevereiro de 1998), a Deep Crack, combinada com a rede de computação voluntária distributed.net, quebrou o DES em apenas 39 dias. O DES Challenge II-2 (julho de 1998) foi vencido em 56 horas.

A rápida redução de 96 dias para 56 horas em apenas um ano demonstrou como melhorias no hardware e uma coordenação mais eficiente podiam acelerar os ataques de força bruta.

Em janeiro de 1999, a Deep Crack da EFF, combinada com a distributed.net, quebrou o DES Challenge III em apenas 22 horas e 15 minutos, ganhando um prêmio de US$ 10.000 da RSA Security.

Essa demonstração definitiva de que o DES podia ser quebrado em menos de 24 horas encerrou efetivamente qualquer argumento a favor da segurança do DES. Pouco depois, a NIST iniciou o processo de seleção de um substituto para o DES, que se tornou o AES.

A Distributed.net organizou esforços de computação voluntária nos quais usuários comuns da internet doavam ciclos de CPU aos desafios do DES. No auge, centenas de milhares de computadores participaram.

Cada computador testava uma parte diferente do espaço de chaves, coordenado por um servidor central. Isso foi pioneiro no modelo de computação distribuída para criptoanálise, ainda usado hoje em desafios como a quebra de cifras mais antigas.

O esgotamento de chaves funciona porque cada descriptografia do DES é rápida (microssegundos no hardware) e independente. Não há dependência entre testar a chave N e a chave N+1, portanto a busca pode ser paralelizada perfeitamente em qualquer número de máquinas.

Essa natureza altamente paralelizável significa que duplicar o hardware reduz exatamente pela metade o tempo. Adicionar mais máquinas produz um ganho linear de velocidade, tornando a relação custo-benefício favorável aos adversários.

Eli Biham e Adi Shamir publicaram a criptoanálise diferencial em 1990, uma técnica que explora como diferenças em pares de entradas se propagam pelas rodadas da cifra. Para DES, teoricamente são necessários 2^47 textos simples escolhidos.

Mais tarde, revelou-se que as caixas S do DES haviam sido projetadas tendo em mente a resistência à criptoanálise diferencial, o que sugere que a NSA conhecia essa técnica na década de 1970. O ataque é teoricamente impressionante, mas na prática é superado pela força bruta em hardware.

Mitsuru Matsui publicou a criptoanálise linear em 1993, exigindo 2^43 textos simples conhecidos para atacar o DES. Ele implementou o ataque e quebrou o DES experimentalmente em 1994, confirmando a análise teórica.

A criptoanálise linear encontra aproximações lineares do comportamento das caixas S e as usa para recuperar bits da chave com um viés estatístico. Em teoria, exige muito menos dados que a força bruta, mas era impraticável antes dos ataques em hardware.

A criptoanálise diferencial foi publicada em 1990, mas exige textos simples escolhidos (impraticável na maioria dos cenários reais). A criptoanálise linear foi publicada em 1993 e funciona com textos simples conhecidos, mas exige 2^43 deles.

A força bruta em hardware (Deep Crack) quebrou o DES em 22 horas em 1999. Na prática, o ataque de hardware foi mais devastador que os avanços teóricos em criptoanálise, porque não exigia pares especiais de texto simples e texto cifrado.

A quebra pública e documentada do DES teve implicações imediatas para as políticas de segurança. A NIST iniciou o processo da competição do AES em 1997, o mesmo ano em que o DES Challenge I foi bem-sucedido. A competição foi explicitamente projetada para evitar as vulnerabilidades do processo de padronização do DES.

Bancos e órgãos governamentais começaram a migrar para 3DES como medida provisória enquanto o AES era desenvolvido. A cronologia da quebra do DES determinou diretamente a urgência e o cronograma do esforço de adoção do AES.

Teste sua compreensão da história da quebra do DES.

O DES foi quebrado em tempos cada vez menores: 96 dias em 1997, 56 horas em 1998 e 22 horas em 1999. A Deep Crack da EFF, com custo de US$ 250.000, usou ASICs personalizados para testar 90 bilhões de chaves por segundo.

Tanto a criptoanálise diferencial (2^47 textos simples escolhidos) quanto a criptoanálise linear (2^43 textos simples conhecidos) também quebram teoricamente o DES, mas a força bruta em hardware foi o fator decisivo na prática. A quebra em 22 horas encerrou a vida do DES como cifra viável.