Ataques criptográficos
•Meet
In The Middle Attack
•Birthday Attack
Carlos Galinho Pires [email protected]
Meet In The Middle Attack
Objectivo: Descobrir as chaves de um
sistema simétrico de cifra reversível
com 2 ou mais ciclos
 Armas: Conhecer 2 ou mais pares
plaintext/cyphertext
 Defesas: Evitar o acesso a algum par
plaintext/cyphertext e usar chaves
grandes.

Carlos Galinho Pires [email protected]
Meet In The Middle Attack
Texto
Key1 Texto intermédio
Key2
Cifra
Cifra
Key2 Texto intermédio
Key1
Texto
Para um ataque brute force "naive", seriam necessárias
2n.2n [O(1)], portanto teoricamente a chave composta
teria 2n (n=nº bits).
 Meet In The Middle apenas necessita de 2n.2 [O(2n)]:

1.
2.
3.
para todas as chaves, cifrar o texto e guardar cada um
numa tabela (obtendo uma cifra intermédia)
para todas as chaves, decifrar a cifra (cifra intermédia) e
comparar cada uma com a tabela anterior, obtendo-se
um par de chaves
testar as chaves no outro par plaintext/cyphertext, se
resultar é muito provável que o par esteja correcto
Carlos Galinho Pires [email protected]
Birthday Attack

Objectivo: Descobrir colisões num
sistema de cifra irreversível.

Defesas: Resultado das funções de
hash deve ser suficientemente
grande.
Carlos Galinho Pires [email protected]
Birthday Attack

Birthday está relaccionado com o
problema dos nascimentos na teoria das
probabilidades:
◦ Qual a probabilidade de numa turma de 23
pessoas escolhidas à sorte, existir 1 par que
faz anos no mesmo dia?
◦ R: Paradoxalmente é maior que 50%!

Teoricamente, e segundo a teoria das
probabilidades, "apenas" são
necessárias 2n/2 em vez de 2n tentativas
para se descobrir uma colisão.
Carlos Galinho Pires [email protected]
Birthday Attack
Yuval propôs o seguinte método para forjar assinaturas digitais:
1.
Criar uma mensagem F (mensagem a forjar) e uma mensagem C
(mensagem parecida com F mas que a Alice não se importa de
assinar);
2.
Gerar 2n/2 variações para cada mensagem (acrescentar vírgulas,
espaços, sinónimos, etc e que não alterem o significado da
mensagem);
3.
Descobrir um par [F',C'] tal que f_hash(F') = f_hash(C'), F' =
variação de F e C' = variação de C (probabilidade de 50%);
4.
Pedir à Alice para assinar a mensagem C';
5.
Retirar a assinatura de C' e colocar em F'.

Assinatura: É a cifra do hash code de uma mensagem, ou seja,
sign( f_hash( mensagem ), Key ).

Assim, é possível forjar uma assinatura sem que se conheça a
chave de encriptação.
Carlos Galinho Pires [email protected]
Perguntas, Dúvidas?
Referências





http://en.wikibooks.org/wiki/Cryptography/Meet_In_The
_Middle_Attack
http://en.wikipedia.org/wiki/Meet-in-the-middle_attack
http://en.wikipedia.org/wiki/Birthday_problem
http://www.x5.net/faqs/crypto/q96.html
Slides Sistemas Distribuídos (Introdução à Segurança e
Primitivas Criptográficas)
Carlos Galinho Pires [email protected]