SHA-1 Broken

O metodo ainda nao foi divulgado exaustivamente, e apesar de o grupo de pesquisas citado ser confiavel, nao existem ainda ataques serios e/ou concretizados. Trocar de SHA-1 pra outro message digest nao eh tao dificil caso a necessidade se prove necessaria, entao eu nao vejo - AINDA - motivo pra muito alarde.

Se for pensar, um nego com essa vontade toda de quebrar um banco provavelmente ja conseguiu ha muito tempo usando engenharia social

Olá

CV, não se esqueça que SHA-1 (160 bits) é algoritmo de message digest que até hoje era considerado como dos melhores e junto com o ultrapassado MD5 (128 bits) é um dos mais usados.

Pelo que se chama de birthday paradox, se pode chegar que com MD5 são necessárias 264 operações para se obter 2 valores iguais (colisão) e com SHA-1 seriam necessárias 280 operações. Daí se pode deduzir a dificuldade de se quebrar o código com força bruta. Há um autor que previu em 1996 que estes métodos iriam ser quebrados sem usar força bruta. Ele estava certo, os chineses afirmam que bastam 2**69.

[]s
Luca

Luca,

Então, eu não consegui entender o real perigo de eles terem achado uma colisão… Um exemplo bem simples do que eu acredito ser o problema:

eu tenho uma mensagem e tenho o sha-1 dela. Só que a partir do momento que eu consigo encontrar uma outra mensagem que tenha o mesmo hash da primeira, eu não consigo provar que a primeira mensagem era a original minha, é isso?

Muito obrigado,
Tiago

Eu acho que eles só não divulgaram pra não causar pânico. Mas o dia que isso for divulgado, aí já era. Então é bom começar a se abandonar o SHA-1 já.

Olá

Esta notícia apesar de surpreendente para mim, na verdade ainda não mostra nenhum real perigo como o próprio CV disse. Apenas foi afirmado que bastam 2**69 operações para encontrar uma colisão e com isto abrir o código ou a mensagem. E isto ainda é melhor do que MD-5 usado por muita gente.

Porque com colisão se perde a segurança? Porque um atacante pode criar uma outra mensagem com a mesma assinatura e então se passar pelo verdadeiro autor.

Mas na prática ainda seria inviável juntar um monte de CPUs com a atual capacidade para realizar todas estas operações durante um monte de tempo só para abrir uma mensagem. Portanto, mesmo com a lei de Moore atingindo seus limites, ainda temos muitos anos até que SHA-1 perca a confiança.

[]s
Luca

Um problema que pode se tornar critico daqui um tempo, caso nao surja nenhum algoritmo de message digest pra substituir MD5 e SHA-1, eh que diversos sites hoje guardam o hash de senhas no banco de dados.

Imaginando que - e isso em si ja eh uma situacao improvavel - o atacante tenha acesso ao hash da senha, ele pode criar uma colisao e ter acesso aos servicos. O problema eh que nao se sabe qual o tamanho da massa de dados necessaria pra causar uma colisao. Podem ser 3 letras, podem ser 3 terabytes, e convenhamos, ninguem usa uma senha com mais do que 200, 300 caracteres, o que limita enormemente a capacidade de se encontrar colisoes.

Novamente, o problema existe e merece ser tratado com carinho, mas nao eh motivo pra chamar o Jack Bauer ainda :mrgreen:

Ufa, ainda bem que estou usando HMAC-SHA-1 para um sistema que estou fazendo e não o SHA-1 - no caso do HMAC, não há problemas com colisões, mesmo que o hash subjacente tenha problemas.
Qual hash que eu ia usar agora? MD5 - não funciona mais. SHA-1 - está sob risco. E por aí vai.

MD5 funciona, sim - SHA-1 tambem, a diferenca eh que o numero de operacoes necessarias pra gerar uma colisao diminuiu, e considerando que no caso do SHA1 ainda nem tem implementacao…

Alias, tem implementacao da quebra do MD5 em algum paper? Alguem mais esclarecido tem um link?

http://eprint.iacr.org/2004/199.pdf é o paper que você queria sobre o MD5. Em alguns dias o autor deve publicar o paper sobre o SHA-1.

Confesso que estou “boiando” um pouquinho no assunto. Alguem tem um link interessante que explique o que vcs estão falando ?

:lol:

Depois do Google, so a Wikipedia :mrgreen:

Olá

Message digest ou hash = meio de verificar integridade dos dados. Um algoritmo calcula um “número” que pode ser usado para verificar se o texto da mensagem é autêntico.

O algoritmo MD5 pega uma mensagem de comprimento arbitrário e produz um resultado de 128-bits que é como se fosse uma assinatura digital ou uma impressão digital da mensagem. O algoritmo SHA-1 faz coisa semelhante porém produz um resultado de 160 bits.

Sobre colisões e especificamente sobre vulnerabilidades do MD5 se pode ver os links abaixo:

hash collision Q&A

Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD

A real MD5 collision

[]s
Luca

[]s
Luca

É, eu e minha incrível falta de hábito de pesquisar na Wikipedia.

Tks, cv

cv:

Depois do Google, so a Wikipedia :mrgreen:

Pensando melhor, depois dessa do Luca, incluiria ele no ranking tb. :mrgreen:

Valeu Luca.

Luca:

Olá

Message digest ou hash = meio de verificar integridade dos dados. Um algoritmo calcula um “número” que pode ser usado para verificar se o texto da mensagem é autêntico.

O algoritmo MD5 pega uma mensagem de comprimento arbitrário e produz um resultado de 128-bits que é como se fosse uma assinatura digital ou uma impressão digital da mensagem. O algoritmo SHA-1 faz coisa semelhante porém produz um resultado de 160 bits.

Sobre colisões e especificamente sobre vulnerabilidades do MD5 se pode ver os links abaixo:

hash collision Q&A

Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD

A real MD5 collision

[]s
Luca

[]s
Luca

Só para completar a boa explicação do mestre Luca, hash também serve para se gerar chaves para objetos que serão armazenados em certos tipos de coleções (conhecidas como hash tables), permitindo que operações de busca nestas coleções se tornem mais rápidas (se não estiver enganado, a complexidade de um algoritmo de busca em uma hashtable é da ordem O(1) ).

Mais informações: http://en.wikipedia.org/wiki/Hash_table

p.s.: para pensar no banheiro: junte todas estas informações e pense no motivo pela qual sempre se recomenda que o método hashCode seja sempre reescrito (principalmente quando o método equals também é reescrito).

Que tal saber como é que funciona uma combinação de um cofre? Aquelas que você precisa ‘girar 10 para a esquerda, 2 para a direita etc.’

Safecracking for the computer scientist - http://www.crypto.com/papers/safelocks.pdf

thingol:

Que tal saber como é que funciona uma combinação de um cofre? Aquelas que você precisa ‘girar 10 para a esquerda, 2 para a direita etc.’

Safecracking for the computer scientist - http://www.crypto.com/papers/safelocks.pdf

Pultz, muito bom Thingol! Tá na minha lista de leitura já! Valew!

Olá

Sem querer ser chato mas já sendo pra caramba…

Dificilmente se usam em hashtables funções que fazem o chamado hash perfeito. Portanto hash tables quase sempre tem colisões e quase sempre precisam de um esquema para resolver as colisões. Daí na prática localizar uma chave em uma tabela hash com colisões não é bem da ordem O (1).

Assim, apesar do nome parecido, o algoritmo hash usado em criptografia é totalmente diferente das funções hash usadas em hash tables porque em criptografia não se admitem colisões.

PS.: Mas, porém, contudo, todavia, antigamente a gente usava XOR para criptografia e usava XOR também como função hash.

[]s
Luca

http://theory.csail.mit.edu/~yiqun/shanote.pdf é o paper que descreve o ataque a SHA-0 e a uma versão reduzida do SHA-1. Nesse paper não há uma demonstração de uma colisão no SHA-1 real, porque os autores não tiveram tempo (ou recursos computacionais ) para conseguir efetuar o ataque, mas como ele dizem, é só uma questão de esforço.