Alguma substring de um hash (md5, sha1) é mais "aleatório" do que outro?

Question

Aqui estão 3 exemplo md5 hashes

$ md5 -s "1" && md5 -s "2" && md5 -s "3"
MD5 ("1") = c4ca4238a0b923820dcc509a6f75849b
MD5 ("2") = c81e728d9d4c2f636f067f89cc14862c
MD5 ("3") = eccbc87e4b5ce2fe28308fd9f2a7baf3

Digamos que eu queria tirar 8 caracteres de qualquer hash. A parte inicial do hash é particularmente mais "aleatória" do que o fim? meio? Ou todas as substringas são igualmente "aleatórias"?

Answer 1

Eu estava curioso, então fui em frente e escrevi um programa Para testar isso. Você precisará Cripto ++ Para compilar o código.

Isenção de responsabilidade: quando se trata de criptografia, ou mesmo apenas matemática em geral, sei o suficiente para me matar no pé. Portanto, tome os seguintes resultados com um grão de sal e lembre -se de que só tenho um conhecimento superficial das ferramentas que estou usando.

Eu apenas experimentei três substringas: os 8 primeiros bytes, os 8 bytes do meio e os últimos 8 bytes. Para encurtar a história, eles são igualmente aleatórios.

No entanto, ao usar um espaço de amostra menor, parece que os últimos 8 bits são um pouco mais aleatórios. Quanto maior o espaço de amostragem, mais próximas todas as três substâncias abordam a aleatoriedade completa.

---

1000 iterações:

First:  0.995914
Middle: 0.996546
Last:   0.998104

5000 iterações:

First:  0.998387
Middle: 0.998624
Last:   0.999501

10000 iterações:

First:  0.999614
Middle: 0.999457
Last:   1

30000 iterações:

First:  1
Middle: 1
Last:   1

---

"Aleatoriedade" é medido por Crypto ++ 's MaurerrandomnessTest classe. Para referência, o executável compilado a partir do código acima tem um valor de aleatoriedade de 0.632411 e uma cópia do Macbeth de Shakespeare baixado do Projeto Gutenburg tem um valor de aleatoriedade de 0.566991.

Answer 2

Todas as substringas de um bom hash (e o MD5 são razoavelmente boas, apesar de serem criptograficamente inseguras) são igualmente aleatórias; portanto, sim, pegue os bits que você gostar da corda, eles devem ser igualmente distribuídos.

Answer 3

Nitpick: "Random" é a palavra errada a ser usada aqui, pois as funções de hash são determinísticas.

Quanto a responder o que você quer dizer :), uma propriedade desejável das funções de hash é alcançar o Efeito Avalanche: Basicamente, ter todo o número de informações causam alterações drásticas na saída. Portanto, para um hash bem projetado, toda substring deve ser afetada igualmente ("ser tão aleatório") Como qualquer outro.

Answer 4

Medir a aleatoriedade da saída de uma função de hash pode ser feita usando testes estatísticos feitos em geradores de números pseudo-aleatórios. De acordo com Manual de criptografia aplicada §5.4.4 (Capítulos de amostra disponíveis gratuitamente), existem cinco testes básicos:

1. Teste de frequência (teste de monobit)
2. Teste serial (teste de dois bits)
3. Teste de poker
4. Executa o teste
5. Teste de autocorrelação

Então, é claro, há o teste estatístico universal do Maurer que Kurige já mencionou.