Data Encryption Standard

O Data Encryption Standard (DES) é algoritmo criptográfico simétrico selecionado como FIPS oficial (Federal Information Processing Standard) pelo governo dos EUA em 1976 e que foi utilizado em larga escala internacionalmente. O algoritmo era inicialmente controverso, com um pequeno tamanho de chave e suspeitas de um backdoor da NSA. O DES foi estudado academicamente e motivou os sistemas modernos de entendimento da criptoanálise. O DES é atualmente considerado inseguro para muitas aplicações. Isto se deve principalmente a pequena chave de 56-bit. Em Janeiro de 1999 a distributed.net e a Electronic Frontier Foundation juntas violaram uma chave DES em 22 horas e 15 minutos (veja na cronologia). Também existem alguns resultados analíticos, obtidos teoricamente, que demonstram a fragilidade da cifra, no entanto são improváveis de se montar na prática. Acredita-se que o algoritmo seja seguro na forma de 3DES embora existam ataques teóricos. Recentemente o DES foi substituído pelo AES.

Em alguns documentos, uma distinção é feita entre o DES como um padrão, e o algoritmo, referido como o DEA(o Data Encryption Algorithm).

História do DES

As origens do DES remontam ao início da década de 1970. Em 1972, após concluir um estudo sobre as necessidades de segurança de informação do governo norte-americano, o então NBS (National Bureau of Standards), atualmente conhecido como NIST (National Institute of Standards and Technology), na época o órgão de padrões do governo norte-americano) identificou a necessidade de um padrão governamental para criptografia de informações não confidenciais, porém sensíveis. Em conseqüência, em 15 de Maio de 1973, após uma consulta à NSA, o NBS solicitou proposta para um algoritmo de criptografia que atendesse a critérios rigorosos de projeto. Entretanto, nenhuma das propostas recebidas se mostrou viável. Uma segunda solicitação foi aberta em 27 de Agosto de 1974. Desta vez, a IBM submeteu uma proposta candidata que foi considerada aceitável: um algoritmo de criptografia desenvolvido no período de 1973-1974 baseado num algoritmo mais antigo, o algoritmo Lúcifer de Horst Feistel. A equipe da IBM envolvida no projeto do algoritmo incluía Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith and Bryant Tuckerman.

O envolvimento da NSA

Em 17 de Março de 1975 o DES foi publicado no Registro Federal. Foram pedidos comentários públicos e no ano seguinte ocorreram dois seminários para discutir. Houve diversas críticas incluindo por parte dos pioneiros da "Criptografia de chave pública", Martin Hellman e Whitfield Diffie. Eles criticavam o pequeno tamanho da chave e os misteriosos "S-boxes" como uma evidência de interferência da NSA no design do algoritmo. Houve a suspeita de um possível enfraquecimento no algoritmo de forma que a NSA (e somente ela) pudesse ler facilmente as mensagens criptografadas.^[1] No entanto, em 1978, o Comitê de Inteligência dos EUA concluiu que o algoritmo poderia funcionar com o pequeno tamanho de chave e que estava provado que o DES estava livre de fragilidades estatísticas e matemáticas. Foi concluído também que a NSA não teve envolvimento no desenvolvimento do algoritmo. A IBM inventou e desenvolveu o algortimo, tomando todas as deciões pertintentes e concordou que o tamanho da chave seria mais do que o suficiente para aplicações comerciais do DES. Outro membro da equipe desenvolvedora, Walter Tuchman afirmou que a NSA nunca esteve envolvida no desenvolvimento do algoritmo.

A suspeitas sobre a fragilidade nas "S-boxes" foram acalmadas em 1990 com a descoberta independente e publicação aberta de Eli Biham e Adi Shamir sobre criptoanálise diferencial, um método genérico de quebra de criptografia. Os "S-boxes" eram muito mais resistentes à ataques do que se eles fossem selecionados aleatoriamente, sugerindo fortemente que a IBM sabia da técnica antes de 1970.Isto foi motivo de uma publicação em 1994 de Don Coppersmith para os "S-boxes".De acordo com Steven Levy, as pesquisas da IBM descobriram ataques de criptoanálise diferencial e pediram para que a NSA mantivesse a técnica secreta.^[2] Coppersmith explicou a decisão secreta da IBM dizendo que "era porque a criptoanálise diferencial poderia ser uma ferramente muito potente usada contra muitos esquemas, e havia preocupação de que algumas informações em domínio público poderia afetar significativamente a segurança nacional." Levy citou Walter Tuchman : "Eles nos pediram para selar todos os documentos confidencialmente…Nos de fato colocamos um número em cada e lacramos eles em cofres."

A outra crítica — que o tamanho da chave era muito pequeno — foi apoiado pelo fato de que o motivo dado pela NSA para reduzir o tamanho da chave de 64 bits para 56 foi que os outros 8 bits poderiam servir como bits de paridade. Acreditou-se que a decisão da NSA foi motivada pela possibilidade de que eles poderiam atacar por força bruta uma chave de 56 bits vários anos antes do que o resto do mundo.

O algoritmo como padrão

Apesar das diversas críticas, DES foi aprovado pelo governo dos EUA como padrão em 1976 e publicado em 15 de janeiro de 1977 como FIPS PUB 46, autorizado a ser utilizado. Foi subseqüentemente reafirmado como padrão em 1983, 1988 (revisado como FIPS-46-1), 1993 (FIPS-46-2), e novamente em 1999 (FIPS-46-3), o último prescrito "Triplo DES". Em 26 de Maio de 2002, DES foi finalmente substituído pelo AES (Advanced Encryption Standard|AES) após uma competição pública. Mesmo assim até 2004 os restos do DES continuaram a ser utilizados em larga escala. Em 19 de Maio de 2005, FIPS 46-3 foi oficialmente substituído, mas a NIST aprovou o "Triplo DES" até o ano 2030 para informações sensíveis do governo.

Um outro ataque teórico, criptoanálise linear, foi publicado em 1994, mas foi um ataque por força bruta em 1998 que demonstrou que o DES poderia ser atacado e exaltou a necessidade de um algoritmo que substituísse o DES.

A introdução do DES é considerada catalisadora para o estudo acadêmico da criptografia, particularmente de métodos de quebra de blocos de cifragem. De acordo com uma retrospectiva da NIST sobre o DES,

O DES pode ser considerado o lançamento inicial de um estudo e desenvolvimento não militar de algoritmos de criptografia. Em 1970 havia muito poucos métodos de criptografia, a não ser os em organizações militares e de inteligência, e muito pouco estudo acadêmico sobre criptografia. Atualmente há muitos acadêmicos estudando criptografia, departamentos matemáticos com programas poderosos em criptografia, e segurança em informações comerciais de companhias e consultores. Uma geração de cripto-analistas perdeu noites de sono analisando (ou seja, tentando "crackear") o algoritmo DES. Nas palavras do especialista em segurança Bruce Schneier (Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267). "O DES fez mais pelo campo de criptoanálise do que qualquer outro. Agora há um algoritmo para estudar." Uma quantidade incrível da literatura sobre criptografia nos anos 1970 e 80 discutiam sobre o DES, e o DES é o algoritmo base para qualquer comparação entre algoritmos de chave simétrica. (William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology: A Chronicle of Selected NBS/NIST Publications, 1901–2000.)HTML PDF

Cronologia

Data	Ano	Evento
15 de Maio	1973	NBS publica o primeiro pedido para um algoritmo de criptografia padrão.
27 de Agosto	1974	NBS publica o segundo pedido para algoritmos de ecriptação.
17 de Março	1975	O DES é publicado no Registro Federal dos EUA.
Agosto	1976	Primeiro seminário.
Setembro	1976	Segundo seminário, discutindo fundamentos matemáticos do DES.
Novembro	1976	DES é definido como padrão
15 de Janeiro	1977	DES é publicado como FIPS padrão FIPS PUB 46.
	1983	DES é reafirmado pela primeira vez.
	1986	Videocipher II, um sistema de cifragem de um satélite de TV baseado em DES começa a ser utilizado pela HBO.
22 de Janeiro	1988	DES é confirmado pela segunda vez como FIPS 46-1, substituindo o FIPS PUB 46.
Julho	1990	Biham e Shamir modificam a criptoanálise diferencial, e aplicam isso a um sistema de criptação.
	1992	Biham e Shamir relatam o primeiro ataque teórico com menos complexidade do que força bruta: criptoanálise diferencial.
30 Dezembro	1993	DES é reafirmado pela terceira vez como FIPS 46-2.
	1994	A primeira criptoanálise experinental do DES é feita usando criptoanálise linear (Matsui, 1994).
Junho	1997	O Projeto DESCHALL intercepta uma mensagem criptografada com DES pela primeira vez em público.
Julho	1998	A EFF's DES cracker viola uma chave DES em 56 horas.
Janeiro	1999	Juntas, Deep Crack e distributed.net violam uma chave DES em 22 horas e 15 minutos.
25 de Outubro	1999	DES é reafirmado pela quarta vez como FIPS 46-3, com especificações do uso preferencial do Triplo DES, com o DES simples permitido apenas em sistemas legais.
26 Novembro	2001	A AES(Criptografia padrão avançada) é publicada.
26 de Maio	2002	A AES padrão se torna efetiva.
26 de Julho	2004	A retirada do FIPS 46-3 é proposta no Registro Federal. [1]
19 de Maio	2005	NIST retira o FIPS 46-3
15 de Março	2007	A máquina paralela de FPGA da Universidade de Bochum e Kiel, Alemanha, viola o DES em aproximadamente seis dias e meio por um custo de $10,000 em hardware.

Algoritmos alternativos

Preocupações sobre a segurança e a operação relativamente lenta do DES motivou pesquisadores a propor uma variedade de alternativas para a cifragem em bloco, que começaram a aparecer no final dos anos 1980 e início dos anos 1990. Alguns exemplos podem ser citados, como: RC5, Blowfish, NewDES, SAFER, CAST5 and FEAL. A maioria deles mantêm o tamanho de bloco de 64 bits do DES, e portanto funcionam como substituição ao DES se necessário, embora usem tipicamente uma chave de 64 ou 128 bits. Na URSS o algoritmo GOST 28147-89 foi introduzido, com um bloco de 64 bits e chave de 256 bits, que mais tarde foi utilizada na Rússia.

Até mesmo o próprio DES pode ser adaptado para ser usado de modo mais seguro. Muitos ex-usuários de DES agora utilizam o 3DES (também conhecido como TDES) que foi descrito e analisado por um dos patenteadores do DES; este algoritmo envolve aplicar o DES três vezes com duas (2TDES) ou três (3TDES) chaves diferentes. TDES é considerada adequadamente segura, embora seja bastante lenta. Uma alternativa menos custosa computacionalmente falando é a DES-X, que aumenta o tamanho da chave fazendo um XOR antes e depois do DES. GDES é uma variante do DES proposta de forma a aumentar a velocidade da criptografia, mas mostrou-se suscetível à criptoanálise diferencial.

Em 2001, após uma competição internacional, NIST selecionou um novo algoritmo, o AES (Advanced Encryption Standard), como substituto ao DES. O algoritmo que foi selecionado como o AES foi enviado por seus criadores sob o nome Rijndael. Outros finalistas na competição do NIST incluem RC6, Serpent, MARS e Twofish.

Descrição

*Figura 1* — A estrutura geral do Feistel no DES

DES é uma rede de Feistel com chave de 56 bits e mensagens de 64 bits, usando 16 rodadas e oito S-boxes. Antes de aplicar a entrada na rede de Feistel, o DES realiza uma permutação inicial na entrada pela tabela IP. Esta permutação é revertida na saída da rede pela tabela FP. A figura ao lado ilustra o funcionamento do DES.

Descrevemos a função interna do DES. Como em uma rede de Feistel metade dos bits da mensagem é usado de cada vez como entrada para a função interna, a entrada é de 32 bits.

A função interna da rede de Feistel do DES funciona da seguinte maneira: os 32 bits da entrada são expandidos e permutados por E em uma string de 48 bits. Após um ou-exclusivo com a subchave, a entrada é dividida em oito S-boxes (note que usam-se S-boxes, típicas de redes de substituição-permutação, como parte da função interna desta rede de Feistel). Estas S-boxes têm 6 bits de entrada e 4 bits de saída (donde se conclui que a função usada pelo DES na rede de Feistel não tem inversa). Depois, a saída tem 8×4 = 32 bits.

Como outras cifras de bloco, o DES sozinho não é um meio seguro de criptografia, deve ser utilizado em um modo de operação. FIPS-81 especifica muitos modos para usar o DES [2] (Em inglês). Maiores comentários sobre a utilização do DES pode ser encontrado na FIPS-74 [3] (Em inglês).

Estrutura Geral

A estrutura geral do algoritmo é exibida na figura 1: Existem 16 estágios idênticos de processamento, denominados "rounds". Também existe uma permutação inicial e uma final, denominadas "IP" e "FP", que são inversas (IP "desfaz" a ação do FP, e vice-versa). IP e FP não possuem quase nenhuma significância criptográfica, mas foram incluídas, aparentemente, para facilitar a abertura e fechamento dos blocos no hardware dos anos 1970, assim como fazer o DES rodar mais lentamente em software.

Antes dos rounds principais, o bloco é dividido em duas metades de 32 bits e processado alternadamente; este cruzamento é conhecido como "esquema de Feistel". A estrutura de Feistel garante que a criptografia e descriptografia são processos bem similares - a única diferença é que as subchaves são aplicadas de modo reverso ao descriptografar, o resto do algoritmo é idêntico. Isto simplifica bastante a implementação, particularmente em hardware, já que não é necessário separar os algoritmos de encriptação e decriptação.

O símbolo vermelho ⊕ indica a operação XOR. A "função-F" bagunça metade do bloco junto com uma chave. A saída da função-F é então combinada com a outra metade do bloco, e as metades são trocadas antes do próximo round. Depois do round final, as metades não são trocadas, esta é uma características da estrutura Feistel que faz com que a criptografia e descriptografia possuam processos similares.

A Função Feistel

A função-F, representada na figura 2, opera na metade do bloco (32 bits) de cada vez e consiste de 4 estágios:

Expansão - o bloco de 32 bits (metade do bloco) é expandido para 48 bits usando a permutação expansiva, representada pelo E no diagrama, através da duplicação de alguns bits.
Mistura de chaves - o resultado é combinado com uma subchave usando uma operação XOR. Dezesseis subchaves de 48 bits - uma para cada round - são derivadas da chave principal utilizando o escalonamento de chaves (descrito abaixo).
Substituição - após trocar a subchave, o bloco é dividido em oito pedaços de 6 bits antes do processamento pelo box de substituição ou S-box. Cada um dos oito S-boxes substitui os seis bits de entrada por quatro bits de saída de acordo com uma transformação não-linear, fornecida por uma lookup table. Os s-boxes fornecem o núcleo da segurança do DES - sem eles, a cifra seria linear e quebrada de forma trivial.
Permutação - finalmente, as 32 saídas das S-boxes são rearranjadas de acordo com uma permutação fixa, o P-box.

A substituição ocorrida nos S-boxes, a permutação de bits nos P-boxes e a expansão fornecem a chamada "confusão e difusão", respectivamente, um conceito identificado por Claude Shannon nos anos 1940 como uma condição necessária para uma cifragem prática e segura.

Escalonamento de chaves

*Figura 3* — O escalonamento de chave no DES

A figura 3 ilustra o escalonamento de chave para criptografia - o algoritmo que gera as subchaves. Inicialmente, 56 bits da chave são selecionados dos 64 iniciais para a "Troca escolhida 1" (PC-1) - os oito bits restantes são, ou descartados, ou utilizados como bits de paridade. Os 56 bits são então divididos em dois blocos de 28 bits; cada metade é tratada separadamente. Em rounds sucessivos, as duas metades são rotacionadas à esquerda por um ou dois bits (especificado para cada round), e então uma subchave de 48 bits é selecionada para a Troca escolhida 2 (PC-2) - 24 bits da metade esquerda e 24 da metade direita. As rotações (representadas como "<<<" no diagrama) significam que um conjunto diferente de bits foi usado em cada subchave; cada bit é usado em aproximadamente 14 das 16 subchaves.

O escalonamento de chaves para descriptografar é similar - as subchaves estão em ordem reversa, se comparadas com a criptografia. Exceto por essa diferença, todo o processo é o mesmo da criptografia.

Segurança e criptoanálise

Embora terem sido publicadas mais informações a respeito da criptoanálise do DES em relação a outro bloco de cifragem, o ataque mais prático de se encontrar é ainda o acesso por "força bruta". Várias propriedades complementares de criptoanálise são conhecidas, e existem três possíveis ataques teóricos que, mesmo tendo uma complexidade menor se comparada à força bruta, requerem uma quantidade de conhecimentos relativamente elevada e que, portanto, não causam preocupações na prática. Apesar das críticas e fragilidades do DES, não se tem exemplo conhecido de alguém que esteja sofrendo perdas monetárias devido às suas limitações de segurança.

Ataque por força bruta

Para qualquer algoritmo de criptografia, o método de ataque mais básico é a força bruta – testando todas as combinações possíveis no turno. O tamanho da chave determina o número de combinações, e portanto, a exeqüibilidade do acesso. Para o DES, foram levantadas questões a respeito da suficiência do tamanho de sua chave (mesmo tendo sido adotado um padrão) e foi o tamanho pequeno de sua chave, frente a criptoanálises teóricas, que ditou a necessidade de mudança de seu algoritmo. É conhecido que a NSA apoiou, senão persuadiu, a IBM a reduzir o tamanho da chave de 128 para 64 bits, e depois para 56 bits; isto é tido como um indicativo de que a NSA pensava que seria capaz de quebrar as chaves deste tamanho mesmo em meados de 1970.

A DES cracker da EFF de US$250,000 que contém 1,536 chips e que pode quebrar uma chave DES em poucos dias - a foto mostra um circuito de DES Cracker com diversos chips Deep Crack.

Na academia, várias propostas de máquinas para crackear o DES foram desenvolvidas. Em 1977, Diffie e Hellman propuseram uma máquina custando US$20 milhões, na qual seria capaz de achar uma chave do DES em um único dia. De 1993, Wiener teria proposto uma máquina que seria capaz de encontrar uma chave do DES em 7 horas, pelo preço de US$1 milhão. No entanto, nenhuma destas propostas foram implementadas (pelo menos nenhuma implementação reconhecida foi publicada). A vulnerabilidade do DES foi praticamente demonstrada no final dos anos 1990. Em 1997, a RSA Security patrocinou uma série de concursos, oferecendo um prêmio de US$10.000 para a primeira equipe que conseguisse quebrar a mensagem do concurso criptografada com o DES. O concurso foi vencido pela DESCHALL Project, formada por Rocke Verser, Matt Curtin, e Justin Dolske, que usaram ciclos ociosos de milhares de computadores ao redor da Internet. A exeqüibilidade da quebra do DES rapidamente, foi demonstrada em 1998 quando uma DES-cracker foi construída pela Electronic Frontier Foundation (EFF) com um custo aproximado de US$250.000. A motivação foi para mostrar que o DES poderia ser quebrado na prática assim como na teoria. "Existem muitas pessoas que não acreditam em uma verdade enquanto elas não conseguirem ver com os seus próprios olhos. Mostrando então uma máquina física capaz de quebrar o DES em poucos dias é a única maneira de convencê-las que eles realmente não podem confiar sua segurança no DES." A máquina quebrou a chave em um período de aproximadamente 2 dias, sendo que praticamente na mesma hora pelo menos um representante da US Justice Department havia anunciado que o DES era inquebrável.

O outro único DES-cracker confirmado foi a máquina COPACOBANA (cost-optimized parallel code breaker) construída mais recente por equipes da Universities of Bochum e Kiel, ambas na Alemanha. Diferentemente da máquina da EFF, a COPACOBANA é constituída de circuitos integrados reconfiguráveis (FPGA) comercialmente disponíveis e de baixo custo. 120 desses FPGAs do tipo XILINX Spartan3-1000 funcionam em paralelo. Eles são agrupados em 20 módulos DIMM, cada um contendo 6 FPGAs. O fato do hardware ser reconfigurável faz com que a máquina possa quebrar outro tipo de código também. Um dos aspectos mais interessantes do COPACOBANA é o seu custo. Uma máquina destas pode ser construída por aproximadamente U$10,000. O custo 25 vezes menor do que a máquina da EFF é um exemplo evidente da contínua evolução dos hardwares digitais.

Ataques mais eficientes que a força-bruta

Existem três ataques conhecidos que podem quebrar todos os 16 ciclos do DES com menos complexidade que a busca por força bruta: criptoanálise diferencial (DC – Differential Cryptoanalysis), criptoanálise linear (LC - Linear Cryptanalysis) e Davies’ attack. Porém, esses ataques são teóricos e não são viáveis na prática.

Criptoanálise Diferencial foi redescoberta no final dos anos 1980 pelos israelenses Eli Biham e Adi Shamir, e mantida em segredo pela IBM e NSA. Para quebrar todos os 16 ciclos, a criptoanálise diferencial necessita de 2⁴⁷ textos puros escolhidos (quando o cracker tem a possibilidade de obter textos cifrados a partir de textos puros selecionados).
Criptoanálise Linear foi descoberta por Mitsuru Matsui, e precisa de 2⁴³ textos puros conhecidos (Matsui, 1993); o método foi implementado (Matsui, 1994), e foi a primeira experiência de criptoanálise do DES a ser reportada. Não existe evidência que o DES foi desenvolvido para ser resistente a este tipo de ataque. Uma generalização do LC – criptoanálise linear múltipla – foi sugerida em 1994 (Kaliski and Robshaw), e, depois, aperfeiçoada por Biryukov et al (2004); estas análises sugerem que aproximações lineares múltiplas podem ser usadas para reduzir em 4 vezes o número total de dados necessários para o ataque (2⁴¹ ao invés de 2⁴³). Junod (2001) realizou vários experimentos para determinar o tempo atual da complexidade da criptoanálise linear, e reportou que foi mais rápido do que o esperado, exigindo um tempo equivalente de 2³⁹ – 2⁴¹ cálculos.
Improved Davies’ attack: enquanto que a criptoanálise diferencial e linear são técnicas genéricas e podem ser aplicadas em diferentes exemplos, o Davies’ attack é uma técnica especializada em DES, sugerida primeiramente por Donald Davies nos anos 1980, e aperfeiçoado por Biham e Biryukov (1997). A forma mais poderosa do ataque necessita 2⁵⁰ textos puros conhecidos, tem uma complexidade computacional de 2⁵⁰, e 51% de sucesso.

Existem ainda outros ataques propostos para versões com menos ciclos de cifradores, como exemplo o DES com menos de 16 ciclos. A criptoanálise diferencial-linear foi proposta por Langford e Hellman em 1994, e combina a criptoanálise diferencial e linear em um único ataque. Uma versão mais poderosas pode quebrar um DES de nove ciclos com 2^15.8 textos puros conhecidos com uma complexidade de tempo de 2^29.2 (Biham et al, 2002).

Referências

↑ Schneier. Applied Cryptography, 2nd ed., 280
↑ Levy, Crypto, p. 55

Ligações externas

[1] Schneier. Applied Cryptography, 2nd ed., 280

[2] Levy, Crypto, p. 55

[1]

[2]