Tabela Rainbow

Uma tabela rainbow é uma estrutura de consulta pré-calculada baseada em cadeias de hashes. O invasor gera cada cadeia alternando repetidamente a função hash com uma sequência de funções de redução específicas para cada posição da cadeia, a partir de uma senha candidata, e armazena apenas o ponto inicial e o ponto final de cada cadeia — não cada hash intermediário —, o que reduz muito o espaço de armazenamento em comparação com guardar o hash de cada senha individualmente.

Quando obtém uma senha com hash a partir de uma violação, o invasor testa, para cada posição possível da cadeia — da última até a primeira —, a hipótese de que o hash ocupa essa posição: aplica a partir dele a sequência restante de funções de redução e hash até chegar a um ponto final, e verifica se esse ponto final corresponde a algum dos armazenados; havendo correspondência, ele reconstrói a cadeia correspondente desde o início, aplicando as funções de redução na ordem correspondente a cada posição, para chegar à senha candidata. A senha só é recuperada se essa reconstrução reproduzir o hash original; senhas fora das cadeias pré-computadas não são encontradas. Mesmo quando há correspondência, contra hashes MD5 ou SHA1 sem sal, o processo costuma ser rápido, mas nem sempre imediato.

A defesa é o sal: acrescentar um valor aleatório a cada senha antes de gerar o hash. Como o sal é único por senha, tabelas pré-calculadas se tornam inúteis, já que cada combinação exigiria sua própria tabela. Algoritmos modernos de hash de senha (bcrypt, Argon2) já incluem sal por padrão.