valores manipulação close-to-impossíveis colisões on deve-ser-únicas

Question

Existem muitos sistemas que dependem da singularidade de algum valor particular. Qualquer coisa que usa GUIDs vem à mente (ex. O registro do Windows ou outros bancos de dados), mas também coisas que criam um hash de um objeto para identificá-lo e, portanto, precisa deste hash para ser único.

Uma tabela normalmente não se importa se dois objetos têm o mesmo hash porque o hash é usado apenas para quebrar os objetos em categorias, para que em pesquisa, nem todos os objetos na mesa, mas apenas os objetos no mesma categoria (balde) têm de ser comparados para a identidade com o objeto pesquisado.

Outras implementações no entanto (parecem) dependem da singularidade. Meu exemplo (que é o que me levam a fazer esta) é IDs de revisão do Mercurial. Um entrada na lista de discussão Mercurial afirma corretamente

As chances do hash changeset colidindo por acidente em seu primeiro bilhão de commits é basicamente zero. Mas notaremos se isso acontece. E você vai ter de ser famoso como o cara que SHA1 quebrado por acidente.

Mas mesmo a probabilidade menor não significa impossível. Agora, eu não quero uma explicação de por que é totalmente bem para contar com a singularidade (este tem sido discutido aqui por exemplo). Isto é muito claro para mim.

Em vez disso, eu gostaria de saber (talvez por meio de exemplos de seu próprio trabalho):

• Há algum melhores práticas, para cobrir estes casos improváveis ??de qualquer maneira?

• deveriam ser ignorados, porque é mais provável que particularmente fortes ventos solares levar para o disco rígido defeituoso lê?

• Se eles pelo menos ser testado para, apenas para falhar com um "eu desisto, você tem feito o impossível" mensagem para o usuário?

• Ou deve mesmo esses casos se manuseado graciosamente?

Para mim, especialmente o seguinte são interessantes, embora eles são um pouco melosas:

• Se você não lidar com estes casos, o que você faz contra sentimentos de intestino que não ouvir as probabilidades?

• Se você lidar com eles, como justifica este trabalho (para si mesmo e outros), considerando que há casos mais prováveis ??você não tratar, como um supernonva?

Answer 1

• Se você lidar com eles, como justifica este trabalho (para si mesmo e outros), considerando que há casos mais prováveis ??você não tratar, como uma supernova?

A resposta para isso é que você não está testando para detectar uma colisão GUID ocorrendo por acaso. Você está testando para detectar uma colisão GUID ocorre por causa de um bug no código GUID, ou uma pré-condição que o código GUID depende de que você violou (ou foi levado a violar por alguns atacante), como em V1 que MAC endereços são únicos e tempo avança. Ou é consideravelmente mais propensos do que os insetos à base de supernovas.

No entanto, nem todos os clientes do código GUID deve estar testando sua correção, especialmente no código de produção. Isso é o que testes de unidade é suposto fazer, então trade off o custo de perder um bug que o seu uso real iria pegar, mas os testes de unidade não fez, contra o custo de segunda-adivinhando suas bibliotecas de todo o tempo.

Note também que GUIDs só funcionam se todos que está gerando-los coopera. Se seu aplicativo gera os IDs de máquinas que você countrol, GUIDs então você pode não precisar de qualquer maneira - um ID local único como um contador de incremento pode fazer você muito bem. Obviamente Mercurial não pode usar esse, portanto, ele usa hashes, mas, eventualmente, SHA-1 vai cair para um ataque que gera colisões (ou, pior ainda, pré-imagens), e eles vão ter que mudar.

Se seu aplicativo gera não de hash "GUIDs" em máquinas você não controla, como clientes, em seguida, esquecer colisões acidentais, você está preocupado com colisões deliberadas por clientes maliciosos que tentam DOS seu servidor. Proteger-se contra o que provavelmente irá protegê-lo contra acidentes de qualquer maneira.

• Ou deve mesmo esses casos se manuseado graciosamente?

A resposta para isso é provavelmente "não". Se você poderia lidar com a colisão GUIDs graciosamente, como um hashtable acontecer, então por que se preocupar com GUIDs em tudo? O ponto inteiro de um "identificador" é que, se duas coisas têm o mesmo ID, em seguida, eles são o mesmo. Se você não quer tratá-los o mesmo, apenas inicialmente encaminhá-los em baldes como um hashtable que, em seguida, usar um esquema diferente (como um hash).

Answer 2

Dado um pouco de hash boa 128, o provavelmente de colidir com um valor específico de hash dado uma entrada aleatória é:

1 / 2 ** 128 que é aproximadamente igual a 3 * 10 ** -39.

A probabilidade de ver sem colisões (p) dado amostras n pode ser calculado usando a lógica usada para explicar o problema de aniversário .

p = (2 ** 128)! / (2 ** (128 * n) * (2 ** 128 - n)!)

onde !denotes a função fatorial. Podemos então traçar a probabilidade de nenhuma colisão como o número de amostras aumenta:

Probabilidade de um aleatória SHA-1 de colisão como o nero de amostras aumenta. http://img21.imageshack.us/img21/9186/sha1collision.png

Entre 10**17 e 10**18 hashes começamos a ver possibilidades não-triviais de colisão de 0,001% a 0,14% e, finalmente, 13% com hashes 10**19. Assim, em um sistema com um milhão, bilhão, registros contando com singularidade é provavelmente imprudente (e tais sistemas são possíveis), mas na grande maioria dos sistemas a probabilidade de uma colisão é tão pequena que você pode contar com a singularidade de seus hashes para todos os efeitos práticos.

Agora, a teoria de lado, é muito mais provável que as colisões poderiam ser introduzidas em seu sistema, quer através bugs ou alguém atacando seu sistema e assim a resposta de onebyone fornece boas razões para buscar por colisões mesmo que a probabilidade de uma colisão acidental são infimamente pequeno (isto é a probabilidade de erros ou malícia é muito maior do que uma colisão acidental).