Como se verifica a identidade de arquivos grandes se o hashing está limitado à CPU?

Question

Para arquivos pequenos, o hash é ok, mas com os grandes, é possível encontrar facilmente md5sum na CPU. Existe algum algoritmo de hashing capaz de se expandir em múltiplos núcleos? Alguma solução alternativa? Idéias? Qualquer coisa? :)

    

Answer 1

O meu melhor no momento é a solução:

parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum

- Deve-se notar que:

1. O hash md5 resultante não é do arquivo, mas sim do md5s de suas partes, mas ainda permite que você compare se a réplica é idêntica à origem
2. Ele também não funciona muito bem, especialmente quando você usa pipe e não arquiva como entrada
3. parallel --pipepart como descobri não suporta partições de disco

Então eu adoraria ouvir outras maneiras também.

    

Answer 2

Infelizmente, o MD5 é um processo linear em que seu estado depende de todas as entradas anteriores. Em outras palavras, você não pode realmente paralelizar isso. Além disso, não tenho conhecimento de nenhum algarismo de hash real que não funcione dessa maneira.

O que você pode fazer (e, com base na sua resposta, você está fazendo) é dividir os arquivos de origem e calcular simultaneamente o md5sum de cada pedaço.

Se você não puder / não quiser fazer isso, terá que usar uma função de hash mais rápida como xxHash , CityHash ou SpookyHash

Outra idéia (talvez seja aplicável ao seu uso intencional): se você precisar de algo mais rápido que o MD5 (embora single-threaded), você pode usar o CRC32 (que é acelerado por hardware por CPUs recentes) para um primeiro passo rápido. recorrendo ao MD5 / SHA1 para uma segunda passagem em arquivos aparentemente idênticos.

    

Answer 3

Não há praticamente como processar o arquivo inteiro. MD4 ou CRC32 são provavelmente suas melhores apostas para um algoritmo amplamente implementado e rápido (embora o CRC32 seja bem menos eficiente que o MD4).

Testar várias implementações do seu algoritmo de escolha ajudará. Se você puder encontrar uma implementação ASM bem testada, ela provavelmente melhorará o desempenho de seus primos C / C ++.

Se você realmente não se importa com a interoperabilidade, o hash em múltiplos núcleos é facilmente realizável dividindo o arquivo em partes (não precisa ser feito no disco, você apenas começaria lendo de offsets específicos) e processando cada parte separadamente (isso resultará em sérios problemas de disco, degradando o desempenho, especialmente para discos mecânicos). Você vai acabar com hashes separados para cada pedaço (embora isso tenha outras vantagens, como apontar você para o pedaço quebrado), mas você pode sempre misturá-los por um valor final.

Este Gist pode ser um bom começo para algo em Python.

    

Answer 4

A maioria das respostas aqui abordou a natureza linear da maioria dos algoritmos de hash. Embora eu tenha certeza de que existem alguns algoritmos de hashing escalonáveis, uma solução mais fácil é simplesmente dividir os dados em partes menores e fazer o hash individualmente.

Considere a abordagem do BitTorrent: Quando um Torrent é criado, todos os arquivos são divididos em 'blocos', cada bloco individualmente em hash e cada um desses hashes registrados no arquivo .torrent. Isso é o que permite que um par verifique incrementalmente os dados recebidos, sem ter que esperar que o arquivo inteiro termine o download primeiro. Os erros também podem ser corrigidos por bloco, em vez de exigir a retransmissão de todo o arquivo. Além dos benefícios logísticos, essa abordagem também permite que o hash seja dimensionado em vários núcleos - se 8 núcleos estiverem disponíveis, 8 blocos poderão ser simultaneamente hash.

Se você projetar seu processo de verificação para trabalhar em algum subconjunto dos dados, por exemplo, blocos de algum tamanho fixo, você pode hash cada bloco em um núcleo separado, eliminando assim uma grande quantidade de atraso no pipeline. Obviamente, essa abordagem tem um pequeno tempo / troca de memória: cada instância adicional de hashing tem alguma sobrecarga associada a ela, principalmente na forma de memória, embora isso seja mínimo, a menos que você esteja executando centenas de instâncias.

    

Answer 5

Estou trabalhando em um projeto de hash de árvore, que é projetado exatamente para esse problema: hashing paralelo de grandes arquivos prontos para uso. Funciona agora, embora não tenha sido revisado, e há uma boa chance de que as alterações da revisão resultem em alterações no resumo final. Dito isto, é muito rápido: link

    

Answer 6

Você pode usar o md5deep para isso e o hashdeep para outros hashes. Suporta multi-threading com o sinalizador -j . Por padrão, ele criará um encadeamento de hash para cada núcleo. Ele também possui um sinalizador para dividir os arquivos em partes antes do hashing, mas não usará vários encadeamentos em um único arquivo. Eu usei isso para obter sha256 de meio milhão de arquivos e funcionou muito bem. Ele também possui um flash recursivo que facilita o manuseio de árvores de diretórios grandes.

Aqui está a manpage do link e do git repo link

O nome do pacote no ubuntu e debian é md5deep e inclui hashdeep.

    

Answer 7

É fácil projetar um algoritmo de hash escalonável em vários núcleos, mas os algoritmos de hash mais conhecidos tendem a ser projetados especificamente para evitar isso, para que tarefas como encontrar colisões de hash sejam feitas o mais lentas possível. / p>

As funções de hashing que não forçam o processamento em série podem ser adequadas para você, mas isso depende das propriedades que você espera de sua função hash. Como tal, não acho que você tenha dado informações suficientes para uma boa recomendação a ser feita.

Como outros sugeriram, você pode construir uma função hash como o hash dos hashes concatenados de cada um dos blocos de um determinado tamanho no original. Contanto que o tamanho do bloco seja grande o suficiente para dificultar a reversão dos hashes de blocos individuais, é provável que isso funcione bem o suficiente para a maioria dos propósitos. Quão grande isso deve ser depende de quão previsível é o conteúdo desses blocos. Se você puder estimar a entropia e escolher um tamanho de bloco de modo que obtenha 128+ bits de entropia por bloco, isso deve ser suficiente para a maioria dos propósitos (e um exagero para muitos, onde a segurança não é a principal preocupação).

Do ponto de vista da segurança, você está preocupado com o grau de entropia no nível do bloco, pois encontrar uma colisão para um único bloco é suficiente para permitir que um ator mal-intencionado substitua parte do conteúdo e obtenha a mesma final. hash.

Talvez seja interessante notar que ter um tamanho de bloco fixo significa que a principal fraqueza dos MD5s é irrelevante - o hacker não pode anexar dados extras ao bloco.

Se as suas necessidades são sobre a prevenção de colisões de hash ocorrendo naturalmente em vez de colisões maliciosas, você pode, sem dúvida, usar uma função de soma de verificação muito mais rápida. Os hashes criptograficamente seguros geralmente são projetados para serem lentos para calcular.

Uma função do grupo de funções skein usando o modo de árvore hash opcional pode ser adequada para você. Então, novamente, CRC32 pode ser tudo que você precisa.