É seguro ignorar a possibilidade de colisões de SHA na prática?

209

Digamos que temos um bilhão de imagens exclusivas, um megabyte cada. Calculamos o hash SHA-256 para o conteúdo de cada arquivo. A possibilidade de colisão depende de:

o número de arquivos
~~o tamanho do arquivo único~~

Até onde podemos ir ignorando essa possibilidade, assumindo que seja zero?

hash sha Hristo Hristov
fonte

Depende do que você está usando as chaves de hash. Se for algum tipo de identificação de arquivo, uma colisão também pode significar que os arquivos são idênticos e, portanto, você precisará comparar os arquivos também nos casos de colisão. Eu diria que seria bastante seguro comparar os tamanhos dos arquivos.

Mjuba 25/10/10

Sim, neste caso, se você comparar tamanhos de arquivo, a possibilidade diminuirá drasticamente. Você também pode usar dois algoritmos de hash e concatenar os resultados. Então, a possibilidade de uma colisão de ambos diminui mais. Mas, a questão é: quanto é "razoavelmente" seguro? Talvez precisemos de uma fórmula e números.

Hristo Hristov

@Hristo Hristov: se assumirmos que a chave hash é um número pseudo-aleatório (o que teoricamente está correto), um bilhão de chaves de 128 bits fornece uma probabilidade de colisão de 2,9 * 10 ^ -30. Você não pode nem chamá-lo de "minúsculo", é menos do que isso;)

mojuba 25/10/10

@mojuba: melhor ainda, ele está perguntando sobre um hash de 256 bits.

Michael Borgwardt

FWIW: o sistema de controle de versão GIT identifica arquivos pelo seu conteúdo SHA.

Snemarch 25/10/10

Respostas:

385

A resposta usual é a seguinte: qual é a probabilidade de um asteróide desonesto colidir com a Terra no próximo segundo, obliterando a civilização como a conhecemos e matando alguns bilhões de pessoas? Pode-se argumentar que qualquer evento azarado com uma probabilidade menor do que isso não é realmente muito importante.

Se tivermos uma função hash "perfeita" com tamanho de saída n , e temos p mensagens de hash (comprimento mensagem individual não é importante), então a probabilidade de colisão é de cerca de p ² /2 ^{n + 1} (esta é uma aproximação que é válido para p "pequeno" , ou seja, substancialmente menor que 2 ^{n / 2} ). Por exemplo, com SHA-256 ( n = 256 ) e um bilhão de mensagens ( p = 10 ⁹ ), a probabilidade é de 4,3 * 10 ^-60 .

Um rock espacial assassino em massa acontece cerca de uma vez a cada 30 milhões de anos, em média. Isso leva a uma probabilidade de um evento desse tipo ocorrer no próximo segundo a cerca de 10 a ¹⁵ . São 45 ordens de magnitude mais prováveis que a colisão do SHA-256. Resumindo, se você acha as colisões do SHA-256 assustadoras, suas prioridades estão erradas.

Em uma configuração de segurança, onde um invasor escolhe as mensagens que serão divididas em hash, o invasor pode usar substancialmente mais de um bilhão de mensagens; no entanto, você descobrirá que a probabilidade de sucesso do invasor ainda será muito pequena. Esse é o objetivo de usar uma função hash com uma saída de 256 bits: para que os riscos de colisão possam ser negligenciados.

Obviamente, tudo isso pressupõe que o SHA-256 é uma função hash "perfeita", que está longe de ser comprovada. Ainda assim, o SHA-256 parece bastante robusto.

Thomas Pornin
fonte

Esta é uma resposta muito boa, obrigado! Mas, se em caso de colisão uma usina nuclear explodir, e depende de você, você corre esse risco? Se você estiver completamente certo, podemos correr o risco, porque é 45 ordens de magnitude mais provável que a civilização seja destruída. Certo?

Hristo Hristov

@Hristo Acho que sim, correríamos esse risco. Uma usina nuclear já tem uma chance muito maior de explodir devido a outras coisas, como falha mecânica, erro humano na construção ou erro do operador durante a operação, e já estamos arriscando. Se as colisões do SHA-256 fossem as únicas coisas que causavam incidentes nucleares, quase certamente teríamos exatamente zero deles até agora.

Roman Starkov

foxnews.com/science/2013/02/11/… Eu começaria a pensar no SHA512.

Dustin Oprea

Agora posso ficar tranquilo, sabendo que provavelmente vou ser exterminado por um asteróide muito antes de viver uma colisão com o SHA-256.

precisa saber é o seguinte

Desculpe, você está perdendo o chamado "paradoxo do aniversário". Dê uma olhada melhor na "boa mesa", ela não funciona da maneira que você pensa. Para as figuras que eu forneço, nessa tabela, seria um valor "10 ^ 9" em uma coluna denominada "4.3 * 10 ^ -60" e a linha "128 bits" (mas a tabela não fica abaixo de 10 ^ -18 )

Thomas Pornin

A possibilidade de uma colisão não depende do tamanho dos arquivos, apenas do número deles.

Este é um exemplo do paradoxo do aniversário . A página da Wikipedia fornece uma estimativa da probabilidade de uma colisão. Se você executar os números, verá que todos os discos rígidos já produzidos na Terra não podem conter arquivos de 1 MB suficientes para obter uma probabilidade de colisão de 0,01% para o SHA-256.

Basicamente, você pode simplesmente ignorar a possibilidade.

Michael Borgwardt
fonte

Não posso concordar com a conclusão. Sim, nenhum disco rígido pode armazenar esse número de arquivos, mas você IMO interpreta mal a situação. São necessários apenas dois arquivos para produzir uma colisão. Embora a possibilidade seja muito baixa, ainda pode acontecer.

Sharptooth 25/10/10

@ sharptooth: não, não estou deturpando a situação. A possibilidade de você e todos que você conhece morrerem de um acidente de viação no mesmo dia é muito baixa, mas ainda pode acontecer (e é muito maior do que a de uma colisão SHA-256). No entanto, você está ignorando essa possibilidade.

Michael Borgwardt

@ sharptooth: eu estava falando sobre acidentes rodoviários separados e simultâneos de algumas centenas de pessoas específicas. Você realmente não pode dar nenhum passo para diminuir isso. Seria inútil, pois já é estranhamente baixo. Mas ainda é muito mais provável que uma colisão com SHA-256 que você nem imagina quanto. É o mesmo argumento que Thomas fez.

Michael Borgwardt

@ sharptooth: Não, as chances não aumentam significativamente, porque o número ainda é absolutamente reduzido pelo tamanho do espaço de hash do SHA-256. Essa é a única coisa que você não está levando em consideração adequadamente - todos os fatores devem ser ponderados pela magnitude real, e não igualmente. Se você gerasse um bilhão de hashes por segundo para cada pessoa na Terra e fizesse isso por mil anos, ainda teria menos de 1% de chance de uma colisão.

Michael Borgwardt

Se você não verificar a possibilidade de um erro não corrigido em todas as buscas na memória ou leitura no disco (que têm uma probabilidade muito maior do que uma colisão SHA-256), talvez não compreenda completamente as probabilidades.

Christophe

Primeiro de tudo, não é zero, mas muito próximo de zero .

A questão principal é o que acontece se realmente ocorrer uma colisão ? Se a resposta for "uma usina nuclear explodirá", é provável que você não deva ignorar a possibilidade de colisão. Na maioria dos casos, as consequências não são tão graves e você pode ignorar a possibilidade de colisão.

Além disso, não esqueça que seu software (ou uma pequena parte dele) pode ser implantado e usado simultaneamente em um zilhão de computadores (alguns minúsculos microcomputadores incorporados que estão em quase todos os lugares hoje em dia). Nesse caso, você precisa multiplicar a estimativa obtida pelo maior número possível de cópias.

dente afiado
fonte

... não pelo número de cópias, mas pelo número de conjuntos de dados que todas as cópias são digeridas.

Andreas Spindler

Isso está errado, o número de cópias do software em execução é irrelevante. A única coisa que importa é o número de arquivos exclusivos que são processados e o paradoxo do aniversário é a matemática para o cálculo.

Dirk Bester

Ouvi outra pessoa mencionar que a probabilidade de falha de hardware - ou seja, um pouco invertida em algum lugar devido à radiação etc. - é mais provável do que uma colisão de hash e, portanto, se preocupar com a colisão de hash é bobagem. Pessoalmente, eu tentaria cobrir os dois casos, para estar seguro (quanto mais segurança em uma usina nuclear, melhor), mas as colisões de hash provavelmente seriam muito baixas na lista de perigos em potencial (assumindo que o espaço de hash seja grande o suficiente) . No entanto, tudo isso pressupõe que não haja algum comportamento oculto na função hash que causa colisões com mais frequência.

Chris Middleton

'0' tem sua área

Green Tree

@ GreenTree O que você vinculou foi a criação deliberada de colisões.

Sharptooth