Criptoanálise Linear

A técnica de criptoanálise linear foi apresentada em 1993 no Eurocrypt's93 por Mitsuru Matsui e formalizada por Eli Biham em 1994. Por ocasião da primeira publicação, seus autores focaram o estudo na criptoanalise do DES.

A técnica de criptoanálise linear é basicamente um ataque de mensagem conhecida. O propósito do método é obter uma expressão linear aproximada de um dado algoritmo criptográfico.

A criptoanálise linear estuda as relações estatísticas entre os bits de uma mensagem, os bits das cifras correspondentes e da chave utilizada na criptografia. Estas relações são usadas para predizer valores dos bits da chave quando muitas mensagens e os respectivos criptogramas são conhecidos.

Para alcançar o objetivo acima proposto, Matsui elaborou um modelo estatístico linear relacionando entradas e saídas das S box do DES, que em seguida é estendido para todo o algoritmo obtendo uma expressão linear não dependente de valores intermediários.

Uma vez que todas as operações no DES são lineares, exceto as efetuadas com as S box, o que se deve fazer para obter uma aproximação linear do algoritmo é obter uma tal aproximação para as S box.

As relações necessárias para se obter aproximação linear para que um ataque com criptoanálise linear é possível são as seguintes:

  1. escolhe-se um subconjunto dos bits da entrada da S box analisada, dentre 26 valores possíveis e calcula-se a paridade (operação de "ou exclusivo") dos mesmos;
  2. escolhe-se um subconjunto dos bits da saída da S box analisada, dentre 24 valores possíveis e calcula-se a paridade paridade (operação de "ou exclusivo") dos mesmos;
  3. a análise acima é repetida até que todos os subconjuntos de entrada e saída sejam verificados;
  4. os valores acima são tabelados de tal forma que as linhas da tabela contenham os subconjuntos possíveis de entrada, enquanto as colunas contem os subconjuntos possíveis de saída;
  5. as entradas desta tabela representaram o número de vezes que para um dado subconjunto de bits de entrada, a paridade do mesmo é igual a paridade do subconjunto de bits de saída correspondente;
  6. o ataque por criptoanálise linear será tão mais eficaz quanto o valor da entrada se afastar do valor 32 (metade do número de entradas de uma S box);

Matsui e Biham adotam a convenção de subtrair 32 unidades de cada entrada da tabela, o que faz com que a uma entrada de valor zero correspondam a entrada 32 como descrito anteriormente.

Através do estudo de Matsui conclui-se quanto mais afastado do valor zero, em outras palavras, quanto maior o valor absoluto de uma entrada da tabela, tão mais provável o sucesso de um ataque.

De modo semelhante ao estudo da criptoanálise diferencial, a cada entrada na tabela está associada uma probabilidade. Portanto pode-se facilmente concluir que se de uma análise for verificado que um dado conjunto analisado tem probabilidade ½ o ataque não funcionará.

Neste ponto é conveniente esclarecer qual a relação da análise feita nas S box com a chave utilizada no algoritmo, a qual, em última instância, é o elemento do qual deseja-se obter o valor.

Para estabelecer a relação acima referida, é utilizado o enunciado contido no trabalho de Matsui no item "princípio da criptoanálise linear":

"O propósito da criptoanálise linear é descobrir a seguinte expressão linear "efetiva" para um dado algoritmo:

P [i1, i2,..., ia] Å C[j1, j2,..., jb] = K[k1, k2, ..., kc], (1)

onde i1, i2,..., ia, j1, j2,..., jb, k1, k2, ..., kc denotam posição fixas de bits, e a equação (1) mantém-se válida com probabilidade p diferenet de 1/2 para uma mensagem em claro P escolhida ao acaso e correspondente à cifra C. A magnitude de | p-1/2 | representa o quão correta pode ser a expressão (1)".

Isso significa que se for calculado o "XOR" de um conjunto de bits de uma mensagem, o "XOR" de um conjunto de bits do criptograma e então calcular o "XOR" do resultado será obtido um bit o qual é o resultado do "XOR" de um conjunto de bits da chave.

Para inferir-se bits da chave são utilizadas mensagens conhecidas e respectivos criptogramas em uma amostragem suficientemente grande . Quanto mais dados são analisados, mais confiável serão as suposições relativas a chave.

O ataque básico é usar a melhor aproximação linear para o DES com dezesseis iterações. Serão necessários 247 blocos de texto conhecidos para inferir-se o valor de um bit. Um segundo bit também é obtido intercambiando cifra e texto em claro, executando o algoritmo em ordem inversa (decifrando). Este não é um resultado útil, porém há refinamentos.

Um possível refinamento é utilizar quatorze dos dezesseis passos do DES, iniciando no passo dois e indo até o passo 15. Considerando os passos 2 e 15 e utilizando os algoritmos e expressões matemáticas enunciadas no trabalho do Matsui é possível inferir quatorze bits da chave. Sendo que os restantes quarenta e dois bits são determinados por exaustão das possibilidades.

Dos estudos de Matsui, para determinação dos quatorze bits da chave são necessários a aplicação de uma série de lemas e expressões matemáticas que relacionam bits da chave procurada, bits da cifra, bits do texto em claro e finalmente bits do resultado da última função de iteração. São utilizados dois algoritmos com a finalidade de inferir os valores corretos dos bits utilizados nas expressões. Como ilustração, abaixo está transcrito a expressão na qual é baseada a inferência dos valores dos quatorze bits da chave do DES de dezesseis iterações é a seguinte:

PH[7,18,24] Å PL[12,16] Å CH[15] Å CL[7,18,24,29] Å F16(CL,K16)[15] =

K1[19,23]
Å K3[22] Å K4[44] Å K5[22] Å K7[22] Å K8[44] Å K9[22] Å K11[22] Å K12[44] Å K13[22] Å K15[22]. (2)

Onde:

Biham, em seu trabalho demonstra que o formalismo aplicado a criptoanálise diferencial pode ser aplicado criptoanálise linear. Biham define uma característica para aplicação à análise linear. Embora seu uso seja similar ao feito na criptoanálise diferencial, a segunda difere da primeira nas regras de concatenação de n características.

A última parte do trabalho de Matsui apresenta algumas conclusões para ataque que faz uso apenas de criptogramas, sendo o mesmo bem sucedido (com complexidade inferior ao que seria necessário por exaustão da chave).

A criptoanálise linear é fortemente dependente da estrutura da das S box. No caso particular do DES, o algoritmo do mesmo não é otimizado contra este tipo de ataque. Como expresso por Matsui em seu trabalho contido no Eurocript's 94, a proteção oferecida pelas S box escolhidas para o DES é da ordem de 9 a 16% contra a criptoanálise linear.

De acordo com o que declarou Don Coppersmith (membro da equipe que projetou o DES), resistência a criptoanálise linear "não fez parte dos critérios do DES". Segundo Schneier "ou eles (projetistas do DES) não conheciam este técnica ou conheciam algo mais poderoso o qual teve precedência no projeto". O trabalho original de Matsui foca especificamente a criptoanálise do DES, no entanto a técnica é extensiva a cifradores de blocos similares.