Hash de tamanho variável como solução para a falta de resistência a
colisões
Igor G. F. de Almeida, Wirland de S. F. Filho, Luiz F.S. Sousa, Igor Ruiz Gomes
Centro Universitário do Pará (CESUPA) – Área de Ciências Exatas e Tecnologia (ACET)
Laboratório de Computação Natural (LCN) – Grupo de Estudos Temáticos de Matemática Computacional
(MatComp-CESUPA) - 66.060- 230, Belém – Pará – Brasil
Email: {cmte.igor.almeida, filho.wst, fellipe.skool, ruiz.igor}@gmail.com
RESUMO
Atualmente são feitos bilhões de downloads na world wide web, não se pode confiar
apenas no tamanho do arquivo que é recebido para verificar sua integridade. Uma vez que os
servidores não provem essa verificação, é necessário um método seguro para que não haja
desentendimentos. A criptografia provê um método para realizar tal verificação conhecido como
algoritmos de hash[3].
As funções de hash são umas das bases de um método seguro para fazer verificação de
integridade de arquivos chamada assinatura digital[2]. Este método consiste em uma função que
tem entrada de tamanho arbitrário e saída de tamanho fixo. Um algoritmo recolhe as “tiras” que
são quebradas e cria blocos de tamanho fixo e valor diferente. Se for feita qualquer modificação
no arquivo original, o bloco adquire valor diferente, mudando assim seu valor original. Este
fenômeno é chamado efeito avalanche.
A colisão, ou choque como também é conhecido, é um dos vários tipos de ataques, que
quando bem sucedido, pode comprometer a segurança de um algoritmo hash[4]. Essas colisões
são inevitáveis quando membros de um conjunto são mapeados para uma seqüência de bits
muito pequena, isso ocorre quando dois dados diferentes tem o mesmo valor de hash ou
impressão digital a partir da função H(m), onde m é a mensagem. Assim, possuindo duas
mensagens escolhidas arbitrariamente pelo emissor, m1 e m2, o valor H(m1) é igual ao valor de
H(m2).
Mesmo quando um algoritmo é bem implementado ele pode ser vulnerável a ataques de
colisão. Uma solução possível seria utilizar novos algoritmos que produzem saídas maiores,
aumentando desta forma o número de alternativas possíveis para os valores de saída. Porém, um
sistema cuja segurança foi comprometida, por causa do tamanho do hash utilizado, tem de
esperar a criação de um novo algoritmo para obter novamente um bom nível de segurança. Com
o crescente poder computacional, a facilidade em localizar colisões para um determinado hash é
cada vez maior. Assim os algoritmos têm que ser melhorados e trocados com o tempo.
Este trabalho apresenta uma forma de resolver esse problema usando uma solução que
envolve, ao contrário das outras que usam um hash de tamanho fixo como o SHA1 que tem um
tamanho fixo em 160 bits, alterar o tamanho da saída dessa função hash. O Smash, nome dado
ao algoritmo dessa pesquisa, por sua vez pode alterar esse tamanho de saída para uma mesma
mensagem gerando vários valores hash. O que diferencia o Smash dos demais algoritmos de
hash é sua capacidade de manter-se atualizado ao longo do tempo, uma vez que é necessário
apenas que se modifique seu tamanho de saída para obter-se valores diferentes.
O primeiro passo para utilização desse algoritmo é escolher um tamanho de saída em
bytes. A partir desse tamanho será calculado um inteiro n, esse número será a raiz do número
quadrado maior que o tamanho escolhido, porém o mais próximo a ele, sendo assim, se o
tamanho escolhido for de 63 bytes o valor n será 8, pois 8² = 64. Porém se o tamanho escolhido
837
for 65 bytes o valor de n será 9, uma vez que 9² = 81. Esse número n será usado com a dimensão
de uma matriz quadrada a qual será a base do cálculo do valor hash. Os valores base são então
atualizados com a função que utiliza o princípio double-pipe[1], onde duas matrizes ou pipes
que possuem valores inicias diferentes recebem os valores de entrada.
Quando termina o fluxo de bytes de entrada é feita uma correção de forma que a posição
de entrada nas matrizes retorne a posição inicial (0, 0). Depois os dois pipes serão somados
junto com a base de forma a gerar uma única matriz, que será operada pela função de
finalização que consiste num processo de 64 rodadas. Cada rodada da função consiste transpor a
matriz, trocar suas linhas e colunas e somar-los seguindo a seguinte fórmula: alternam-se entre
somar as linhas inferiores e suas colunas a direita com as linhas superiores e as respectivas
colunas a esquerda. Por fim a matriz então é transformada em um vetor com tamanho n² e é
truncado para obter-se o tamanho da saída deseja
Figura 1 – Fluxograma que explica o funcionamento do algoritmo
Implementado em Java, o Smash possui um bom desempenho, sendo capaz de gerar
valores com tamanhos diferentes sem diferença sensível no tempo de execução do algoritmo.
A pesquisa no momento se orienta em simplificar o Smash, de forma a facilitar a
implementação em hardware e também permitir que ele suporte saídas maiores que 255 bytes.
Palavras chave: criptografia, hash, colisões
Referências
[1] S. Lucks, “A Failure-Friendly Design Principle for Hash Functions”, Asiacrypt,
2005
[2] A. Moldovyan, N. Moldovyan, “Innovative cryptography”, Thomson, 2007
[3] C. Paar, J. Pelzl, “Understanding Cryptography”, Springer-Verlag, 2009
[4] X. Wang, H. Yu, “How to Break MD5 and Other Hash Functions”, Eurocrypt, 2005
838