Detalhes

Categoria: Cifras de bloco

Atualização: Terça, 21 Abril 2009 20:51

Autor: vovó Vicki

Acessos: 10595

O comprimento da chave

O DES foi o resultado de um aperfeiçoamento do algoritmo Lucifer criado por Horst Feistel na IBM. O tamanho da chave no Lucifer é de 128 bits e, no DES, foi reduzido para 56 bits. Foi uma gritaria geral. Muitos criptógrafos estrilaram usando o argumento de que a redução do tamanho da chave aumentava a possibilidade de ataques de força bruta terem sucesso.

Em 1979, Diffie e Hellman declararam que um computador paralelo especialmente construído para quebrar o DES poderia recuperar a chave em um dia e custaria algo em torno de US$20 milhões. Em 1984 Diffie revisou a estimativa - a chave poderia ser obtida em dois dias e o custo seria de US$50 milhões [5]. Diffie e Hellman argumentaram posteriormente que isto estaria fora do alcance de todos, exceto organizações como a NSA, mas que, ao redor de 1990, o DES seria totalmente inseguro [6]. Parece que os maiores reclamões foram Diffie e Hellman. Na época, foram considerados lunáticos insatisfeitos, mas a sequência dos acontecimentos mostrou que eram apenas críticos gabaritados alertando sobre as graves consequências de colocar todas as fichas num sistema que havia sido adequado à capacidade de computação existente há alguns anos e que evoluía a passos largos.

Enquanto a discussão prosseguia, as implementações do DES em hardware chegavam perto de um milhão de encriptações por segundo, ou seja, o que a máquina especial de Diffie e Hellman requeria. Em 1984, chips especiais que implementavam o DES já conseguiam realizar 256.000 encriptações por segundo. Três anos mais tarde, em 1987, o número de encriptações por segundo já havia dobrado e mais de um milhão de chaves por segundo podiam ser testadas... a coisa estava ficando preta.

Nesta época ninguém admitia estar construindo um "crackeador" de DES, mas há um bom argumento para supor sua existência. Numa conferência realizada em 1993, Martin Hellman falou sobre a possibilidade da existência de uma máquina para ataques de força bruta [7]:

Apesar do custo de uma máquina para realizar pesquisas no DES usando a força bruta ter caído para menos de US$10 milhões e réplicas poderem ser construídas por menos de US$1 milhão, duvido que qualquer entidade comercial tenha ou venha a construir uma dessas máquinas no futuro próximo. Esta soma em dinheiro exigiria um conluio de alto nível entre muitas pessoas e, como nenhuma empresa pode apoiar oficialmente tal espionagem, isto seria muito difícil de ser feito. Além do mais, mesmo com a máquina construída, ainda assim seria preciso interceptar os canais de comunicação de interesse.

A situação é muito diferente com a NSA e suas equivalentes estrangeiras, particularmente a francesa Direction Generale de la Securite Exterieure (DGSE), que tem se vangloriado abertamente de estar usando inteligência comercial para ajudar empresas francesas a vencer guerras de licitações para obter grandes contratos. Elas são encorajadas legalmente a fazer espionagem, têm grandes orçamentos e rotineiramente interceptam imensos volumes de dados.

Se elas construíram uma máquina de força bruta ou alguma coisa mais esperta, não sei dizer. Mas ficaria surpreso se elas não possuíssem algum tipo de máquina especial para quebrar o DES.

Nos anos de 1980, a empresa Robotron da Alemanha Ocidental fabricou centenas de milhares de chips DES para a União Soviética. Alegou que se tratava de chips cifradores para clones do IBM-PC XT. Isto leva a duas implicações: a União Soviética usou estes chips para construir um "crackeador" de DES ou a União Soviética usava o DES para encriptar suas próprias comunicações - o que significa que a NSA construiu um.

O número de iterações

Porque 16 rodadas? Porque não 32? Alan Konheim mostrou que após oito iterações o texto cifrado é essencialmente uma função randômica de cada um dos bits do texto claro e de cada bit da chave [8]. Porque, então, o algoritmo não pára depois de oito rodadas?

Com o passar dos anos, vários ataques tiveram sucesso em variações do DES com um número reduzido de rodadas. O DES com três ou quatro rodadas foi quebrado com facilidade em 1982. Alguns anos mais tarde, em 1985, o DES com seis rodadas também caiu. A explicação para tais fatos chegou em 1990, quando Biham e Shamir tornaram público um novo método de criptoanálise: a criptoanálise diferencial. De acordo com este novo método, o DES com menos de 16 rodadas podia ser quebrado com um ataque de texto claro conhecido com mais eficiência do que com um ataque de força bruta.

A estrutura das caixas de substituição (S-boxes)

Além de ser acusada de reduzir o tamanho da chave, a NSA também foi acusada de alterar o conteúdo das caixas S. Quando pressionada para explicar a estrutura das caixas S, a NSA alegou que estes elementos do algoritmo eram "sensíveis" e que não seriam tornados públicos. Diante desta recusa fica fácil entender a preocupação de muitos criptógrafos quanto à existência de uma trap door e o grande número de estudos e análises focando as caixas S.

No final de 1976, a NSA revelou vários critérios aplicados às caixas S [9]:

Nenhuma caixa S é uma função afim linear da sua entrada (input). Em outras palavras, não há um sistema de equações lineares que possa expressar quatro bits de saída em termos dos seis bits de entrada.

A alteração de um bit na entrada de uma caixa S resulta na alteração de pelo menos dois bits na saída. Isto é, as caixas S foram projetadas para maximizar o volume de difusão.

As caixas S foram escolhidas para minimizar a diferença entre o número de 1s e 0s quando qualquer um dos bit de entrada for mantido constante. Isto é, se você mantiver um determinado bit constante e alterar os outros cinco bits, a saída não deveria ter um número desproporcionalmente grande de 1s ou 0s.

Ao invés de acalmar o povo, estas revelações só fizeram aumentar as suspeitas e o debate em torno do assunto. O que não se sabia nesta época é que os critérios usados pela NSA foram utilizados apenas para tornar o algoritmo resistente a uma criptoanálise diferencial, método que só seria publicado por Biham e Shamir depois de mais de 10 anos da adoção do DES. Não foi a toa que a NSA se fechou em copas

Fontes

• Bruce Schneier, Applied Cryptography: John Wiley & Sons, 1994.
• Cracking DES no site da EFF.
• [1] D.W.Davies e W.L.Price, Security for Computer Networks, segunda edição, Nova Iorque: John Wiley & Sons, 1989.
• [2] M.S.Conn, letter to Joe Abernathy, National Security Agency, Ser: Q43-111-92, 10 Jun 1992.
• [3] D.W.Davies, "Some Regular Properties of the DES", Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, p.89-96.
• [4] M.E.Hellman, R.C.Merkle, R.Schroeppel, L.Washington, W.Diffie, S.Pohling e P.Schweitzer, "Results of an Initial Attempt to Cryptanalyze the NBS Data Encryption Standard", Technical Report SEL 76-042, Information Systems Lab., Department of Electrical Engeneering, Stanford University, 1976.
• [5] W.Diffie, "Cryptographic Technology: Fifteen Year Forecast", BNR Inc., Jan 1981.
• [6] M.E.Hellman, "DES Will Be Totally Insecure Within Ten Years", IEEE Spectrum, v. 16, n. 7, Jul 1979. p. 32-39.
• [7] M.E.Hellman, Comments at 1993 RSA Data Security conference, 14-15 Jan 1993.
• [8] A.G.Konheim, Cryptography: A Primer, New York: John Wiley & Sons, 1981.
• [9] D.K.Branstead, J.Gait e S.Katze, Report on the Workshop on Cryptography in Support of Computer Security, NBSIR 77-1291, National Bureau of Standards, Set 21-22, 1976, Setembro 1977.