Encontro no meio e compromissos entre tempo e memória

Os ataques MITM dividem uma cifra em duas metades e as atacam de forma independente. O atacante constrói uma tabela a partir de uma extremidade e, em seguida, procura uma correspondência a partir da outra. Isso reduz a complexidade do ataque de O(2^{2n}) para O(2^n), ao custo de O(2^n) de memória.

O DES duplo aplica DES duas vezes: C = DES_{K2}(DES_{K1}(P)). Espaço de chaves: 2^{112}. Ataque MITM: para todos os 2^{56} valores de K1, calcule DES_{K1}(P) e armazene o resultado. Para todos os 2^{56} valores de K2, calcule DES_{K2}^{-1}(C) e procure na tabela. Correspondência → candidato (K1, K2). Apenas 2^{57} de trabalho no total.

Etapa 1: criptografe o texto simples P com todos os K1 possíveis → tabela T[DES_{K1}(P)] = K1. Etapa 2: para cada K2, descriptografe o texto cifrado C: v = DES^{-1}_{K2}(C). Verifique se v ∈ T. Se T[v] = K1 existir, verifique (K1, K2) em um segundo par de texto simples e texto cifrado. Espere 1–2 correspondências falsas; descarte-as.

O DES triplo (3DES) utiliza três chaves K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). O MITM ainda se aplica, mas com menor eficácia: o 3DES de duas chaves (K3=K1) requer 2^{112} de trabalho. Para o 3DES de três chaves, existe um ataque MITM de 2^{112}, o que explica por que o 3DES oferece apenas cerca de 112 bits de segurança efetiva, apesar de ter uma chave de 168 bits.

Hellman (1980): pré-calcule uma tabela de cadeias de (ponto inicial, ponto final) para acelerar a busca offline de chaves. Dado um resumo ou texto cifrado alvo, procure na tabela de Hellman uma cadeia que o contenha. Compromisso: P = N (tempo × memória = constante de espaço). Essa é a base das tabelas arco-íris.

As tabelas arco-íris (Oechslin, 2003) aprimoram as tabelas de Hellman utilizando funções de redução diferentes em cada posição da cadeia, eliminando falsos alarmes (cadeias mescladas). São eficientes para quebrar resumos de senhas sem sal. Uma consulta leva O(table_size/chain_length) de tempo.

Um sal é um valor aleatório acrescentado ao início da senha antes do cálculo do resumo: H(salt||password). Sais diferentes produzem resumos diferentes para a mesma senha — uma tabela arco-íris para "password" é inútil se outro sal tiver sido utilizado. Os sais devem ser armazenados junto com o resumo.

Os ataques MITM contra o AES-128 (10 rodadas) dividem o algoritmo na rodada 5 — criptografa-se para frente por 5 rodadas, descriptografa-se para trás por 5 rodadas e encontra-se o ponto de encontro no meio. O melhor ataque conhecido, o ataque de biclique, reduz 2^{128} para 2^{126.1} — não é prático, mas mostra que o AES não possui margem de segurança contra abordagens no estilo MITM.

Para resumos Merkle-Damgård, o MITM pode encontrar pré-imagens mais rapidamente que a força bruta em algumas construções. Ataque: construa uma tabela a partir dos blocos da mensagem, começando pelo IV; pesquise para trás a partir do resumo alvo. Contra o SHA-256 com todas as rodadas: ainda são necessários cerca de 2^{255} — nenhuma melhoria em relação à força bruta.

O ataque de dissecação generaliza o MITM para divisões em r partes. Em uma divisão da cifra em 3 partes: criptografe para frente por 1/3 das rodadas, encontre o ponto de encontro no meio da cadeia e, em seguida, descriptografe para trás por 1/3. Requer O(2^{n*2/3}) de tempo e O(2^{n/3}) de memória — um compromisso mais equilibrado.

Em protocolos, os ataques MITM podem ser impedidos por: utilizar chaves longas derivadas por KDF a partir de senhas de alta entropia (reduz o espaço de chaves que pode ser enumerado), utilizar tokens de hardware (FIDO2) em que a chave nunca sai do dispositivo ou utilizar autenticação de chave pública (não há segredo compartilhado a enumerar).

Os ataques MITM dividem as cifras em metades, reduzindo o tempo de 2^{2n} para 2^n com 2^n de memória. Eles quebram o DES duplo; o 3DES é atenuado, mas tem segurança efetiva de 112 bits. As tabelas arco-íris utilizam a lógica do MITM para quebrar senhas — são derrotadas pelo uso de sais. Próximo: ataques de temporização e ataques de canal lateral.