Rainbow Tables – O que são? Como usar?

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.

Image result for skeleton waiting by computer

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.

  1. Pegue uma palavra aleatória (Ex: Batata)
  2. Calcule o hash dessa palavra (Ex: Batata -> 1276167df2a1…)
  3. 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).
  4. 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…)

Image result for rainbow tables are not hash tables

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *