Função Hash e Autenticação em Redes
de Computadores
Marcelo Duffles Donato Moreira (CNPq/Balcão)
Orientador:
Prof. Otto Carlos Muniz Bandeira Duarte
Grupo de Teleinformática e Automação (GTA)
Departamento de Eletrônica e de Computação (DEL)
Escola Politécnica – CT – UFRJ
Problemas
Comunicações em Redes de Computadores em geral e
principalmente em redes abertas como a Internet trouxeram
algumas questões à tona:
• Necessidade de privacidade, autenticidade e integridade
de mensagens;
• Criptografia de chave pública não oferece agilidade em
Assinaturas Digitais;
• Criptografia é insuficiente para garantir integridade de
dados;
• Surgiu a necessidade de se criar mecanismos conhecidos
como Digital Timestamping.
XXVI Jornada de Iniciação Científica, Artística e Cultural
Objetivos
• Estudar o mecanismo encontrado para a solução dos
problemas apresentados: a Função Hash;
•Analisar as principais propriedades e aplicações das
Funções Hash;
• Comparar os algoritmos hash mais utilizados: MD5 e SHA.
XXVI Jornada de Iniciação Científica, Artística e Cultural
Função Hash
Origem:
• Surgiu na Ciência da Computação;
• Função que comprime uma string de tamanho arbitrário em
uma de tamanho fixo;
• Também chamada de Função de Espalhamento.
Definição:
Uma Função Hash é uma função h : {0,1}* 
{0,1}n,
para algum n  1
valor hash ou resumo
da mensagem
XXVI Jornada de Iniciação Científica, Artística e Cultural
Função Hash Criptográfica
Requisitos para o uso em Criptografia:
(1) Fácil de calcular o valor Hash;
(2) Resistência à 1ª inversão, ou seja, é computacionalmente
inviável, dado y, encontrar x tal que h(x) = y;
(3) Resistência à 2ª inversão, ou seja, é computacionalmente
inviável, dado x1, encontrar x2  x1 tal que h(x1) = h(x2);
(4) Resistência a colisões, ou seja, é computacionalmente
inviável, encontrar quaisquer x1 e x2 tais que h(x1) = h(x2).
Note que:
• (2) 
/ (3) e (3) 
/ (2)
• (2) 
/ (4) e (4) 
/ (2)
• (3) 
/ (4), mas (4)  (3)
XXVI Jornada de Iniciação Científica, Artística e Cultural
Classificação das Funções Hash
UOWHF
Funções Hash
Com chave
MAC
Message Authentication Code
Modification Detection Code
OWHF
Sem chave
MDC
CRHF
XXVI Jornada de Iniciação Científica, Artística e Cultural
Aplicações em Assinaturas Digitais
Somente o
valor hash é
assinado
Agilidade
XXVI Jornada de Iniciação Científica, Artística e Cultural
Outras Aplicações
Integridade de dados:
• Valor hash computado previamente, usando MDC;
• Para verificar alteração: recomputar e comparar o valor hash
atual com o anterior;
• Útil para distribuição de software e proteção de vírus.
Digital Timestamping:
• Data e hora de criação/assinatura do documento entram no
cálculo do valor hash;
• Útil para proteção de propriedade intelectual.
Proteção de senhas:
• O valor hash é armazenado, ao invés da senha.
Autenticação de mensagens:
• O valor hash é usado como autenticador;
• Pode ser realizada junto com criptografia ou usando MAC’s.
XXVI Jornada de Iniciação Científica, Artística e Cultural
Construção genérica
• Entrada é dividida em blocos de tamanhos iguais;
• Em seguida, é feita uma anexação ao final da entrada;
• O cálculo do valor hash h(X) é feito da seguinte maneira:
• Exemplo com t = 3:
H0 = IV,
Hi+1 = f(Hi ,Xi) para 0  i < t,
h(X) = g(Ht).
XXVI Jornada de Iniciação Científica, Artística e Cultural
Ataques mais Importantes
• Ataques que dependem somente do tamanho da saída (n bits)
Ataque de inversão
Probabilidade: 1/2n
Encontrar uma inversão
Tempo máximo: 2n operações
Ataque do aniversário
- Num grupo de k pessoas, qual o valor mínimo de k para que a
probabilidade de que pelos menos duas façam aniversário no
mesmo dia seja maior do que 50%?
1 – 365x364x...x(365 –k +1)/365k > ½  k = 23
- Considerando k entradas e m = 2n possíveis saídas, qual o valor
de k para que a probabilidade de colisão seja maior do que 50%?
1 – m!/[(m-k)!mk]  1 – e[-k(k-1)]/n > ½  k  m1/2 = 2n/2
• Ataques a MAC’s
XXVI Jornada de Iniciação Científica, Artística e Cultural
Comparação entre MD5 e SHA
• Pertencem a mesma família de Funções Hash: MDx-class;
• MD5 é mais vulnerável a ataques de força-bruta devido a sua
menor saída: 128 bits contra 160 bits do SHA;
• O MD5 é mais rápido que o SHA, pois este último possui mais
etapas em seu algoritmo (80 contra 64 do MD5) e um buffer
maior (160 bits contra 128 bits do MD5);
• Já foram encontradas colisões para a função de compressão do
MD5, enquanto que o SHA permanece inabalável.
Algoritmo
MD4
MD5
SHA
SHA-1
SHA-224/256
SHA-384/512
Performance relativa
1,00
0,65
0,31
0,31
0,12
0,06
XXVI Jornada de Iniciação Científica, Artística e Cultural
Conclusões
• Esse estudo pôde mostrar a grande importância e a variedade de
aplicações das Funções Hash;
• Foi demonstrado também como aproveitar as propriedades das
Funções Hash para resolver os problemas apresentados;
• Assinaturas digitais exigem resistência a colisões. Logo, deve-se
tomar cuidado na escolha do algoritmo para esse tipo de aplicação,
não sendo recomendados os populares MD4 e MD5;
• Afinal, qual o melhor algoritmo? Qual devo usar?
Não existe o melhor algoritmo. Existe sim o mais adequado.
Nem sempre um algoritmo muito seguro é o melhor para uma dada
aplicação, até porque geralmente um algoritmo com muitas exigências
de segurança é lento. Além disso, na maioria das aplicações nem se
exige resistência a colisões.
XXVI Jornada de Iniciação Científica, Artística e Cultural