Já ouvi falar sobre uma técnica assim chamada, e qualquer coisa sobre explorar colisões de hashes.
Mas como funciona essa técnica, e onde ela pode ser aplicada?
Esse ataque é baseado no problema do aniversário: se n pessoas estiverem numa sala, qual a probabilidade de duas delas fazerem aniversário no mesmo dia? Como existe um número fixo de dias no ano, e a probabilidade de se nascer em um determinado dia é aleatória e igualmente provável para cada dia, a chance da pessoa A nascer no mesmo dia da pessoa B é fixa: 1/365. Se entra uma pessoa C, há 1/365 de chance entre ela e A e 1/365 de chance entre ela e B. À medida que o número de pessoas vai aumentando, a probabilidade vai crescendo, até chegar a 100% quando n for 366 (ignorando anos bissextos para simplificar).
No entanto, dada a maneira como o número de combinações dois a dois cresce rapidamente conforme aumenta o número de pessoas, essa probabilidade supera os 50% muito antes do número de pessoas chegar a 183: apenas 23 pessoas são suficientes. E após 70 pessoas, a probabilidade já supera os 99,9%.
Da mesma forma, funções de hash recebem como entrada um dado de tamanho arbitrário e produzem como saída um dado de tamanho fixo. De modo que se um número muito grande de entradas distintas forem utilizadas, a probabilidade da colisão de hashes se torna cada vez maior. Ou seja, pode-se produzir colisões simplesmente gerando-se um número suficientemente alto de entradas distintas, e pelo problema do aniversário esse número é muito menor do que o total de saídas distintas.
A título de exemplo, se uma função de hash possui uma saída de 128 bits, um ataque de força bruta teria de examinar em média 2^127
entradas de modo a produzir uma colisão. Um ataque de aniversário, por outro lado, faria o mesmo com apenas 2^64
tentativas (fonte).
As aplicações práticas, no entanto, são bastante limitadas. A menos que você esteja projetando uma primitiva criptográfica - caso em que é preciso se perguntar: 1) quantas mensagens precisariam ser processadas para que chance de colisão se torne significativa? 2) qual a rapidez máxima que você consegue processar essas mensagens? 3) o que você pode fazer caso você encontre uma colisão? (i.e. no que isso te beneficia?)
No entanto, sistemas criptográficos - que em geral são compostos de várias primitivas distintas - costumam ser projetados de modo a serem resistentes a ataques de aniversário ou, pelo menos, que o custo de um ataque de aniversário seja pelo menos tão alto quanto sua maior vulnerabilidade possível (e esta mais alta do que seria passível de ser explorada na prática). De modo que essa não é uma preocupação que o desenvolvedor comum precise ter, independentemente do cenário (ex.: hash de senhas? irrelevante, seja ele feito de forma correta ou não; checksum de arquivos? hashes bons não são vulneráveis, hashes ruins são ruins por outros motivos; cifragem? idem; etc).
Para não deixar sem exemplo (teórico; como dito, na prática esse ataque não costuma ser viável), vou reproduzir aqui o exemplo da Wikipedia:
Digamos que Mallory quer enganar Alice para que ela assine digitalmente um contrato fraudulento. Ela elabora um número muito grande de contratos legítimos - variando somente alguns detalhes, como pontuação, espaçamento, etc, mas mantendo a semântica do mesmo constante - e um número também grande de contratos fraudulentos. Produz o hash de todos (o hash normalmente é a primeira etapa num sistema de assinatura digital - e o mesmo pode ser feito por Mallory sem o conhecimento da chave privada de Alice), na esperança de encontrar uma colisão entre uma versão honesta e uma fraudulenta.
De posse dessa colisão, ela entrega o contrato honesto para Alice assinar. Alice assina com sua chave privada. No entanto, como o que é assinado é um hash do contrato e não o contrato em si, ao assinar aquele hash ela implicitamente assinou também o contrato fraudulento (uma vez que ambos possuem o mesmo hash). Mallory então pode pegar a assinatura, anexá-la ao contrato fraudulento, e apresentá-lo a terceiros - que confiarão que Alice o assinou uma vez que a assinatura digital é válida para aquele documento.
O "Ataque de aniversário" é utilizado unicamente para medir o quão o algorítimo criptográfico é seguro (ou não) pelas técnicas de força bruta.
O "ataque de aniversário" é nada mais do que uma força bruta. Os algorítimos de encriptação em funções de hash estão expostos à duas vulnerabilidades: ataque de força bruta e a criptoanalise.
O ataque de força bruta depende da quantidade do tamanho do valor da hash em bit. Enquanto uma criptoanalise, ao contrário, se baseia em uma falha especifica no algorítimo criptográfico.
Ataques de pre-imagem:
Um
y
obtido tal queH(x) = y
.
A resistência de "pre-imagem" garante que uma hash é verdadeiramente de mão única, não sendo possível gerar a mensagem utilizando a hash. Se a hash não for resistente à pre-imagem um atacante terá como ler a mensagem e/ou obter o código secreto. Por exemplos imagine utilizar uma hash insegura à ataques de pré-imagem em assinaturas de HMAC. Se alguém que interceptar conseguirá chave utilizada e poderá alterar a mensagem e assinar usando a chave descoberta.
Isso indica que você tem uma hash h e uma mensagem m e sabe que a hash utilizada é H( s || m )
. Você deseja descobrir o s
para que pudesse gerar uma nova mensagem e criar uma assinatura válida. Para isso você precisaria inverter a função da hash, de modo que consiga quebrar a "mão-única", sim o MD5 também é vulnerável a isso.
Ataque de segunda pre-imagem:
Um
y
ex
tal queH(x) = H(y)
porémx != y
.
A "segunda pré-imagem" é gerar uma nova mensagem, diferente, de maneira que duas mensagens possuam uma mesma hash.
Uma pessoa deseja encontrar um valor x
tal que H(x)
seja igual à uma uma hash h
. Por exemplo, imagine que possua um texto a
e a H(a)
resulta em h
, você deseja que um outro texto, b
tal que H(b)
também seja igual h
, criando assim uma colisão.
Para que consiga faze isto você irá gerar um valor de b
e experimentar cada valor gerado até que H(b) = H(a)
. O número de tentativas necessárias para encontrar uma colisão é proporcional 2**m
, o m
é o número de bits, logo você deveria gerar até 2**(m-1)
valores de b
para achar um que seja igual a hash resultante do H(a)
.
Ataque do dia do aniversário:
Se o esforço exigido seria de 2**(m-1)
, mas utilizando o resultado matemático do paradoxo do dia do aniversario o esforço será menor. O paradoxo do aniversário foi explicado pelo @mgibsonbr, basicamente isso torna a possibilidade de 2**(m-1)
reduzida para 2**(m/2)
, vou explicar de um jeito diferente.
Se você precisa de 23 pessoas para ter 50% de chance de encontrar uma pessoa entre si com o mesmo dia de aniversário. Então, quantas pessoas são necessárias para que eu tenha 50% de chance de encontrar alguém que faz aniversário no mesmo dia que eu? 183 (365 / 2).
Isso é o mesmo com a hash, quantas hash preciso gerar (tendo 50% de chance) de encontrar uma hash que seja igual a minha? x/2, no caso: 2**(x/2)
, onde o x
é o número de bits.
Se for utilizado uma hash de 64 bits, seria necessário apenas 2**32
tentativas. Em 1994, o Van Oorschot provou ser possível quebrar o MD5, criando colisões em apenas 24 dias por 10 milhões de dólares:
As a particular example, a $10 million custom machine for applying parallel collision search to the MD5 hash function could complete an attack with an expected run time of 24 days.
Vale lembrar que o tamanho da hash do MD5 é de 128 bits e isso foi proposto lá em 1994, nesse caso essa mesma maquina demoraria mais de quatro mil anos para quebrar uma criptografia de 160 bits, como o SHA1. Hoje em dia uma hash de 160 bits, como o SHA1
já não é segura, mas era na época.
O mesmo exemplo do @mgibsonbr pode ser aplicado em algo mais grave o SSL, que possui como base assinaturas! Em 2008 um grupo conseguiu falsificar o SSL utilizando o poder de literalmente duzentos Playstation 3 (não é erro, é literalmente 200 x Sony Playstation 3). Isso foi possível criando colisões de certificados de SSL que utilizavam o fraco algorítimo MD5.
Em 2009 ainda existiam cerca de 14% dos websites utilizando certificados vulneráveis, talvez existam até hoje, mas os navegadores não mais confiam em certificados em MD5. Nessa mesma época o SHA-1 era largamente utilizado, embora já não fosse considerado seguro desde 2005. A razão da falha do SHA-1
é por criptoanalise, em tese a força bruta teria (através do calculo do "Ataque do aniversário) 2**80
operações, porém por falha na criptografia esse número cai para 2**69
.
Em 2014 o Google Chrome passou não confiar mais em certificados SHA-1, uma vez que já não era mais considerado seguro desde 2005. Isso mostrava uma imagem de triangulo junto ao cadeado no canto do navegador e em novembro do mesmo ano o cadeado foi removido, assim não mostrado ao usuário que o website como "Seguro" (mas sim como um HTTP normal) e em 2015 é mostrado como "Inseguro".
A Microsoft apenas permitirá a utilização de certificados SHA-1 até 2016:
However, SHA-1 Code Signing Certificates should be used for targeting at these earlier platforms only due to the fact that SHA-1 is no longer considered to be secure and is susceptible to attacks. Windows 7 and later platforms will stop accepting SHA-1 Code Signing Certificates after January 1 st , 2016. Software developers may need to use both SHA-1 and SHA-2 certificates depending on the target platforms.
Isso indica que hoje em dia o Windows apenas aceita assinaturas da "família" do SHA-2 (entenda como SHA-224, SHA-256, SHA-384, SHA-512), a razão é simples: se tornou fácil colidir as assinaturas.
Em questão de alguns anos, conforme o avanço da tecnologia for barateando o custo de tais forças brutas os outros algorítimos criptográficos, como o SHA-256 será considerado totalmente inseguro, é questão de tempo.