Quanto mais provável são colisões de hash se eu botar um monte de hashes?

Question

Say Eu estou usando um hash para identificar arquivos, então eu não preciso que ele seja seguro, eu só preciso para minimizar colisões. Eu estava pensando que eu poderia acelerar o hash-se executando quatro hashes em paralelo usando SIMD e depois hash o resultado final. Se o hash é projetado para levar um bloco de 512 bits, eu só passo através do arquivo tomar 4x512 blocos de bits de uma só vez e gerar quatro hashes fora disso; em seguida, no final do hash do arquivo que os quatro hashes resultantes juntos.

Eu tenho certeza que este método seria produzir hashes mais pobres ... mas quanto mais pobre? Qualquer parte de trás dos cálculos envelope?

Answer 1

A idéia de que você pode ler blocos do arquivo a partir do disco mais rápido do que você pode picar-los é, assim, uma hipótese não testada? Disk IO - mesmo SSD - é muitas ordens de magnitude mais lenta que a RAM que o hashing está indo embora.

Garantir baixas colisões é um critério de design para todos os hashes, e todos os hashes tradicionais fazer um bom trabalho dele - basta usar um hash dominante por exemplo MD5.

Específico para a solução do cartaz está considerando, não é um dado que hashing paralelo enfraquece o hash. Há hashes projetados especificamente para hash paralela de blocos e combinando os resultados como o cartaz disse, embora talvez ainda não em adoção generalizada (por exemplo, MD6 , que retirou ininterrupta de SHA-3)

De modo mais geral, há implementações tradicionais de funções hash que fazem uso SIMD. implementadores hash são muito desempenho-aware , e fazer ter tempo para otimizar suas implementações ; você teria um trabalho duro igualando seu esforço. O melhor software para forte hashing é de cerca de 6 a 10 ciclos / byte. Hardware acelerado hashing também está disponível se hashing é o verdadeiro gargalo.