Speed Hashing

Os hashes são um pouco como impressões digitais para dados.

Um determinado hash representa de forma exclusiva um arquivo ou qualquer coleção arbitrária de dados. No mínimo em teoria. Esse é um hash MD5 de 128 bits que o senhor está vendo acima, portanto, ele pode representar no máximo 2¹²⁸ itens exclusivos, ou 340 trilhões de trilhões de trilhões. Na realidade, o espaço utilizável é substancialmente menor; o senhor pode começar a ver colisões significativas quando tiver preenchido metade a raiz quadrada do espaço, mas a raiz quadrada de um número impossivelmente grande ainda é impossivelmente grande.

Em 2005, perguntei-me sobre a diferença entre um checksum e um hash. O senhor pode pensar em um checksum como o nome completo de uma pessoa: Eubediah Q. Horsefeathers. É um atalho para a exclusividade que é rápido e simples, mas fácil de falsificar, porque a segurança não é realmente o objetivo da nomeação. O senhor não se aproxima de uma pessoa e exige suas impressões digitais para provar que ela é quem diz ser. Os nomes são apenas desambiguadores convenientes, uma forma de determinar rapidamente com quem o senhor está falando por motivos sociais, e não uma prova absoluta de identidade. Certamente pode haver várias pessoas no mundo com o mesmo nome, e não seria muito difícil mudar legalmente seu nome para corresponder ao de outra pessoa. Mas mudar seu impressão digital para coincidir com a de Eubediah é outra questão totalmente diferente; isso deve ser impossível, exceto nos filmes.

Os hashes seguros são projetados para serem à prova de adulteração

Uma função hash segura adequadamente projetada altera radicalmente sua saída com pequenas alterações de um único bit nos dados de entradamesmo que essas alterações sejam maliciosas e tenham a intenção de fraudar o hash. Infelizmente, nem todos os hashes foram projetados adequadamente, e alguns, como o MD5, estão totalmente quebrados e provavelmente deveriam ser revertidos para checksums.

Como explicaremos a seguir, o algoritmo de Wang e Yu pode ser usado para criar arquivos de tamanho arbitrário que tenham hashes MD5 idênticos e que diferem apenas em 128 bytes em algum lugar no meio do arquivo. Várias pessoas usaram essa técnica para criar pares de arquivos interessantes com hashes MD5 idênticos:

• Magnus Daum e Stefan Lucks criaram dois arquivos PostScript com hash MD5 idêntico, sendo que um deles é uma carta de recomendação e o outro é uma autorização de segurança.
• Eduardo Diaz descreveu um esquema pelo qual dois programas poderiam ser empacotados em dois arquivos com hash MD5 idêntico. Um programa “extrator” especial transformava um arquivo em um programa “bom” e o outro em um programa “ruim”.
• Em 2007, Marc Stevens, Arjen K. Lenstra e Benne de Weger usaram uma versão aprimorada do ataque de Wang e Yu, conhecida como colisão de prefixo escolhido para produzir dois arquivos executáveis com o mesmo hash MD5, mas com comportamentos diferentes. Ao contrário do método antigo, em que os dois arquivos só podiam diferir em alguns bits cuidadosamente escolhidos, o método do prefixo escolhido permite que dois arquivos completamente arbitrários tenham o mesmo hash MD5, acrescentando alguns milhares de bytes no final de cada arquivo.
• Didier Stevens usou o programa evilize (abaixo) para criar dois programas diferentes com a mesma assinatura digital Authenticode. O Authenticode é o mecanismo de assinatura de código da Microsoft e, embora use SHA1 por padrão, ainda é compatível com MD5.

Se o senhor pudesse imitar a impressão digital ou o DNA de outra pessoa à vontade, poderia fazer algumas a sério coisa ruim. O MD5 está claramente comprometido, e o SHA-1 está não parece muito bom atualmente.

A boa notícia é que os algoritmos de hashing (supondo que o senhor não tenha criado o seu próprio, Deus o livre) foram projetados por matemáticos e criptógrafos profissionais que sabiam o que estavam fazendo. Basta escolher um hash de uma safra mais recente do que MD5 (1991) e SHA-1 (1995) e o senhor não terá problemas, pelo menos no que diz respeito a colisões e exclusividade. Mas continue lendo.

Os hashes seguros são projetados para serem lentos

A velocidade de um cálculo de soma de verificação é importante, pois as somas de verificação geralmente funcionam nos dados à medida que são transmitidos. Se a soma de verificação demorar muito, isso poderá afetar as velocidades de transferência. Se a soma de verificação incorrer em uma sobrecarga significativa da CPU, isso significa que a transferência de dados também ficará mais lenta ou sobrecarregará o computador. Por exemplo, imagine o tipo de soma de verificação que é usado em padrões de vídeo como DisplayPort, que pode atingir o pico de 17,28 Gbit/s.

Mas os hashes não foram projetados para serem rápidos. Na verdade, é exatamente o contrário: os hashes, quando usados para segurança, precisam ser lentos. Quanto mais rápido o senhor puder calcular o hash, mais viável será usar a força bruta para realizar ataques. Infelizmente, “lento” em termos de 1990 e 2000 pode não ser suficiente. Os projetistas do algoritmo de hashing podem ter previsto o aumento previsto da potência da CPU por meio da Lei de Moore, mas é quase certo que o fizeram não vêem os aumentos radicais na capacidade de computação da GPU.

Quão radical? Bem, compare os resultados de uma CPU alimentada por hashcat com a GPU alimentada oclHashcat ao calcular hashes MD5:

Radeon 7970	8213,6 M c/s
CPU AMD de 6 núcleos	52,9 M c/s

A GPU em uma única placa de vídeo moderna produz mais de 150 vezes o número de cálculos de hash por segundo em comparação com uma CPU moderna. Se a Lei de Moore prevê um duplicação do poder de computação a cada 18 meses, a, isso é como espiar 10 anos no futuro. É um material incrível, não é mesmo?

Hashes e senhas

Vamos falar sobre senhas, já que hash e senhas estão intimamente relacionados. A menos que o senhor esteja armazenando as senhas incorretamenteo senhor sempre armazena a senha de um usuário como um hash salgado, nunca como texto simples. Certo? Certo? Isso significa que se o banco de dados que contém todos esses hashes for comprometido ou vazado, oos usuários ainda estão protegidos – ninguém pode descobrir qual é a sua senha com base no hash armazenado no banco de dados. Sim, é claro que existem ataques de dicionário que podem ser surpreendentemente eficazes, mas não podemos proteger os usuários decididos a usar “monkey1” como senha deles mesmos. E, de qualquer forma, a verdadeira solução para os usuários que escolhem senhas ruins não é fazer com que os usuários se lembrem de senhas cada vez mais complicadas e longas, mas eliminar completamente as senhas.

Isso tem uma ramificação infeliz para os hashes de senha: pouquíssimos deles foram projetados tendo em mente uma potência de GPU tão grande e comumente disponível. Aqui estão meus resultados no meu PC atual, que tem duas placas ATI Radeon 7970 gerando quase 16000 M c/s com MD5. Eu usei oclHashcat-lite com a gama completa de um teclado americano comum, ou seja, incluindo letras maiúsculas, minúsculas, números e todos os símbolos possíveis:

todas as senhas MD5s de 6 caracteres	47 segundos
todos os MD5s de senhas de 7 caracteres	1 hora, 14 minutos
todas as senhas MD5s de 8 caracteres	~465 dias
todos os MD5s de senhas de 9 caracteres	fuggedaboudit

O processo é escalonado quase perfeitamente à medida que se adicionam GPUs, de modo que é possível reduzir o tempo pela metade colocando quatro placas de vídeo em uma máquina. Pode parecer loucura, mas os entusiastas têm feito isso desde 2008. E o senhor pode reduzi-lo pela metade novamente construindo outro PC com mais quatro placas de vídeo, dividindo o espaço de ataque. (Continue se o senhor for louco ou estiver trabalhando para a NSA.) Agora temos 117 dias razoáveis para gerar todos os MD5s de 8 caracteres. Mas talvez esse seja o pior cenário possível, pois muitas senhas não têm caracteres especiais. E se tentarmos a mesma coisa usando apenas letras maiúsculas, minúsculas e números?

todas as senhas MD5s de 6 caracteres	3 segundos
todas as senhas MD5s de 7 caracteres	4 minutos
todas as senhas MD5s de 8 caracteres	4 horas
todas as senhas MD5s de 9 caracteres	10 dias
todas as senhas de 10 caracteres MD5s	~625 dias
todas as senhas MD5s de 11 caracteres	fuggedaboudit

Se o senhor estiver curioso para saber qual é o pior cenário possível, uma senha com 12 caracteres, todos em minúsculas, pode ser obtida em cerca de 75 dias nesse PC. Tente você mesmo; aqui está o script que usei:

set BIN=oclHashcat-lite64
set OPTS=--gpu-accel 200 --gpu-watchdog 0 --outfile-watch 0 --restore-timer 0 --pw-min 6 --pw-max 6 --custom-charset1 ?l?d?s?u
%BIN% %OPTS% --hash-type 0 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ?1?1?1?1?1?1?1?1?1?1?1?1?1

Basta modificar o pw-min, pw-max e o custom-charset conforme apropriado. Ou, se o senhor for muito preguiçoso para tentar fazer isso sozinho, navegue pelo benchmarks oclHashcat existentes que outros executaram. Isso também lhe dará uma ideia de como vários hashes conhecidos são computacionalmente caros em GPUs em relação uns aos outros, como:

MD5	23070,7 M/s
SHA-1	7973,8 M/s
SHA-256	3110,2 M/s
SHA-512	267,1 M/s
NTLM	44035.3 M/s
DES	185,1 M/s
WPA/WPA2	348,0 k/s

E quanto às tabelas de arco-íris?

As mesas arco-íris são enormes listas pré-computadas de hashes, trocando pesquisas em tabelas por grandes quantidades de espaço em disco (e potencialmente memória) por velocidade de cálculo bruta. Agora eles estão total e completamente obsoletos. Ninguém que saiba o que está fazendo se incomodaria com isso. Estariam desperdiçando seu tempo. Vou deixar que o Coda Hale explique:

As tabelas Rainbow, apesar de sua recente popularidade como assunto de postagens em blogs, não envelheceram graciosamente. As implementações de crackers de senhas podem aproveitar a enorme quantidade de paralelismo disponível nas GPUs, atingindo o pico de bilhões de senhas candidatas por segundo. O senhor pode literalmente testar todas as senhas alfabéticas e minúsculas que tenham ≤7 caracteres em menos de 2 segundos. E agora o senhor pode alugar o hardware que torna isso possível por menos de US$ 3/hora. Por cerca de US$ 300/hora, o senhor poderia decifrar cerca de 500.000.000.000 de senhas candidatas por segundo.

Considerando essa grande mudança na economia dos ataques criptográficos, simplesmente não faz sentido desperdiçar terabytes de espaço em disco na esperança de que a vítima não tenha usado um salt. É muito mais fácil simplesmente decifrar as senhas. Mesmo um “bom” esquema de hashing de SHA256(salt + password) ainda é totalmente vulnerável a esses ataques baratos e eficazes.

Mas quando armazeno senhas, uso sais, portanto nada disso se aplica a mim!

Ei, incrível, o senhor é inteligente o suficiente não apenas para usar um hash, mas também para salgar o hash. Parabéns.

$saltedpassword = sha1(SALT . $password);

Sei o que o senhor está pensando. “Posso ocultar o sal, assim o invasor não saberá!” O senhor certamente pode tentar. O senhor pode colocar o salt em outro lugar, como em um banco de dados diferente, ou em um arquivo de configuração, ou em algum hardware hipoteticamente seguro que tenha camadas adicionais de proteção. No caso de um invasor obter seu banco de dados com os hashes de senha, mas de alguma forma não ter acesso ou conhecimento do salt, isso é teoricamente possível.

Isso proporcionará mais a ilusão de segurança do que qualquer segurança real. Como o senhor precisa tanto do salt quanto da escolha do algoritmo de hash para gerar o hash e verificar o hash, é improvável que um invasor tenha um, mas não o outro. Se o senhor foi comprometido a ponto de um invasor ter o seu banco de dados de senhas, é razoável supor que ele tenha ou possa obter o seu salt secreto e oculto.

A primeira regra de segurança é sempre presumir e planejar o pior. O senhor deve usar um salt, de preferência um salt aleatório para cada usuário? Sem dúvida, essa é uma boa prática e, no mínimo, permite que o senhor identifique dois usuários que tenham a mesma senha. Mas hoje em dia, os sais por si só não podem mais salvar o senhor de uma pessoa disposta a gastar alguns milhares de dólares em hardware de placa de vídeo, e se o senhor acha que eles podem, está em apuros.

Estou muito ocupado para ler tudo isso.

Se o senhor for um usuário:

Certifique-se de que todas as suas senhas tenham 12 caracteres ou maise, de preferência, muito mais. Recomendo a adoção de frases de efeito, que não só são muito mais fáceis de lembrar do que as senhas (se não forem digitadas), mas também ridiculamente seguros contra a força bruta, devido exclusivamente ao seu comprimento.

Se o senhor for um desenvolvedor:

Use bcrypt ou PBKDF2 exclusivamente para fazer hash de qualquer coisa, o senhor precisa estar seguro. Esses novos hashes foram projetados especificamente para serem difíceis de implementar em GPUs. Fazer não usar qualquer outra forma de hash. Quase todos os outros esquemas de hashing populares são vulneráveis à força bruta por conjuntos de GPUs de commodities, que só ficam mais rápidos, mais paralelos e mais fáceis de programar a cada ano.