Nota: A explicação técnica do que é uma Rainbow Table está na parte 3. Pule para lá, se quiser.
Imagine que você, após utilizar todas suas habilidades de 1337 h4xx0r, consegue uma lista de hashes de senha e quer recuperar as senhas originais. Quais são as suas opções?
1) Brute-Force
Esse é metodo menos custoso em termos de espaço e mais custoso em termos de tempo/processamento. Geralmente é utilizado em último caso, quando nada mais funcionou.
Tudo que você precisa fazer é criar palavras aleatórias e passá-las pela mesma função de hash usada para criar a tabela. Se o hash da palavra aleatória que você usou bater com o hash de algum usuário, você sabe que essa era a senha do usuário (Ou uma colisão, mas isso é muito improvável).
Existem várias maneiras diferentes de se fazer um brute-force, mas esse não é o foco do post.
Diferente dos outros métodos, você não precisa de nenhum arquivo pronto na máquina além do programa que faz o brute-force, tornando-o assim o método mais “leve” em termos de memória. No entanto, se a senha for muito complexa você pode deixar sua máquina rodando até a morte entrópica do universo e não encontrar a senha original.
2) Hash Table ou Lookup Table
Esse é o método mais simples e mais rápido, porém mais falível e que gasta mais espaço em disco. Geralmente é usado primeiro.
Você precisa de uma lista pré-computada de palavras e o hash resultante de cada uma, como o exemplo abaixo:
Então, dado um hash qualquer, tudo que você precisa fazer é ver se ele está na lista. Se ele estiver, parabéns! Você já sabe a senha original. Se não estiver, você pode chorar ou tentar outro método.
Como já dito anteriormente, esse é método que gasta mais espaço em disco. Quanto, exatamente? Bom, a função MD5 por exemplo é considerada velha e fraca, e cada hash tem 128 bits. Isso nos dá um total de 2^128 hashes possíveis, cada um com 128 bits, o que nos dá algo em torno de 10^30 Gigabytes. 9 em cada 10 dentistas concordam que 10^30 é um número muito muito muito muito grande.
Ele é frequentemente confundido e chamado de “Rainbow Table”. Não sei por quê, mas gostaria de deixar claro que Rainbow Table é um conceito completamente diferente e que será explicado agorinha mesmo:
3) Rainbow Table
Finalmente chegamos.
Usar Rainbow Tables é um “meio-termo” entre um brute-force e uma Hash Table: elas não consomem tanto espaço quanto uma Hash Table, mas requerem tempo de processamento para você achar a senha original.
Criar uma Rainbow Table é um processo extremamente demorado, mas depois que ela é criada, utilizá-la não é tão difícil.
Para facilitar, vou explicar primeiro como uma Rainbow Table é criada.
- Pegue uma palavra aleatória (Ex: Batata)
- Calcule o hash dessa palavra (Ex: Batata -> 1276167df2a1…)
- Crie uma nova palavra usando à partir desse hash. Para isso, você deve usar uma função de redução. Ela pode ser algo extremamente simples, como pegar os 6 primeiros caracteres do hash (Ex: 1276167df… -> 127616 é sua nova palavra).
- Volte para o passo 2. A cada 10000 loops, por exemplo, salve o par palavra/hash da palavra em algum arquivo texto.
Ou seja, você transforma a palavra em hash, o hash em palavra, a palavra em hash, e por aí vaí… Você só precisa gravar alguns pontos dessa sua “cadeia”, fazendo com que a Rainbow Table seja bem menor que uma hash Table.
O processo continua até que a lista se torne grande o bastante OU o computador pegue fogo. Geralmente também são feitas outras “cadeias” à partir de palavras iniciais diferentes, para diversificar o negócio. A imagem abaixa roubada da Wikipédia ilustra bem a ideia:
(OBS: A imagem abaixo usa uma função de redução completamente diferente. No caso, é uma função que transforma “ao4kd” em “secret”, “9kpmw” em “jimbo”, e por aí vai…)
MAS CALMA, ainda não chegamos no pulo do gato necessário para tornar essa “cadeia” útil. Qual o pulo do gato? Você vai ver agora.
The jump of the cat, ou, como usar uma Rainbow Table para quebrar um hash:
Você tem a sua Rainbow Table:
E você pegou um hash qualquer e começou a passar ele pela função de redução:
E você viu que, uma hora, o hash que você gerou bateu com algum que já tinha sido calculado:
Então, o que você precisa fazer agora para achar a senha original?
Já descobriu? Não? Talvez o gráfico abaixo te ajude:
Percebeu agora? Se você chegou até um ponto que estava registrado na RainbowTable, basta utilizar a função de redução à partir do ponto anterior! A função de redução te levará até a palavra que foi usada para gerar aquele hash.
Não entendeu? Calma. Leia de novo. O negócio é bizarro mesmo.
Como toda boa ideia, o diabo está nos detalhes. Existem muitas formas diferentes de se fazer uma Rainbow Table para evitar algumas coisinhas chatas.
Um ponto importantíssimo sobre Salts e Rainbow Tables
Se um Salt fosse… um Sal… o Rainbow Table seria uma lesma indefesa, que é derretida pela cloretisse de sódio do sal.
Em termos mais claros: Salts derrotam Rainbow Tables. Senhas armazenadas com Salts não podem ser quebradas com Rainbow Tables, à não ser que exista uma Rainbow Table para aquele Salt específico (e muito provavelmente não existe.)
Ferramentas Práticas
Uma ferramenta que pode quebrar hashes na prática usando rainbow-tables é o incrível RainbowCrack. Vale conferir!
Conclusão
Espero ter sido claro o bastante. Se não fui, por favor deixe um comentário ou me envie um pombo-correio com suas sugestões, dúvidas, críticas e declarações de amor.
Mais detalhes podem ser encontrados nas páginas abaixo (em inglês): http://kestas.kuliukas.com/RainbowTables/
https://en.wikipedia.org/wiki/Rainbow_table