Code de hachage et somme de contrôle - quelle est la différence?

115

Je crois comprendre qu'un code de hachage et une somme de contrôle sont des choses similaires - une valeur numérique, calculée pour un bloc de données, qui est relativement unique.

c'est-à-dire que la probabilité que deux blocs de données produisent la même valeur de hachage numérique / somme de contrôle est suffisamment faible pour pouvoir être ignorée aux fins de l'application.

Alors avons-nous deux mots pour la même chose, ou y a-t-il des différences importantes entre les codes de hachage et les sommes de contrôle?

Richard Ev
la source
3
Pour résumer les réponses ci-dessous: Un code de hachage réduit l'entrée à un petit nombre, de manière à minimiser les risques de collisions. Une somme de contrôle, par contre, réduit l'entrée à un petit nombre, de manière à minimiser le risque de collision. Vous pouvez rendre un son différent de l'autre en reformulant arbitrairement cette description.
Dan Stahlke
3
@DanStahlke - Non, ce n'est pas ce que disent les réponses ci-dessous. Oui, ils réduisent tous les deux l'entrée à un nombre plus petit. Mais il existe de nombreuses façons de le faire, comment choisir quel algorithme utiliser? Cela dépend de votre objectif. Pour résumer les deux premières réponses: le but d'une somme de contrôle est de " détecter les erreurs les plus courantes ". Choisissez un algorithme qui produit une somme de contrôle différente, quelles que soient les erreurs "les plus courantes" dans votre scénario. Si vous craignez qu'un ou deux bits soient basculés, vous pouvez choisir un algorithme qui garantit la détection de cette erreur spécifique! C'est un compromis très spécifique.
ToolmakerSteve
1
@DanStahlke - d'autre part, le code de hachage couvre un large éventail de compromis possibles. Si nous parlons d'une valeur utilisée pour créer une table de hachage, nous savons qu'il y aura des collisions, beaucoup d'entre elles. C'est un compromis très différent (qu'une somme de contrôle). Nous essayons de réduire les collisions en moyenne . Nous ne garantissons rien. Certaines entrées peuvent différer d'un bit seulement, mais qui donnent le même hachage. C'est parfaitement bien, si en moyenne nous obtenons une bonne répartition des valeurs de hachage. Pourtant, ce serait inacceptable pour une somme de contrôle.
ToolmakerSteve

Réponses:

72

Je dirais qu'une somme de contrôle est nécessairement un hashcode . Cependant, tous les hashcodes ne font pas de bonnes sommes de contrôle.

Une somme de contrôle a un but particulier - elle vérifie ou vérifie l'intégrité des données (certains peuvent aller au-delà en permettant la correction d'erreurs ). Les «bonnes» sommes de contrôle sont faciles à calculer et peuvent détecter de nombreux types de corruption de données (par exemple un, deux, trois bits erronés).

Un hashcode décrit simplement une fonction mathématique qui mappe les données à une certaine valeur. Lorsqu'elle est utilisée comme moyen d'indexation dans des structures de données (par exemple une table de hachage), une faible probabilité de collision est souhaitable.

Zach Scrivena
la source
6
Peut-être que l'un pourrait être utilisé comme l'autre, mais étant donné qu'ils ont des objectifs de conception différents, cela ne fait que confondre le problème.
Wim Coenen
8
@gumbo: non, tous les hashcode ne sont pas une somme de contrôle. Voir l'exemple de chaîne de MSalters ci-dessous.
MarcH
41

Il y a un objectif différent derrière chacun d'eux:

  • Code de hachage - conçu pour être aléatoire dans son domaine (pour minimiser les collisions dans les tables de hachage et autres). Les codes de hachage cryptographiques sont également conçus pour ne pas pouvoir être inversés d'un point de vue informatique.
  • Somme de contrôle - conçue pour détecter les erreurs les plus courantes dans les données et souvent pour être rapide à calculer (pour une somme de contrôle efficace des flux de données rapides).

En pratique, les mêmes fonctions sont souvent bonnes pour les deux objectifs. En particulier, un code de hachage cryptographiquement fort est une bonne somme de contrôle (il est presque impossible qu'une erreur aléatoire casse une fonction de hachage forte), si vous pouvez vous permettre le coût de calcul.

Rafał Dowgird
la source
1
Il est également bon de mentionner que la version non cryptographique des codes de hachage peut fournir un bon compromis entre le temps de calcul (proche du CRC) et la détection d'erreur, que ce soit intentionnel ou juste une erreur de communication / pourriture de bits (on ne peut pas s'attendre à ce que le CRC détecte une falsification intentionnelle car il est relativement facile de concevoir intentionnellement une collision).
gaborous
1
Pour moi, la phrase clé de votre réponse, c'est que la somme de contrôle est conçue pour détecter les erreurs les plus courantes . Oui c'est ça. c'est un algorithme de hachage qui a été choisi pour donner des valeurs différentes pour les corruptions probables des données. C'est un objectif spécifique, et conduit à des algorithmes spécifiques, qui optimisent pour cela - en fonction des types de perturbations qui préoccupent.
ToolmakerSteve
22

Il y a en effet quelques différences:

  • Les sommes de contrôle doivent juste être différentes lorsque l'entrée est différente (aussi souvent que possible), mais il est presque aussi important qu'elles soient rapides à calculer.
  • Les codes de hachage (à utiliser dans les tables de hachage) ont les mêmes exigences et doivent en outre être répartis uniformément dans l'espace de code, en particulier pour les entrées similaires.
  • Les hachages cryptographiques ont l' exigence beaucoup plus stricte que, étant donné un hachage, vous ne pouvez pas construire une entrée qui produit ce hachage. Les temps de calcul viennent en second, et selon l'application, il peut même être souhaitable que le hachage soit très lent à calculer (afin de lutter contre les attaques par force brute).
Michael Borgwardt
la source
1
Je ne pense pas que les sommes de contrôle différentes pour différentes entrées aient des avantages. Ils sont juste pour vérifier l'intégrité, pas pour le hachage.
user541686
1
@Mehrdad: alors comment proposez-vous de vérifier l'intégrité sans obtenir des résultats différents pour différentes entrées?
Michael Borgwardt
Euh, j'ai peut-être mal exprimé ce que j'ai dit? Je faisais référence à la partie où vous avez dit "dans la mesure du possible" - je dis simplement qu'il n'y a aucune raison pour qu'ils soient imprévisibles ou "loin" comme le sont les hachages. Tant qu'il y a un certain changement dans la somme de contrôle lorsque l'entrée subit un changement typique, c'est une somme de contrôle fine. Comparez cela avec les hachages, qui ont également pour objectif de distribuer les choses aussi uniformément / aléatoirement / imprévisiblement / «loin» que possible sur leur codomaine.
user541686
Je pense que vous venez de mal interpréter ce que je voulais dire par «dans la mesure du possible» - je voulais simplement dire que les collisions devraient être aussi rares que possible, même si bien sûr elles sont inévitables. Je vais changer le libellé.
Michael Borgwardt
@Mehrdad - au début, cela n'avait aucun sens pour moi. Si une somme de contrôle n'a pas une bonne distribution sur les valeurs de somme de contrôle possibles, cela signifie que certaines valeurs de somme de contrôle sont renvoyées pour beaucoup plus de valeurs d'entrée (que pour d'autres sommes de contrôle). Mais, cela diminue l'utilité de la somme de contrôle? [Cela augmente les chances que les données perturbées retournent le même résultat, non?] Hmm, je me trompe, vous avez raison: la somme de contrôle doit seulement être bonne pour détecter les perturbations probables . Cela peut ne pas nécessiter une distribution uniforme sur toutes les valeurs.
ToolmakerSteve
10

Les codes de hachage et les sommes de contrôle sont tous deux utilisés pour créer une valeur numérique courte à partir d'un élément de données. La différence est qu'une valeur de somme de contrôle doit changer, même si une petite modification est apportée à l'élément de données. Pour une valeur de hachage, l'exigence est simplement que les éléments de données du monde réel doivent avoir des valeurs de hachage distinctes.

Un exemple clair sont les chaînes. Une somme de contrôle pour une chaîne doit inclure chaque bit, et l'ordre est important. Un hashcode, d'autre part, peut souvent être implémenté comme somme de contrôle d'un préfixe de longueur limitée. Cela signifierait que "aaaaaaaaaaba" hacherait de la même manière que "aaaaaaaaaaab", mais les algorithmes de hachage peuvent traiter de telles collisions.

MSalters
la source
Cette réponse est celle qui sonne la cloche pour moi. L'intégrité des données n'est donc pas au centre d'un hachage.
truthadjustr
9

Wikipédia le dit bien:

Les fonctions de somme de contrôle sont liées aux fonctions de hachage, aux empreintes digitales, aux fonctions de randomisation et aux fonctions de hachage cryptographique. Cependant, chacun de ces concepts a des applications différentes et donc des objectifs de conception différents. Les chiffres de contrôle et les bits de parité sont des cas particuliers de sommes de contrôle, appropriés pour de petits blocs de données (tels que les numéros de sécurité sociale, les numéros de compte bancaire, les mots informatiques, les octets simples, etc.). Certains codes de correction d'erreurs sont basés sur des sommes de contrôle spéciales qui non seulement détectent les erreurs courantes, mais permettent également de récupérer les données d'origine dans certains cas.

Jon Skeet
la source
28
Après avoir lu cela, je me demande toujours quelle est la différence.
kirk.burleson
@ kirk.burleson - Je dirais que c'est le même principe , mais en pratique on fait toujours des compromis . Dans différentes situations, différents compromis s'appliquent, de sorte que différentes approches sont utilisées. Ce n'est pas vraiment une justification pour qu'il y ait deux mots différents, simplement en disant que si vous recherchez de bonnes techniques pour les sommes de contrôle, vous pouvez trouver un ensemble d'algorithmes différent de celui de la recherche de codes de hachage.
ToolmakerSteve
5

Une somme de contrôle protège contre les modifications accidentelles.

Un hachage cryptographique protège contre un attaquant très motivé.

Lorsque vous envoyez des bits sur le câble, il peut arriver accidentellement que certains bits soient retournés, supprimés ou insérés. Pour permettre au récepteur de détecter (ou parfois de corriger) des accidents comme celui-ci, l'expéditeur utilise une somme de contrôle.

Mais si vous supposez qu'il y a quelqu'un qui modifie activement et intelligemment le message sur le fil et que vous souhaitez vous protéger contre ce type d'attaquant, utilisez un hachage cryptographique (j'ignore la signature cryptographique du hachage, ou j'utilise un canal secondaire ou autre, car la question ne semble pas y échapper).

user3464863
la source
3
Le "hachage cryptographique" augmente la confusion entre "hachage" et "somme de contrôle". La "somme de contrôle cryptographique" est meilleure parce qu'elle ne l'est pas.
MarcH
5

Bien que le hachage et les sommes de contrôle soient similaires en ce sens qu'ils créent tous deux une valeur basée sur le contenu d'un fichier, le hachage n'est pas la même chose que la création d'une somme de contrôle. Une somme de contrôle est destinée à vérifier (vérifier) ​​l'intégrité des données et à identifier les erreurs de transmission de données, tandis qu'un hachage est conçu pour créer une empreinte numérique unique des données.

Source: CompTIA ® Security + Guide to Network Security Fundamentals - Cinquième édition - Mark Ciampa - Page 191

N Randhawa
la source
4

Ces jours-ci, ils sont interchangeables, mais jadis, une somme de contrôle était une technique très simple où vous ajoutiez toutes les données (généralement en octets) et ajoutiez un octet à la fin avec cette valeur dans .. alors vous espérez savoir si l'une des données d'origine a été corrompue. Similaire à un bit de contrôle, mais avec des octets.

Steven Robbins
la source
4

La différence entre les fonctions de code de hachage et de somme de contrôle est qu'elles sont conçues à des fins différentes.

  • Une somme de contrôle est utilisée pour savoir si quelque chose dans l'entrée a changé.

  • Un code de hachage est utilisé pour savoir si quelque chose dans l'entrée a changé et pour avoir autant de "distance" entre les valeurs de code de hachage que possible.

    En outre, il peut y avoir d'autres exigences pour une fonction de hachage, en opposition à cette règle, comme la possibilité de former des arbres / clusters / seaux de valeurs de code de hachage tôt.

    Et si vous ajoutez une randomisation initiale partagée, vous arrivez au concept de cryptage / échanges de clés modernes.


À propos de la probabilité:

Par exemple, supposons que les données d'entrée changent toujours (100% du temps). Et supposons que vous ayez une fonction de hachage / somme de contrôle "parfaite", qui génère une valeur de hachage / somme de contrôle de 1 bit. Par conséquent, vous obtiendrez différentes valeurs de hachage / somme de contrôle, 50% du temps, pour les données d'entrée aléatoires.

  • Si exactement 1 bit dans vos données d'entrée aléatoires a changé, vous serez en mesure de détecter cela 100% du temps, quelle que soit la taille des données d'entrée.

  • Si 2 bits dans vos données d'entrée aléatoires ont changé, votre probabilité de détecter "un changement" est divisée par 2, car les deux changements pourraient se neutraliser, et aucune fonction de hachage / somme de contrôle ne détecterait que 2 bits sont réellement différents dans les données d'entrée .

    ...

Cela signifie que si le nombre de bits dans vos données d'entrée est plusieurs fois plus grand que le nombre de bits dans votre valeur de hachage / somme de contrôle, votre probabilité d'obtenir en fait différentes valeurs de hachage / somme de contrôle, pour différentes valeurs d'entrée, est réduite et n'est pas un constante .

Sascha Wedler
la source
2

J'ai tendance à utiliser le mot checksum lorsque je me réfère au code (numérique ou autre) créé pour un fichier ou un élément de données pouvant être utilisé pour vérifier que le fichier ou les données n'ont pas été corrompus. L'usage le plus courant que je rencontre est de vérifier que les fichiers envoyés sur le réseau n'ont pas été modifiés (délibérément ou non).

Ian1971
la source
1
Parce que les sommes de contrôle ne sont pas faites pour être difficiles à inverser, cela suggère qu'elles ne seraient pas bonnes pour vérifier si quelque chose a été délibérément modifié.
benblasdell
0

Dans le partage de données de cluster Redis, il utilise a hash slotpour décider à quel nœud il va. Prenez par exemple l'opération modulo ci-dessous:

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

Le 6apparaît deux fois sur des entrées différentes. Le but du hachage est simplement de mapper une valeur d'entrée à une valeur de sortie et l'unicité ne fait pas partie de l'accord. Donc, deux entrées différentes qui produisent la même sortie sont très bien dans le monde des hachages.

Une somme de contrôle, en revanche, doit différer la sortie même si un bit de l'entrée change car son but n'est pas de mapper, mais de détecter la corruption des données. Donc, deux entrées différentes qui produisent la même sortie ne sont pas acceptables dans une somme de contrôle.

truthadjustr
la source
-4

Une somme de contrôle est simplement un nombre généré à partir du champ de données par oring (par addition logique donc somme). La somme de contrôle a la capacité de détecter une corruption de n'importe quel bit ou nombre de bits dans le champ de données à partir duquel elle est générée, c'est-à-dire qu'elle vérifie les erreurs c'est tout, elle ne peut pas les corriger. Une somme de contrôle est un hachage car la taille de la somme de contrôle est plus petite que les données d'origine. Oui, vous aurez des collisions car la somme de contrôle n'est pas du tout sensible à la position du bit dans le champ de données.

Un contrôle de redondance cyclique (CRC) est quelque chose de très différent, de plus complexe et ne s'appelle PAS une somme de contrôle. C'est l'application d'une série polynomiale qui a la capacité de corriger n'importe quel nombre choisi de bits corrompus individuels dans le champ de données à partir duquel il a été généré. La création d'un CRC aboutit à un nombre plus grand que le champ de données d'origine (contrairement à la somme de contrôle) - d'où le nom incluant le mot «redondance» et le prix que vous payez pour la capacité de correction d'erreur. Un CRC n'est donc PAS un hachage et ne doit pas être confondu ni nommé comme somme de contrôle, car la redondance ajoute nécessairement à la taille des données d'origine.

CapitaineSensible
la source