Na criptoanálise e na segurança computacional, um ataque de trade-off tempo-memória-dados (frequentemente abreviado pela sigla em inglês TMDTO, de Time-Memory-Data Trade-off) é uma classe de ataque criptográfico genérico concebida para inverter funções unidirecionais e recuperar a chave criptográfica ou o estado interno de um sistema criptográfico — particularmente cifras de fluxo — equilibrando estrategicamente quatro grandezas interdependentes: O tempo de pré-computação offline (); O volume de memória ou armazenamento necessário (); O tempo de computação online durante o ataque (); A quantidade de dados observados ou interceptados ().

O método constitui uma generalização direta do clássico ataque de trade-off tempo-memória (TMTO) proposto por Martin Hellman em 1980. Enquanto o ataque de Hellman opera sobre instâncias fixas com um único dado de entrada (), os ataques TMDTO exploram o fato de que um adversário no mundo real pode interceptar múltiplos fluxos contínuos de dados gerados a partir de diferentes chaves ou de sucessivos estados internos de uma mesma cifra. Ao incorporar a disponibilidade de dados () por meio do paradoxo do aniversário, esses ataques conseguem reduzir drasticamente tanto a memória requerida quanto a complexidade do tempo de execução em tempo real, atingindo custos ordens de magnitude inferiores à força bruta.

A descoberta do paradigma TMDTO impôs uma mudança estrutural na engenharia de segurança criptográfica moderna, culminando no princípio de projeto que exige que o tamanho do estado interno de uma cifra de fluxo em bits seja pelo menos o dobro do tamanho de sua chave de segurança efetiva (, implicando que o espaço de busca cresça quadraticamente em relação ao espaço de chaves).

Contexto histórico e evolução

O trade-off tempo-memória de Hellman (1980) Em 1980, Martin Hellman introduziu uma técnica intermediária entre dois extremos computacionais para a inversão de uma função unidirecional com espaço de busca de tamanho : A busca exaustiva (força bruta), que não consome memória (), mas requer tempo linear no espaço de busca (); A tabela de consulta direta (lookup table), na qual todos os pares pré-calculados são ordenados previamente, demandando tempo de resposta quase instantâneo ( ou ), porém com custo de armazenamento proibitivo ().

Hellman organizou o espaço de busca em matrizes de "cadeias de redução", onde cada cadeia parte de um ponto inicial e itera a função por passos, armazenando na memória apenas o par . O algoritmo alcança a célebre curva de compensação:

permitindo operar em pontos como e . Posteriormente, em 2003, Philippe Oechslin otimizou a estrutura com as tabelas arco-íris (rainbow tables), que utilizam funções de redução distintas por coluna para mitigar colisões entre cadeias.

O paradoxo do aniversário e o trade-off de Babbage–Golić Em meados da década de 1990, Steve Babbage (1995) e Jovan Golić (1997) observaram que, em cifras de fluxo, a tarefa do atacante não é necessariamente descobrir o estado em um instante predeterminado, mas sim encontrar qualquer estado interno que tenha ocorrido ao longo da sequência cifrante interceptada.

Se o atacante dispõe de uma sequência contínua de blocos de saída do gerador de fluxo e pré-computa uma tabela com estados aleatórios e seus primeiros blocos de saída, pelo paradoxo do aniversário, uma colisão entre um dos estados observados e um dos estados tabelados ocorrerá com alta probabilidade quando:

Essa formulação deu origem ao chamado trade-off de Babbage–Golić (BG), caracterizado por:

com a curva de compensação linear:

O ponto mais notável da curva BG ocorre quando , no qual a recuperação de um estado interno viável exige tempo e memória de apenas , sem necessidade de pré-computação excessiva ().

O trade-off unificado de Biryukov–Shamir (2000) Na conferência ASIACRYPT 2000, Alex Biryukov e Adi Shamir integraram as cadeias de Hellman com a multiplicidade de dados do paradoxo do aniversário, formulando a teoria geral dos ataques TMDTO para cifras de fluxo.

No modelo de Biryukov–Shamir (BS), o adversário constrói múltiplas tabelas de Hellman cobrindo apenas uma fração do espaço de estados, compensando a cobertura parcial pelo fato de que diferentes pontos-alvo são consultados simultaneamente durante a fase ativa. A relação fundamental da curva BS é expressa por:

sob as seguintes condições de contorno de viabilidade:

Um ponto de equilíbrio comumente adotado na literatura é:

Nesse cenário, o atacante requer apenas blocos de dados interceptados para recuperar a chave em tempo e memória , com uma pré-computação única de esforço , muito abaixo dos passos da busca exaustiva.

Parâmetros do ataque A eficácia e a viabilidade prática de um ataque TMDTO são descritas por cinco parâmetros quantitativos:

Símbolo Parâmetro Descrição formal Restrição prática típica Espaço de busca Número total de estados internos possíveis da cifra ( para um registrador de bits). Determinado pela especificação do algoritmo. Pré-computação Número de passos de avaliação da função na fase de montagem das tabelas offline. Deve ser viável uma única vez (). Memória Número de pontos (pares extremidade de cadeias) armazenados em memória permanente ou disco. Limitado pela capacidade de armazenamento do atacante. Dados interceptados Quantidade de fluxo de chave gerado (keystream) ou blocos cifrados obtidos pelo atacante em tempo real. Limitado pelo volume de tráfego emitido na sessão. Tempo online Número de operações aritméticas ou avaliações de função executadas na fase de ataque em tempo real. Deve permitir quebra antes da expiração da validade da chave.

Fases do algoritmo TMDTO A execução de um ataque TMDTO canônico de Biryukov–Shamir estrutura-se em duas etapas operacionais bem demarcadas:

Fase 1: Pré-computação (offline) A fase de preparação é computacionalmente onerosa, porém realizada apenas uma vez para uma dada especificação de cifra: Define-se a função de mapeamento de estado para saída , que recebe um estado interno e produz os primeiros bits da sequência cifrante correspondente. Para construir tabelas independentes e mitigar a fusão antecipada de cadeias, projetam-se funções de redução distintas () que remapeiam sequências de bits de volta ao conjunto de estados internos. Em cada tabela , selecionam-se estados iniciais aleatórios e, para cada um, itera-se a função composta por passos:

Armazena-se na memória apenas o par ordenado contendo o estado inicial e o estado terminal . Os passos intermediários da cadeia são descartados para economizar espaço de armazenamento. As tabelas resultantes são ordenadas pelo valor final para permitir busca binária eficiente em tempo .

Fase 2: Ataque em tempo real (online) Uma vez compiladas as tabelas, o adversário executa a fase de interceptação ativa: O atacante intercepta um fluxo contínuo de dados contendo blocos de saída sobrepostos da cifra. Para cada bloco de saída interceptado () e para cada tabela , calcula-se o estado reduzido correspondente . Aplica-se sucessivamente a iteração por até passos. Em cada passo, consulta-se a tabela ordenada para verificar se coincide com algum estado terminal registrado . Caso haja correspondência positiva, reconstrói-se a cadeia original a partir do estado inicial associado até o ponto de colisão anterior, obtendo o estado interno que originou o bloco . O candidato a estado interno é validado gerando os bits de fluxo subsequentes e confrontando-os com o tráfego interceptado.

Comparativo de curvas de trade-off A tabela a seguir contrasta as características dos principais modelos teóricos de compensação criptoanalítica:

Modelo Tipo de alvo Equação da curva Dados () Pré-computação () Ponto de operação clássico Busca exaustiva Geral Hellman (1980) Cifras de bloco / Hashes Babbage–Golić (1995/97) Cifras de fluxo Biryukov–Shamir (2000) Cifras de fluxo

Impacto na segurança e quebra de cifras reais

O caso do algoritmo A5/1 (GSM) O impacto prático mais célebre do ataque TMDTO deu-se contra a cifra de fluxo A5/1, algoritmo criptográfico historicamente empregado para cifrar as comunicações de voz e dados em redes de telefonia móvel GSM.

O A5/1 possui uma chave secreta de 64 bits () e um estado interno total de exatamente 64 bits distribuído entre três registradores de deslocamento com retroalimentação linear (LFSRs), totalizando um espaço de estados de . Como o tamanho do estado interno é idêntico ao tamanho da chave: Biryukov, Shamir e Wagner (2000) apresentaram um ataque TMDTO capaz de recuperar o estado interno em menos de um segundo em um computador pessoal, a partir de apenas dois minutos de conversa telefônica interceptada ( a frames GSM), utilizando cerca de 300 gigabytes de tabelas pré-computadas. Em 2003, Barkan, Biham e Shamir aperfeiçoaram o ataque para uma modalidade com apenas texto cifrado (ciphertext-only), decifrando chamadas GSM quase instantaneamente.

Outras cifras vulneráveis E0 (Bluetooth): Utilizada no protocolo de segurança Bluetooth, a cifra E0 emprega um tamanho de chave configurável de até 128 bits. Entretanto, seu estado interno possui 132 bits (128 bits provenientes de quatro LFSRs somados a 4 bits de memória no somador não linear). Em virtude desse dimensionamento restrito, o espaço de estados não suporta os 128 bits nominais de segurança sob a curva de equilíbrio TMDTO (), permitindo que ataques híbridos combinando trade-offs e técnicas de busca com retrocesso (guess-and-determine) operem com complexidade significativamente abaixo do limite de força bruta na chave. RC4: A cifra clássica RC4 possui uma matriz de permutação cujo estado interno atinge bits, conferindo imunidade teórica completa contra ataques TMDTO diretos sobre seu estado pleno. Não obstante, Biryukov e Shamir analisaram variantes com estados projetados ou tabelas reduzidas para calibrar a margem de segurança da arquitetura perante reconstruções parciais de estado.

Contramedidas e princípios de projeto modernos As lições aprendidas com a eficácia dos ataques TMDTO forçaram os criptógrafos a estabelecer novos padrões fundamentais de dimensionamento em cifras simétricas:

A regra do estado interno duplo: n ≥ 2k Para garantir que uma cifra de fluxo ofereça bits de segurança efetiva contra qualquer adversário, o tamanho do seu estado interno (em bits) deve satisfazer obrigatoriamente a regra:

Com essa exigência: No ponto de equilíbrio de Babbage–Golić (), a complexidade é , igualando o custo da força bruta na chave; No ponto clássico de Biryukov–Shamir ( com ), o custo do ataque permanece de pelo menos operações, preservando o nível de segurança do sistema mesmo se o atacante coletar volumes massivos de tráfego.

Esse critério foi estritamente imposto pelo projeto europeu eSTREAM (2004–2008), responsável pela seleção de cifras de fluxo modernas como ChaCha20, Salsa20, Trivium e Grain, todas concebidas com estados internos significativamente maiores que suas chaves secretas (por exemplo, o Trivium utiliza chave de 80 bits e estado de 288 bits; o ChaCha20 opera com estado de 512 bits para chaves de 256 bits).

Limitação de volume de dados por sessão Outra contramedida prática amplamente incorporada em protocolos de comunicação (TLS, IPsec) consiste em restringir o número de blocos transmitidos sob um mesmo par de chave e vetor de inicialização (IV), forçando uma rotatividade frequente de chaves (rekeying) antes que o parâmetro atinja patamares criptoanaliticamente perigosos.

Ver também Criptoanálise Tabela arco-íris Paradoxo do aniversário Cifra de fluxo

Bibliografia

Categoria:Ataques criptográficos