Criptoanálise Diferencial

A técnica de criptoanálise diferencial foi apresentada ao público em 1990 como resultado do trabalho dos pesquisadores Eli Biham e Adi Shamir.

Pode-se dizer que esta técnica foi "redescoberta" por Shamir e Biham pois a mesma já era conhecida em 1974 pelos pesquisadores que elaboraram o algoritmo do DES (Data Encryption Standard). O motivo pelo qual este conhecimento fora mantido por quase vinte anos em segredo foi (segundo um dos membros da equipe que projetou o DES) de segurança nacional dos Estados Unidos.

O método utilizado por Biham e Shamir baseia-se em ataque por mensagens escolhidas, as quais são tomadas aos pares e cuja diferença entre os respectivos criptogramas é analisada. O método pode ser estendido para ataque de mensagens conhecidas.

Neste ponto, faz-se necessário definir o termo "diferença" utilizado neste estudo. Entende-se por "diferença" a operação de "ou exclusivo" entre dois n-gramas. O uso da palavra "diferença" com a significação enunciada aplica-se, em especial, ao estudo de cifradores de bloco como o DES e similares.

A criptoanálise é realizada sobre pares de criptogramas cifrados com a mesma chave e cujos textos em claro correspondentes possuem um certo valor particular de diferença. O efeito desta diferença é analisado através das n iterações do algoritmo resultando em parâmetros que permitem inferir possíveis valores da chave utilizada no processo de criptografia.

Estes parâmetros são expressos analiticamente através de probabilidades, as quais são usadas como indicadores para tomada de decisão de qual chave foi utilizada para cifrar a mensagem criptoanalisada.

O método fornece como resultado um conjunto de probabilidades associadas respectivamente a um conjunto de chaves. A decisão pela chave correta é feita escolhendo-se aquela cuja probabilidade é a de maior valor. Caso haja duas ou mais chaves com probabilidade igual, será necessário analisar mais pares de criptogramas.

O resultado da criptoanálise de um algoritmo iterativo é a determinação da sub chave do último passo do algoritmo. No caso do DES, são 48 bits, o que significa que os 8 bits restantes podem ser determinados por exaustão dos 2 8 valores restantes.

Um parâmetro básico da criptoanálise linear, definido por Biham e Shamir, é a CARACTERíSTICA. A definição formal dada por Biham envolve alguns conceitos não aprofundados neste trabalho, no entanto Biham fornece uma definição do conceito de característica, classificada por ele próprio com "informal" , a qual é transcrita a seguir.

Característica: Associado a qualquer par de cifras estão: o valor do "XOR" dos textos em claro correspondentes as cifras; o "XOR" entre as cifras; o "XOR" entre os valores das entradas de cada passo do algoritmo (em duas execuções do mesmo); o "XOR" dos valores das saídas (em duas execuções distintas do algoritmo) de cada passo do algoritmo . Estes valores de "XOR" formam uma característica de "n iterações". A característica possui associada a ela um probabilidade, a qual é a probabilidade de um par, selecionado ao acaso cujo resultado da operação "XOR" é conhecido, ter especificados na característica os valores "XOR" resultantes dos passos intermediários do algoritmo e das cifras. O símbolo associado a característica é o W.

Em suma, a característica é um parâmetro que descreve como certas diferenças entre pares de mensagens em claro podem provocar a ocorrência de certas diferenças nos pares resultantes do processo de cifração, com certa probabilidade p.

Em determinados casos, diferentes características, associadas as passos intermediários distintos de um algoritmo, podem ser associadas num único parâmetro com uma única probabilidade que será igual (supondo a passos intermediários independentes) ao produto das probabilidades intermediárias. Características com essa propriedade são denominadas características iterativas.

Duas outras definições feitas por Biham são as de par correto e par errado.

Par correto é um par de texto em claro o qual satisfaz a característica, enquanto par errado é par que não satisfaz a característica.

Um par correto fornecerá indicadores para a determinação da chave correta para o iteração analisada enquanto um par errado apenas indicará uma chave aleatória.

A determinação da chave correta resulta da análise continuada de pares de texto em claro e as correspondentes características. Com a repetição dos testes a chave correta aparecerá mais freqüentemente que as outras possibilitando a sua determinação.

Para a determinação de todos os 48 bits (para o DES) da subchave do último passo do algoritmo, existem problemas consideráveis. Primeiro, as chances de serem determinados todos os bits da subchave em um número de repetições que seja menor que aquele correspondente a exaustão da chave são pequenas. Em outras palavras, até que sejam acumulados dados suficientes para determinação da subchave correta dentre todas as opções que emergem como prováveis, a ordem de grandeza da complexidade da pesquisa pode se igualar ao valor correspondente ao que se obtém varrendo-se todos os valores possíveis de subchave.

Devido ao problema descrito acima fica claro a dificuldade computacional que é envolvida para a determinação da subchave. Seria necessário, considerando o pior caso, a utilização de ponteiros em número suficiente para serem associados a diferentes probabilidades de 248 subchaves.

Para superar os inconvenientes mencionados, Biham e Shamir utilizaram o seguinte refinamento do ataque: ao invés de utilizar a característica associada aos dezesseis passos do DES, os pesquisadores optaram por utilizar a característica referente a apenas treze iterações e completando o ataque com alguns recursos matemáticos. Uma vez obtidos os "candidatos" a chave correta, os mesmos são testados imediatamente sem a necessidade de acumular valores de contadores. Obviamente que o fato de se executar a análise em menos passos faz com que haja um universo menor de possíveis chaves a considerar, no entanto, apesar deste inconveniente, esta ainda é uma opção adequada, uma vez que permite um número de testes inferior ao teste por exaustão. Vale a pena lembrar que sempre existe a possibilidade de se determinar a chave com exatidão imediatamente.

A tabela abaixo mostra os melhores resultados de ataques contra o DES com variáveis números de iterações. A primeira coluna mostra o número de iterações. A segunda coluna mostra o número de mensagens escolhidas. A terceira coluna mostra o número de mensagens conhecidas que precisam ser levantadas para realizar um ataque. A quarta coluna mostra o número de mensagens da terceira coluna que realmente são examinadas. A última coluna representa a complexidade da análise após as mensagens serem descobertas.

 

Número de iterações

Mensagens escolhidas

Mensagens conhecidas

Mensagens analisadas

Complexidade da análise

8

214

238

4

221

9

224

244

2

232

10

224

243

214

215

11

231

247

2

232

12

231

247

221

221

13

239

252

2

232

14

239

251

229

229

15

247

256

27

237

16

247

255

236

237

Resultados de ataque ao DES pela técnica da cripoanálise diferencial

O melhor ataque contra o DES de dezesseis iterações requer 247 mensagens escolhidas. é possível converter esse tipo de ataque em outro baseado em mensagem conhecida, porém o mesmo irá requerer 255 mensagens conhecidas. O número de operações necessárias é de 237.

O ataque baseado em criptoanálise diferencial age contra algoritmos tais como o DES que possuam S box constantes. A análise depende fortemente da estrutura da S box. No caso particular do DES, o ataque possui a mesma complexidade seja qual for o modo de operação que o algoritmo esteja (ECB, CBC, CFB e OFB).

A resistência de um cifrador de blocos pode ser melhorada através do aumento do número de iterações. Utilizando o exemplo do DES: caso seja usada uma variante do DES com dezessete ou dezoito iterações o ataque terá a mesma magnitude de um ataque de força bruta. Com dezenove iterações ou mais o ataque por criptoanálise diferencial se torna inviável pois a ordem de grandeza do número de operações necessárias para descobrir a chave é maior que o número de mensagens possíveis (264).