Kiedy CRC jest bardziej odpowiednie niż MD5 / SHA1?

130

Kiedy należy używać CRC do wykrywania błędów w porównaniu z nowszymi funkcjami mieszającymi, takimi jak MD5 lub SHA1? Czy to pierwsze jest łatwiejsze do wdrożenia na sprzęcie wbudowanym?

Gili
źródło

Odpowiedzi:

114

CRC działa dobrze w przypadku wykrywania przypadkowych błędów w danych, które mogą wystąpić, na przykład z powodu zakłóceń sieciowych, szumów linii, zniekształceń itp.

CRC jest obliczeniowo znacznie mniej skomplikowane niż MD5 lub SHA1. Używanie funkcji skrótu, takiej jak MD5, jest prawdopodobnie przesadą w przypadku wykrywania przypadkowych błędów. Jednak użycie CRC do dowolnego rodzaju kontroli bezpieczeństwa byłoby znacznie mniej bezpieczne niż bardziej złożona funkcja mieszająca, taka jak MD5.

I tak, CRC jest znacznie łatwiejsze do wdrożenia na sprzęcie wbudowanym, możesz nawet uzyskać różne pakiety rozwiązań do tego na układach scalonych.

definiuje
źródło
1
@gili: zawsze możesz po prostu xorować dwordy razem, aby uzyskać pojedynczy wynikowy dword.
Blindy
2
@Dustin: Masz całkowitą rację w swojej odpowiedzi, ale może rozważ zmianę „CRC jest obliczeniowo znacznie bardziej wydajne” na „CRC jest obliczeniowo znacznie łatwiejsze”? Algorytmy MD5 / SHA-1 są złożone, ale nie są tak naprawdę „nieefektywne” IMO.
Coxy,
1
@coxymla masz rację, słowo, którego powinienem był użyć, to „złożone”, a nie „nieefektywne”. Dzięki!
definiuje
27
Aby zredukować długi hash do 32 bitów, po prostu weź pierwsze 32 bity.
orip
1
Jeśli Twoim celem jest bezpieczeństwo, nigdy nie powinieneś go używać MD5, SHA-1należy go również unikać, SHA-2zalecany jest pewien wariant .
Peter
33

CRC jest zaprojektowany przed niezamierzonymi zmianami danych. Oznacza to, że jest dobry do wykrywania niezamierzonych błędów, ale będzie bezużyteczny jako sposób na upewnienie się, że dane nie zostały złośliwie przetworzone.

Zobacz także to .

Liran Orevi
źródło
Najważniejsza część z linku w tej odpowiedzi: „(...) nawet 2048-bitowy CRC byłby kryptograficznie znacznie mniej bezpieczny niż 128-bitowy MD5”
Marc
3
Chociaż odpowiedź jest nadal prawidłowa, MD5 i SHA1 są obecnie na tym samym poziomie bezpieczeństwa. Innymi słowy, nadaje się tylko do wykrywania niezamierzonych błędów.
Piskvor opuścił budynek
22

Znalazłem badanie, które pokazuje, jak nieodpowiednie są skróty CRC dla tabel skrótów . Wyjaśnia również rzeczywistą charakterystykę algorytmu. Badanie obejmuje również ocenę innych algorytmów wyznaczania wartości skrótu i ​​jest dobrym źródłem informacji.

Odpowiedni wniosek dotyczący CRC dla hashów:

CRC32 nigdy nie był przeznaczony do użytku z tablicą mieszającą. Naprawdę nie ma dobrego powodu, aby używać go w tym celu i radzę tego unikać. Decydując się na użycie CRC32, ważne jest, aby użyć bitów skrótu od końca przeciwnego do tego, w którym podawane są oktety klucza. Który koniec zależy od konkretnej implementacji CRC32. Nie traktuj CRC32 jako funkcji skrótu „czarnej skrzynki” i nie używaj jej jako skrótu ogólnego przeznaczenia. Pamiętaj, aby przetestować każdą aplikację pod kątem przydatności.

AKTUALIZACJA

Wygląda na to, że witryna nie działa. Archiwum internetowego ma kopię chociaż.

Andre Luus
źródło
Link jest uszkodzony. Może sam możesz napisać wyjaśnienie? Jeśli nie, odpowiedź jest bezużyteczna.
ceving
Okej, dołączę wniosek do mojej odpowiedzi.
Andre Luus,
Dziwne, według benchmarku tutaj , CRC faktycznie robi bardzo dobrze pod względem szybkości i liczby kolizji.
ostrokach
Rzeczywiście bardzo interesujące. Musiałem ponownie przejrzeć badanie, z którym się połączyłem, ale gdybym miał zgadywać, musi to być spowodowane różnymi implementacjami testowymi. Gdybym miał podjąć decyzję, skorzystałbym z rady z badania, wydaje się bardziej uzasadniona naukowo.
Andre Luus
Z mojego doświadczenia wynika, że ​​haszowanie milionów adresów URL, CRC64 zderzyło się 8 razy, a MD5 zderzyło się 5. Oczywiście MD5 było lepsze, ale CRC64 było świetnym, znacznie szybszym i prostszym hashem.
J. Dimeo,
18

Uruchomiłem każdą linię tego kodu PHP w pętli 1.000.000. Wyniki są w komentarzach (#).

hash('crc32', 'The quick brown fox jumped over the lazy dog.');#  750ms   8 chars
hash('crc32b','The quick brown fox jumped over the lazy dog.');#  700ms   8 chars
hash('md5',   'The quick brown fox jumped over the lazy dog.');#  770ms  32 chars
hash('sha1',  'The quick brown fox jumped over the lazy dog.');#  880ms  40 chars
hash('sha256','The quick brown fox jumped over the lazy dog.');# 1490ms  64 chars
hash('sha384','The quick brown fox jumped over the lazy dog.');# 1830ms  96 chars
hash('sha512','The quick brown fox jumped over the lazy dog.');# 1870ms 128 chars

Mój wniosek:

  • Użyj „crc32b”, gdy potrzebujesz http://en.wikipedia.org/wiki/Cyclic_redundancy_check i nie zależy Ci na bezpieczeństwie.
  • Użyj "sha256" (lub nowszego), gdy potrzebujesz dodatkowej warstwy bezpieczeństwa.

  • Nie używaj „md5” ani „sha1”, ponieważ mają:

    1. niektóre problemy związane z bezpieczeństwem, gdy zależy Ci na bezpieczeństwie
    2. są dłuższe i wolniejsze niż "crc32b", gdy wszystko czego potrzebujesz to CRC
Jaskółka oknówka
źródło
masz na myśli bity, a nie znaki
esskar
Nie całkiem. echo hash ('crc32', 'Szybki brązowy lis przeskoczył leniwego psa.'); echo "413a86af", czyli 8-znakowy ciąg. Przy okazji, jest to 32-bitowa liczba zapisana w formacie HEX. Na przykład "sha256" ma 256-bitowy hash, ponownie przechowywany jako HEX, co daje 64-znakowy ciąg.
Martin
46
Te wyniki są bardzo mylące. Gdy te algorytmy haszujące zostaną zastosowane do dużego zestawu danych ( zamiast wojny i pokoju"The quick brown fox jumped over the lazy dog." ), zobaczysz, o ile szybsze jest CRC niż MD5.
ubiquibacon
1
Istnieje przypadek pośredni (zduplikowane sprawdzanie w bibliotekach), w którym MD5 / Sha1 są właściwym rozwiązaniem: nie muszą zajmować się przypadkiem, w którym przeciwnik ostrożnie tworzy znikającą, mało prawdopodobną kolizję hash, ale musi radzić sobie z przypadkowymi kolizjami. A więc: Wykrywanie błędów bitowych i uszkodzeń: CRC32 Wykrywanie kolizji w bibliotekach: MD5 / SHA1 Aplikacje adwersyjne: Sha256 i nowsze. Oczywiście, jeśli masz bibliotekę z miliardami wpisów, prawdopodobnie będziesz musiał również zwiększyć liczbę bitów mieszania.
Dewi Morgan
PHP? na platformie ARM, kod osadzony, 16 MHz i CRC32 o rozmiarze 46 bajtów, może 12 mikrosekund. To ma pomoc sprzętową. Nawet wspomagany sprzętowo AES byłby kilkaset razy wolniejszy. CRC tabeli przeglądowej bez wspomagania powinno nadal nadejść za około 50 mikrosekund.
ilgitano
11

Aby uzyskać informacje o CRC na temat implementacji, szybkości i niezawodności, zobacz Bezbolesny przewodnik po algorytmach wykrywania błędów CRC . Ma wszystko na CRC.

Chyba że ktoś spróbuje złośliwie zmodyfikować twoje dane i ukryć zmianę CRC jest wystarczające. Po prostu użyj „dobrego” (standardowego) wielomianu.

Gerhard
źródło
10

Wszystko zależy od Twoich wymagań i oczekiwań.

Oto krótkie krótkie różnice między tymi algorytmami funkcji skrótu :

CRC (CRC-8/16/32/64)

  • jest nie kryptograficzny algorytm skrótu (to jest przy użyciu funkcji liniowej na podstawie cykliczny kod nadmiarowy)
  • może produkować 9, 17, 33 lub 65 bitów
  • nie jest przeznaczony do celów kryptograficznych, ponieważ nie daje żadnych gwarancji kryptograficznych,
  • nie nadaje się do podpisów cyfrowych, ponieważ jest łatwo odwracalny 2006 ,
  • nie powinny być używane do celów szyfrowania,
  • różne ciągi mogą generować kolizję,
  • wynaleziony w 1961 roku i używany w Ethernecie i wielu innych standardach,

MD5

  • jest kryptograficznym algorytmem mieszania,
  • tworzenie 128-bitowej (16-bajtowej) wartości skrótu (32-cyfrowe liczby szesnastkowe)
  • jest to skrót kryptograficzny, ale jest uważany za przestarzały, jeśli martwisz się o bezpieczeństwo,
  • są znane ciągi, które mają tę samą wartość skrótu MD5
  • może służyć do szyfrowania,

SHA-1

  • jest kryptograficznym algorytmem mieszania,

  • generuje 160-bitową (20-bajtową) wartość skrótu zwaną skrótem wiadomości

  • jest to hash kryptograficzny i od 2005 roku nie jest już uważany za bezpieczny,

  • może służyć do szyfrowania,

  • znaleziono przykład kolizji sha1

  • pierwszy raz opublikowany w 1993 roku (jako SHA-0), a następnie 1995 jako SHA-1,

  • serie: SHA-0, SHA-1, SHA-2, SHA-3,

    Podsumowując, przy użyciu SHA-1 nie jest już uważane za bezpieczne przeciwko dobrze finansowanych przeciwników, bo w 2005 roku, znaleziono kryptoanalitycy ataki na SHA-1, co sugeruje, że być może nie wystarczająco bezpieczne dla ciągłego użytkowania Schneier . NIST USA zaleca, aby agencje federalne zaprzestały używania SHA1-1 do zastosowań wymagających odporności na kolizje i muszą używać SHA-2 po NIST 2010 .

Dlatego jeśli szukasz prostego i szybkiego rozwiązania do sprawdzania integralności plików (pod kątem uszkodzenia) lub do prostych celów buforowania pod względem wydajności, możesz rozważyć CRC-32, jako haszowanie, które możesz rozważyć. MD5, jeśli jednak tworzysz profesjonalną aplikację (która powinna być bezpieczna i spójna), aby uniknąć prawdopodobieństwa kolizji - użyj SHA-2 i nowszych (takich jak SHA-3).

Występ

Kilka prostych testów porównawczych w PHP:

# Testing static text.

$ time php -r 'for ($i=0;$i<1000000;$i++) crc32("foo");'
real    0m0.845s
user    0m0.830s
sys     0m0.008s

$ time php -r 'for ($i=0;$i<1000000;$i++) md5("foo");'
real    0m1.103s
user    0m1.089s
sys     0m0.009s

$ time php -r 'for ($i=0;$i<1000000;$i++) sha1("foo");'
real    0m1.132s
user    0m1.116s
sys   0m0.010s

# Testing random number. 

$ time php -r 'for ($i=0;$i<1000000;$i++) crc32(rand(0,$i));'
real    0m1.754s
user    0m1.735s
sys     0m0.012s\

$ time php -r 'for ($i=0;$i<1000000;$i++) md5(rand(0,$i));'
real    0m2.065s
user    0m2.042s
sys     0m0.015s

$ time php -r 'for ($i=0;$i<1000000;$i++) sha1(rand(0,$i));'
real    0m2.050s
user    0m2.021s
sys     0m0.015s

Związane z:

kenorb
źródło
8

Nie mówisz, co próbujesz chronić.

CRC jest często używany w systemach wbudowanych jako kontrola przed przypadkowym uszkodzeniem danych, w przeciwieństwie do zapobiegania złośliwej modyfikacji systemu. Przykładami miejsc, w których CRC może być przydatna, jest walidacja obrazu EPROM podczas inicjalizacji systemu w celu ochrony przed uszkodzeniem oprogramowania układowego. Program ładujący system obliczy CRC dla kodu aplikacji i porówna go z zapisaną wartością przed zezwoleniem na uruchomienie kodu. Chroni to przed możliwością przypadkowego uszkodzenia programu lub niepowodzeniem pobierania.

CRC może być również używany w podobny sposób do ochrony danych konfiguracyjnych przechowywanych w pamięci FLASH lub EEPROM. Jeśli CRC jest niepoprawne, dane można oznaczyć jako nieważne i użyć domyślnego lub zapasowego zestawu danych. CRC może być nieważne z powodu awarii urządzenia lub jeśli użytkownik odłączył zasilanie podczas aktualizacji magazynu danych konfiguracyjnych.

Pojawiły się komentarze, że hash zapewnia większe prawdopodobieństwo wykrycia uszkodzenia niż CRC z wieloma błędami bitów. To prawda, a decyzja, czy użyć 16- lub 32-bitowego CRC, będzie zależeć od konsekwencji bezpieczeństwa użycia uszkodzonego bloku danych i czy można uzasadnić szansę 1 na 2 ^ 16 lub 2 ^ 32 blok danych został nieprawidłowo zadeklarowany jako ważny.

Wiele urządzeń ma wbudowany generator CRC dla standardowych algorytmów. Seria MSP430F5X z Teksasu posiada sprzętową implementację standardu CRC-CCITT.

uɐɪ
źródło
6

CRC32 jest szybszy, a hash ma tylko 32 bity.

Użyj go, gdy chcesz uzyskać szybką i lekką sumę kontrolną. CRC jest używany w sieci Ethernet.

Jeśli potrzebujesz większej niezawodności, lepiej jest użyć nowoczesnej funkcji mieszania.

François
źródło
5

Używaj CRC tylko wtedy, gdy zasoby obliczeniowe są bardzo ograniczone (np. Niektóre środowiska osadzone) lub musisz przechowywać / transportować wiele wartości wyjściowych, a przestrzeń / przepustowość jest niewielka (ponieważ CRC są zwykle 32-bitowe, a wyjście MD5 jest 128-bitowe, SHA1 160 bit i inne warianty SHA do 512 bitów).

Nigdy nie używaj CRC do kontroli bezpieczeństwa, ponieważ CRC jest bardzo łatwe do „sfałszowania”.

Nawet w przypadku wykrycia przypadkowych błędów (zamiast wykrywania złośliwych zmian) skróty są lepsze niż zwykłe CRC. Częściowo z powodu prostego sposobu obliczania CRC (a częściowo dlatego, że wartości CRC są zwykle krótsze niż typowe wartości wyjściowe skrótu, więc mają znacznie mniejszy zakres możliwych wartości), jest znacznie bardziej prawdopodobne, że w sytuacji, gdy wystąpią dwa lub więcej błędów jeden błąd maskuje inny, więc mimo dwóch błędów otrzymujesz ten sam CRC.

W skrócie: jeśli nie masz powodu, aby nie używać przyzwoitego algorytmu mieszającego, unikaj prostych CRC.

David Spillett
źródło
1
CRC przechwyci wszystkie przypadkowe zmiany danych, jeśli użyjesz odpowiedniego wielomianu. 1/2 ^ 32 zmiany są pomijane, jeśli dokładnie zmieni się kilka właściwych bitów.
Gerhard
Z odpowiednim wielomianem wyłapuje również wszystkie błędy pewnych typowych klas, np. Błędy serii.
erikkallen
Zgadzam się z twoją odpowiedzią, z wyjątkiem pytania o systemy wbudowane. Wydajność algorytmu kryptograficznego może być problematyczna w mniejszych systemach wbudowanych.
Craig McQueen
Zupełnie się z tym nie zgadzam. Wielomiany błędów CRC są starannie dobrane, tak aby w niektórych przypadkach mogły wykryć 1, 2, 3, 5, aw niektórych przypadkach nawet do około 11 bitów. Hash kryptograficzny jest czysto statystyczny, więc musisz używać dużych wartości skrótu. 8-32 bitów jest nierealistyczne dla kryptograficznego skrótu, a także bezcelowo drogie w cyklach procesora i bramkach. Zdecydowanie nie jest to odpowiedź do podjęcia, jeśli pracujesz nad systemami wbudowanymi. Jedyny moment, w którym NIE używaj CRC, to sytuacja, w której musisz zmierzyć się z inteligentnym scenariuszem przeciwnika.
ilgitano
5

Niedawno natknąłem się na zastosowanie CRC, które było sprytne. Autor narzędzia do identyfikacji i usuwania duplikatów plików jdupe (ten sam autor popularnego narzędzia exif jhead) używa go podczas pierwszego przejścia przez pliki. CRC jest obliczane na pierwszych 32K każdego pliku, aby oznaczyć pliki, które wydają się takie same, również pliki muszą mieć ten sam rozmiar. Pliki te są dodawane do listy plików, dla których ma zostać wykonane pełne porównanie binarne. Przyspiesza sprawdzanie dużych plików multimedialnych.

John Wright
źródło
Jeden problem z tym podejściem polega na tym, że gdy jest uruchamiany na pliku, który zawiera wbudowany CRC32, wynikowy CRC może być niezależny od danych w pliku (ponieważ jeśli dane ulegną zmianie, CRC32 zostanie zmieniony tak, aby zlikwidować różnicę ). Łączenie danych w prosty sposób przed obliczeniem CRC32 pozwoliłoby uniknąć tego problemu.
supercat
1
@supercat - naprawdę nie wierzę, że to faktycznie problem. Jeśli plik zawiera nagłówek crc32, który jest crc32 reszty pliku, to po zaktualizowaniu pliku każdy bit w nagłówku crc32 będzie miał około 50% szans na bycie innym. Zmiany w nagłówku powinny mieć dość losowy rozkład. Nie widzę, jak to doprowadzi do tego, że CRC32 (nagłówek + dane) będzie zawsze taki sam lub w jakikolwiek sposób niezależny od części danych pliku.
teratorn
@teratorn: Widziałem wiele plików, które na końcu mają CRC32, obliczone w taki sposób, że CRC32 całego pliku, obliczone przy użyciu określonej stałej ziarna, zawsze będzie inną stałą wartością. Jest to dość powszechne w przypadku obrazów z kodem binarnym. Jeśli odtwarzacz DVD Acme 1000 używa obrazów kodu o stałym rozmiarze do aktualizacji oprogramowania sprzętowego i oczekuje, że każdy obraz kodu będzie miał określony CRC32, wówczas procedura obliczająca CRC32 różnych plików nie będzie w stanie rozróżnić różnych obrazów kodu dla Acme 1000.
supercat
Celem CRC w tym przypadku jest szybkie stwierdzenie, że pliki są różne. Jeśli CRC wróci tak samo, musisz teraz przeprowadzić kosztowne porównanie binarne, aby osadzony CRC nie złamał algorytmu. Może się zdarzyć, że niektóre pliki zostaną porównane binarnie, ponieważ pierwszy przebieg CRC mówi, że MOGĄ być takie same, ale jest mało prawdopodobne, aby było ich wiele i możesz tego uniknąć, używając niestandardowego wielomianu.
ilgitano
4

CRC32 jest znacznie szybszy i czasami obsługuje sprzęt (np. Na procesorach Nehalem). Naprawdę, jedyny raz, kiedy go użyjesz, to połączenie ze sprzętem lub jeśli masz naprawdę małą wydajność

Ana Betts
źródło
4

Zacznijmy od podstaw.

W kryptografii algorytm mieszający konwertuje wiele bitów na mniej bitów poprzez operację skrótu. Hashe służą do potwierdzania integralności wiadomości i plików.

Wszystkie algorytmy haszujące generują kolizje. Kolizja ma miejsce, gdy kilka kombinacji wielobitowych daje taką samą mniejszą liczbę bitów na wyjściu. Siła kryptograficzna algorytmu haszującego jest definiowana przez niezdolność osoby do określenia, jakie będą dane wyjściowe dla danego wejścia, ponieważ gdyby mogli skonstruować plik z hashem pasującym do legalnego pliku i naruszyć zakładaną integralność systemu. Różnica między CRC32 i MD5 polega na tym, że MD5 generuje większy hash, który jest trudniejszy do przewidzenia.

Kiedy chcesz zaimplementować integralność wiadomości - co oznacza, że ​​wiadomość nie została naruszona podczas przesyłania - niemożność przewidywania kolizji jest ważną właściwością. 32-bitowy hash można opisać 4 miliardy różnych komunikatów lub plików za 4 miliardy różnych unikatowych skrótów. Jeśli masz 4 miliardy i 1 pliki, masz gwarancję 1 kolizji. 1 TB przestrzeni bitowej umożliwia miliardy kolizji. Jeśli jestem atakującym i mogę przewidzieć, jaki będzie ten 32-bitowy hash, mogę skonstruować zainfekowany plik, który koliduje z plikiem docelowym; który ma ten sam hash.

Dodatkowo, jeśli wykonuję transmisję z prędkością 10 Mb / s, prawdopodobieństwo uszkodzenia pakietu tylko po to, aby ominąć crc32 i kontynuować do miejsca docelowego i wykonać jest bardzo niskie. Powiedzmy, że przy 10 Mb / s pojawia się 10 błędów \ sekunda . Jeśli zwiększę to do 1 Gb / s, teraz otrzymuję 1000 błędów na sekundę . Jeśli staram się do 1 exabit na sekundę, wówczas wskaźnik błędów wynosi 1000000000 błędów na sekundę . Powiedzmy, że mamy współczynnik kolizji 1 \ 1 000 000błędy transmisji, co oznacza, że ​​1 na milion błędów transmisji powoduje, że uszkodzone dane przechodzą niewykryte. Przy 10 Mb / s dane o błędach były wysyłane co 100 000 sekund lub mniej więcej raz dziennie. Przy 1 Gbps zdarzało się to raz na 5 minut. Przy 1 eksabitie na sekundę rozmawiamy kilka razy na sekundę.

Jeśli otworzysz Wireshark, zobaczysz, że typowy nagłówek Ethernet ma CRC32, nagłówek IP ma CRC32, a nagłówek TCP ma CRC32, i to dodatkowo do tego, co mogą robić protokoły wyższych warstw; np. IPSEC może używać MD5 lub SHA do sprawdzania integralności oprócz powyższych. Istnieje kilka warstw sprawdzania błędów w typowej komunikacji sieciowej, które NADAL czasami zawodzą przy prędkościach poniżej 10 Mb / s.

Cykliczna kontrola nadmiarowa (CRC) ma kilka popularnych wersji i kilka rzadkich, ale generalnie jest zaprojektowana tak, aby po prostu stwierdzić, kiedy wiadomość lub plik został uszkodzony podczas przesyłania (przerzucanie wielu bitów). Sam CRC32 nie jest dobrym protokołem sprawdzania błędów według dzisiejszych standardów w dużych, skalarnych środowiskach korporacyjnych ze względu na współczynnik kolizji; przeciętny dysk twardy użytkownika może mieć do 100 tys. plików, a udziały plików w firmie mogą mieć dziesiątki milionów. Stosunek przestrzeni mieszania do liczby plików jest po prostu za mały. CRC32 jest obliczeniowo tani do wdrożenia, podczas gdy MD5 nie.

MD5 został zaprojektowany, aby powstrzymać celowe użycie kolizji, aby złośliwy plik wyglądał łagodnie. Jest uważany za niezabezpieczony, ponieważ obszar skrótu został wystarczająco zmapowany, aby umożliwić wystąpienie niektórych ataków, a niektóre kolizje są przewidywalne. SHA1 i SHA2 to nowe dzieciaki w okolicy.

Wielu dostawców zaczyna używać Md5 do weryfikacji plików, ponieważ można z nim szybko tworzyć pliki wielobajtowe lub wielobajtowe i układać je na szczycie ogólnego wykorzystania i obsługi CRC32 przez system operacyjny. Nie zdziw się, jeśli w ciągu następnej dekady systemy plików zaczną używać MD5 do sprawdzania błędów.

bobinator
źródło
1

Kod CRC jest prostszy i szybszy.

Do czego potrzebujesz?

Macarse
źródło