terça-feira, 16 de outubro de 2012

Algoritmos de Hash Unidirecionais para Senhas: II - Teoria e Prática

No primeiro artigo da série sobre Algoritmos de Hash Unidirecionais vimos porque devemos criptografar, que tipo de algoritmo devemos utilizar e a lógica por trás do seu funcionamento.
Agora vamos mais a fundo para entender como funcionam as funções de hash.
Embora os algoritmos de hash sejam muito utilizados para checksum de arquivos, neste artigo vamos imaginar o seu uso exclusivamente para autenticação de mensagens de texto (strings) para facilitar a compreensão.

Teoria 

 

Algoritmos de hash basicamente consistem de funções que recebem uma mensagem de tamanho variável como entrada e retornam um hash de tamanho fixo na saída. Isto ocorre de tal forma que uma simples mudança na mensagem de entrada resulte em uma mudança no hash de saída.
Um algoritmo seguro deve seguir as seguintes premissas:
  • Dado um determinado hash h, deve ser impraticável obter uma mensagem m que satisfaça a condição hash(m) = h.
  • Dada uma determinada mensagem m1, deve ser impraticável obter uma segunda mensagem m2 que satisfaça a condição hash(m1) = hash(m2).
  • Deve ser impraticável encontrar duas mensagens arbitrárias que retornem o mesmo hash.
Observe que para o termo "impraticável" você deve ter em mente uma faixa probabilística extremamente baixa.
Vamos dar uma olhada no funcionamento de um algoritmo genérico na imagem abaixo (clique para ampliar):

Atenção: a imagem acima representa o funcionamento básico de um algoritmo de hash, e foi simplificado para facilitar o entendimento.
Como podemos ver, a mensagem de entrada do algoritmo é quebrada em vários blocos de tamanho fixo, cada algoritmo possui seu próprio tamanho de bloco definido, o MD5 por exemplo utiliza blocos de 128 bits. Todos os blocos devem possuir o mesmo tamanho, caso o último bloco da mensagem não seja completamente preenchido, este deve incluir valores de preenchimento, como podemos ver no exemplo, o número 1 seguido de quantos zeros forem necessários para preencher o bloco.
O algoritmo utiliza um Valor Inicial IV fixo como entrada para o cálculo da função juntamente com o Bloco 1. O resultado desta primeira função serve de entrada para a segunda função juntamente com o Bloco 2. Desta forma, o algoritmo realiza um processo em cascata, onde o resultado de um nível é dependente do nível anterior. A função empregada no processo é sempre a mesma, normalmente uma função de compressão unidirecional. Após ser obtido o hash do último bloco do algoritmo, uma segunda função é utilizada. Esta função varia em cada algoritmo e o seu principal objetivo, normalmente, é aumentar a resistência a colisões.

Agora que já temos uma idéia melhor de como um algoritmo de hash pega uma string qualquer e transforma em um hash, vamos observar este processo de uma forma mais simples.
Em uma abstração, o que o algoritmo faz é pegar uma determinada string e mapeá-la para um determinado hash.

 Desta forma, sabemos que quando recebemos determinado hash, este só pode ter vindo daquela string específica. Mesmo duas strings muito próximas, devem mapear para áreas distintas do universo de hashes.

Prática


A Teoria quase perfeita não resiste à prática. De fato, a imagem anterior não reflete a realidade. Isto porque se pararmos para pensar, no primeiro exemplo do artigo nosso algoritmo fictício pegava uma string de tamanho variável e gerava hashes alfanuméricos de 17 caracteres. Portanto, é fácil perceber que um universo de todos os hashes possíveis contendo apenas letras e números e com 17 caracteres de comprimento possui um tamanho x. Já um universo de todas as strings de tamanhos variáveis compreendendo quaisquer caracteres possui um tamanho muitas vezes x.
Então, na prática, a imagem que devemos ter em mente é mais ou menos esta:
Agora fica fácil de compreender que existem alguns problemas com relação ao mapeamento de strings com algoritmos de hash.
Evidentemente não há como garantir um hash único para cada string possível, visto que o número de hashes possíveis é muito menor.
Portanto, na prática, existem várias strings que mapeiam para cada hash.

Colisões de Hash


Uma colisão de hash ocorre quando encontramos duas strings que produzem o mesmo hash, como no exemplo:
Ora, se o objetivo dos Algoritmos de Hash Unidirecionais é criar uma "impressão digital" de um dado, para que se possa comprovar sua identidade ou atestar que não foi modificado, então como isso é possível se existem vários dados que geram o mesmo hash, ou impressao digital?
Em primeiro lugar, existe uma grande diferença entre você falar que existem várias strings que mapeiam para o mesmo hash e você efetivamente encontrar uma colisão de hash. É mais ou menos a mesma diferença entre você dizer que um meteoro pode cair a qualquer momento no seu quintal e você ouvir um grande estrondo.
Embora o universo de hashes possíveis seja, relativamente, pequeno, para que você possa encontrar uma colisão de hash, você não vai pesquisar nele e sim no universo de strings possíveis, e este universo é gigantesco.
Simplificando, imagine que você queira encontrar uma colisão com a string "paralelepípedo" que gera o hash MD5 "f20ad8e19cfceae9afbcfc15da15b1cf". O que você tem que fazer é gerar um hash MD5 de toda e qualquer string possível para encontrar uma que resulte naquele mesmo hash. Sempre existe a possíbilidade de você conseguir encontrar uma colisão, inclusive na primeira tentativa, mas as probabilidades disto ocorrer são tão ínfimas que sequer são consideradas. O mais provável é que o tempo que você leve para conseguir uma colisão seja tão grande que o processo todo não vale a pena. E existe a possibilidade igualmente boa de você não encontrar colisão alguma mesmo que fique rodando o algoritmo por anos. Lembre-se que neste artigo estamos falando apenas de hash de strings, mas o algoritmo mapeia qualquer dado binário.
Em segundo lugar, algoritmos modernos como os do SHA-2 possuem uma resistência a colisões que ainda não pôde ser quebrada na prática.
A conclusão é que um algoritmo bem implementado não oferece nenhum risco aos dados que proteje.
Os principais problemas acontecem quando a implementação não é bem feita.
É o que veremos no próximo artigo da série.

Um comentário: