Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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.

2

Estimar o viés (desvio de 0,5) de cada aproximação linear usando análise estatística das transformações de rodada.

3

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.

4

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

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Abrir referência DOI
    Copiado.
  2. 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 DOI
    Copiado.