Qual é a diferença entre um segundo ataque de pré-imagem e um ataque de colisão?

A Wikipedia define um segundo ataque de pré-imagem como:

dada uma mensagem fixa m1, encontre uma mensagem diferente m2, tal que hash (m2) = hash (m1).

A Wikipedia define um ataque de colisão como:

encontre duas mensagens diferentes arbitrárias m1 e m2, de modo que hash (m1) = hash (m2).

A única diferença que vejo é que, em um segundo ataque de pré-imagem, o m1 já existe e é conhecido pelo invasor. No entanto, isso não me parece significativo - o objetivo final ainda é encontrar duas mensagens que produzam o mesmo hash.

Quais são as diferenças essenciais na forma como um segundo ataque de pré-imagem e ataque de colisão são realizados? Quais são as diferenças nos resultados?

(Além disso, não posso marcar essa pergunta corretamente. Estou tentando aplicar as tags "colisão de pré-imagem de segurança de criptografia", mas não tenho reputação suficiente. Alguém pode aplicar as tags apropriadas?)

Eu posso motivar a diferença para você em cenários de ataque.

$H(m)$$m$$m'$$H(m')$$H(m)$$\{username, H(password)\}$$\{username, password\}$$H(input) =? H(password)$$1/2^n$$n$O primeiro ataque de pré-imagem é a situação em que um adversário só tem acesso a um resumo da mensagem e está tentando gerar uma mensagem com hashes nesse valor.

$H(m)$$m$p q d m ′ = m p q + m H ( m p q + m ) = ( m p q + m ) $H(m) = m^d \mod{pq}$$p$$q$$d$$m' = mpq + m$$H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$. E assim o adversário encontrou uma colisão com pouco ou nenhum cálculo.

Gostaríamos que, de uma maneira, as funções hash fossem resistentes a ataques de segunda pré-imagem por causa de esquemas de assinatura digital, caso em que é considerado informação pública e é repassado (por meio de um nível de indireção) a cada cópia do documento. Aqui, um invasor tem acesso ao e ao . Se o atacante puder apresentar uma variação no documento original (ou em uma mensagem totalmente nova) modo que ele poderá publicar seu documento como se fosse o assinante original.$H(document)$$document$$H(document)$$d'$$H(d') = H(document)$

Um ataque de colisão permite ao adversário ainda mais oportunidades. Nesse esquema, pedimos ao adversário (posso chamá-lo de Bob?) Para encontrar duas mensagens e tais que . Devido ao princípio do pigeonhole e ao paradoxo do aniversário, até funções de hash 'perfeitas' são quadraticamente mais fracas a ataques de colisão do que ataques de pré-imagem. Em outras palavras, dada uma função imprevisível e irreversível de digitação de mensagens que leva tempo para força bruta, uma colisão pode sempre seja encontrado no tempo esperado .$m_1$$m_2$$H(m_1) = H(m_2)$$f(\{0,1\}^*) = \{0,1\}^n$$O(2^n)$$O(sqrt(2^n)) = O(2^{n/2})$

Bob pode usar um ataque de colisão para sua vantagem de várias maneiras. Aqui está uma das mais simples: Bob encontra uma colisão entre dois binários e ( ), de forma que b é um patch de segurança válido do Microsoft Windows é um malware. (Bob trabalha para Windows). Bob envia seu patch de segurança para a cadeia de comando, onde atrás de um cofre eles assinam o código e enviam o binário para usuários do Windows em todo o mundo para corrigir uma falha. Agora, Bob pode entrar em contato e infectar todos os computadores Windows em todo o mundo com e a assinatura que a Microsoft calculou parab ′ H ( b ) = H ( b ′ ) b ′ b ′$b$$b'$$H(b) = H(b')$$b'$$b'$$b$. Além desses tipos de cenários de ataque, se se acredita que uma função de hash é resistente a colisões, é mais provável que a função de hash seja resistente a pré-imagens.

Os ataques de colisão podem ser muito mais fáceis, mas se forem bem-sucedidos, muito menos úteis.

O problema que Ross menciona como sendo o problema de log discreto é, na realidade, um problema completamente diferente, o problema da RSA, que está muito mais relacionado às raízes da computação do que ao log discreto.