Criptoanálise Linear
- Proposto por
- Mitsuru Matsui
- Ano
- 1993
- Tipo
- linear approximation attack
- Família
- Cryptanalytic technique
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Criptoanálise linear é um ataque de texto plano conhecido que explora aproximações lineares das transformações não lineares de um cifrador para recuperar bits da chave secreta.
Introduzida por Mitsuru Matsui em 1993, a criptoanálise linear fornece ataques práticos contra cifradores como o DES com complexidade computacional inferior à força bruta. A técnica analisa vieses estatísticos em como combinações lineares de bits de texto plano e texto cifrado se relacionam com bits da chave, permitindo a recuperação da chave com requisitos de dados reduzidos.
A intuição por trás do método
A criptoanálise linear encontra equações lineares relacionando bits de texto plano, bits de texto cifrado e bits de chave. Devido à mistura não perfeita nas rodadas do cifrador, essas equações lineares se mantêm com probabilidade ligeiramente superior ao acaso. Ao coletar muitos pares de texto plano-texto cifrado e observar quais valores de chave fazem essas equações se manterem com mais frequência, o atacante pode estreitar a chave correta.
História
A criptoanálise linear foi introduzida por Matsui em 1993 como um ataque de texto plano conhecido ao DES. Em 1994, Matsui demonstrou a primeira criptoanálise experimental do padrão DES usando criptoanálise linear, recuperando uma chave com 2^43 textos planos conhecidos. Esse avanço demonstrou ataques práticos contra um padrão implantado e influenciou o desenvolvimento do AES com limites de resistência comprovados.
Quando usar
A criptoanálise linear é usada em pesquisa de criptoanálise e avaliação de design de cifradores. Ela orienta os designers de cifradores na seleção de S-boxes e transformações que resistem a aproximações lineares. Cifradores modernos são projetados com limites comprovados na força da aproximação linear.
Limitações e considerações
- Cifradores modernos (AES) são cuidadosamente projetados para resistir à criptoanálise linear com limites comprováveis
- Requer pares de texto plano-texto cifrado conhecidos, que podem não estar disponíveis em todos os cenários
- Requisitos computacionais e de dados podem exceder a viabilidade prática para cifradores bem projetados
- Descobrir aproximações lineares fortes para cifradores modernos é extremamente difícil
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Ataque prático ao DES exigindo 2^43 pares de texto plano-texto cifrado e 2^39 operações
- Estrutura matemática bem formalizada (lema de empilhamento) para analisar vieses de aproximação
- Complementa a criptoanálise diferencial, encontrando fraquezas que a análise diferencial pode não detectar
- Moldam os requisitos de design de cifradores para seleção de S-box e transformação de rodada
Aplicações
- Criptoanálise de cifradores em bloco avaliando propriedades de segurança em pesquisa e padronização
- Design de cifradores e seleção de S-box para garantir limites adequados de aproximação linear
- Validação de padrões criptográficos (NIST, ETSI) exigindo análise de resistência linear
- Avaliação de cifradores legados para decisões de aposentadoria e substituição
Como funciona
Como funciona
Encontrar aproximações lineares: relações lineares entre bits de texto plano, bits de texto cifrado e bits de chave que se mantêm com probabilidade significativamente diferente de 0,5.
Estimar o viés (desvio de 0,5) de cada aproximação linear usando análise estatística das transformações de rodada.
Para valores de chave candidatos, contar quantas vezes a aproximação linear se mantém em pares de texto plano-texto cifrado conhecidos. A chave correta faz a aproximação se manter com mais frequência.
Verificar bits de chave recuperados descriptografando o texto cifrado e verificando a correção.
Erros comuns
- Assumindo que todas as aproximações lineares são exploráveis; aproximações fracas fornecem vantagem mínima
- Subestimar a dificuldade prática do ataque quando os requisitos teóricos de dados parecem razoáveis
- Negligenciar a interação entre propriedades lineares e diferenciais na análise de cifradores
Perguntas frequentes
O que é o lema de empilhamento?
O lema de empilhamento fornece um método para calcular o viés de aproximações lineares através de múltiplas rodadas, combinando os vieses de aproximações de rodadas individuais. Ele é fundamental para a criptoanálise linear.
Como o AES resiste à criptoanálise linear?
O AES usa S-boxes escolhidas para minimizar a probabilidade máxima de aproximação linear e uma camada de difusão que garante a rápida difusão de vieses lineares através das rodadas. Limites comprovados garantem que não haja aproximações lineares práticas.
Qual a diferença entre criptoanálise linear e diferencial?
A análise diferencial estuda as diferenças de entrada-saída, enquanto a análise linear estuda aproximações lineares (XOR de bits de texto plano e texto cifrado). Ambas exploram fraquezas estruturais em cifradores.
A criptoanálise linear pode quebrar cifradores modernos?
Não na prática. Cifradores modernos como o AES têm limites comprováveis em aproximações lineares, tornando os ataques computacionalmente inviáveis.
Como avalio a resistência linear no design do meu cifrador?
Analise tabelas de aproximação linear de S-box e calcule o viés máximo através das rodadas usando o lema de empilhamento. Garanta que o viés máximo seja negligenciável em todas as aproximações lineares possíveis.
Métodos relacionados
Fontes
Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
Abrir referência DOICopiado.Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.
Abrir referência DOICopiado.