DEAL

Em Criptografia, DEAL (Data Encryption Algorithm with Larger blocks) é um algoritmo de cifra de blocos simétrica construído baseado em um outro, conhecido como DES (Data Encryption Standard). Proposto inicialmente por Lars Knudsen em 1998, e, posteriormente, submetido ao AES Contest por Richard Outerbridge, o DEAL não avançou às finais do concurso, como já se era esperado, pois foram encontradas falhas de segurança graves, além de que seu tempo de execução, comparado com os demais candidatos, era muito alto, próximo ao do Triple-DES.

Diz-se que o DEAL é uma rede de Feistel que usa o DES como função de turno, em inglês, round function. Seu funcionamento se dá com blocos de 128 bits, e com as chaves podendo ter tamanhos iguais a 128, 192 ou 256 bits. Nos casos em que o tamanho da chave é igual a 128 ou a 192 bits, o DEAL realiza 6 turnos para cifrar ou decifrar a mensagem, e no caso de a chave possuir tamanho igual a 256 bits, o algoritmo realiza 8 turnos.

Introdução

O DES é um algoritmo de cifra de blocos que utiliza chaves de tamanho igual a 64 bits, dos quais 56 são realmente utilizados, e o restante . Possui estrutura de uma rede de Feistel, e realiza 16 turnos de maneira iterativa para criptografar a mensagem original .

Segundo e , um dos problemas que podem ser apontados no DES é o tamanho da chave, considerado pequeno atualmente, pois alguns softwares conseguiram quebrar sua criptografia, por meio de buscas exaustivas pela chave, ou seja tentando todas as chaves possíveis.

Esta falha foi superada com o 3-DES, ou Triple-DES, que consiste em criptografar a mensagem 3 vezes usando o DES e chaves diferentes a cada vez. Entretanto, ainda assim o algoritmo é vulnerável a um ataque conhecido como "Chave Relacionada", em inglês, related-key attack, com tempo de execução próximo ao ataque no DES original .

Proposto em 1999 por Lars Knudsen, o DEAL é uma rede de Feistel com R turnos, sendo o DES a função de turno do algoritmo, e utiliza blocos de tamanho igual a 128 bits e a chave tem tamanho variando entre 128, 192 ou 256 bits. O autor do projeto é professor no departamento de matemática aplicada e ciência da computação na universidade técnica de Denmark, e sua página com informações de contato pode ser acessada em .

Segundo para chaves de tamanho 128 ou 192 bits, é recomendado usar R = 6, isto é, realizar 6 turnos do algoritmo, e R = 8 no caso de a chave ter 256 bits de tamanho, e seu tempo de execução é próximo do Triple-DES. O DEAL foi um dos algoritmos que concorreram no AES contest.

Este concurso foi promovido para eleger um algoritmo para substituir o DES. O algoritmo não avançou às finais, pois foi considerado lento e algumas falhas graves de segurança foram apontadas.

Algoritmos semelhantes ao DEAL, são conhecidos por serem cifras de Luby-Rackoff. Isso se deve ao fato de que Michael Luby e Charles Rickoff demonstraram uma forma eficiente de se construir funções pseudo-aletórias, de maneira bastante eficiente, utilizando uma rede de feistel de 3 ou 4 turnos.

Um algoritmo semelhante ao DEAL também caiu em desuso, pois foram encontradas falhas de segurança. Este algoritmo é conhecido como Ladder-DES e alguns artigos como provam as falhas encontradas.

Princípios do projeto

O algoritmo DES foi tido como seguro durante algum tempo, e considerado como algoritmo padrão de criptografia pela NIST (National Institute of Standards and Technology). Entretanto, com o avanço da tecnologia foi possível explorar falhas do algoritmo, tais como encontrar a chave por meio de tentativa e erro, ou seja testar todas as chaves possíveis até encontrar a correta, dado que o tamanho desta é 56 bits e, posteriormente, publicações demonstravam como quebrar a criptografia do algoritmo em menos e um dia .

Por volta de 1999, a NIST anunciou a intenção de substituir o DES, dando lugar a um outro algoritmo que receberia o nome de AES (Advanced Encryption Standart), motivando a criação de vários outros algoritmos que buscavam suprir as falhas que eram apontadas, como o DEAL. Além disso, nesta época, a NIST se mostrou ciente de que levaria alguns anos até que o AES estivesse pronto para uso e, por conta disso, o Triple-DES foi reconhecido como algoritmo oficial .

Esta atitude da NIST, de aprovar o Triple-DES como algoritmo oficial para criptografia, motivou a criação do DEAL, uma vez que ele pode ser entendido como um aprimoramento do DES e executa com tempo similar ao do Triple-DES, utiliza conceitos conhecidos, explicados mais adiante, e seguros, além de que ele oferece meios para aumentar o tamanho da chave, visando se prevenir de ataques de força bruta, ainda que a tecnologia avançasse bastante, e, portanto, poderia vir a ser o algoritmo padrão.

Estrutura de funcionamento

O DEAL é uma cifra de blocos de tamanho igual a 128 bits, que fornece três opções para o tamanho, em bits, da chave: 128, 192 ou 256, denominados DEAL-128, DEAL-192 ou DEAL-256. Sua estrutura é de uma rede de Feistel, explicada a seguir, que utiliza como função de turno o algoritmo DES, também explicado a seguir.

Um turno do DEAL funciona da seguinte forma:

• Divide a entrada em duas partes de mesmo tamanho L e R;
• Seja NL o resultado da aplicação do DES em L;
• recebe R ⊕ NL;
• Retorne R || L, em que || significa concatenação.

A saída de um turno é a entrada do próximo, com exceção do último, cuja saída é o texto cifrado.

Rede de Feistel

Rede de Feistel, em inglês Feistel Network, é uma construção especifica para esquemas de criptografia simétrica e foi descrita primeiramente por Horst Feistel durante seu trabalho na cifra de Lúcifer, predecessora do DES, na IBM .

Uma rede de Feistel define uma função F: $\{0,1\}^{2n}$ → $\{0,1\}^{2n}$ parametrizada por um número inteiro D, geralmente entre 12 e 16, que é a quantidade de turnos a serem executados. Cada turno utiliza uma função, denominada função de turno, definida por f : $\{0,1\}^{n}$ → $\{0,1\}^{n}$. A figura 1 descreve o processo de encriptação e decriptação de uma rede de Feistel:

Encriptação e Decriptação em uma rede de Feistel

Formalmente, um turno i ∈ [1, D], da rede de Feistel pode ser descrito da seguinte forma:

1. Divida a entrada em duas partes de mesmo tamanho, denominadas $L_{i-1}$ e $R_{i-1}$;
2. Aplique a função de turno à metade direita, denominada $f_{i}(R_{i-1})$;
3. Faça um XOR bit a bit da metade esquerda com $f_{i}(R_{i-1})$;
4. Gere $R_{i-1}$ || $L_{i-1}$ ⊕ $f_{i}(R_{i-1})$ , em que || indica concatenação.

Inicialmente, $L_{0}$ é a metade esquerda da entrada e $R_{0}$ a metade direita;

A saída de um turno é a entrada do seguinte, com exceção do último, cuja saída é o resultado esperado.

DES - Data Encryption Standard

O DES, algoritmo base para o DEAL, também é uma rede de Feistel de 16 turnos e seu funcionamento, simplificado, está descrito pelo pseudo-código a seguir:

Entrada:

• T: 64 bits de texto em claro
• $k_{1},k_{2},...,k_{16}$ chaves para cada turno

Saída:

• C: texto cifrado de 64 bits

inicio
T ← IP(T) //IP = Permutação Inicial
$L_{0}$ ← T >> 32
$R_{0}$ ← T & 0xFFFF
para r = 1 a R faça:
    $L_{r}$ ← $R_{r-1}$
    $R_{r}$ ← $L_{r-1}$ ⊕ $f(R_{r-1},K_{r})$
fim_para
X ← $R_{r}$ << 32 & $L_{r}$
retorne FP(X) //FP = Permutação Final
fim_algoritmo

Funcionamento do algoritmo

Segundo , o funcionamento do DEAL pode ser explicado, utilizando o modo de operação ECB, de acordo com a figura 2, que mostra a estrutura de um dos R turnos que são executados:

Estrutura de um dos R turnos do DEAL

Neste caso, $E_{j}$ é a função usada no turno j, que corresponde ao DES aplicado a $X_{j-1}^{A}$ com a chave $K_{j}$. Neste caso $X_{j-1}^{A}$ é a parte esquerda da entrada e $X_{j-1}^{B}$ a parte direita. Formalmente, define-se a estrutura de funcionamento da seguinte forma:

1. Seja $E_{b}(A)$ a encriptação em 64 bits de A com a chave b usando o DES;
2. Seja $X_{i}^{L}$ a metade esquerda do texto no turno i;
3. Seja $X_{i}^{R}$ a metade direita do texto no turno i;

Divide-se o texto em claro P em blocos de 128 bits, denominados $P_{1},P_{2},P_{3},...,P_{n}$. A rotina de geração de chaves, definida mais adiante, recebe um conjunto de S chaves como entrada e retorna R chaves para o DES, denominadas $K_{1},K_{2},K_{3},...,K_{R}$.

Para cada bloco executa-se o seguinte procedimento, para cada bloco i, com i variando de 1 a n:

inicio
Inicialmente define-se $X_{0}^{L}=P_{i}^{L}$ e $X_{0}^{R}=P_{i}^{R}$;
Para todo j de 1 à r executa-se os seguintes passos:
     $X_{j}^{L}$ = $E_{K_{j}}(X_{j-1}^{L})$ ⊕ $X_{j-1}^{R}$;
     $X_{j}^{R}$ = $X_{j-1}^{L}$.
fim_para
$C_{i}=X_{r}^{L}$ || $X_{r}^{R}$, em que || significa concatenação.
Retorne $C_{i}$
fim_algoritmo

A rotina, retirado de , de modo geral, para criação das R chaves necessárias está descrita a seguir:

1. Receba como entrada S chaves para o DES: $SK_{1},SK_{2},...,SK_{S}$;
2. Seja DK uma chave para aplicação do algoritmo DES;
3. Expanda as S chaves para R chaves, com operações ⊕ (XOR) entre elas e uma nova constante para cada repetição, usando as S chaves de maneira cíclica, isto é, use-as na sequência e volte ao começo quando a sequência acabar;
4. Criptografe as R chaves com o DES em modo CBC com IV (Initial value) igual a zero e aplicado com a chave DK;
5. O resultado destas criptografias formam o conjunto de chaves do DEAL.

Em particular, esta rotina funciona de três formas diferentes, uma para cada um dos três tamanhos de chave do DEAL, e estão especificados a seguir:

Para chave de tamanho 128 bits é construída uma chave para cada um dos 6 turnos:

• $K_{1}=E_{DK}(SK_{1})$;
• $K_{2}=E_{DK}(SK_{2}$ ⊕ $K_{1})$;
• $K_{3}=E_{DK}(SK_{1}$ ⊕ 1 ⊕ $K_{2})$;
• $K_{4}=E_{DK}(SK_{2}$ ⊕ 2 ⊕ $K_{3})$;
• $K_{5}=E_{DK}(SK_{1}$ ⊕ 4 ⊕ $K_{4})$;
• $K_{6}=E_{DK}(SK_{2}$ ⊕ 8 ⊕ $K_{5})$.

Desta forma, para chave de tamanho igual a 128 bits é necessário a escolha de S = 2 chaves para o DES, além da chave DK.

Para chave de tamanho 192 bits é construída uma chave para cada um dos 6 turnos:

• $K_{1}=E_{DK}(SK_{1})$;
• $K_{2}=E_{DK}(SK_{2}$ ⊕ $K_{1})$;
• $K_{3}=E_{DK}(SK_{3}$ ⊕ $K_{2})$;
• $K_{4}=E_{DK}(SK_{1}$ ⊕ 1 ⊕ $K_{3})$;
• $K_{5}=E_{DK}(SK_{2}$ ⊕ 2 ⊕ $K_{4})$;
• $K_{6}=E_{DK}(SK_{3}$ ⊕ 4 ⊕ $K_{5})$.

Desta forma, para chave de tamanho igual a 192 bits é necessário a escolha de S = 3 chaves para o DES, além da chave DK.

Para chave de tamanho 256 bits é construída uma chave para cada um dos 8 turnos:

• $K_{1}=E_{DK}(SK_{1})$;
• $K_{2}=E_{DK}(SK_{2}$ ⊕ $K_{1})$;
• $K_{3}=E_{DK}(SK_{3}$ ⊕ $K_{2})$;
• $K_{4}=E_{DK}(SK_{4}$ ⊕ $K_{3})$;
• $K_{5}=E_{DK}(SK_{1}$ ⊕ 1 ⊕ $K_{4})$;
• $K_{6}=E_{DK}(SK_{2}$ ⊕ 2 ⊕ $K_{5})$;
• $K_{7}=E_{DK}(SK_{3}$ ⊕ 4 ⊕ $K_{6})$;
• $K_{8}=E_{DK}(SK_{4}$ ⊕ 8 ⊕ $K_{7})$.

Desta forma, para chave de tamanho igual a 256 bits é necessário a escolha de S = 4 chaves para o DES, além da chave DK.

Segundo , as constantes foram incluídas para evitar chaves fracas, pois caso estas não estivessem presentes todas as subchaves poderiam ser iguais, por exemplo, suponha para o DEAL-128 as chaves $SK_{1}=SK_{2}=D_{k}(0)$ geraria 6 subchaves iguais a zero.

Criptoanálise

Segundo , o DEAL está vulnerável aos seguintes ataques:

1. Meet-in-the-middle;
2. Ataque de texto em claro escolhido para a versão de 6 turnos;
3. Ataque de texto cifrado escolhido ao DEAL-192;
4. Ataque de chaves relacionadas ao DEAL-192 e 256.

Segundo , o ataque Meet-in-the-middle pode ser aplicado para recuperar as chaves utilizadas nos turnos do DEAL. O autor do algoritmo, Lars Knudsen, em , explica que o ataque pode ser feito, embora demande um alto processamento computacional e muito tempo para se conseguir. Para a versão de 6 turnos são necessárias $(2^{56})^{3}=2^{168}$ encriptações, e para a versão de 8 turnos são necessárias $(2^{56})^{4}=2^{224}$ encriptações. Desta forma, devido a quantidade de memória necessária, este ataque não poderia ser feito com a tecnologia atual.

Segundo , o ataque de texto cifrado escolhido pode ser aplicado ao DEAL para qualquer tamanho de chave, uma vez que é possível mostrar que para quebrar a criptografia gerada a partir de uma rede de Feistel de N bits com 5 ou 6 turnos, que utiliza uma função de turno que gera uma permutação de $2*N$ bits verdadeiramente aleatória, requer o conhecimento de pelo menos $2^{2*N/3}$ textos em claro e suas cifras correspondentes. Desta forma, ele enuncia a seguinte proposição: "Existe um ataque ao DEAL de 6 turnos independente do tamanho da chave, que necessita de $2^{121}$ encriptações usando DES e $2^{70}$ textos em claro escolhidos".

Segundo , para este ataque são necessários $2^{32+r}$ textos cifrados escolhidos, com r ∈ ]0,32], podendo ser um número real.

Uma vez que este ataque é realizado ao DEAL-192, o número de turnos é igual a seis. Desta forma, considere os últimos quatro turnos $R_{3},R_{4},R_{5},R_{6}$. Seja a entrada destes o par $(x_{2},y_{2})$ ∈ $\{0,1\}^{64}$ e a saída o par $(x_{6},y_{6})$ ∈ $\{0,1\}^{64}$. Considere dois pares de entrada e saída $(x_{2},y_{2})$, $(x_{6},y_{6})$ e $(x_{2}^{'},y_{2}^{'})$, $(x_{6}^{'},y_{6}^{'})$ com $y_{6}=y_{6}^{'}$, $x_{2}$ ⊕ $x_{2}^{'}$ = α = $x_{6}$ ⊕ $x_{6}^{'}$.

Entretanto, esses dois pares de entrada e saída não podem existir, pois: uma vez que α = $x_{6}$ ⊕ $x_{6}^{'}$ e $y_{6}=y_{6}^{'}$, temos que $x_{5}$ ⊕ $x_{5}^{'}$ = α = $x_{4}$ ⊕ $x_{4}^{'}$ e, então, $y_{4}$ ⊕ $y_{4}^{'}$ ≠ 0. Por outro lado, uma vez que $x_{3}$ ⊕ $x_{3}^{'}$ = α = $x_{2}$ ⊕ $x_{2}^{'}$, e $x_{5}$ ⊕ $x_{5}^{'}$ = α = $x_{4}$ ⊕ $x_{4}^{'}$, seria necessário que $y_{3}$ ⊕ $y_{3}^{'}$ = 0. O que é uma contradição com $y_{4}=y_{3}$ e $y_{4}^{'}=y_{3}^{'}$.

Desta forma, é possível explorar a não existência destes pares para recuperar as chaves:

1. Escolha um valor $y_{6}$ = $y_{6}^{'}$ ∈ $\{0,1\}^{64}$ e $s=2^{32+r}$ ∈ $\{0,1\}^{64}$ valores diferentes, gerando $2^{32+r}$ textos cifrados diferentes $(s,y_{6})$. Considere dois textos cifrados $(x_{6},y_{6})$ e $(x_{6}^{'},y_{6}^{'})$ com $x_{6}$ ≠ $x_{6}^{'}$ e os correspondentes textos cifrados $(x_{0},y_{0})$ e $(x_{0}^{'},y_{0}^{'})$;
2. Para todas as possíveis chaves R, compute $y_{1}=y_{0}$ ⊕ $E_{R}(x_{0})$ e $y_{1}^{'}=y_{0}^{'}$ ⊕ $E_{R}(x_{0}^{'})$;
3. Para todas as possíveis chaves S, compute $x_{2}=x_{1}$ ⊕ $E_{S}(y_{1})$ e $x_{2}^{'}=x_{1}^{'}$ ⊕ $E_{S}(y_{1}^{'})$. Se $x_{2}$ ⊕ $x_{2}^{'}=x_{6}$ ⊕ $x_{6}^{'}$, então o par $(R,S)$ pode ser descartado, ou seja $(R_{1},R_{2})$ ≠ $(R,S)$. Se $(R,S)$ é um par errado, espera-se atingir o par correto com probabilidade $2^{-64}$. Uma vez que temos $2^{32+r}$ textos cifrados escolhidos e assim ${2^{32+r} \choose {2}}$ conjuntos com exatamente dois textos cifrados, e espera-se que $1-2^{-2*r}$ pares descartados, logo se r = 0.5, espera-se descartar 50% dos pares.

Segundo , há ainda um ataque possível de se fazer ao DEAL quando as chaves possuem tamanhos 192 ou 256. Neste ataque, detecta-se chaves quase equivalentes às chaves originais. Isto pode ser feito da seguinte forma: dado três pares de textos em claro e cifrados, suponha que o par de chaves $(K,K^{*})$ seja quase equivalente aos pares originais. É possível determinar se este par possui esta propriedade, ou seja de ser quase equivalente, com um custo de $2^{64}$ e utilizando $3*2^{56}$ alocações de memória. Montamos algo muito parecido com o ataque Meet-in-the-middle utilizado para quebrar o 2-DES (uma variante do algoritmo DES, que utiliza duas chaves do DES para encriptar a mensagem).

Exemplo prático

Devido às falhas de segurança e ao tempo de execução, o DEAL não avançou às finais do concurso do AES, e, por conta disso, não há exemplos práticos de uso deste algoritmo.

Algoritmos semelhantes, tais como Ladder-DES, também não têm aplicações práticas que podem ser descritas aqui.

Entretanto, é possível implementar o DEAL, uma vez que há bibliotecas que implementam o DES. Fica a cargo do programador definir as rotinas de geração das chaves para o DES. Feito isso, pode-se usar o código, implementado em Java, a seguir como base para a construção do algoritmo:

Cipher enc = Cipher.getInstance("DES/ECB/PKCS5Padding");

SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
byte chaveBytes[] = {(byte)0xf3,(byte)0xf1,(byte)0x10,(byte)0x56,
 (byte)0x89,(byte)0x23,(byte)0x07,(byte)0x43};

DESKeySpec dks = new DESKeySpec(chaveBytes);

SecretKey chave = skf.generateSecret(dks); 

	String[] DESkeys = constructKeysForDES();

enc.init(Cipher.ENCRYPT_MODE, chave);

String input;
input = entrada();

String []blocos128bit = quebraBlocos(input);
int tamanho_chave = getKeyLength();
int turnos = getTurnos(tamanho_chave);
String[] chaves = geraChaves(tamanho_chave, DESkeys);

ArrayList<String>cifrados = new ArrayList<>();

for (int i = 0 ; i < blocos128bit.length ; ++i)
{
	String x0 = esquerda(blocos128bit[i]);
	String y0 = direita(blocos128bit[i]);
	
	for (int j = 0; j < turnos; ++j)
	{
		String auxiliar = y0;
		y0 = XOR(enc.update(x0.getBytes(), 0, x0.getBytes().length), y0);
		x0 = auxiliar;
	}
	cifrados.add(y0 + x0);
}

Conclusões

O DEAL foi excluído da competição para a escolha do AES por apresentar falhas de seguranças graves conforme foi discutido. Isso implica que o algoritmo foi deixado de lado e atualmente não é possível encontrar aplicações nem implementações deste.

Embora o DEAL tenha algumas provas de segurança, outros ataques puderam ser feitos para quebrar a sua segurança, partindo do princípio de que a tecnologia atual tem poder para executar um número de operações bastante elevado, que permite quebrar criptografias que no passado eram consideradas seguras, avanço este que motivou o concurso para a substituição do DES.

Algoritmos como o Ladder-DES, que é muito semelhante ao DEAL por usar blocos de 128 bits e usar o DES como função de turno para a rede de Feistel, também caíram em desuso por apresentarem falhas de segurança, o que torna mais complicado encontrar aplicações que implementam algoritmos semelhantes ao DEAL.

Inclusive o autor do algoritmo Lars Knudsen não possui nada sobre o algoritmo em sua página.

Desta forma, apesar de usar conceitos bastante conhecidos, o DEAL, embora seja imune a ataques de força bruta, parte de premissas, cujas falhas podem ser exploradas por um atacante, e o torna vulnerável a ataques de texto em claro ou cifrado escolhido.