|
Data Encryption Standard
 Nota: "DES" redireciona para este artigo. Para a moeda internacional criada pelo FMI, veja Direitos especiais de saque.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 DESAs 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 NSAEm 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ãoApesar 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,
Cronologia
Algoritmos alternativosPreocupaçõ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 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 GeralA 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 FeistelA função-F, representada na figura 2, opera na metade do bloco (32 bits) de cada vez e consiste de 4 estágios: 
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 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áliseEmbora 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 brutaPara 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.  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-brutaExistem 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.
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 215.8 textos puros conhecidos com uma complexidade de tempo de 229.2 (Biham et al, 2002). ReferênciasLigações externas |
