Hash Code i Checksum - jaka jest różnica?

115

Rozumiem, że kod skrótu i ​​suma kontrolna to podobne rzeczy - wartość liczbowa obliczona dla bloku danych, która jest stosunkowo unikalna.

tj. prawdopodobieństwo, że dwa bloki danych dadzą tę samą numeryczną wartość skrótu / sumy kontrolnej jest na tyle niskie, że można je zignorować na potrzeby aplikacji.

Czy mamy więc dwa słowa na tę samą rzecz, czy też istnieją istotne różnice między kodami skrótu a sumami kontrolnymi?

Richard Ev
źródło
3
Podsumowując poniższe odpowiedzi: Kod skrótu redukuje dane wejściowe do niewielkiej liczby w sposób, który minimalizuje ryzyko kolizji. Z drugiej strony suma kontrolna redukuje dane wejściowe do niewielkiej liczby w sposób, który minimalizuje ryzyko kolizji. Możesz sprawić, że jeden dźwięk różni się od drugiego, dowolnie przeformułowując ten opis.
Dan Stahlke
3
@DanStahlke - Nie, nie tak mówią poniższe odpowiedzi. Tak, obaj redukują wkład do mniejszej liczby. Ale jest wiele, wiele sposobów, aby to zrobić, jak wybrać algorytm do użycia? To zależy od twojego celu. Podsumowując dwie najważniejsze odpowiedzi: celem sumy kontrolnej jest „ wykrycie najczęstszych błędów ”. Wybierz algorytm, który daje inną sumę kontrolną, dla wszystkich błędów „najbardziej typowych” w Twoim scenariuszu. Jeśli martwisz się, że jeden lub dwa bity zostaną przełączone, możesz wybrać algorytm, który gwarantuje wykrycie tego konkretnego błędu! To bardzo specyficzny kompromis.
ToolmakerSteve
1
@DanStahlke - z drugiej strony kod skrótu obejmuje szeroki zakres możliwych kompromisów. Jeśli mamy na myśli wartość używaną przy tworzeniu tablicy mieszającej, wiemy, że będzie ich dużo, kolizji. To zupełnie inny kompromis (niż suma kontrolna). Staramy się średnio ograniczać kolizje . Nic nie gwarantujemy. Mogą istnieć dane wejściowe, które różnią się tylko jednym bitem, ale dają ten sam hash. Jest to całkowicie w porządku, jeśli średnio uzyskujemy dobry rozkład wartości skrótu. Jednak dla sumy kontrolnej byłoby nie do przyjęcia.
ToolmakerSteve

Odpowiedzi:

72

Powiedziałbym, że suma kontrolna jest koniecznie hashcode . Jednak nie wszystkie kody skrótu tworzą dobre sumy kontrolne.

Suma kontrolna ma specjalne przeznaczenie - weryfikuje lub sprawdza integralność danych (niektóre mogą wykraczać poza to, umożliwiając korekcję błędów ). „Dobre” sumy kontrolne są łatwe do obliczenia i mogą wykryć wiele rodzajów uszkodzeń danych (np. Jeden, dwa, trzy błędne bity).

Hashcode po prostu opisuje funkcję matematyczną, która odwzorowuje dane na pewną wartość. W przypadku stosowania jako środka indeksowania w strukturach danych (np. Tablicy skrótów) pożądane jest niskie prawdopodobieństwo kolizji.

Zach Scrivena
źródło
6
Może jeden mógłby być użyty jako drugi, ale biorąc pod uwagę, że mają one inne cele projektowe, to po prostu wprowadza zamieszanie.
Wim Coenen
8
@gumbo: nie, nie każdy kod skrótu jest sumą kontrolną. Zobacz przykład ciągu z MSalters poniżej.
MarcH
41

Za każdym z nich kryje się inny cel:

  • Kod skrótu - zaprojektowany tak, aby był losowy w całej swojej domenie (aby zminimalizować kolizje w tablicach skrótów i tym podobne). Kryptograficzne kody skrótu są również zaprojektowane tak, aby były niemożliwe do odwrócenia obliczeniowo.
  • Suma kontrolna - zaprojektowana w celu wykrywania najczęstszych błędów w danych i często do szybkiego obliczania (w celu efektywnego sumowania szybkich strumieni danych).

W praktyce te same funkcje są często dobre do obu celów. W szczególności silny kryptograficznie kod skrótu jest dobrą sumą kontrolną (jest prawie niemożliwe, aby przypadkowy błąd złamał silną funkcję skrótu), jeśli możesz sobie pozwolić na koszt obliczeniowy.

Rafał Dowgird
źródło
1
Warto również wspomnieć, że niekryptograficzna wersja kodów skrótu może zapewnić dobry kompromis między czasem obliczeń (zbliżonym do CRC) a wykrywaniem błędów, niezależnie od tego, czy jest to celowy, czy tylko błąd komunikacji / rotacja bitów (nie można oczekiwać, że CRC wykryje celowe manipulowanie celowe zaprojektowanie kolizji jest stosunkowo łatwe).
hałaśliwy
1
Dla mnie kluczową frazą w Twojej odpowiedzi jest to, że suma kontrolna ma na celu wykrycie najczęstszych błędów . Tak, to jest to. jest to algorytm skrótu, który został wybrany w celu uzyskania różnych wartości dla prawdopodobnych uszkodzeń danych. Jest to konkretny cel i prowadzi do określonych algorytmów, które optymalizują się pod tym kątem - w zależności od rodzaju niepokojących zaburzeń.
ToolmakerSteve
22

Rzeczywiście istnieją pewne różnice:

  • Sumy kontrolne muszą być inne, gdy dane wejściowe są różne (tak często, jak to możliwe), ale prawie tak ważne jest, aby były szybkie do obliczenia.
  • Kody skrótu (do użytku w tabelach skrótów) mają te same wymagania, a ponadto powinny być równomiernie rozmieszczone w przestrzeni kodu, szczególnie w przypadku danych wejściowych, które są podobne.
  • Hashy kryptograficzne mają znacznie bardziej rygorystyczne wymagania, ponieważ mając skrót, nie można skonstruować danych wejściowych, które generują ten skrót. Czasy obliczeń są na drugim miejscu, aw zależności od zastosowania może być nawet pożądane, aby obliczanie skrótu było bardzo powolne (w celu zwalczania ataków siłowych).
Michael Borgwardt
źródło
1
Nie sądzę, aby różne sumy kontrolne dla różnych danych wejściowych miały jakieś korzyści. Służą tylko do sprawdzania integralności, a nie do haszowania.
user541686
1
@Mehrdad: jak więc proponujesz sprawdzić integralność bez uzyskiwania różnych wyników dla różnych danych wejściowych?
Michael Borgwardt
Eee, może źle sformułowałem to, co powiedziałem? Miałem na myśli część, w której powiedziałeś „tak daleko, jak to możliwe” - mówię tylko, że nie ma powodu, aby były nieprzewidywalne lub „dalekie” jak hashe. Dopóki istnieje pewne zmiany sumy kontrolnej, gdy wejście przechodzi typowe zmiany, to suma kontrolna porządku. Porównaj to z hashami, które również mają na celu dystrybucję rzeczy tak równomiernie / losowo / nieprzewidywalnie / „daleko”, jak to możliwe, w ich kodomenie.
user541686
Myślę, że po prostu źle zinterpretowałeś, co miałem na myśli, mówiąc „tak daleko, jak to możliwe” - miałem na myśli tylko, że kolizje powinny być tak rzadkie, jak to tylko możliwe, chociaż oczywiście są nieuniknione. Zmienię sformułowanie.
Michael Borgwardt
@Mehrdad - na początku to nie miało dla mnie sensu. Jeśli suma kontrolna nie ma dobrego rozkładu na możliwe wartości sum kontrolnych, oznacza to, że istnieją pewne wartości sumy kontrolnej, które są zwracane dla znacznie większej liczby wartości wejściowych (niż dla innych sum kontrolnych). Ale to zmniejsza użyteczność sumy kontrolnej? [Zwiększa prawdopodobieństwo, że zakłócone dane zwrócą ten sam wynik, prawda?] Hmm, mylę się, masz rację: suma kontrolna musi tylko dobrze wykrywać prawdopodobne zakłócenia. To może nie wymagać równego rozkładu wszystkich wartości.
ToolmakerSteve
10

Kody skrótów i sumy kontrolne są używane do tworzenia krótkich wartości liczbowych z elementu danych. Różnica polega na tym, że wartość sumy kontrolnej powinna ulec zmianie, nawet jeśli wprowadzono niewielką modyfikację elementu danych. W przypadku wartości skrótu wymaga się jedynie, aby elementy danych ze świata rzeczywistego miały różne wartości skrótu.

Wyraźnym przykładem są struny. Suma kontrolna dla łańcucha powinna obejmować każdy bit i kolejność ma znaczenie. Z drugiej strony kod skrótu może być często implementowany jako suma kontrolna prefiksu o ograniczonej długości. Oznaczałoby to, że „aaaaaaaaaaba” oznaczałoby to samo, co „aaaaaaaaaaab”, ale algorytmy haszujące mogą sobie radzić z takimi kolizjami.

MSalters
źródło
Ta odpowiedź jest tą, która dzwoni do mnie. Tak więc integralność danych nie jest celem skrótu.
trueadjustr
9

Wikipedia dobrze to ujmuje:

Funkcje sum kontrolnych są powiązane z funkcjami skrótu, odciskami palców, funkcjami randomizacji i kryptograficznymi funkcjami skrótu. Jednak każda z tych koncepcji ma inne zastosowania, a zatem różne cele projektowe. Cyfry kontrolne i bity parzystości to szczególne przypadki sum kontrolnych, odpowiednie dla małych bloków danych (takich jak numery PESEL, numery kont bankowych, słowa komputerowe, pojedyncze bajty itp.). Niektóre kody korygujące błędy są oparte na specjalnych sumach kontrolnych, które nie tylko wykrywają typowe błędy, ale także pozwalają w określonych przypadkach odzyskać oryginalne dane.

Jon Skeet
źródło
28
Po przeczytaniu tego nadal zastanawiam się, jaka jest różnica.
kirk.burleson
@ kirk.burleson - powiedziałbym, że to ta sama zasada , ale w praktyce zawsze idzie się na kompromisy . W różnych sytuacjach mają zastosowanie różne kompromisy, więc stosowane są różne podejścia. Właściwie nie jest to uzasadnienie dla istnienia dwóch różnych słów, po prostu mówiąc, że jeśli szukasz dobrych technik dla sum kontrolnych, możesz znaleźć inny zestaw algorytmów niż podczas wyszukiwania kodów skrótów.
ToolmakerSteve
5

Suma kontrolna chroni przed przypadkowymi zmianami.

Hash kryptograficzny chroni przed bardzo zmotywowanym napastnikiem.

Kiedy wysyłasz bity przewodem, może się przypadkowo zdarzyć, że niektóre bity zostaną odwrócone, usunięte lub wstawione. Aby umożliwić odbiorcy wykrycie (lub czasami skorygowanie) takich wypadków, nadawca używa sumy kontrolnej.

Ale jeśli zakładasz, że ktoś aktywnie i inteligentnie modyfikuje wiadomość w sieci i chcesz zabezpieczyć się przed tego typu napastnikiem, użyj kryptograficznego skrótu (ignoruję kryptograficzne podpisywanie skrótu lub używanie dodatkowego kanału lub czegoś podobnego, ponieważ pytanie nie wydaje się omijać tego).

user3464863
źródło
3
„Hash kryptograficzny” zwiększa zamieszanie między „hashem” a „sumą kontrolną”. „Kryptograficzna suma kontrolna” jest lepsza, ponieważ tak nie jest.
MarcH
5

Chociaż haszowanie i sumy kontrolne są podobne, ponieważ oba tworzą wartość na podstawie zawartości pliku, haszowanie nie jest tym samym, co tworzenie sumy kontrolnej. Suma kontrolna ma na celu weryfikację (sprawdzenie) integralności danych i identyfikację błędów transmisji danych, podczas gdy hash ma na celu stworzenie unikalnego cyfrowego odcisku palca danych.

Źródło: Przewodnik po podstawach bezpieczeństwa sieci CompTIA ® Security + - Wydanie piąte - Mark Ciampa - Strona 191

N Randhawa
źródło
4

Obecnie są one wymienne, ale w dawnych czasach suma kontrolna była bardzo prostą techniką, w której należało dodać wszystkie dane (zwykle w bajtach) i przypiąć bajt na końcu z tą wartością w ... wtedy miejmy nadzieję wiedzieć, czy któreś z oryginalnych danych zostały uszkodzone. Podobny do bitu kontrolnego, ale z bajtami.

Steven Robbins
źródło
4

Różnica między funkcjami kodu skrótu i ​​sumy kontrolnej polega na tym, że są one projektowane do różnych celów.

  • Suma kontrolna służy do sprawdzenia, czy coś na wejściu uległo zmianie.

  • Kod skrótu służy do sprawdzania, czy coś w danych wejściowych uległo zmianie i aby zachować jak największą odległość między poszczególnymi wartościami kodu skrótu.

    W przeciwieństwie do tej reguły mogą również istnieć dalsze wymagania dotyczące funkcji skrótu, takie jak możliwość wczesnego tworzenia drzew / klastrów / zasobników wartości kodu skrótu.

    A jeśli dodasz trochę współdzielonej początkowej randomizacji, dojdziesz do koncepcji nowoczesnego szyfrowania / wymiany kluczy.


O prawdopodobieństwie:

Na przykład załóżmy, że dane wejściowe faktycznie zawsze się zmieniają (w 100% przypadków). I załóżmy, że masz „idealną” funkcję mieszającą / sumy kontrolnej, która generuje 1-bitową wartość skrótu / sumy kontrolnej. W związku z tym otrzymasz różne wartości skrótu / sumy kontrolnej, w 50% przypadków, dla losowych danych wejściowych.

  • Jeśli zmienił się dokładnie 1 bit w Twoich losowych danych wejściowych, będziesz w stanie wykryć to przez 100% czasu, niezależnie od wielkości danych wejściowych.

  • Jeśli 2 bity w losowych danych wejściowych uległy zmianie, prawdopodobieństwo wykrycia „zmiany” jest podzielone przez 2, ponieważ obie zmiany mogą się wzajemnie zneutralizować, a żadna funkcja skrótu / sumy kontrolnej nie wykryje, że 2 bity są w rzeczywistości różne w danych wejściowych .

    ...

Oznacza to, że jeśli liczba bitów w danych wejściowych jest wielokrotnie większa niż liczba bitów w wartości skrótu / sumy kontrolnej, prawdopodobieństwo uzyskania różnych wartości skrótu / sumy kontrolnej dla różnych wartości wejściowych zmniejsza się i nie jest stała .

Sascha Wedler
źródło
2

Zwykle używam słowa suma kontrolna, odnosząc się do kodu (numerycznego lub innego) utworzonego dla pliku lub fragmentu danych, których można użyć do sprawdzenia , czy plik lub dane nie zostały uszkodzone. Najczęstszym zastosowaniem, z jakim się spotykam, jest sprawdzenie, czy pliki wysyłane przez sieć nie zostały zmienione (celowo lub w inny sposób).

Ian1971
źródło
1
Ponieważ sumy kontrolne nie są trudne do odwrócenia, sugeruje to, że nie byłyby one dobre do sprawdzania, czy coś zostało celowo zmienione.
benblasdell
0

W przypadku fragmentowania danych klastra Redis używa on hash slotdo zdecydowania, do którego węzła trafi. Weźmy na przykład poniższą operację modulo:

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

Plik 6 dwukrotnie w przypadku różnych danych wejściowych. Celem skrótu jest po prostu odwzorowanie wartości wejściowej na wartość wyjściową, a unikalność nie jest częścią umowy. Tak więc dwa różne dane wejściowe, które generują ten sam wynik, są w porządku w świecie skrótów.

Z drugiej strony, suma kontrolna musi różnić się od danych wyjściowych, nawet jeśli zmieni się jeden bit wejścia, ponieważ jego celem nie jest mapowanie, ale wykrywanie uszkodzeń danych. Tak więc dwa różne wejścia, które dają ten sam wynik, nie są akceptowane w sumie kontrolnej.

trueadjustr
źródło
-4

Suma kontrolna to po prostu liczba wygenerowana z pola danych przez oring (przez dodanie logiczne, stąd suma). Suma kontrolna może wykryć uszkodzenie dowolnego bitu lub liczby bitów w polu danych, z którego jest generowana, tj. Sprawdza błędy, to znaczy nie może ich poprawić. Suma kontrolna to skrót, ponieważ rozmiar sumy kontrolnej jest mniejszy niż oryginalne dane. Tak, wystąpią kolizje, ponieważ suma kontrolna wcale nie jest wrażliwa na pozycję bitu w polu danych.

Cykliczna kontrola nadmiarowa (CRC) jest czymś zupełnie innym, bardziej złożonym i NIE jest nazywana sumą kontrolną. Jest to zastosowanie szeregu wielomianowego, który ma możliwość korygowania dowolnej wybranej liczby pojedynczych uszkodzonych bitów w polu danych, z którego został wygenerowany. Utworzenie CRC skutkuje liczbą większą niż oryginalne pole danych (w przeciwieństwie do sumy kontrolnej) - stąd nazwa zawierająca słowo „redundancja” i cena, jaką płacisz za możliwość korekcji błędów. Dlatego CRC NIE jest hashem i nie można go mylić ani nazywać sumą kontrolną, ponieważ nadmiarowość z konieczności zwiększa rozmiar oryginalnych danych.

CapitainSensible
źródło