Histórico
Ainda na década de sessenta, consciente de que num futuro não muito longínquo haveria uma explosão nas comunicações de dados, a IBM deu início a estudos de métodos para sua proteção. Estes estudos culminaram, em 1971, com o desenvolvimento do algoritmo LUCIFER por Horst Feistel e seu grupo, e que chegou a ser usado pelo Lloyds Bank of London.
A versão definitiva do DES foi elaborada, entre 1972 e 1974, por um grupo gerenciado por Walter Tuchman, um veterano da IBM e especialista em teoria da informação, disciplina essencial para a moderna criptografia (criptografia computacional). Eles partiram do LUCIFER, pretensamente com o objetivo de eliminar suas fraquezas. Nesta época, todos os critérios obtidos no trabalho de Tuchman foram tornados secretos por interferência da NSA (National Security Agency), o multibilionário e supersecreto braço criptológico do governo americano.
Mesmo após uma turbulenta polêmica, onde de um lado estavam a IBM (criadora do algoritmo) e a NSA , e do outro lado a comunidade acadêmica americana, liderada por Martin Hellman e Whitfield Diffie, ambos de Stanford, o DES foi adotado pelo NBS (National Bureou of Standards), em 1978, para uso pelos órgãos governamentais não militares nem diplomáticos, desde que sua implementação fosse em hardware, e sua utilização ficasse restrita à cifragem de dados não confidenciais. Em 1981, foi adotado com o nome de DEA (Data Encryption Algorithm) pela ANSI (American Standard Institution), com objetivo de padronizar os procedimentos de cifragem do segmento privado, em especial as instituições financeiras.
Com isso, o DES se transformou no principal e mais difundido algoritmo de chave única do mundo e o único até hoje a se transformar em padrão.
Descrição
O DES é um ciframento composto que cifra blocos de 64 bits (8 caracteres) em blocos de 64 bits, para isso ele se utiliza de uma chave composta por 56 bits mais 8 bits de paridade (no total são 64 bits também). Assim, para cada chave, o DES faz substituição monoalfabética sobre um alfabeto de 264 (» 1,8x1019) letras. A rigor, é uma substituição monoalfabética, mas as técnicas publicadas de quebra de substituições monoalfabéticas se aplicam apenas a alfabetos pequenos.
Basicamente o DES funciona através dos seguintes passos:
As substituições no DES são conhecidas como S-boxes (Caixas S - caixas de substituição) e são especificadas em 8 tabelas onde entram blocos de 6 e saem blocos de 4 bits. O primeiro e o último bit são tomados como se fossem um número de 2 bits, formando assim as linhas das tabelas das caixas S. Os bits 2 a 5 agrupados formam um vetor de 0 a 15.
Passa-se a ter, então, uma tabela onde a primeira linha é formada por números decimais que podem ser representados por 4 bits (os quatro bits do meio dos 4 bits de entrada), e a primeira coluna é formada por números decimais que possam ser representados em 2 bits (os bits dos extremos do bloco de 6 bits de entrada). Para cada uma das caixas S, a combinação dos 4 bits do meio com os 2 bits das pontas fornecerá 4 bits conforme a tabela da caixa.
Segurança do DES
No caso do DES, várias tentativas de quebra (criptoanálise) já foram feitas e publicadas. O DES pode ser quebrado pelo método da “força bruta”, tentando-se todas as combinações possíveis para a chave. Como a chave é de 56 bits, tem-se um total de 256 chaves possíveis, ou aproximadamente 1017 possibilidades.
Porém, Diffie e Hellman conjeturam a construção de uma máquina especial a 1012 ciframentos por segundo, que exauriria as possibilidades em um dia; a máquina conteria 106 chips, cada chip examinando uma parte diferente do espaço de chaves. A máquina custaria em torno de 20 milhões de dólares, com um custo diminuído para algumas centenas de milhares de dólares até o final da década de 80.
A questão da segurança do DES criou polêmica desde sua criação. Existem muitas especulações, inclusive sobre a existência de uma trap door (“porta dos fundos” - uma entrada por onde seria mais fácil o deciframento por parte do governo americano através da NSA) e também a respeito do número de bits da chave, do número de interações, do formato das caixas S e uma série de problemas que foram apontados já na época da publicação do algoritmo e até bem pouco tempo atrás ainda não passavam de especulações.
Chaves Fracas
Por causa da modificação inicial que a chave sofre, transformando-se em duas subchaves que são usadas em partes diferentes do algoritmo, o DES corre o risco de trabalhar com as chamadas chaves fracas.
Inicialmente o valor da chave é dividido em duas metades as quais vão sofrer deslocamentos separadamente. Se todos os bits de cada metade forem 0 ou 1, então a chave usada para qualquer ciclo do algoritmo será a mesma usada para qualquer outro ciclo do algoritmo. Isto pode ocorrer se a chave for inteiramente formada por 1 ou inteiramente por 0 ou metade por 1 e metade por 0.
Com isso, existem pares de chaves [A, B] onde A cifra um texto em claro e tanto A quanto B são capazes de decifrar o criptograma cifrado por A.
Tamanho das Chaves
Quando a IBM criou o LUCIFER, ele tinha uma chave de 128 bits. Alguns anos depois, quando da criação e padronização do DES a chave utilizada para algoritmos criptográficos caiu para 58 bits. Muitos criptólogos da época argumentaram que deveria ser aumentado o número de bits da chave para dificultar a utilização do método da força bruta.
Em 1981, Diffie e Hellman disseram que, com a evolução da tecnologia computacional, principalmente no que diz respeito a capacidade de armazenamento e de processamento, no ano de 1990 o DES seria um algoritmo completamente inseguro. E realmente, em 1990, uma dupla de israelenses, Biham e Shamir, descobriram e publicaram uma técnica nova: a criptoanálise diferencial (que será explicada posteriormente neste capítulo).
Número de Interações
Através dos anos, existiram vários ataques bem sucedidos contra variantes do DES com poucas interações. Em 1982 o DES foi facilmente quebrado com 4 interações, alguns anos depois o mesmo ocorreu para 6 interações. A teoria de Shamir e Biham explica que o DES com menos de 16 bits é mais facilmente quebrado pelo método do texto conhecido do que pela força bruta.
Estrutura das caixas S
Além da acusação de reduzir o tamanho da chave, a NSA foi também acusada da modificação da estrutura das caixas S. Vários criptólogos chegaram a conclusão que a NSA desenhou as caixas S para esconder uma trap door, deixando uma porta aberta apenas para eles entrarem.
Criptoanálise Diferencial
Em 1990, Eli Biham e Adi Shamir, ambos israelenses, introduziram o termo differential cryptanalysis (ou, criptoanálise diferencial). Era lançado um novo método de criptoanálise através do qual Biham e Shamir mostravam uma maneira de quebrar o DES com maior eficiência do que o método da força bruta.
A criptoanálise diferencial procura por pares de textos em claro e pares de textos cifrados. Especificamente, o ataque examina os pares cifrados: pares de textos cifrados cujo os textos em claro têm certas particularidades. Os dois textos em claro podem ser escolhidos randomicamente, até que se satisfaçam as tais condições particulares, e o criptoanalista não necessita saber seus valores.
Certas diferenças presentes nos pares de textos em claro têm alta probabilidade de se repetirem nos pares de textos cifrados. A isto chama-se características. Por exemplo, se a diferença entre dois pares de texto em claro em hexadecimal é 0080 8200 6000 0000, então (ignorando a permutação inicial do DES) depois de três interações provavelmente a diferença continua a mesma. Biham e Shamir encontraram várias características semelhantes. A criptoanálise diferencial usa estas características para aumentar as possibilidades de encontrar a possível chave ou, eventualmente, encontrar a chave. Porém este é um ataque estatístico e poderá falhar em alguns casos.
Este tipo de ataque funciona bem contra o DES ou qualquer outro tipo de algoritmo que utilize uma estrutura de caixas S semelhante a do DES.
Maiores informações poderão ser encontradas no arquivo que se encontra neste mesmo diretório, em formato DOC do Word 6.0, referente ao Projeto de Diplomação realizado no segundo semestre de 1995. O nome do arquivo é projabnt.doc