MD5 desmistificado

Não é de hoje que surgem burburinhos toda vez que há uma grande divulgação de vulnerabilidades em algoritmos de criptografia. É até muito lógico se esperar grandes movimentações e agito, já que muita coisa vem sendo protegida baseada nesse conceito antigo, mas muito eficiente. Imagino a sensação de insegurança que paira nas vésperas de grandes conferências sobre o tema, principalmente quando já há aquela desconfiança no ar ...

Apesar de compreender, infelizmente também tenho acompanhado como alguns casos são veiculados e passados fora do contexto. Na maioria das vezes, as quebras apresentadas não são, por si só, generalizadas. Elas podem ser reproduzidas, mas exigem condições específicas que acabam por limitar a exploração da vulnerabilidade. Nas apresentações, os pesquisadores tomam todo o cuidado possível para preservar a pesquisa e fazer com que os resultados sejam aplicados na melhoria da segurança, inclusive deixando claro o contexto onde o problema acontece. Nem todo mundo que veicula o trabalho dos pesquisadores tem o mesmo cuidado, e no fim das contas uma vulnerabilidade que exige várias condições únicas para ser explorada acaba sendo veiculada na mídia fora do contexto e com a famosa frase "caiu o algoritmo xyz". Resultado: desconfiança e até um certo pânico, na maioria das vezes completamente infundado. A situação lembra um pouco a antiga brincadeira do telefone sem fio, e reforça o ditado que diz "quem conta um conto aumenta um ponto".

Recentemente, uma bomba dessas explodiu nos jornais. Um grupo de pesquisadores mostrou, durante sua palestra, que era possivel gerar uma CA falsa que poderia assinar certificados falsos que seriam reconhecidos como verdadeiros. A base da pesquisa foi a quebra do MD5 usando uma determinada técnica criada em 2004 por um grupo de pesquisadoras chinesas. O fato benéfico dessa pesquisa foi imediato, já que os certificados pararam de usar MD5 nos certificados. Porém, imediatamente seguiu-se uma caça às bruxas, e todos os usos do MD5 passaram a ser criticados. Tornou-se comum ouvir "MD5 não serve, já foi quebrado".

Essa paranóia com o MD5 atingiu a Computação Forense, já que o utilizamos em várias operações com objetivo de comprovação de integridade. Apareceram alguns questionando o uso do MD5 na comprovação de integridade de imagens forenses, e outros chegaram a dizer que a imagem poderia estar inválida e ter sido adulterada, já que a integridade dela foi verificada com o MD5 e ele foi quebrada.

Essa discussão apareceu recentemente no blog da SANS e, ainda agora, estava sendo discutida na lista Perícia Forense. Em algum ponto do assunto, preferi listar minhas dúvidas diretamente com a turma que realizou a pesquisa, ao invés de conjecturar se a tal pesquisa e quebra do MD5 afetava ou não o uso que fazemos dele. "Deus salve a Internet", pensei, quando localizei a palestra a, a partir dela, o contato da equipe que a produziu. O assunto é bastante técnico e específico, ao ponto de gerar complicações de entendimento, e por isso preferi resumir minhas dúvidas e ir direto ao ponto: Esse tipo de uso (integridade em imagens) é seguro ou não ?
Para abordar o assunto, comentei com o pesquisador como usamos o hash na questão da verificação de integridade, informei inclusive que os arquivos são muito grandes (média atual de uma imagem chega a 80 Gb) e mostrei como seria a alegação: Você tem o arquivo original, ele é duplicado, adulterado para favorecer uma parte, e no fim aplica-se algum algoritmo que faz o hash ser igual ao outro. O autor da pesquisa, Marc Stevens, foi muito simpático e explicou em linguagem bem acessível o trabalho de busca de colisões em hash e como funciona o algoritmo de quebra. Ao final, foi categórico em dizer que o uso do MD5 está garantido dessa forma, até então.

A explicação é a seguite:

Um algoritmo de hash é uma espécie de redução/compactação. Você pega uma entrada de qualquer tamanho e a mapeia em uma saída de tamanho fixo, geralmente muito menor. Ora, naturalmente o que vai acontecer é que várias entradas diferentes teriam a mesma saída. Um bom algoritmo de hash garante que esse acontecimento, conhecido como colisão, tenha uma possibilidade de acontecer muito baixa. É tão baixa que se torna extremamente difícil gerá-la propositalmente (o que seria ter dois arquivos e ir alterando-os de forma que em dado momento ambos tenham o mesmo hash). Sem exageros, considere esse "extremamente difícil" como algo não praticável até então.

No entanto, algoritmos também podem apresentar vulnerabilidades. No caso do MD5, foram descobertas duas delas, mas ambas funcionam de maneira bem específica.

O primeiro, mais simples, chama-se de ataque de prefixo identico. Usando essa técnica, é possível obter, a partir de dois arquivos iguais, dois conjuntos 128 bytes distintos que, adicionados (ou sobrepondo-os no final) aos arquivos iniciais, obtemos o mesmo hash para ambos. Note que, neste caso, não há controle sobre a alteração, ou seja, no fim das contas os arquivos apenas vão diferir nos 128 últimos bytes. De acordo com o pesquisador, esse ataque é simples e o código que o gera está disponível.

O segundo ataque, um tanto mais complexo, chama-se ataque de colisão com prefixo escolhido. Ele consiste em pegar dois arquivos do mesmo tamanho, mas que podem ser completamente diferentes, e em seguida adicionar cerca de 1Kb pré-calculado em cada um deles de forma que o hash final dos dois fique igual. Esse ataque é mais convincente, pois os arquivos podem ser totalmente diferentes e o hash seria igual. Entretanto, a técnica leva cerca de um dia para os calculos saírem com as duas sequencias de 1kb, a rotina que as calcula não está disponibilizada e no fim das contas, também não há controle sobre elas. Nos dois casos, as condições de quebra não afeta como a Computação Forense usa o MD5. Isso significa que nenhuma das duas técnicas permitiria que alguém duplicasse uma imagem forense, adulterando uma delas, e em seguida obtendo nas duas o mesmo hash que o valor inicial.

Abaixo eu colei a resposta onde o pesquisador reafirma a impossibilidade (até agora) de aplicar o ataque em como usamos o MD5:

Tony:
Just to check if I understood. When you say: "The stronger attack is the chosen-prefix collision attack and basically allows you to append about 1kb to two arbitrarily chosen files of the same length making them collide: the attack can be mounted in about a day", this means that would be possible for someone to take a huge file (let´s say, 80Gb with MD5 hash=XXX), clone it, change lots of parts inside the clone, and apply this method you described in order to get both with the same MD5 hash=XXX in the end ? I understood that in the end we would have the same MD5 hash for both files, but this hash would never be the XXX ...
Anyway, If yes, what would be the processing power to accomplish it (maybe a good guess) ? Same order of that 200-PS3 ? I ask this because even its possible, maybe the cost would make it non practical for most of cases, so the MD5 hash as validation would remain Ok for a while ...

Marc:
Hi Tony,
you guessed it right, although the attack allows you to let two files have the same hash, you cannot target a specific hash.That would require a even more powerful attack called second preimage or preimage attack.The chosen-prefix collision attack gives you two files with the same hash, however it has to modify both files and it cannot target a specific hash.
The cost to create a chosen-prefix collision is 1 day on a quad core pc,our attack using 200 PS3s needed that much more computing power since we were aiming for a very short chosen-prefix collision (about 3*64 bytes instead of a kilobyte).

Comentários ?

Até o próximo post !