Não faz muito tempo (mais ou menos 2 anos) que foi anunciado uma quebra do algoritmo de hash SHA-1. Pois bem, a façanha foi repetida há poucos dias por uma turma de pesquisadores da Macquarie University, em Sydney, Australia.
O avanço anterior já tinha reduzido a possibilidade de colisão do algoritmo de 280 operações para algo em torno de 269. A pesquisa agora reduziu esse número a "meros" 263 , o que colocaria este esforço ao alcance de empresas com orçamento e intencionadas em se beneficiar de algum resultado obtido via colisão provocada.
Um ponto a destacar, principalmente para os alarmistas de plantão, é que ataques contra o uso de hashs em Forense Computacional ainda não são efetivos. Tais ataques, conhecido como pre-image attacks, não são ainda factíveis usando as técnicas apresentadas, nem no SHA-1 nem no MD5, conforme descrevi aqui alguns posts atrás. Apesar disso, como nossos casos podem durar anos, considero bastante válido que as ferramentas tratem de apresentar cálculos de hashs usando algoritmos com mais capacidades de bits. Eles estão chegando muito perto ...
Veja aqui o PDF do trabalho.
Comentários ?
Até o próximo post !
Mostrando postagens com marcador md5. Mostrar todas as postagens
Mostrando postagens com marcador md5. Mostrar todas as postagens
sábado, 13 de junho de 2009
terça-feira, 12 de maio de 2009
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 !
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 !
terça-feira, 10 de março de 2009
To hash or not to hash: Eis a questão
O assunto hash como comprovação de integridade veio a tona algumas semanas atrás nos blogs dos EUA. Além do já conhecido "birthday attack", foram levantadas novas polêmicas em relação a esta forma de cálculo. De certa forma, o assunto retornou porque não faz muito tempo um grupo de pesquisadores conseguiu emitir um certificado digital válido atacando vulnerabilidades do MD5. Depois do burburinho inicial, a polêmica do uso de hashs acabou por retornar.
O fato novo é que, desta vez, a discussão não parou no uso do algoritmo X, Y ou Z. De certa forma, foi mais profunda e acredito que tenha ajudado a levantar questões ainda não respondidas. Sim, porque em muitas situações, adotamos um procedimento como o correto a ser feito para todas as ocasiões, sem o menor questionamento, e acaba por ficar anos assim. Isso me lembra a estória do caminho das cabras. Há quem diga que, há alguns séculos, as cabras criavam suas próprias rotas no pasto, em busca de alimento. Os colonizadores, ao chegar, percebiam mais facilidade naquele caminho, pois a vegetação ali já estaria menos densa. Ao usá-los com frequência, acabaram por alargar a vegetação a sua volta e criaram ali as primeiras ruas. O progresso chegou e o primeiro passo foi asfaltar as ruas da tal cidade. Hoje, crianças perguntam aos avós porque determinada rua faz curva, enquanto que outras são retas e ninguém sabe a resposta. É porque aquele era o caminho das cabras ...
Pois bem, a polêmica foi boa para se repensar nos procedimentos e não ficarmos colocando asfalto sobre caminho de cabras. Um dos pontos questionados foi por que é obrigatório o uso de hash em casos de comprovação de integridade, quando os algoritmos usados já foram quebrados. É possível uma prova não ser admitida só porque alguém quebrou o algoritmo que comprovaria a sua integridade ??? E o caso de Live Forensics, onde o hash não vai ser igual porque o ambiente muda o tempo todo, já que ainda está em uso ? Houve ainda quem falasse da própria forense de memória, e que não dá para usar esta forma de comprovação de integridade.
Entre perguntas para cá e para lá, gostei muito da postura e opiniões de um dos participantes. Algo que ele ponderou, e que vale para nós brasileiros, é que não há nenhuma exigência legal de que seja usado o hash para a garantia de integridade. Isso foi um procedimento adotado e que agora precisa ser questionado. No caso americano, não haveria nenhum ponto no que eles conhecem como Dalbert Challenge que eliminaria uma prova só porque o hash dela não está idêntico. Outro ponto muito bem indicado é que a prova deve ter uma integridade estrutural por si mesma. Se ela não tiver, então não há caso. Simplificando o que ele disse, não podemos nunca basear uma conclusão em um único ponto, mas sim em um conjunto de vestígios que irão comprovar a história toda. Não podemos dizer que alguém é pedófilo porque simplesmente uma foto foi encontrada em um HD, mas poderemos se a foto estiver em um diretório particular, com algum tipo de classificação, se encontrarmos vestígios de que ela foi baixada em um site e que este site está gravado nos favoritos, ou ainda achamos atalhos no "recent documents" apontando para ela. Neste caso, é inegável a conclusão, e um hash não faria a menor falta ao processo.
O que você tem feito para constatar a integridade de dumps de memória ? E em casos onde o conteúdo só está on-line ? Ou ainda, caso seja impossível capturar toda a mídia, o que você usa como procedimento ? Comente !
Até o próximo post !
O fato novo é que, desta vez, a discussão não parou no uso do algoritmo X, Y ou Z. De certa forma, foi mais profunda e acredito que tenha ajudado a levantar questões ainda não respondidas. Sim, porque em muitas situações, adotamos um procedimento como o correto a ser feito para todas as ocasiões, sem o menor questionamento, e acaba por ficar anos assim. Isso me lembra a estória do caminho das cabras. Há quem diga que, há alguns séculos, as cabras criavam suas próprias rotas no pasto, em busca de alimento. Os colonizadores, ao chegar, percebiam mais facilidade naquele caminho, pois a vegetação ali já estaria menos densa. Ao usá-los com frequência, acabaram por alargar a vegetação a sua volta e criaram ali as primeiras ruas. O progresso chegou e o primeiro passo foi asfaltar as ruas da tal cidade. Hoje, crianças perguntam aos avós porque determinada rua faz curva, enquanto que outras são retas e ninguém sabe a resposta. É porque aquele era o caminho das cabras ...
Pois bem, a polêmica foi boa para se repensar nos procedimentos e não ficarmos colocando asfalto sobre caminho de cabras. Um dos pontos questionados foi por que é obrigatório o uso de hash em casos de comprovação de integridade, quando os algoritmos usados já foram quebrados. É possível uma prova não ser admitida só porque alguém quebrou o algoritmo que comprovaria a sua integridade ??? E o caso de Live Forensics, onde o hash não vai ser igual porque o ambiente muda o tempo todo, já que ainda está em uso ? Houve ainda quem falasse da própria forense de memória, e que não dá para usar esta forma de comprovação de integridade.
Entre perguntas para cá e para lá, gostei muito da postura e opiniões de um dos participantes. Algo que ele ponderou, e que vale para nós brasileiros, é que não há nenhuma exigência legal de que seja usado o hash para a garantia de integridade. Isso foi um procedimento adotado e que agora precisa ser questionado. No caso americano, não haveria nenhum ponto no que eles conhecem como Dalbert Challenge que eliminaria uma prova só porque o hash dela não está idêntico. Outro ponto muito bem indicado é que a prova deve ter uma integridade estrutural por si mesma. Se ela não tiver, então não há caso. Simplificando o que ele disse, não podemos nunca basear uma conclusão em um único ponto, mas sim em um conjunto de vestígios que irão comprovar a história toda. Não podemos dizer que alguém é pedófilo porque simplesmente uma foto foi encontrada em um HD, mas poderemos se a foto estiver em um diretório particular, com algum tipo de classificação, se encontrarmos vestígios de que ela foi baixada em um site e que este site está gravado nos favoritos, ou ainda achamos atalhos no "recent documents" apontando para ela. Neste caso, é inegável a conclusão, e um hash não faria a menor falta ao processo.
O que você tem feito para constatar a integridade de dumps de memória ? E em casos onde o conteúdo só está on-line ? Ou ainda, caso seja impossível capturar toda a mídia, o que você usa como procedimento ? Comente !
Até o próximo post !
Assinar:
Postagens (Atom)