DES, A codificação com chave secreta

A 15 de Maio de 1973 o NBS (National Institute of Standards and Technology) lançou um apelo no Federal Register (o equivalente, nos Estado-Unidos, do Diário da República, em Portugal) para a criação de um algoritmo de codificação que respondesse aos seguintes critérios:

• possuir um elevado nível de segurança ligado a uma chave pequena que sirva para a codificação e descodificação
• ser compreensível
• não depender da confidencialidade do algoritmo
• ser adaptável e económico
• ser eficaz e exportável

No final de 1974, a IBM propõe “Lucifer” que, graças ao NSA (National Security Agency), é alterada a 23 de Novembro de 1976 para dar origem ao DES (Data Encryption Standard). O DES foi finalmente aprovado em 1978 pelo NBS. O DES foi normalizado pelo ANSI (American National Standard Institute) sob o nome de ANSI X3.92, mais conhecido sob a denominação DEA (Data Encryption Algorithm).

Princípio do DES

Trata-se de um sistema de codificação simétrico por blocos de 64 bits, dos quais8 bits (um octet) servem de teste de paridade (para verificar a integridade da chave). Cada bit de paridade da chave (1 em cada 8 bits) serve para testar um dos bytes da chave por paridade ímpar, quer dizer que cada um dos bits de paridade é ajustado de forma a ter um número ímpar “de 1” no byte a que pertence. A chave possui então um comprimento “útil” de 56 bits, o que significa que só 56 bits servem realmente no algoritmo.

O algoritmo consiste em efetuar combinações, substituições e permutações entre o texto a codificar e a chave, fazendo de modo a que as operações possam fazer-se nos dois sentidos (para a descodificação). A combinação entre substituições e permutações chama-se código produzido.

A chave é codificada em 64 bits e formada por 16 blocos de 4 bits, geralmente notados k₁ à k₁₆. Já que “apenas” 56 bits servem efectivamente para calcular, podem existir 2⁵⁶ (quer dizer 7.2*10¹⁶) chaves diferentes!

O algoritmo do DES

As grandes linhas do algoritmo são as seguintes:

• Fraccionamento do texto em blocos de 64 bits (8 octetos);
• Permuta inicial dos blocos;
• Corte dos blocos em duas partes: esquerda e direita, nomeadas G e D;
• Etapas de permuta e de substituição repetidas 16 vezes (chamadas voltas);
• Recolamento das partes esquerda e direita, seguidamente permutação inicial inversa.

Fraccionamento do texto

Permutação inicial

Inicialmente, cada bit de um bloco é sujeito à permuta inicial, podendo ser representada pela matriz de permuta inicial (notada PI) seguinte:

Esta matriz de permutação indica, percorrendo a matriz da esquerda para a direita e seguidamente de cima para baixo, que o 58º bit do bloco de texto de 64 bits reaparece em primeira posição, o 50º em segunda posição e assim sucessivamente.

Cisão em blocos de 32 bits

Uma vez realizada a permuta inicial, o bloco de 64 bits é cindido em dois blocos de 32 bits, notados respectivamente G e D (para esquerda e direita, a notação anglo-saxónica é L e R para Left and Right). Marcamos como G₀ e D₀ o estado inicial destes dois blocos:

É interessante observar que G₀ contém todos os bits que possuem uma posição par na mensagem inicial, enquanto D₀ contém os bits de posição ímpar.

Rondas

Os blocos G_n e D_n são sujeitos a um conjunto de transformações iterativas chamadas voltas, esclarecidas neste esquema, e cujos detalhes são dados abaixo:

Função de expansão

Os 32 bits do bloco D₀ são estendidos até 48 bits graças a uma tabela (matriz) chamada tabela de expansão (marcada como E), na qual os 48 bits são misturados e 16 dentre eles são duplicados:

Assim, o último bit de D₀ (quer dizer, o 7º bit do bloco de origem) torna-se o primeiro, o primeiro torna-se o segundo,…
Além disso, os bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 e 29 de D₀ (respectivamente 57,33,25, l, 59,35,27,3,6l, 37,29,5,63,39,31 e 7 do bloco de origem) são duplicados e disseminados na matriz.

OU exclusivo com a chave

A matriz resultante de 48 bits é chamada D'₀ ou E[D₀]. O algoritmo procede seguidamente a um OU exclusivo entre a primeira chave K₁ e E[D₀]. O resultado deste OU exclusivo é uma matriz de 48 bits que chamaremos D₀ por conveniência (não se trata do D₀ do início!).

Função de substituição

D₀é cindido seguidamente em 8 blocos de 6 bits, notado D_0i. Cada um destes blocos passa por funções de selecção (chamadas às vezes caixas de substituição ou funções de compressão), marcadas geralmente como S_i.
Os primeiros e últimos bits de cada D_0idetermina (em binário) a linha da função de selecção, os outros bits (respectivamente 2,3,4 e 5) determinam a coluna. A selecção da linha, fazendo-se sobre duas bits, dá 4 possibilidades (0,1,2,3). A seleção da coluna que se faz-se em 4 bits tem 16 possibilidades (0 a 15). Graças a esta informação, a função de selecção “selecciona” um valor codificado em 4 bits.

Eis a primeira função de substituição, representada por uma matriz de 4 por 16:

Suponhamos que D₀₁ é igual a 101110. Os primeiros e últimos bits dão 10, quer dizer, 2 binário. Os bits 2,3,4 e 5 dão 0111, quer dizer 7 binário. O resultado da função de selecção é então o valor situado na linha n°2, na coluna n°7. Trata-se do valor 11, ou em binário 111.

Cada um dos 8 blocos de 6 bits passou na função de selecção correspondente, o que dá no final 8 valores de 4 bits cada um. Eis as outras funções de selecção:

Cada bloco de 6 bits assim é substituído num bloco de 4 bits. Estes bits são agrupados para formar um bloco de 32 bits.

Permuta

O bloco de 32 bits obtido é por último submetido a uma permuta P cuja tabela é a seguinte:

OU Exclusivo

O conjunto destes resultados em saída de P é sujeito a um OU Exclusivo com o G₀ de partida (como indicado no primeiro esquema) para dar D1, enquanto o D₀ inicial dá G₁.

Iteração

O conjunto das etapas precedentes (voltas) é reiterado 16 vezes.

Permuta inicial inversa

No fim das iterações, os dois blocos G₁₆ e D₁₆ são recolados, e seguidamente sujeitos à permuta inicial inversa:

O resultado à saída é um texto codificado de 64 bits!

Geração das chaves

Dado que o algoritmo do apresentado acima é público, toda a segurança assenta na complexidade das chaves de codificação.

O algoritmo abaixo mostra como obter, a partir de uma chave de 64 bits (composta de 64 caracteres alfanuméricos quaisquer) 8 chaves diversificadas de 48 bits cada uma que servem no algoritmo do DES :

Inicialmente, os bits de paridade da chave são eliminados a fim de obter uma chave com um comprimento útil de 56 bits.

A primeira etapa consiste numa permuta notada CP-1 , cuja matriz é apresentada abaixo:

Esta matriz pode, com efeito, escrever-se sob forma de duas matrizes G_i e D_i (para esquerda e direita) compostas cada um de 28 bits:

Marca-se como G₀ e D₀o resultado desta primeira permuta.

Estes dois blocos sofrem seguidamente uma rotação à esquerda, de tal maneira que os bits em segunda posição tomam a primeira posição, os em terceira posição a segunda,…Os bits em primeira posição passam para última posição.

Os 2 blocos de 28 bits são agrupados seguidamente num bloco de 56 bits. Este passa por uma permuta, notada CP-2, fornecendo em saída um bloco de 48 bits, representando a chave K_i.

Iterações do algoritmo permitem dar as 16 chavesK₁ à K₁₆ utilizadas no algoritmo de DES.

TDES, uma alternativa ao DES

Em 1990, Eli Biham e Adi Shamir afinaram a criptanálise diferencial que procura pares de texto normal e pares de texto codificados. Este método funciona até um número de voltas inferior a 15, ora um número de 16 voltas está um presente no algoritmo apresentado acima.

Por outro lado, mesmo se uma chave de 56 bits dá um número enorme de possibilidades, numerosos processadores permitem calcular mais de 106 chaves por segundo; assim, utilizados paralelamente num elevado número de máquinas, é possível para um grande organismo (um Estado, por exemplo) encontrar a chave certa…

Uma solução a curto prazo consiste em encadear três codificação DES com a ajuda de duas chaves de 56 bits (o que equivale a uma chave de 112 bits). Este método é chamado Triplo DES, notado TDES (às vezes 3DES ou 3-DES).

O TDES permite aumentar significativamente a segurança, contudo tem o inconveniente essencial de pedir igualmente mais recursos para a codificação e descodificação.

Distinguem-se habitualmente vários tipos de codificação tripla DES :

• DES-EEE3 :3 codificações DES com 3 chaves diferentes;
• DES-EDE3 : uma chave diferente para cada uma das 3 operações DES (codificação, descodificação, codificação);
• DES-EEE2 et DES-EDE2 : uma chave diferente para a segunda operação (descodificação).

Em 1997 o NIST lançou um novo apelo para um projecto de elaboração do AES (Advanced Encryption Standard), um algoritmo de codificação destinado a substituir o DES.

O sistema de codificação DES foi actualizado todos os 5 anos. Em 2000, aquando da última revisão, após um processo de avaliação que durou 3 anos, o algoritmo concebido conjuntamente por dois candidatos belgas, Vincent Rijmen e Joan Daemen, foi escolhido como novo standard pelo NIST. Este novo algoritmo baptizado RIJNDAEL devido aos seus inventores, substituirá doravante o DES.

Mais informações

• http://csrc.nist.gov/encryption/tkencryption.html - Especificações dos algoritmos DES do TDES e do AES (síte do NIST);
• RFC 2420 RFC 2420 The PPP Triplo- da Encriptação Protocol (3DESE)