Padrão de criptografia de dados

DES ( padrão de criptografia de dados )

Função DES-F. resumo

Designer (s)	IBM
Primeira publicação	1975 ( 1977 para o padrão)
Derivado de	Lúcifer
Criptografia (ões) com base neste algoritmo	DES triplo , G-DES , DES-X , LOKI89 , ICE

Características

Tamanho (s) do bloco	64 bits
Comprimento (s) da chave	56 bits
Estrutura	Esquema Feistel
Número de voltas	16 voltas do DES

Melhor criptoanálise

criptanálise linear , criptoanálise diferencial , ataques de força bruta agora possíveis

O Padrão de Criptografia de Dados ( DES , pronuncia / d ɛ s /) é um algoritmo de criptografia simétrica ( codificação de bloco ) usando 56 bits de chave . Seu uso não é mais recomendado hoje, devido à sua lentidão na execução e seu espaço de chave muito pequeno permitindo um ataque sistemático em um tempo razoável. Quando ainda é usado geralmente é em Triple DES , o que não melhora seu desempenho. DES foi usado em particular no sistema de senhas UNIX .

O primeiro padrão DES é publicado pela FIPS em15 de janeiro de 1977 sob o nome de FIPS PUB 46. A última versão antes da obsolescência data de 25 de outubro de 1999.

História

Dentro Maio de 1973, o American National Bureau of Standards pede a criação de um algoritmo de criptografia que pode ser usado pelas empresas. Naquela época, a IBM já tinha um algoritmo chamado Lúcifer , projetado em 1971 por Horst Feistel .

Logicamente, esse algoritmo deveria ter sido selecionado pelo NBS. Na prática, era quase o caso: a NSA exigia que Lúcifer fosse mudado por ele. Assim foi criado o DES, que foi adotado como padrão em novembro de 1976 . Isso levantou suspeitas de que a NSA enfraqueceu intencionalmente o algoritmo, na tentativa de quebrá-lo. Estranhamente, o DES provou ser resistente a vários ataques que não eram esperados para aparecer na comunidade acadêmica até muito mais tarde. Ainda mais surpreendente, Lúcifer , ele, resistiu menos bem. Isso sugere que a NSA estava ciente, naquela época, dessas técnicas de criptoanálise e que, portanto, teria, na realidade, tornado o DES mais resistente.

Operação

O algoritmo DES transforma um bloco de 64 bits em outro bloco de 64 bits. Ele lida com chaves individuais de 56 bits, representadas por 64 bits (com um bit em cada byte sendo usado para verificação de paridade ). Este sistema de cifras simétricas faz parte da família das cifras de bloco iterativas, mais especificamente é um esquema Feistel (nomeado após Horst Feistel na origem da cifra de Lúcifer ).

Em geral, podemos dizer que o DES funciona em três etapas:

permutação inicial e fixa de um bloco (sem qualquer impacto no nível de segurança);
o resultado está sujeito a 16 iterações de uma transformação, essas iterações dependem a cada volta de outra chave parcial de 48 bits. Este turn key intermediário é calculado a partir da chave inicial do usuário (graças a uma rede de tabelas de substituição e operadores XOR ). Durante cada curva, o bloco de 64 bits é dividido em dois blocos de 32 bits, e esses blocos são trocados entre si de acordo com um esquema Feistel. O bloco de 32 bits mais significativo (aquele que se estende de 32 para 64 bits) passará por uma transformação;
o resultado da última volta é transformado pela função inversa da permutação inicial.

DES usa oito tabelas de substituição (as S-Boxes ) que foram objeto de muita controvérsia quanto ao seu conteúdo. Suspeitamos de uma fraqueza deliberadamente inserida pelos designers. Esses rumores foram dissipados no início da década de 1990 com a descoberta de criptoanálise diferencial, que demonstrou que as tabelas foram bem projetadas.

Ataques

Vários ataques foram descobertos no DES. Permitem reduzir os custos de uma procura exaustiva de chaves que equivale , em média, a operações. Alguns desses métodos não são mais eficientes com algoritmos de criptografia mais recentes devido à introdução de um efeito de avalanche . $2 ^ {{55}}$

A criptoanálise diferencial descoberta por Eli Biham e Adi Shamir em 1991 torna possível encontrar a chave usando texto simples. O princípio é ter um DES implementado em uma caixa preta hermética com uma chave secreta dentro. Ao fornecer texto suficiente como entrada, podemos analisar estatisticamente o comportamento das saídas de acordo com as entradas e encontrar a chave. As entradas usadas para este ataque devem ter uma ligeira diferença entre si (por exemplo, uma mudança de bit). Observando como a diferença afeta a saída, você pode estabelecer estatísticas e, ao aumentar o número de entradas, melhora a confiabilidade do ataque. $2 ^ {{47}}$
O T-attack (ataque de cócegas ) é uma variante da criptoanálise diferencial descoberta em 1974 durante o projeto do DES por pesquisadores da IBM. Por vinte anos, houve um silêncio completo sobre essa descoberta. Foi Don Coppersmith quem revelou o segredo em 1994. Na época, ela encorajou os designers do DES a fortalecer o conteúdo das tabelas de substituição (em vez de enfraquecê-lo como o boato sugeria).
A criptoanálise linear , inventada por Henry Gilbert e independentemente por Mitsuru Matsui em 1993, é mais eficaz, mas menos conveniente, pela simples razão de que o atacante não tem a caixa preta e não pode enviar seus próprios textos. Este ataque requer pares (todos criptografados com a mesma chave) que o invasor conseguiu recuperar de uma forma ou de outra. Consiste em fazer uma aproximação linear do DES simplificando-o. Ao aumentar o número de pares disponíveis, a precisão da aproximação é melhorada e a chave pode ser extraída. $2 ^ {{43}}$
O compromisso tempo-memória é um conceito inventado por Martin Hellman no início dos anos 1980. Supondo que a mesma mensagem será criptografada várias vezes com chaves diferentes, poderíamos calcular uma tabela enorme que contém todas as versões criptografadas dessa mensagem. Quando interceptamos uma mensagem criptografada, podemos encontrá-la na tabela e obter a chave que foi usada para codificá-la. Obviamente, esse ataque não é viável porque precisamos de uma mesa da ordem de um bilhão de GB. A genialidade de Hellman foi encontrar uma maneira de reduzir essa tabela para cerca de 1 terabyte (ou 1 milhão de vezes menos que a tabela completa), o que é factível hoje em dia.
Por outro lado, os ataques são implementações específicas e não são necessariamente específicos do DES. No caso de um DES implementado em hardware, pode-se analisar o consumo de energia e deduzir algumas informações sobre a chave (o aumento do consumo indica bits ativos ). O mesmo estilo de ataque também pode ser usado em um computador, calculando o tempo necessário para criptografar com diferentes textos ou analisando a memória usada.
Todos os outros ataques DES visam reduzir o tempo de computação de uma busca exaustiva usando máquinas projetadas especificamente para a tarefa (graças a FPGAs em paralelo, por exemplo). Essa máquina foi construída em 1998 . O Deep Crack custava cerca de US $ 200.000 e poderia quebrar a chave em menos de uma semana. A computação distribuída usando os computadores de pessoas físicas ( Distributed.net ) tem se mostrado eficaz em quebrar uma chave em menos de 24 horas .

Status

O algoritmo desenvolvido originalmente pela IBM usava uma chave de 112 bits. A intervenção da NSA reduziu o tamanho da chave para 56 bits. Hoje em dia, o Triple DES ainda é muito popular e o DES “simples” só existe em aplicativos mais antigos. O padrão DES foi substituído em 2001 pelo AES (Advanced Encryption Standard).

Notas e referências

Notas

Referências

(em) " Data Encryption Standard (DES) " [PDF] ,25 de outubro de 1999(acessado em 20 de outubro de 2015 ) .
Envolvimento da NSA no desenvolvimento do padrão de criptografia de dados
(in) Don Coppersmith , " The Data Encryption Standard (DES) e sua força contra ataques " , IBM Journal of Research and Development , Vol. 38, n o 3, Maio de 1994, p. 243 ( leia online [PDF] )

Apêndices

links externos

(pt) Um Tutorial sobre Criptoanálise Linear e Diferencial por Howard M. Heys: Documento que resume a análise linear e diferencial