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

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?

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.

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.

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).

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.

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.

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).

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

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.

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 .

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).

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.

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.