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

24

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?)

Thomas Owens
fonte
1
Sua impressão está correta - essa é a diferença. A parte em que você está incorreto é que essa é uma enorme diferença na prática. Uma coisa é ser capaz de encontrar duas coisas que tenham uma colisão, e outra é ser capaz de encontrar uma colisão para um texto simples específico. Por exemplo, se você deseja falsificar uma mensagem específica, é inútil poder cometer falsificações existenciais - você precisa de outra mensagem que corresponda à mesma coisa que a mensagem que você interceptou.
Adrian Petrescu
@ Adrian Petrescu: Você poderia fazer uma resposta e talvez elaborar um pouco mais? Adicione itens como quando cada um (você fornece uma situação para um ataque de pré-imagem, mas não para um ataque de colisão) é mais adequado?
Thomas Owens

Respostas:

27

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

H(m)mmH(m)H(m){username,H(password)}{username,password}H(input)=?H(password)1/2nnO 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)mp q d m = m p q + m H ( m p q + m ) = ( m p q + m ) dH(m)=mdmodpqpqdm=mpq+mH(mpq+m)=(mpq+m)dmodpq=mdmodpq. 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)documentH(document)dH(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 .m1m2H(m1)=H(m2)f({0,1})={0,1}nO(2n)O(sqrt(2n))=O(2n/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 bbbH(b)=H(b)bbb. 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.

Ross Snider
fonte
Isso é lindamente explicado. Muito mais matemática do que estava procurando, mas aprecio muito o esforço - segui você através de cada uma delas. Obrigado.
Thomas Owens
E uau. Um colega estudante do RIT.
Thomas Owens
1
Como vai o Thomas? Eu acho que você teve Física com meu amigo Alan Meekins. É bom ver as pessoas da RIT aqui! Além disso, obrigado por aceitar a resposta.
Ross Snider
Muito bom. Se você estiver no campus no outono e estiver interessado em segurança, talvez possamos nos encontrar pessoalmente. Eu estive realizando algum trabalho de segurança aplicada (aplicação de estenografia, análise esteganográfica, criptografia de chave pública, assinaturas digitais) neste verão e gostaria de ouvir sobre o lado teórico (por mais que eu esteja interessado - não tenho o tempo ou conhecimentos matemáticos para analisar muitos trabalhos sobre o assunto).
Thomas Owens
[email protected]
Ross Snider
2

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

Jukka Suomela
fonte
1

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.


fonte
2
Isto é certamente verdade! Opa Originalmente, usei o problema de log discreto e depois editei os detalhes do esquema. Boa pegada. Não tenho certeza se isso constitui uma nova resposta - provavelmente foi mais apropriado deixar como um comentário em minha resposta.
Ross Snider