On the security of 2-key triple DES

Este artigo demonstra que o 2-key triple DES oferece uma margem de segurança muito menor do que o estimado anteriormente, apresentando novos ataques que desafiam a crença de sua robustez e reforçam a urgência de substituí-lo por uma variante de 3 chaves.

O essencial

🛡️ O Fim da "Trava Dupla" de Segurança: Por que o Triple DES de 2 Chaves está em Perigo

Imagine que você tem um cofre muito antigo e famoso, usado por bancos e lojas de cartão de crédito há décadas. Para abrir esse cofre, você precisa de uma chave. O problema é que a chave original (o algoritmo DES) ficou pequena demais e os ladrões modernos conseguem descobri-la com facilidade.

Para resolver isso, os bancos criaram uma "versão reforçada": o Triple DES. Em vez de usar a chave uma vez, eles a usam três vezes. É como se você tivesse três fechaduras na mesma porta.

Existem duas versões dessa porta reforçada:

1. 3 Chaves: Você usa três chaves diferentes (K1, K2, K3). É como ter três guardas diferentes, cada um com sua própria chave.
2. 2 Chaves: Você usa apenas duas chaves (K1, K2, K1). A primeira e a terceira fechaduras são iguais. É como ter dois guardas, mas o primeiro guarda volta para trancar a porta no final.

Este artigo foca na versão de 2 chaves, que ainda é muito usada, mas que o autor diz que está mais fraca do que todos pensavam.

🕵️‍♂️ O Velho Plano de Roubo (Ataque de 1990)

Desde 1990, os especialistas sabiam que existia um jeito de quebrar essa porta de 2 chaves. O plano era basicamente:

• O ladrão precisa de muitas fotos do cofre aberto e fechado (chamadas de "texto claro" e "texto cifrado").
• Ele tenta adivinhar a primeira chave, verifica se bate com as fotos e, se bater, tenta a segunda chave.
• O problema: Para isso funcionar, o ladrão precisava de bilhões de fotos geradas com a mesma chave.
• A defesa: Os bancos diziam: "Não se preocupe! Se mudarmos a chave toda semana, o ladrão nunca terá fotos suficientes da mesma chave para quebrar o sistema."

🚀 O Novo Plano de Roubo (A Descoberta de 2016)

O autor do artigo, Chris Mitchell, descobriu que esse plano de 1990 estava incompleto. Ele mostrou que o ladrão pode ser muito mais esperto e eficiente de três formas novas:

1. O "Mix" de Chaves (Generalização)

• A analogia: Imagine que o ladrão não precisa de 4 bilhões de fotos do mesmo cofre. Ele pode pegar 1 milhão de fotos do cofre A, 1 milhão do cofre B, 1 milhão do cofre C, e assim por diante.
• O truque: O novo ataque mistura todas essas fotos. Ele consegue testar as chaves de todos os cofres ao mesmo tempo.
• O impacto: A defesa de "trocar a chave frequentemente" não funciona mais. Mesmo que você troque a chave, o ladrão apenas acumula mais fotos de diferentes chaves e continua o ataque. Ele só precisa de uma chave quebrada para roubar os dados daquela chave específica.

2. O Truque do Espelho (Propriedade de Complementação)

• A analogia: O DES tem uma característica estranha: se você inverter todas as cores de uma foto (preto vira branco) e inverter a chave, a "foto fechada" também inverte. É como um espelho.
• O truque: O autor mostrou que, usando esse espelho, o ladrão pode testar duas possibilidades de chave ao mesmo tempo.
• O impacto: Isso dobra a velocidade do ataque. O ladrão trabalha duas vezes mais rápido sem precisar de mais equipamentos.

3. O "Quebra-Cabeça" Incompleto (Texto Parcialmente Conhecido)

• A analogia: Muitas vezes, o ladrão não vê a foto completa do cofre. Ele vê 56 bits da imagem, mas 8 bits estão borrados (como um PIN de cartão que é um número de 4 dígitos escondido dentro de um bloco de dados).
• O truque: Antigamente, achava-se que isso parava o ataque. Mas o autor mostrou que o ladrão pode criar "fotos falsas" preenchendo os bits borrados com todas as combinações possíveis.
• O impacto: Mesmo com dados incompletos, o ataque funciona quase tão bem quanto com dados completos. Isso torna o ataque aplicável em muitos mais cenários reais, como transações bancárias onde o número da conta é conhecido, mas o PIN é secreto.

📉 A Conclusão: A Margem de Segurança é Fina

O mundo financeiro e as normas internacionais (como a ISO) diziam que a versão de 2 chaves oferecia 80 bits de segurança. Isso soava como um número alto e seguro.

O autor diz: "Esse número é otimista demais."
Com os novos truques (misturar chaves, usar o espelho e usar dados incompletos), a segurança real é muito menor. A "margem de segurança" é tão fina que o sistema está à beira de ser quebrado por computadores modernos.

💡 O Que Fazer Agora?

O artigo conclui com um aviso urgente:

1. Pare de usar a versão de 2 chaves: Não confie na ideia de que "trocar a chave frequentemente" vai salvá-lo.
2. Mude para 3 chaves ou AES: Substitua o sistema antigo imediatamente. O AES (o padrão moderno de criptografia) é mais rápido, mais seguro e usa chaves maiores (até 256 bits), o que o torna resistente até mesmo a computadores quânticos do futuro.

Resumo em uma frase:
O "cofre" de 2 chaves que os bancos usam há anos tem uma fechadura defeituosa que os ladrões aprenderam a forçar usando um novo conjunto de ferramentas, e a única solução segura é trocar a fechadura inteira por uma moderna o mais rápido possível.

Resumo técnico

Resumo Técnico: Segurança do 2-key Triple DES

1. Problema e Contexto

O 2-key Triple DES (uma variante do algoritmo de criptografia que utiliza duas chaves DES, seguindo o esquema Criptografar-Decifrar-Criptografar com $K_1, K_2, K_1$) permanece amplamente utilizado, especialmente na indústria de pagamentos (ex: cartões de crédito EMV), apesar de ter sido despadronizado pelo NIST em 2015.

• Estimativa de Segurança Atual: A avaliação de segurança amplamente aceita é de que o 2-key Triple DES oferece 80 bits de segurança. A crença comum é que o esquema é seguro desde que as chaves sejam trocadas regularmente, limitando a quantidade de dados criptografados sob uma única chave.
• O Problema: O autor argumenta que essa margem de segurança é ilusória e que a estimativa de 80 bits não é conservadora. O artigo demonstra que a segurança real é ainda menor do que se pensava, desafiando a eficácia da troca regular de chaves como medida de mitigação.

2. Metodologia e Contribuições Principais

O paper propõe uma generalização e aprimoramento do ataque clássico de van Oorschot-Wiener (1990), que era o ataque mais eficaz conhecido contra o 2-key Triple DES nas últimas 25 anos. O autor introduz três melhorias principais:

A. Generalização para Múltiplas Chaves

• Insight: O ataque original de van Oorschot-Wiener exigia que todos os pares de texto plano/cifrado fossem gerados sob a mesma chave. O autor demonstra que o ataque funciona igualmente bem se os pares forem gerados usando várias chaves diferentes.
• Mecanismo: O algoritmo é modificado para agrupar os pares $(P, C)$ por rótulos de chave ($s$). Ao encontrar uma correspondência, o atacante recupera apenas a chave específica associada àquele rótulo.
• Impacto: Isso invalida a defesa de "troca frequente de chaves". Mesmo que o atacante não consiga quebrar todas as chaves, a capacidade de quebrar uma chave a partir de um grande conjunto de dados mistos (gerados por múltiplas chaves) torna o ataque viável em cenários onde antes se acreditava ser seguro.

B. Exploração da Propriedade de Complementação do DES

• Insight: O DES possui uma propriedade de complementação: $E_K(P) = \overline{E_{\overline{K}}(\overline{P})}$.
• Mecanismo: O ataque é modificado para testar simultaneamente um valor $A$ e seu complemento $\overline{A}$. Isso permite processar duas tentativas de chave por iteração.
• Impacto: Reduz o custo computacional do ataque por um fator de 2 (ganho de 1 bit de eficiência).

C. Uso de Texto Plano Parcialmente Conhecido

• Insight: Em muitos cenários práticos (ex: blocos PIN na indústria de pagamentos), o texto plano não é totalmente conhecido, mas parte dele é (ex: número da conta conhecido, PIN desconhecido).
• Mecanismo: O autor propõe gerar todos os possíveis textos planos candidatos para os bits desconhecidos e tratá-los como pares válidos no ataque. Se um par for falso, ele será descartado na etapa de verificação final.
• Impacto: Permite que o ataque seja aplicado em cenários onde apenas o texto cifrado e parte do texto plano são conhecidos, sem aumentar significativamente a complexidade computacional, desde que o número de bits desconhecidos ($w$) seja pequeno em relação ao tamanho do bloco.

3. Resultados e Complexidade do Ataque

Ao combinar essas três técnicas, o autor recalcula a complexidade do ataque:

• Complexidade Original (van Oorschot-Wiener): Para $n = 2^t$ pares conhecidos, a complexidade era de aproximadamente $2^{121-t}$ operações DES.
• Complexidade Aprimorada (Proposta):
  • Com a exploração da propriedade de complementação, a complexidade cai para $2^{120-t}$ operações DES.
  • O uso de texto plano parcial aumenta a complexidade de armazenamento para $O(2^{t+w})$, mas mantém a complexidade computacional próxima de $2^{120-t}$(ou$2^{121-t}$ se não usar complementação).
• Exemplo Prático:
  • Com $n = 2^{32}$ (4 bilhões) de pares de texto plano/cifrado (ou parcialmente conhecidos), gerados possivelmente por múltiplas chaves, a chave pode ser descoberta em **$2^{88}$** (ou$2^{89}$) operações DES.
  • Isso é computacionalmente viável com hardware moderno ou clusters distribuídos, muito abaixo do que seria esperado para um sistema de 80 bits de segurança.

4. Aplicação ao ANSI Retail MAC

O artigo também aplica essa generalização ao ANSI Retail MAC (usado em transações financeiras).

• O ataque tradicional de Preneel-van Oorschot para recuperar chaves de MAC requer $2^{32}$ pares gerados sob a mesma chave.
• A generalização proposta permite quebrar o MAC mesmo que os pares de mensagem/MAC tenham sido gerados por múltiplas chaves.
• Conclusão: Limitar a quantidade de MACs gerados por uma única chave (uma prática comum de segurança) não protege contra este ataque generalizado.

5. Significância e Conclusões

O artigo conclui que a segurança do 2-key Triple DES é muito mais frágil do que se acreditava:

1. Margem de Segurança Inexistente: A estimativa de 80 bits de segurança não é conservadora; a margem de segurança é "fina".
2. Troca de Chaves é Insuficiente: A recomendação de trocar chaves regularmente não impede o ataque, apenas limita o impacto de uma quebra bem-sucedida (apenas os dados daquela chave específica são comprometidos).
3. Urgência na Migração: O uso contínuo do 2-key Triple DES representa um risco real. O autor recomenda a migração urgente para o 3-key Triple DES ou, preferencialmente, para algoritmos modernos como o AES (que oferece chaves de 256 bits e resistência futura contra computação quântica).
4. Viabilidade do ANSI MAC: A viabilidade futura do ANSI Retail MAC usando DES é questionada devido à aplicabilidade deste ataque generalizado.

Em suma, o trabalho demonstra que o 2-key Triple DES está "quase quebrado" na prática, exigindo ação imediata da indústria para substituí-lo, pois as defesas atuais baseadas em limitação de volume de dados por chave são ineficazes contra a nova variante do ataque.