O que são tabelas de arco-íris e como são usadas?

As tabelas do arco-íris são comumente confundidas com outra técnica mais simples que aproveita um tempo de computação compensação de torage na recuperação de senha: tabelas de hash.

As tabelas de hash são construídas por hash de cada palavra em um dicionário de senha. Os pares de hash de senha são armazenados em uma tabela, classificados por valor de hash. Para usar uma tabela hash, basta pegar o hash e realizar uma pesquisa binária na tabela para encontrar a senha original, se estiver presente.

As tabelas do arco-íris são mais complexas. A construção de uma tabela do arco-íris requer duas coisas : uma função de hash e uma função de redução. A função de hash para um determinado conjunto de Rainbow Tables deve corresponder à senha com hash que você deseja recuperar. A função de redução deve transformar um hash em algo utilizável como uma senha. Uma função de redução simples é Base64 codifique o hash e trunque-o para um determinado número de caracteres.

As tabelas do arco-íris são construídas com “cadeias” de um determinado comprimento: 100.000 por exemplo. Para construir a cadeia, escolha um valor inicial aleatório. aplique as funções de hashing e redução a esta semente e sua saída e continue iterando 100.000 vezes. Apenas a semente e o valor final são armazenados. Repita este processo para criar quantas cadeias desejar.

Para recuperar um senha usando Rainbow Tables, o hash de senha passa o processo acima para o mesmo comprimento: neste caso 100.000, mas cada elo da cadeia é retido. Cada elo da cadeia é comparado com o valor final de cada cadeia. Se houver uma correspondência, a cadeia pode ser reconstruída, mantendo a saída de cada função de hashing e a saída de cada função de redução. Essa cadeia reconstruída conterá o hash da senha em questão, bem como a senha que a produziu.

Os pontos fortes de uma tabela de hash são que recuperar uma senha é extremamente rápido (pesquisa binária) e a pessoa que está construindo a tabela hash pode escolher o que deve ser inserido, como as 10.000 senhas principais. O ponto fraco em comparação com as Rainbow Tables é que as tabelas hash devem armazenar cada par de hash-senha.

As Rainbow Tables têm a vantagem de que a pessoa que as constrói pode escolher quanto armazenamento é necessário, selecionando o número de links em cada cadeia. Quanto mais links entre a semente e o valor final, mais senhas são capturadas. Um ponto fraco é que a pessoa que está construindo as cadeias não escolhe as senhas que capturam, portanto, o Rainbow Tables não pode ser otimizado para senhas comuns. Além disso, a recuperação de senha envolve a computação de longas cadeias de hashes, tornando a recuperação uma operação cara. Quanto mais longas as cadeias, mais senhas são capturadas nelas, mas mais tempo é necessário para encontrar uma senha dentro dela.

As tabelas de hash são boas para senhas comuns, as tabelas do arco-íris são boas para senhas difíceis. A melhor abordagem seria recuperar o máximo de senhas possível usando tabelas hash e / ou cracking convencional com um dicionário das N senhas principais. Para aqueles que sobraram, use as tabelas Rainbow.

Comentários

• Oh meu Deus, admito que estou chocado – discuto e explico as tabelas Rainbow todas as tempo, e todo esse tempo parece que fui um dos ” comumente confundidos “! Eu iria no total mais de 1000 vezes, realmente aprendi algo novo aqui (e pensei que sabia a resposta). Ainda bem que fiz a pergunta, afinal … Obrigado!
• Embora para ser específico (agora que você abriu meus olhos, fiz mais pesquisas :)), Rainbow Tables são diferenciadas de Hellman Hash Chains usando várias funções de redução diferentes. Mais complexo, de fato … mas realmente uma ideia muito bonita (Ah! É por isso que eles ‘ são chamados de ” Rainbow ” tabelas?)
• Concordo que esta é uma explicação muito boa. Na minha resposta, expliquei de forma simples e também realmente expliquei errado por ser muito simples.A beleza das tabelas Rainbow é o fato de que elas não ‘ armazenam todos os valores de hash. Vou editar o meu, mas também votarei nisso, pois é definitivamente uma explicação melhor.
• Hmm … Embora quanto mais eu penso nisso, nos sistemas da vida real, as Rainbow Tables não são tão úteis quanto tabelas de hash. Como você afirmou, para senhas comuns, as tabelas de hash são muito melhores (uma vez que são ordem de magnitude mais rápidas e os requisitos de tamanho para um dicionário de senhas são, obviamente, muito menores do que toda a gama possível de senhas). E quem ‘ estamos enganando? A maioria das senhas se enquadra nessa categoria. É muito raro (e permanecerá por algum tempo) que você precise ligar para o RT.
• Infelizmente, você me perdeu aqui: ” Para recuperar uma senha usando Rainbow Tables, a senha passa pelo processo acima para o mesmo tamanho. ” Como a senha pode passar pelo processo quando ‘ nem mesmo é conhecido? Você quis dizer o hash da senha? Além disso, há ‘ s isto: ” Cada elo da cadeia é comparado com o valor final de cada cadeia. ” Não consigo ver uma situação em que um elo da cadeia corresponda ao valor final da cadeia, já que o valor do link seria continuamente hash e reduzido.

Existem muitas boas explicações sobre o que são as tabelas arco-íris, esta Como funcionam as tabelas arco-íris é particularmente bom. Além disso, o artigo da Wikipedia também tem uma explicação muito boa. Para ler um pouco mais detalhadamente, o artigo definitivo sobre o assunto é Fazendo uma troca mais rápida de memória de tempo criptanalítica .

Uma explicação simples das tabelas do arco-íris é que elas usam uma técnica de troca de memória de tempo. Significa, em vez de pegar um valor de hash de destino e um dicionário de palavras, fazer hash de cada palavra e fazer a comparação em tempo real (abordagem de força bruta usando algo como John ), em vez disso, você faz o hash de todos os valores no dicionário antecipadamente (isso pode levar muito tempo dependendo do tamanho do dicionário). Mas, uma vez feito isso, você pode comparar quantos hashes quiser com os valores pré-hash nas tabelas de arco-íris, isso é significativamente mais rápido do que calcular os hashes novamente.

A explicação que escrevi aqui anteriormente em um esforço para ser curto era enganoso, pois não explicava o uso de reduções que as tabelas arco-íris fazem. Para uma explicação melhor até que eu reescreva este trecho, consulte @Crunge answer .

Você pode gerar as tabelas de arco-íris usando um aplicativo como RainbowCrack ou você pode baixá-los de fontes como The Shmoo Group , Site do projeto Rainbow Tables gratuito, projeto Ophcrack e muitos outros lugares, dependendo do tipo de hashes para os quais você precisa das tabelas.

Para se proteger contra um ataque baseado em Rainbow Table, o método mais eficaz de combatê-lo é garantir que cada hash dentro de um sistema seja salgado . Isso torna as rainbow tables pré-geradas inúteis e significaria que um invasor teria que gerar um conjunto personalizado de tabelas para usar contra os hashes direcionados, o que só seria possível se eles conhecessem o salt.

Comentários

• Além disso (considere editá-lo no), se você usar um sal diferente para cada senha, gravando-o sem criptografia no banco de dados, o atacado precisaria gerar um conjunto personalizado de tabelas para cada hash, o que anularia o objetivo do exercício – o objetivo da tabela arco-íris é forçar todo o espaço da senha e, em seguida, obter todas as senhas para uma força bruta esforço; se você ‘ está obtendo apenas uma senha por tabela de arco-íris, você também pode usar força bruta direta no hash.

Finalidade e relevância

As tabelas Rainbow ajudam a decifrar senhas difíceis, ou seja, aquelas que não podem ser encontradas em um grande dicionário. As senhas eram historicamente armazenadas como hashes simples em bancos de dados, e é contra isso que as rainbow tables são eficazes: crie uma única rainbow table (lento) e execute qualquer número de bancos de dados cheios de hashes (rápido).

Atualmente, cada vez mais sistemas usam algoritmos de armazenamento de senha adequados, como Bcrypt, Scrypt ou Argon2. Consulte: Como [armazenar] senhas com segurança? Esses algoritmos são não é mais “vulnerável” às rainbow tables: como cada hash é único, mesmo que as senhas sejam iguais, as rainbow tables não funcionam mais.

É por isso que as rainbow tables são impopulares hoje.Mesmo que algo moderno como Argon2 não seja usado, os desenvolvedores hoje em dia geralmente sabem que devem pelo menos usar um salt. Isso já é o suficiente para tornar inútil uma tabela de arco-íris.

Como funcionam

Criação de uma tabela

Imagine que criamos uma tabela rainbow com apenas duas cadeias, cada uma com comprimento 5. A tabela rainbow é para a função hash fictícia MD48, que produz 48 bits (apenas 12 caracteres hexadecimais). Ao construir a cadeia, vemos o seguinte:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Começamos com 0 porque é a primeira cadeia (só precisamos de algum valor para começar). Quando hash isso com MD48, ele se transforma em cfcd208495d5. Agora aplicamos uma função “reduzir” que basicamente formata esse hash de volta em um senha, e terminamos com “z”. Quando o hash novamente, obtemos fbade9e36a3f, reduzimos novamente e obtemos renjaj820 . Existem mais alguns ciclos e o resultado final é WLgOSj.

O mesmo para a segunda cadeia. Apenas começamos com outro valor e fazemos a mesma coisa. Isso termina em 0uUoAD.

Nossa tabela arco-íris completa agora é esta:

WLgOSj => 0 0uUoAD => 1 

É tudo o que você precisa armazenar.

Procurando um hash

Digamos que encontramos um hash online, 7668b2810262. Vamos quebrá-lo usando nossa tabela!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

Para brincar com isso sozinho, os exemplos acima foram criados usando este script Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Propriedades de escala

Resumindo:

• Pesquisas rápidas significam tabelas maiores, assumindo que a cobertura permaneça a mesma.
• Melhor cobertura significa pesquisas mais lentas ou tabelas maiores.
• Tabelas menores significam pesquisas mais lentas ou cobertura pior.

As seções a seguir assumem que o tempo por redução de hash + é de 1 µs e não leva em consideração as colisões. Todos esses são números aproximados, que pretendem ser exemplos e não valores exatos.

Tempo de pesquisa

Se uma operação de redução de hash + levar um microssegundo, a geração de uma tabela com um milhão de cadeias e 10.000 reduções por cadeia levaria cerca de 3 horas:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 horas.

Fazer uma pesquisa nessa tabela leva em média 10 milissegundos. Isso ocorre porque normalmente teremos que passar por chain_length/2 reduções antes de encontrarmos qual cadeia contém o hash. Por exemplo, podemos ter que fazer 3.000 reduções em um hash antes de encontrar um valor que está na tabela. Em seguida, temos que refazer essa cadeia desde o início até encontrar o valor correspondente. Se tivéssemos que fazer 3.000 para encontrá-lo em nossa tabela, teríamos de fazer 7.000 reduções desde o início para chegar ao ponto certo na cadeia. Basicamente, fazemos tantas operações ao olhar para cima quanto ao gerar uma única cadeia. Portanto, o tempo de pesquisa é 10.000 vezes um microssegundo, o que é dez milissegundos (ou um centissegundo, se preferir).

Requisitos de armazenamento

Quando você deseja fazer uma tabela de pesquisa completa e rápida para uma função hash, mesmo MD5, você ainda precisará de cem bilhões de bilhões de terabytes de armazenamento. não é muito útil. Mas e se quisermos cobrir apenas senhas em minúsculas até 10 caracteres?

Se quisermos gastar no máximo 30 segundos procurando um hash, e presumindo que precisamos de 1 microssegundo (um milionésimo de segundo) por hash + reduzir o ciclo, então podemos ter um comprimento de cadeia de: 1 million × 30 = 30 milhões. Existem 26 ¹⁰ (ou 10 ¹⁴ ) possíveis senhas em minúsculas de 10 caracteres, e por cadeia cobrimos 30 milhões de valores. Isso nos deixa com 4 milhões de cadeias. Sabemos que cada cadeia tem apenas um valor inicial e final armazenado e que os valores têm 10 caracteres cada. Portanto, 2 × 10 × 4 million = dados de 76 MiB.

Gerar a tabela iterando todas as senhas de 10 caracteres leva muito tempo: 30 segundos por cadeia, vezes 4 milhões de cadeias é cerca de 91 anos. Muitas pessoas estariam interessadas em tal tabela, então, ao juntar 1092 CPUs (= 91 × 12), leva apenas 1 mês. Isso mostra o quão pequena essa tabela pode ser comparada ao espaço de senha que ela cobre: as pesquisas levam apenas 30 segundos e você tem que armazenar apenas 76MiB de dados.

Conclusão

As tabelas Rainbow podem ser considerada uma compensação de tempo e memória : armazena-se apenas uma pequena parte da tabela e a recupera por meio de alguns cálculos extras no tempo de consulta. Esta é parte da razão pela qual os sais, ou melhor, um bom algoritmo de armazenamento de senha como Scrypt ou Argon2 são importantes para manter as senhas seguras.Uma tabela de arco-íris só pode recuperar uma senha com salt se a tabela contiver uma entrada grande o suficiente para conter o sal e a senha, o que seria extremamente ineficiente e anularia todo o propósito.

Observe que algo semelhante se aplica à criptografia: quando as pessoas criptografam arquivos com uma senha, uma tabela de arco-íris pode ser construída para quebrar os arquivos. Digamos que o software use AES e o primeiro bloco do arquivo deva ser descriptografado para “senha correta” usando a senha fornecida pelo usuário, então uma rainbow table usaria AES em vez de uma função hash.

Sempre que você manipular uma senha (um segredo de força desconhecida e especialmente se o usuário puder reutilizá-la), sempre execute-a por meio de um algoritmo de armazenamento de senha adequado (lento) para torná-la lenta e exclusiva para ser quebrada.

Comentários

• Boa explicação. Se entendi bem, o poder das tabelas de arco-íris está em ter uma boa função de redução, certo? Como faço para encontrar um bom? E como evito colisões para todos os candidatos nas cadeias?
• @ Kyu96 Boas perguntas! Eu não ‘ não sei a resposta, mas estaria interessado se você encontrar uma. Esta página trata apenas da questão geral do que é uma tabela arco-íris, não de detalhes específicos como projetar um algoritmo. Você deve abrir uma nova pergunta , mas este site é sobre ” proteger ativos de ameaças digitais ” (iirc ) Acho que seria no tópico do nosso site irmão, crypto.stackexchange.com , que é sobre ” a matemática e as propriedades dos sistemas criptográficos, sua análise (” criptoanálise “) e tópicos subsidiários que geralmente compõem a criptologia, como o número aleatório geração. ”