Código hash e soma de verificação - qual é a diferença?

115

Meu entendimento é que um código hash e soma de verificação são coisas semelhantes - um valor numérico, calculado para um bloco de dados, que é relativamente único.

ou seja, a probabilidade de dois blocos de dados gerando o mesmo valor numérico de hash / checksum é baixa o suficiente para que possa ser ignorada para os propósitos do aplicativo.

Portanto, temos duas palavras para a mesma coisa ou existem diferenças importantes entre códigos hash e somas de verificação?

Richard Ev
fonte
3
Para resumir as respostas abaixo: Um código hash reduz a entrada a um pequeno número, de forma a minimizar a chance de colisões. Uma soma de verificação, por outro lado, reduz a entrada a um pequeno número, de forma a minimizar a chance de colisões. Você pode fazer um som diferente do outro reformulando arbitrariamente essa descrição.
Dan Stahlke
3
@DanStahlke - Não, não é isso que as respostas abaixo dizem. Sim, ambos reduzem a entrada a um número menor. Mas existem muitas, muitas maneiras de fazer isso, como escolher qual algoritmo usar? Isso depende do seu objetivo. Para resumir as duas principais respostas: o objetivo de uma soma de verificação é " detectar os erros mais comuns ". Escolha um algoritmo que produza uma soma de verificação diferente, para quaisquer erros que sejam "mais comuns" em seu cenário. Se você está preocupado com a alternância de um ou dois bits, pode escolher um algoritmo que garanta a detecção desse erro específico! Esta é uma compensação muito específica.
ToolmakerSteve
1
@DanStahlke - por outro lado, o código hash cobre uma ampla gama de possíveis compensações. Se nos referimos a um valor usado na criação de uma tabela hash, sabemos que haverá colisões, muitas delas. Esta é uma compensação muito diferente (do que uma soma de verificação). Estamos tentando reduzir as colisões em média . Não garantimos nada. Pode haver algumas entradas que diferem em apenas um bit, mas geram o mesmo hash. Isso é perfeitamente normal , se em média obtivermos uma boa distribuição de valores de hash. No entanto, seria inaceitável para uma soma de verificação.
Toolmaker Steve

Respostas:

72

Eu diria que uma soma de verificação é necessariamente um código hash . No entanto, nem todos os códigos de hash são boas somas de verificação.

Uma soma de verificação tem um propósito especial - ela verifica ou verifica a integridade dos dados (alguns podem ir além, permitindo a correção de erros ). "Boas" somas de verificação são fáceis de calcular e podem detectar muitos tipos de corrupção de dados (por exemplo, um, dois, três bits errados).

Um hashcode simplesmente descreve uma função matemática que mapeia dados para algum valor. Quando usado como meio de indexação em estruturas de dados (por exemplo, uma tabela hash), uma baixa probabilidade de colisão é desejável.

Zach Scrivena
fonte
6
Talvez um pudesse ser usado como o outro, mas considerando que eles têm objetivos de design diferentes, isso só confunde a questão.
Wim Coenen de
8
@gumbo: não, nem todo código hash é uma soma de verificação. Veja o exemplo de string do MSalters abaixo.
MarcH
41

Há um propósito diferente por trás de cada um deles:

  • Código hash - projetado para ser aleatório em seu domínio (para minimizar colisões em tabelas hash e outros). Os códigos hash criptográficos também são projetados para serem computacionalmente inviáveis ​​para reversão.
  • Check sum - projetado para detectar os erros mais comuns nos dados e, muitas vezes, para ser rápido de calcular (para uma soma de verificação eficaz em fluxos rápidos de dados).

Na prática, as mesmas funções costumam ser boas para os dois propósitos. Em particular, um código hash criptograficamente forte é uma boa soma de verificação (é quase impossível que um erro aleatório interrompa uma função hash forte), se você puder pagar o custo computacional.

Rafał Dowgird
fonte
1
Também é bom mencionar que a versão não criptográfica dos códigos hash pode fornecer uma boa compensação entre o tempo de computação (perto do CRC) e a detecção de erros, seja intencional ou apenas erro de comunicação / podridão de bits (CRC não pode ser esperado para detectar adulteração intencional porque é relativamente fácil projetar uma colisão intencionalmente).
maravilhoso
1
Para mim, a frase-chave em sua resposta é que a soma de verificação foi projetada para detectar os erros mais comuns . Sim é isso. é um algoritmo hash que foi escolhido para gerar valores diferentes para prováveis corrupções dos dados. Esse é um propósito específico e leva a algoritmos específicos, que otimizam para isso - dependendo dos tipos de perturbações com que se está preocupado.
Toolmaker Steve
22

De fato, existem algumas diferenças:

  • As somas de verificação só precisam ser diferentes quando a entrada é diferente (sempre que possível), mas é quase tão importante que sejam rápidas de calcular.
  • Os códigos de hash (para uso em tabelas de hash) têm os mesmos requisitos e, além disso, devem ser distribuídos uniformemente no espaço do código, especialmente para entradas semelhantes.
  • Os hashes criptográficos têm o requisito muito mais rigoroso de que, dado um hash, você não pode construir uma entrada que produza esse hash. Os tempos de computação vêm em segundo lugar e, dependendo da aplicação, pode até ser desejável que o hash seja muito lento para calcular (a fim de combater ataques de força bruta).
Michael Borgwardt
fonte
1
Eu não acho que as somas de verificação serem diferentes para entradas diferentes tem algum benefício. Eles são apenas para verificar a integridade, não para hash.
user541686
1
@Mehrdad: então, como você propõe verificar a integridade sem obter resultados diferentes para entradas diferentes?
Michael Borgwardt
Er, talvez eu tenha errado o que disse? Eu estava me referindo à parte em que você disse "na medida do possível" - estou apenas dizendo que não há razão para que sejam imprevisíveis ou "distantes" como os hashes. Contanto que haja alguma mudança na soma de verificação quando a entrada passa por uma mudança típica, é uma soma de verificação perfeita. Compare isso com os hashes, que também têm o objetivo de distribuir as coisas da maneira mais uniforme / aleatória / imprevisível / "longe" possível em seu codomínio.
user541686
Eu acho que você interpretou mal o que eu quis dizer com "na medida do possível" - eu apenas quis dizer que as colisões devem ser tão raras quanto possível, embora, é claro, sejam inevitáveis. Vou mudar o texto.
Michael Borgwardt
@Mehrdad - a princípio isso não fez sentido para mim. Se uma soma de verificação não tiver uma boa distribuição sobre os valores de soma de verificação possíveis, isso significa que alguns valores de soma de verificação são retornados para muitos mais valores de entrada (do que para outras somas de verificação). Mas, isso diminui a utilidade da soma de verificação? [Isso aumenta as chances de que os dados perturbados retornem o mesmo resultado, certo?] Hmm, estou errado, você está certo: a soma de verificação só precisa ser boa para detectar perturbações prováveis . Isso pode não exigir uma distribuição uniforme de todos os valores.
Toolmaker Steve
10

Hashcodes e checksums são usados ​​para criar valores numéricos curtos de um item de dados. A diferença é que um valor de checksum deve mudar, mesmo se uma pequena modificação for feita no item de dados. Para um valor hash, o requisito é apenas que os itens de dados do mundo real devem ter valores hash distintos.

Um exemplo claro são as cordas. Uma soma de verificação para uma string deve incluir cada bit e questões de ordem. Um hashcode, por outro lado, pode frequentemente ser implementado como uma soma de verificação de um prefixo de comprimento limitado. Isso significaria que "aaaaaaaaaaba" teria o mesmo hash que "aaaaaaaaaaab", mas algoritmos de hash podem lidar com essas colisões.

MSalters
fonte
Esta resposta é aquela que me chama a atenção. Portanto, a integridade dos dados não é o foco de um hash.
truthadjustr
9

A Wikipedia coloca bem:

As funções de checksum estão relacionadas a funções hash, impressões digitais, funções de randomização e funções hash criptográficas. No entanto, cada um desses conceitos tem aplicações diferentes e, portanto, objetivos de design diferentes. Dígitos de verificação e bits de paridade são casos especiais de somas de verificação, apropriados para pequenos blocos de dados (como números do Seguro Social, números de contas bancárias, palavras de computador, bytes únicos, etc.). Alguns códigos de correção de erros são baseados em somas de verificação especiais que não apenas detectam erros comuns, mas também permitem que os dados originais sejam recuperados em certos casos.

Jon Skeet
fonte
28
Depois de ler isso, ainda estou me perguntando qual é a diferença.
kirk.burleson
@ kirk.burleson - Eu diria que eles são o mesmo princípio , mas na prática sempre fazemos concessões . Em diferentes situações, diferentes compensações se aplicam, portanto, abordagens diferentes são usadas. Não é realmente uma justificativa para a existência de duas palavras diferentes, apenas dizer que, se você pesquisar boas técnicas para somas de verificação, poderá encontrar um conjunto de algoritmos diferente do que na pesquisa de códigos hash.
Toolmaker Steve
5

Uma soma de verificação protege contra alterações acidentais.

Um hash criptográfico protege contra um invasor muito motivado.

Quando você envia bits na transmissão, pode acontecer acidentalmente que alguns bits sejam invertidos, excluídos ou inseridos. Para permitir que o receptor detecte (ou às vezes corrija) acidentes como esse, o remetente usa uma soma de verificação.

Mas se você presumir que há alguém ativamente e de forma inteligente modificando a mensagem na transmissão e deseja se proteger contra esse tipo de invasor, use um hash criptográfico (estou ignorando a assinatura criptográfica do hash, ou usando um canal secundário ou algo assim, desde a questão não parece escapar a isso).

user3464863
fonte
3
"hash criptográfico" aumenta a confusão entre "hash" e "checksum". "checksum criptográfico" é melhor porque não.
MarcH
5

Embora o hash e as somas de verificação sejam semelhantes, pois ambos criam um valor com base no conteúdo de um arquivo, o hash não é o mesmo que criar uma soma de verificação. Uma soma de verificação destina-se a verificar (verificar) a integridade dos dados e identificar erros de transmissão de dados, enquanto um hash é projetado para criar uma impressão digital exclusiva dos dados.

Fonte: CompTIA ® Security + Guide to Network Security Fundamentals - Quinta edição - Mark Ciampa -Página 191

N Randhawa
fonte
4

Hoje em dia eles são intercambiáveis, mas no passado, uma soma de verificação era uma técnica muito simples em que você adicionava todos os dados (geralmente em bytes) e acrescentava um byte no final com esse valor em ... então, esperançosamente saber se algum dos dados originais foi corrompido. Semelhante a um bit de verificação, mas com bytes.

Steven Robbins
fonte
4

A diferença entre o código hash e as funções de soma de verificação é que eles estão sendo projetados para finalidades diferentes.

  • Uma soma de verificação é usada para descobrir se algo na entrada mudou.

  • Um código hash é usado para descobrir se algo na entrada mudou e para ter o máximo de "distância" possível entre os valores do código hash individual.

    Além disso, pode haver requisitos adicionais para uma função hash, em oposição a esta regra, como a capacidade de formar árvores / clusters / depósitos de valores de código hash antecipadamente.

    E se você adicionar alguma randomização inicial compartilhada, chegará ao conceito de criptografia moderna / trocas de chaves.


Sobre Probabilidade:

Por exemplo, vamos supor que os dados de entrada sempre mudam (100% do tempo). E vamos supor que você tenha uma função hash / checksum "perfeita", que gera um valor hash / checksum de 1 bit. Portanto, você obterá valores diferentes de hash / checksum, 50% do tempo, para dados de entrada aleatórios.

  • Se exatamente 1 bit em seus dados de entrada aleatórios mudou, você será capaz de detectar isso 100% do tempo, não importa o tamanho dos dados de entrada.

  • Se 2 bits em seus dados de entrada aleatórios mudaram, sua probabilidade de detectar "uma mudança" é dividida por 2, porque ambas as mudanças podem se neutralizar, e nenhuma função hash / checksum detectaria que 2 bits são realmente diferentes nos dados de entrada .

    ...

Isso significa que, se o número de bits em seus dados de entrada for várias vezes maior do que o número de bits em seu valor de hash / checksum, sua probabilidade de realmente obter diferentes valores de hash / checksum, para diferentes valores de entrada, é reduzida e não é um constante .

Sascha Wedler
fonte
2

Costumo usar a palavra soma de verificação quando me refiro ao código (numérico ou outro) criado para um arquivo ou parte dos dados que pode ser usada para verificar se o arquivo ou os dados não foram corrompidos. O uso mais comum que encontro é verificar se os arquivos enviados pela rede não foram alterados (deliberadamente ou não).

Ian1971
fonte
1
Como as somas de verificação não são difíceis de reverter, isso sugere que elas não seriam boas para verificar se algo foi alterado deliberadamente.
benblasdell,
0

Na fragmentação de dados do cluster Redis, ele usa um hash slotpara decidir para qual nó ele vai. Veja, por exemplo, a operação de módulo abaixo:

123 % 9 = 6
122 % 9 = 5
141 % 9 = 6

O 6surge duas vezes em entradas diferentes. O objetivo do hash é simplesmente mapear um valor de entrada para um valor de saída e a exclusividade não faz parte do negócio. Portanto, duas entradas diferentes que produzem a mesma saída estão bem no mundo dos hashes.

Uma soma de verificação, por outro lado, deve diferenciar a saída, mesmo que um bit na entrada seja alterado, porque sua finalidade não é mapear, mas detectar dados corrompidos. Portanto, duas entradas diferentes que produzem a mesma saída não são aceitáveis ​​em uma soma de verificação.

Truthadjustr
fonte
-4

Uma soma de verificação é simplesmente um número gerado a partir do campo de dados por oring (por adição lógica, portanto, soma). A soma de verificação tem a capacidade de detectar a corrupção de qualquer bit ou número de bits dentro do campo de dados a partir do qual é gerado, ou seja, verifica se há erros, não pode corrigi-los. Uma soma de verificação é um hash porque o tamanho da soma de verificação é menor do que os dados originais. Sim, você terá colisões porque a soma de verificação não é totalmente sensível à posição do bit no campo de dados.

Uma verificação de redundância cíclica (CRC) é algo bem diferente, mais complexo e NÃO é chamado de checksum. É a aplicação de uma série polinomial que tem a capacidade de corrigir qualquer número escolhido de bits individuais corrompidos dentro do campo de dados a partir do qual foi gerado. A criação de um CRC resulta em um número maior em tamanho do que o campo de dados original (ao contrário da soma de verificação) - daí o nome incluir a palavra "redundância" e o preço que você paga pela capacidade de correção de erros. Portanto, um CRC NÃO é um hash e não deve ser confundido ou nomeado como uma soma de verificação, porque a redundância necessariamente aumenta o tamanho dos dados originais.

CapitainSensible
fonte