Movatterモバイル変換


[0]ホーム

URL:


Saltar para o conteúdo
Wikipédia
Busca

Data Encryption Standard

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado deDES)
Esta página cita fontes, mas não cobrem todo o conteúdo
Esta páginacita fontes, mas quenão cobrem todo o conteúdo. Ajude ainserir referências (Encontre fontes:ABW  • CAPES  • Google (notícias • livros • acadêmico)).(Junho de 2016)
 Nota: "DES" redireciona para este artigo. Para a moeda internacional criada pelo FMI, vejaDireitos especiais de saque.

OData Encryption Standard (DES) é algoritmo criptográfico simétrico selecionado comoFIPS oficial (Federal Information Processing Standard) pelo governo dosEUA em 1976 e que foi utilizado em larga escala internacionalmente.Oalgoritmo era inicialmente controverso, com um pequenotamanho de chave e suspeitas de umbackdoor daNSA. O DES foi estudado academicamente e motivou os sistemas modernos de entendimento dacriptoanálise. O DES é atualmente considerado inseguro para muitas aplicações. Isto se deve principalmente a pequena chave de 56-bit. Em Janeiro de 1999 adistributed.net e aElectronic Frontier Foundation juntas violaram uma chave DES em 22 horas e 15 minutos (veja nacronologia). 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 de3DES embora existam ataques teóricos. Recentemente o DES foi substituído peloAES.

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

História do DES

[editar |editar código-fonte]

As origens do DES remontam ao início da década de 1970. Em 1972, após concluir um estudo sobre as necessidades desegurança de informação do governo norte-americano, o então NBS (National Bureau of Standards), atualmente conhecido comoNIST (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, em15 de Maio de1973, após uma consulta àNSA, o NBS solicitou proposta para umalgoritmo 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 em27 de Agosto de1974. Desta vez, aIBM 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 deHorst 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 andBryant Tuckerman.

O envolvimento da NSA

[editar |editar código-fonte]

Em17 de Março de1975 o DES foi publicado noRegistro 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 eWhitfield Diffie. Eles criticavam o pequeno tamanho dachave 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 deEli Biham eAdi Shamir sobrecriptoaná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 comSteven Levy, as pesquisas da IBM descobriram ataques decriptoaná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 acriptoaná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 de64 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 porforça bruta uma chave de 56 bits vários anos antes do que o resto do mundo.

O algoritmo como padrão

[editar |editar código-fonte]

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 comoFIPS PUB 46, autorizado a ser utilizado.Foi subseqüentemente reafirmado como padrão em 1983, 1988 (revisado comoFIPS-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 peloAES (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 aNIST 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 porforç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çaBruce 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.)HTMLPDF

Cronologia

[editar |editar código-fonte]
DataAnoEvento
15 de Maio1973NBS publica o primeiro pedido para um algoritmo de criptografia padrão.
27 de Agosto1974NBS publica o segundo pedido para algoritmos de ecriptação.
17 de Março1975O DES é publicado noRegistro Federal dos EUA.
Agosto1976Primeiro seminário.
Setembro1976Segundo seminário, discutindo fundamentos matemáticos do DES.
Novembro1976DES é definido como padrão
15 de Janeiro1977DES é publicado como FIPS padrão FIPS PUB 46.
1983DES é reafirmado pela primeira vez.
1986Videocipher II, um sistema de cifragem de um satélite de TV baseado em DES começa a ser utilizado pela HBO.
22 de Janeiro1988DES é confirmado pela segunda vez como FIPS 46-1, substituindo o FIPS PUB 46.
Julho1990Biham e Shamir modificam acriptoanálise diferencial, e aplicam isso a um sistema de criptação.
1992Biham e Shamir relatam o primeiro ataque teórico com menos complexidade do que força bruta:criptoanálise diferencial.
30 Dezembro1993DES é reafirmado pela terceira vez como FIPS 46-2.
1994A primeira criptoanálise experinental do DES é feita usandocriptoanálise linear (Matsui, 1994).
Junho1997OProjeto DESCHALL intercepta uma mensagem criptografada com DES pela primeira vez em público.
Julho1998AEFF'sDES cracker viola uma chave DES em 56 horas.
Janeiro1999Juntas,Deep Crack edistributed.net violam uma chave DES em 22 horas e 15 minutos.
25 de Outubro1999DES é reafirmado pela quarta vez como FIPS 46-3, com especificações do uso preferencial doTriplo DES, com o DES simples permitido apenas em sistemas legais.
26 Novembro2001AAES(Criptografia padrão avançada) é publicada.
26 de Maio2002A AES padrão se torna efetiva.
26 de Julho2004A retirada do FIPS 46-3 é proposta noRegistro Federal.[1]
19 de Maio2005NIST retira o FIPS 46-3
15 de Março2007A 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

[editar |editar código-fonte]

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 andFEAL. 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. NaURSS o algoritmoGOST 28147-89 foi introduzido, com um bloco de 64 bits e chave de 256 bits, que mais tarde foi utilizada naRú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 o3DES (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 é aDES-X, que aumenta o tamanho da chave fazendo umXOR 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, oAES (Advanced Encryption Standard), como substituto ao DES. O algoritmo que foi selecionado como o AES foi enviado por seus criadores sob o nomeRijndael. Outros finalistas na competição do NIST incluemRC6,Serpent,MARS eTwofish.

Descrição

[editar |editar código-fonte]
Figura 1 — A estrutura geral do Feistel no DES

DES é umarede de Feistel com chave de 56 bits e mensagens de 64 bits, usando 16 rodadas e oitoS-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 é de32 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-seS-boxes, típicas deredes de substituição-permutação, como parte da função interna desta rede de Feistel). EstasS-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 ummodo 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

[editar |editar código-fonte]

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

[editar |editar código-fonte]

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

Figura 2 —A função Feistel (função-F) do DES
  1. Expansão - o bloco de 32 bits (metade do bloco) é expandido para 48 bits usando apermutação expansiva, representada peloE no diagrama, através da duplicação de alguns bits.
  2. Mistura de chaves - o resultado é combinado com umasubchave usando uma operação XOR. Dezesseis subchaves de 48 bits - uma para cada round - são derivadas da chave principal utilizando oescalonamento de chaves (descrito abaixo).
  3. Substituição - após trocar a subchave, o bloco é dividido em oito pedaços de 6 bits antes do processamento pelobox de substituição ouS-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 umalookup table. Os s-boxes fornecem o núcleo da segurança do DES - sem eles, a cifra seria linear e quebrada de forma trivial.
  4. Permutação - finalmente, as 32 saídas das S-boxes são rearranjadas de acordo com uma permutação fixa, oP-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 porClaude Shannon nos anos 1940 como uma condição necessária para uma cifragem prática e segura.

Escalonamento de chaves

[editar |editar código-fonte]
Figura 3 — O escalonamento de chave no DES

A figura 3 ilustra oescalonamento 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 aTroca 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

[editar |editar código-fonte]

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

[editar |editar código-fonte]

Para qualquer algoritmo de criptografia, o método de ataque mais básico é aforç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 aNSA 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 aNSA 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áquinaCOPACOBANA (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, aCOPACOBANA é constituída decircuitos integrados reconfiguráveis (FPGA) comercialmente disponíveis e de baixo custo. 120 dessesFPGAs do tipo XILINX Spartan3-1000 funcionam em paralelo. Eles são agrupados em 20 módulosDIMM, cada um contendo 6FPGAs. 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 doCOPACOBANA é 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

[editar |editar código-fonte]

Existem três ataques conhecidos que podem quebrar todos os 16 ciclos do DES com menos complexidade que a busca porforç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 eNSA. Para quebrar todos os 16 ciclos, a criptoanálise diferencial necessita de 247 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 243 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 (241 ao invés de 243). 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 239 – 241 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 250 textos puros conhecidos, tem uma complexidade computacional de 250, 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. Acriptoaná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ências

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

Ligações externas

[editar |editar código-fonte]
Obtida de "https://pt.wikipedia.org/w/index.php?title=Data_Encryption_Standard&oldid=64703006"
Categoria:
Categorias ocultas:

[8]ページ先頭

©2009-2025 Movatter.jp