Widziałem 8-bitowe, 16-bitowe i 32-bitowe CRC.Długość danych a długość CRC
W którym momencie muszę przejść do szerszego CRC?
My jelita reakcji jest to, że opiera się na długości na serwerze
EDIT: Patrząc na stronie Wikipedia o CRC i Lott za odpowiedź, oto co mamy:
< 64 bajtów: 8-bitowy CRC
< 16K bajtów: 16-bitowe CRC
< 512M bajtów: 32-bitowy CRC
To nie jest temat badań. Jest to naprawdę dobrze zrozumiałe: http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Matematyka jest bardzo prosta. 8-bitowy CRC sprowadza wszystkie wiadomości do jednej z 256 wartości. Jeśli twoja wiadomość ma więcej niż kilka bajtów, możliwość wysyłania wielu wiadomości o tej samej wartości mieszania rośnie coraz wyżej.
16-bitowy CRC, podobnie, daje jedną z 65 536 dostępnych wartości skrótu. Jakie są szanse dwóch dowolnych wiadomości mających jedną z tych wartości?
32-bitowy CRC daje około 4 miliardów dostępnych wartości skrótu.
Z artykułu w Wikipedii: "maksymalna całkowita długość bloku jest równa 2**r − 1". To w kawałkach. Nie trzeba robić wiele badań, aby zobaczyć, że 2**9 - 1 jest 511 bitów. Przy użyciu CRC-8 wiele wiadomości dłuższych niż 64 bajty będzie miało tę samą wartość sumy kontrolnej CRC.
Jest to dokładne i pomocne, jeśli CRC jest używane do wykrywania zmian w pliku. Jeśli jednak jest używany jako skrót do wykrywania duplikatów między plikami, jest to bardziej skomplikowane. W szczególności paradoks urodzin wymaga od nas uwzględnienia w ilu różnych wartościach spodziewamy się mieć. –
@Steven Sudit: Prawidłowo. Niestety, pytanie jest zbyt niejasne, aby ustalić cokolwiek na temat użycia CRC. –
Myślę, że * dowolny * wiadomość samotnika niż szerokość CRC (r-1, a nie 2^r-1) będzie mieć wiele wiadomości mapowanych na tę samą sumę kontrolną. IOW, każda wiadomość o długości większej niż bajt, będzie miała nakładające się mapowania CRC8. Myślę, że jednym z wyzwań jest zaprojektowanie mapowania w taki sposób, aby dystrybucja ciągów komunikatów nad skrótami była jednolita. – ysap
myślę, że wielkość CRC ma więcej wspólnego z tym, jak wyjątkowa CRC, którego potrzebujesz, zamiast rozmiaru danych wejściowych. Jest to związane ze szczególnym użyciem i liczbą elementów, na których obliczasz CRC.
CRC powinno być wybrane specjalnie dla długości wiadomości, to nie jest tylko kwestia wielkości CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Skuteczność CRC jest zależna od wielu czynników. Musisz nie tylko wybrać ROZMIAR CRC, ale także GENERATING POLYNOMIAL do użycia. Istnieją skomplikowane i nieintuicyjne kompromisy w zależności od:
Papier Cyclic Redundancy Code Wybór wielomianu Dla sieci wbudowanych, Philip Koopman i Tridib Chakravarty, publised w pracach Międzynarodowej Konferencji na temat systemów niezawodne i Sieci w 2004 roku daje bardzo dobry przegląd i sprawia, że kilka rekomendacji. Zapewnia również bibliografię w celu lepszego zrozumienia.
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Wybór długości CRC kontra format jest przede wszystkim istotne w przypadkach, gdy jeden jest bardziej prawdopodobne, że wejście, które różni się od „poprawny” wejście przez trzech lub mniejszej liczby bitów niż mieć jeden, który jest masowo inny. Biorąc pod uwagę dwa wejścia, które różnią się znacznie, możliwość fałszywego dopasowania będzie wynosić około 1/256 dla większości form 8-bitowej wartości kontrolnej (w tym CRC), 1/65536 dla większości form 16-bitowej wartości kontrolnej (w tym CRC) itp. Zaletą CRC jest jego przetwarzanie danych wejściowych, które są bardzo podobne.
W przypadku 8-bitowego CRC, którego wielomian generuje dwa okresy o długości 128, ułamek błędów pojedynczego, podwójnego lub potrójnego pakietu w pakiecie krótszym niż ten, który pozostaje niewykryty, nie będzie wynosił 1/256 - będzie być zero. Podobnie z 16-bitowym CRC okresu 32768, używając pakietów 32768 bitów lub mniej.
Jeśli jednak pakiety są dłuższe niż okres CRC, błąd podwójnego bitu pozostanie niewykryty, jeśli odległość między błędnymi bitami jest wielokrotnością okresu CRC. Chociaż może się to wydawać niezbyt prawdopodobnym scenariuszem, CRC8 będzie nieco gorszy w wychwytywaniu błędów podwójnych w długich pakietach, niż przy łapaniu błędów "pakiet jest całkowicie zakodowany". Jeśli błędy dwubitowe są drugim najczęstszym błędem (po błędach jednobitowych), byłoby to złe. Jeśli coś, co psuje niektóre dane, może zepsuć wiele z nich, jednak gorsze zachowanie CRC z błędami dwubitowymi może nie być problemem.
Atak MD5 pod koniec 2008 r. Jest podręcznikowym przykładem problemu z CRC, który jest zbyt jednolity lub zbyt mały: http://www.win.tue.nl/hashclash/rogue-ca/ – bzlm
CRC nie jest algorytm mieszający. Jest to sposób na sprawdzenie, czy trochę zostało przypadkowo odwrócone. Nie widzę połączenia z linkiem MD5. Przyjrzę się jeszcze raz. – Robert
@bzlm MD5 nie ma z tym nic wspólnego. CRC w ogóle nie opierają się takim atakom, służą do wykrywania przypadkowych błędów, a nie złośliwych ataków. – starblue