Ataques de DOS via Complexidade Algoritmica

Eu li meio por cima na JavaSpecialists que o algoritmo de hashing dos HashMaps mudou na 1.4.1… Em qual versão da API vc olhou?

sempre eh possivel gerar elementos que gerem o mesmo hash. a nao ser que eles sejam todos uniques e nao ultrapassem Integer.MAX_INT (2 bi)

por isso voce tem de usar uma colecao de Hashing universal. Voce sorteia sua funcao de hash ao criar a tabela, e o atacante NUNCA vai conseguir prever as colisoes, ja que as funcoes sao meio que aleatorias.

antigamente o hash da String do java soh levava em consideracao os 16 primeiros caracteres. Ai colidia PRA CARAMBA. Hoje melhorou muito.

crei eu que olhei a versao da 1.4.1_02.

Paulo, sortear uma funcao entre 1 coleção de funções apenas adia o problema, o ideia é usar 1 funcao de hashing segura logo de primeira, como o MD5 sugerido no artigo.

O problema no java é pior, pq esperamos que cada objeto seja esperto na hora de calcular seu hash, oque nos deixa a merce da implementação da JVM.

Agora, ate onde eu sei, todos pacotes de coleção que eu ja vi (java.util, jakarta, colt, ), usam Object::hashCode() como método de gerar hashes pros objetos, alguns, como o java.util, faz 1 modificação no valor, porem isso apenas ajuda no espalhamento de valores proximos, não de valores iguais.

Ou seja, sera que não é possivel construir 1 ataque de DOS contra, por exemplo, o Tomcat, se valendo do fato de conhecermos 1 gerador de Strings com hashCode igual?

“louds”:

crei eu que olhei a versao da 1.4.1_02.

Paulo, sortear uma funcao entre 1 coleção de funções apenas adia o problema, o ideia é usar 1 funcao de hashing segura logo de primeira, como o MD5 sugerido no artigo.

Ja vi voce comentando sobre o Cormen. Veja o capitulo do Cormen sobre estruturas de dados simples, no final de hashing, ele fala sobre as colecoes universais, e como impedir esses ataques maleficos. (pagina 229)

Usar MD5 realmente eh uma boa solucao. Ja que pro cara achar outra String/Objeto que tenha o mesmo MD5 eh meio complicado heehehhe. E se ele achar isso de uma maneira rapida, ele estaria rico…

Rico é pouco, aliás.

A confiança no MD5 fez com que muita gente usasse esse algoritmo pra guardar dados confidenciais em bases de dados críticas, senhas em máquinas Unix, etc, etc, etc

Paulo
vc falou em sortear 1 algoritmo quando a coleção é criada, quanto a utilizar universal hashing, isso resolveria o problema, alem de ser mais rapido que MD5.

Hoje em dia vc gasta alguns dias de 1 boa cpu para conseguir criar 1 string que produz 1 hash especifico. Isso levando em conta todos bits do MD5, mas ainda assim fica inviavel criar 1 ataque de hash contra MD5…

Eu so uso MD5 pro shadow no unix, pro resto, como senhas de LDAP, é SHA1 256 mesmo, que é muito mais seguro.

curti o assunto, postei na lsita de uma materia e me passaram mais esses dois links.

bug do kernel com o mesmo problema?

resposta:
http://msgs.securepoint.com/cgi-bin/get/djbdns-0306/4.html