Detalhes

Categoria: Notícias da Criptografia

Atualização: Domingo, 12 Abril 2009 22:20

Autor: vovó Vicki

Acessos: 12769

Não uma versão reduzida. Não uma versão simplificada. A SHA-1 de verdade!

A equipe de pesquisa de Xiaoyun Wang, Yiqun Lisa Yin e Hongbo Yu (a maioria dos integrantes são da Universidade Shandong na China) fez circular no mocó um paper descrevendo os resultados que obteve:

• colisões na SHA-1 completo em 2**69 operações hash, muito menos que o ataque de força bruta de 2**80 operações baseadas no comprimento do hash.
• colisões na SHA-0 em 2**39 operações.
• colisões na SHA-1 de 58 etapas em 2**33 operações.

Este ataque se baseia em ataques anteriores à SHA-0 e à SHA-1, e é um resultado criptoanalítico importante, muito importante mesmo: é o primeiro ataque à SHA-1 que é mais rápido do que a força bruta.

Bruce Schneier escreveu sobre o SHA, e a necessidade de substituí-lo, em setembro de 2004. Exceto pelos detalhes do novo ataque, tudo o que ele disse continua de pé.

"Funções hash one-way são estruturas criptográficas usadas em muitas aplicações. São usadas juntamente com algoritmos de chave pública, tanto na encriptação quanto nas assinaturas digitais. São usadas para checar a integridade. São usada na autenticação. Têm todo tipo de aplicação na maioria dos diferentes protocolos. Muito mais do que algoritmos de encriptação, as funções hash one-way são a locomotiva da criptografia moderna."

"Em 1990, Ron Rivest inventou a função hash MD4. Em 1992, ele melhorou a MD4 e desenvolveu outra função hash: a MD5. Em 1993, a National Security Agency, NSA, publicou uma função hash muito parecida com a MD5, chamada de SHA (Secure Hash Algorithm). Depois, em 1995, citando a recente descoberta de uma fraqueza que a agência se recusava a corrigir, a NSA fez uma alteração na SHA. O novo algoritmo foi chamado de SHA-1. Hoje, a função hash mais utilizada é a SHA-1 e a MD5 ainda é usada em aplicações mais antigas."

"Espera-se que as funções hash one-way tenham duas propriedades. Uma, que sejam one way. Isto significa que é fácil calcular o valor hash de uma mensagem, mas que é impossível recriar a mensagem original usando-se seu valor hash (com 'impossível' eu quero dizer que 'não pode ser feito num tempo razoável') A segunda, que não apresentem colisões. Isto significa que é impossível encontrar duas mensagens que se fragmentem no mesmo valor hash. O raciocínio criptográfico por trás destas duas propriedades é sutil e convido os leitores curiosos a buscarem maiores detalhes no meu livro Applied Cryptography."

"Quebrar uma função hash significa mostrar que uma destas propriedades, ou ambas, não é verdadeira."

No mês passado, três criptógrafos chineses mostraram que a SHA-1 não está livre de colisões, isto é, eles desenvolveram um algoritmo mais rápido do que a força bruta, capaz de encontrar colisões.

A SHA-1 produz um hash de 160 bits, ou seja, toda mensagem é fragmentada num número de 160 bits. Dado que existe um número infinito de mensagens que se fragmentam em cada um dos valores possíveis, então existe um número infinito de possíveis colisões. Mas, como o número dos hashes possíveis é extremamente grande, a possibilidade de encontrar uma colisão por acaso é insignificante (uma em 2^80, para ser exato). Se fragmentarmos 2^80 mensagens randômicas, encontraremos um par que se fragmentou no mesmo valor. Esta é a forma "brute force" de encontrar colisões e depende unicamente do tamanho do valor hash. "Quebrar" a função hash significa poder encontrar colisões mais depressa do que isto. E foi isto o que os chineses fizeram.

Eles conseguem encontrar colisões na SHA-1 com 2^69 cálculos, cerca de 2.000 mais rápido do que a força bruta. No momento, esta é apenas a ponta do iceberg do que é possível fazer usando a tecnologia disponível. Dois exemplos comparáveis de computação macissa ilustram este ponto.

Em 1999, um grupo de criptógrafos construíu um cracker de DES. Ele era capaz de realizar 2^56 operações DES em 56 horas. A máquina custou $250K, se bem que o custo de clones ficava entre $50K e $75K. Extrapolando esta máquina usando a Lei de Moore, uma máquina similar construída nos dias de hoje poderia realizar os 2^60 cálculos em 56 horas e 2^69 cálculos em três anos e três meses. Ou, uma máquina que custasse $25M a $38M poderia fazer os 2^69 cálculos nas mesmas 56 horas.

Do ponto de vista do software, a melhor comparação é a procura de uma das 2^64 chaves realizada pela distributed.net e que terminou em 2002. Um artigo descreveu o acontecimento da seguinte maneira:

"Durante a competição, 331.252 usuários participaram colocando ciclos ociosos dos seus processadores à disposição da procura da chave. Após 1.757 dias (4.81 anos), um participante no Japão descobriu a chave vencedora". A Lei de Moore mostra que, nos dias de hoje, este cálculo levaria um quarto do tempo para ser realizado -- ou que apenas um quarto dos computadores seria necessário. Deste modo, atualmente, uma computação de 2^69 levaria oito vezes mais de tempo ou necessitaria oito vezes mais computadores.

"A magnitude destes resultados depende de quem você é. Se você for um criptógrafo, é um grande negócio. Apesar de não serem revolucionários, estes resultados são avanços substanciais na área. As técnicas descritas pelos pesquisadores têm chance de terem outras aplicações e, como resultado, será possível projetar sistemas mais seguros. É aasim que a ciência da criptografia progride: aprendemos como projetar novos algoritmos quebrando outros algoritmos. Adicionalmente, algoritmos da NSA são considerados uma espécie de tecnologia alienígena: vêm de uma raça superior sem mais explicações. Qualquer criptoanálise bem sucedida contra um algoritmo da NSA é um dado interessante na questão de quanto o pessoal deles é realmente bom."

Para o usuário comum da Internet, esta notícia não é motivo para pânico. Ninguém poderá quebrar assinaturas digitais ou ler mensagens encriptadas imediatamente. Depois deste anúncioa, o mundo eletrônico não está menos seguro do que sempre foi.

Mas existe um velho ditado na NSA: "Os ataques ficam cada vez melhores; nunca ficam piores". Assim como o ataque desta semana se baseou em outros textos descrevendo ataques contra versões simplificadas da SHA-1, SHA-0, MD4 e MD5, outros pesquisadores se basearão nestes resultados. O ataque contra a SHA-1 ficará cada vez melhor assim que outros utilizarem estas informações para desenvolver truques mais rápidos, otimizações, etc. E a Lei de Moore continuará marchando, fazendo com que o ataque existente se torne mais rápido e mais barato.

Jon Callas, o CTO do PGP, situa a coisa melhor: "É a hora de andar, mas não de correr, para as saídas de incêndio. Você não vê fumaça, mas os alarmes de fogo começaram a tocar". Basicamente a mesma coisa foi dita por Schneier em agosto de 2004.

"Está na hora de abandonar a SHA-1."

"Por sorte, existem alternativas. O National Institute of Standards and Technology já possui padrões para funções hash mais longas e mais difíceis de serem quebradas: SHA-224, SHA-256, SHA-384, e SHA-512. Já são padrões governamentais e já podem ser usadas. São boas substitutas, mas eu gostaria de ver mais."

"Gostaria de ver o NIST orquestrar uma competição mundial para uma nova função hash, do mesmo modo que fez com o novo algoritmo de encriptação, o AES, para substituir o DES. O NIST deveria fazer uma chamada para algoritmos e conduzir uma série análises, onde a comunidade analisa várias propostas com o objetivo de estabelecer um novo padrão."

"A maioria das funções hash que temos, e todas as que são amplamente utilizadas, baseiam-se nos princípios gerais da MD4. Aprendemos muito sobre as funções hash na década passada e penso que podemos começar a aplicar estes conhecimentos para criar algo ainda mais seguro."

As funções hash são as primitivas criptográficas menos entendidas e as técnicas de hashing são muito menos desenvolvidas do que as técnicas de encriptação. Frequentemente aparecem resultados criptográficos surpreendentes no hashing. Schneier tem um paper, escrito com John Kelsey, que descreve um algoritmo para encontrar segundas pre-imagens com SHA-1 -- uma técnica que pode ser generalizada para praticamente todas as outras funções hash -- em 2^106 cálculos: muito menos do que os 2^160 cálculos necessários na força bruta. Este ataque é completamente teórico e nem remotamente prático, mas ele demonstra que ainda há muito o que aprender sobre hashing.

Diz Schneier: "Ao reler o que escrevi em setembro passado, fica claro que eu esperava que isto acontecesse. Mas não tão cedo e muito menos de forma tão impressionante. Os criptógrafos chineses merecem muito crédito pelo trabalho realizado e nós precisamos começar a trabalhar para substituir a SHA".

• Resumo do paper (a versão completa ainda não está disponível): SHA NOTE (em Inglês)
• O ensaio original de Bruce Schneier (em Inglês)
• O padrão NIST para SHA-224, SHA-256, SHA-384 e SHA-512 (em Inglês)
• O texto de Schneier para as segundas pre-imagens (em Inglês)
• Mais notícias sobre funções hash
• Dois certificados X-509 com hashes MD5 idênticos (em Inglês)
• Colisões MD5 mais rápidas (oito horas num computador de 1.6 GHz - em Inglês)

Texto extraído do Crypto-Gram de 15.03.05 - autor Bruce Schneier