Qual é a diferença entre uma multicolisão e um primeiro ou segundo ataque de pré-imagem em uma função hash?
Pergunta
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:
Solução
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.
Outras dicas
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.