Como verificar a identidade de arquivos enormes se o hash estiver vinculado à CPU?

A minha melhor solução no momento é:

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

— Note-se que:

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

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

Infelizmente, MD5 é um processo linear onde seu estado depende de todas as entradas anteriores. Em outras palavras, você não pode realmente paralelizá-lo. Além disso, não tenho conhecimento de nenhum hash alg real que não opere dessa maneira.

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

Se você não pode/não quer fazer isso, você deve usar uma função de hash mais rápida como xxHash , CityHash ou SpookyHash

Outra ideia (talvez seja aplicável ao seu uso pretendido): 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 passe rápido, recorrendo ao MD5 /SHA1 para uma segunda passagem em arquivos aparentemente idênticos.

Não há como contornar o processamento de todo o arquivo. MD4 ou CRC32 são provavelmente suas melhores apostas para um algoritmo rápido e amplamente implantado (embora o CRC32 seja muito menos eficaz que o MD4).

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

Se você realmente não se importa com a interoperabilidade, o hash em vários núcleos é facilmente possível dividindo o arquivo em partes (não precisa ser feito no disco, você apenas começa a ler a partir de deslocamentos específicos) e processa cada parte separadamente (no entanto, isso resultará em graves problemas de disco, degradando o desempenho, especialmente para discos mecânicos). Você terminará com hashes separados para cada pedaço (embora isso tenha outras vantagens, como apontar para o pedaço quebrado), mas você sempre pode misturá-los para um valor final.

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

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

Considere a abordagem do BitTorrent: quando um Torrent é criado, todos os arquivos são divididos em 'blocos', cada bloco com hash individualmente e cada um desses hashes gravados no arquivo .torrent. Isso é o que permite que um par verifique gradualmente os dados de entrada, sem ter que esperar que o download do arquivo inteiro termine 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 podem ser hash simultaneamente.

Se você projetar seu processo de verificação para trabalhar em algum subconjunto dos dados, por exemplo, blocos de tamanho fixo, você pode fazer o hash de cada bloco em um núcleo separado, eliminando assim uma grande quantidade de atraso no pipeline. Obviamente, essa abordagem tem uma pequena compensação de tempo/memória: cada instância adicional de hash 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.

Estou trabalhando em um projeto de hash de árvore, projetado exatamente para esse problema: hashing paralelo pronto para uso de arquivos grandes. 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: https://github.com/oconnor663/bao

Você pode usar md5deep para isso e hashdeep para outros hashes. Ele suporta multi threading com o -jsinalizador. Por padrão, ele criará um thread de hash para cada núcleo. Ele também possui um sinalizador para quebrar os arquivos em pedaços antes do hash, 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 grandes árvores de diretórios.

Aqui está a página de manual para ele http://md5deep.sourceforge.net/md5deep.html e git repo https://github.com/jessek/hashdeep

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

É fácil projetar um algoritmo de hash que seja escalável em vários núcleos, apenas 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 lento possível.

As funções de hash que não forçam o processamento serial podem ser adequadas para você, mas isso depende das propriedades que você espera de sua função de hash. Como tal, não acho que você tenha fornecido informações suficientes para que uma boa recomendação seja 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 funcione bem o suficiente para a maioria dos propósitos. Quão grande 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 a obter mais de 128 bits de entropia por bloco, isso deve ser suficiente para a maioria dos propósitos (e um exagero para muitos em que 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, porque, caso contrário, encontrar uma colisão para um único bloco é suficiente para permitir que um ator malicioso substitua parte do conteúdo e obtenha o mesmo hash final.

Talvez valha a pena 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 suas necessidades são evitar colisões de hash que ocorrem 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. Hashes criptograficamente seguros são normalmente projetados para serem lentos para calcular.

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