Qual é a diferença entre uma multicolisão e um primeiro ou segundo ataque de pré-imagem em uma função hash?

Question

Qual é a diferença entre uma multicolisão em uma função hash e uma primeira ou segunda pré-imagem.

• Primeiros ataques de pré-imagem: dado um hash h, encontre uma mensagem m tal que

  hash (m) = h.

• Segundos ataques de pré-imagem: dada uma mensagem fixa m1, encontre uma mensagem diferente m2 tal que

  hash(m2) = hash(m1).

• Ataques de múltiplas colisões: gerar uma série de mensagens m1, m2, ...mN, tal que

  hash(m1) = hash(m2) = ...= hash(mN).

A Wikipédia nos diz que um ataque de pré-imagem difere de um ataque de colisão porque há um hash ou mensagem fixa que está sendo atacada.

Estou confuso com artigos com os quais fazem declarações como:

As técnicas são não só eficiente para procurar colisões, mas também aplicáveis a explore a segunda pré-imagem do MD4.Sobre o segundo ataque pré-imagem, eles mostrou que uma mensagem aleatória era um mensagem fraca com probabilidade 2^–122 e só precisava de um MD4 único computação para encontrar o segunda pré-imagem correspondente ao mensagem fraca.

O ataque de segunda pré-imagem no MD4

Se bem entendi, o que os autores parecem estar dizendo é que eles desenvolveram um ataque de múltiplas colisões que abrange um conjunto grande o suficiente de mensagens para que, dada uma mensagem aleatória, haja uma chance significativa, embora extremamente pequena, de que ela se sobreponha a uma de suas múltiplas mensagens. colisões.

Vi argumentos semelhantes em muitos artigos.Minha pergunta é quando um ataque deixa de ser um ataque de múltiplas colisões e se torna um segundo ataque de pré-imagem.

• Se uma multicolisão colidir com 2 ^ 300 outras mensagens, isso conta como uma segunda pré-imagem, uma vez que a multicolisão poderia ser usada para calcular a "pré-imagem" de uma das mensagens com a qual colide?Onde está a linha divisória, 2^60, 2^100, 2^1000?

• E se você pudesse gerar uma pré-imagem de todos os resumos de hash que começam com 23?Certamente não atende à definição estrita de pré-imagem, mas também é certamente uma falha séria na função hash criptográfica.

• Se alguém tiver uma grande multicolisão, sempre poderá recuperar a imagem de qualquer mensagem cujo hash colidiu com a multicolisão.Por exemplo,

  hash(m1) = hash(m2) = hash(m3) = h

  Alguém solicita a pré-imagem de h e responde com m2.Quando isso deixa de ser bobagem e se torna um verdadeiro ataque?

Regras de ouro?Conhece algum bom recurso para avaliar ataques de função hash?

Links Relacionados:

• Perguntas e Respostas sobre Colisão de HASH
• Hashes criptográficos
• A página principal do eHash

Answer 1

Trata-se de um cenário de ataque.A diferença está na escolha da entrada.Na multicolisão há livre escolha de ambas as entradas.A segunda pré-imagem trata de encontrar qualquer segunda entrada que tenha a mesma saída que qualquer entrada especificada.
Quando uma função não possui resistência a múltiplas colisões, pode ser possível encontrar colisão para alguns tipos de mensagens - não para todas elas.Portanto, isso não implica fraqueza na segunda pré-imagem.

Answer 2

Você pesquisou bastante antes de postar a pergunta.Não posso responder muito além da questão dos recursos.Qual é:Eu uso criptografia aplicada be Menezes/Oorschot para quase tudo que sempre quis saber sobre tópicos de criptografia, incluindo hashes.

Talvez você encontre uma cópia na biblioteca da sua universidade.Boa sorte.