it-swarm-pt.tech

Qual é a diferença entre resistência fraca e forte

Li alguns textos sobre forte resistência à colisão e fraca resistência à colisão, mas não consegui entender a diferença. A única coisa que posso entender é que existe uma baixa probabilidade de colisão nas funções de hash que possuem fraca resistência à colisão e uma maior probabilidade de colisão nas funções de hash da resistência à colisão forte. Eu não conseguia entender o que é real, qual é o significado desses parâmetros. Alguém pode me ajudar nisso ?

37
phoxis

A propriedade de resistência à colisão fraca às vezes também é chamada de segunda resistência de pré-imagem :

Dado um x arbitrário, não existe x 'com x'! = X, de modo que h(x) = h (x ')

Por outro lado, forte resistência à colisão é definida como:

Não existem x e x 'com x! = X', de modo que h(x) = h (x ')

A diferença óbvia em suas definições é que, para fraca resistência à colisão, assumimos estar vinculados a uma escolha específica de x, enquanto que na definição de forte resistência à colisão, somos livres para escolher arbitrariamente nossos x e x '. Ainda assim, isso parece ser muito semelhante, então vamos ver dois exemplos.

Resistência fraca à colisão

Um bom exemplo em que realmente estamos interessados ​​apenas na fraca resistência à colisão seria um esquema simples de armazenamento de senhas. Suponha que armazenemos senhas fornecidas pelo usuário em um banco de dados, armazenando seu hash. A autenticação será bem-sucedida quando o hash de alguma senha fornecida por um usuário for igual ao valor que foi armazenado anteriormente (esse é um esquema inerentemente inseguro, mas, por favor, tenha paciência comigo). Agora, nesse caso, o x fornecido é a senha original (desconhecida) fornecida anteriormente. Se um invasor fosse capaz de resolver o problema da "segunda pré-imagem" de forma eficiente, ele poderia obter um x 'cujo valor de hash é igual ao do x original e, assim, seria autenticado com êxito. Observe que a capacidade de produzir colisões arbitrárias (ou seja, resolver o forte problema de colisão) é inútil em geral neste cenário, porque não é muito provável que o x e o x que se assemelhem se assemelhem a senhas reais cujos hashes já foram armazenados no banco de dados. .

Forte resistência à colisão

Um cenário diferente em que nossa preocupação é a forte resistência a colisões é, por exemplo, um aplicativo em que você deseja procurar dados arbitrários armazenados em um banco de dados com a ajuda de IDs exclusivos. Em vez de emitir consultas sobre os dados originais (que geralmente seriam muito lentos devido ao tamanho potencialmente ilimitado dos dados), você deve calcular hashes dos dados. Os hashes são muito compactos, limitados em seu tamanho e, portanto, podem ser consultados com muito mais eficiência. De fato, nesses casos, muitas vezes você não se importa com a (segunda) propriedade de resistência pré-imagem de uma função hash, principalmente porque as pré-imagens em si não são secretas. No entanto, você se preocupa com o fato de que você absolutamente deseja evitar dois conjuntos de dados distintos com hash no mesmo valor, o que é essencialmente uma colisão. Você não se importa com nenhuma colisão em particular, mas deseja que essa propriedade seja universal - ou seja, você não deseja nenhum dois conjuntos de dados com hash para o mesmo valor (imagine que haja uma 'restrição exclusiva' definida nessa coluna). Como a segurança geralmente não é um problema nesses aplicativos, geralmente usamos hashes não criptográficos, principalmente porque eles apresentam melhor desempenho.

A relação entre ambos

Intuitivamente e também implicados por seus nomes, assumiríamos que a forte resistência à colisão é algo mais difícil de fornecer do que a fraca resistência à colisão. Felizmente para nós, nossa intuição pode ser comprovada como correta segundo o Modelo Oracle Aleatório. Podemos provar isso por contraposição assumindo que, se tivéssemos um algoritmo polinomial probabilístico eficiente para resolver a "segunda pré-imagem", isso também nos daria um algoritmo eficiente para resolver a "colisão".

Considere uma função hash he este algoritmo probabilístico simples a seguir [1]:

Seja 2ndPreimage outro algoritmo probabilístico (e, Q) que resolve a "segunda pré-imagem" para a função hash h.

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x' (!= x) -> return (x, x')

É fácil ver que esse também é um algoritmo (e, Q) que resolve o forte problema de colisão. Isso implica que, dado que temos um algoritmo para resolver a "segunda pré-imagem", também podemos usar esse algoritmo que provavelmente produzirá uma colisão. Como não fizemos suposições sobre a função hash subjacente h, agora podemos dizer com segurança que

Forte resistência à colisão implica fraca resistência à colisão, mas o oposto não é necessariamente válido.


[1] e é a probabilidade de sucesso do algoritmo, 0 <= e <1. Q é o número máximo de consultas Oracle (ou seja, "avaliações" do algoritmo). Em caso de sucesso, o algoritmo retorna uma solução válida, caso contrário, retorna um valor indicando falha.

65
emboss

Eu escrevi esta resposta devido ao comentário de Alexander; Toda a definição é copiada; Fundamentos da função hash criptográfica: definições, implicações e separações para resistência à pré-imagem, resistência à segunda pré-imagem e resistência à colisão por P. Rogaway e T. Shrimpton.

  • resistência à pré-imagem - para essencialmente todas as saídas pré-especificadas, é inviável computacionalmente encontrar qualquer entrada que faça hash nessa saída, ou seja, encontrar qualquer pré-imagem x' De modo que h(x') = y quando fornecido qualquer y para o qual uma entrada correspondente não seja conhecida.
  • Resistência da segunda pré-imagem, colisão fraca - é computacionalmente inviável encontrar qualquer segunda entrada que tenha a mesma saída que qualquer entrada especificada, ou seja, x, para encontrar uma segunda pré-imagem x' != x tal que h(x) = h(x').
  • resistência à colisão, forte-colisão - é computacionalmente inviável encontrar duas entradas distintas x, x' com hash para a mesma saída, ou seja, de modo que h(x) = h(x').

Fato 1 : A resistência à colisão implica resistência na segunda pré-imagem das funções de hash.

Fato 2: A resistência da 2ª pré-imagem implica resistência à pré-imagem.


Como Alexander observou, pelo princípio do buraco de pombo, quando o espaço de entrada maior que o espaço de saída da função hash, as colisões são inevitáveis.

2
kelalaka