Czy CRC32 może być używany jako funkcja skrótu?

Question

Czy CRC32 może być używany jako funkcja skrótu? Jakiekolwiek wady tego podejścia? Dowolne transakcje?

Answer 1

CRC32 działa bardzo dobrze jako algorytm mieszający. Całkowity punktCRC polega na tym, że zawiera strumień bajtów z jak najmniejszą liczbą kolizji. To powiedziawszy, jest kilka kwestii do rozważenia:

• CRC nie są bezpieczne. Do bezpiecznego mieszania potrzebujesz znacznie bardziej kosztownego obliczeniowo algorytmu. W przypadku prostego mieszania kubełkowego zabezpieczenie zwykle nie stanowi problemu.

• Różne smaki CRC istnieją z różnymi właściwościami. Upewnij się, że używasz odpowiedniego algorytmu, np. z wielomianem mieszającym 0x11EDC6F41 (CRC32C), który jest optymalnym wyborem ogólnego przeznaczenia.

• Jako kompilacja prędkości/jakości, instrukcja CRC32 dla x86 jest trudna do pokonania. Jednak ta instrukcja nie istnieje w starszych procesorach, więc należy uważać na problemy z przenośnością.

---- EDIT ----

Mark Adler warunkiem link do użytecznego artykule dla oceny hash przez Bret Mulvey. Korzystając z kodu źródłowego podanego w artykule, uruchomiłem "test kubełkowy" zarówno dla CRC32C, jak i Jenkins96. Tabele te pokazują prawdopodobieństwo, że prawdziwie jednolita dystrybucja byłaby gorsza od wyniku zmierzonego tylko przez przypadek. Tak więc, wyższe liczby są lepsze. Autor uznał 0,05 lub mniej za słaby i 0,01 lub za bardzo za słaby. Całkowicie ufam autorowi tego wszystkiego i właśnie zgłaszam wyniki.

Umieściłem * we wszystkich przypadkach, w których CRC32C działał lepiej niż Jenkins96. W tym prostym teście CRC32C był bardziej jednorodny haszysz niż Jenkins96 54 z 96 razy. Zwłaszcza, jeśli można użyć instrukcji CRC32 x86, kompromis w zakresie wydajności prędkości jest doskonały.

 
CRC32C (0x1EDC6F41) 

     Uniform keys  Text keys   Sparse keys 

Bits Lower Upper  Lower Upper  Lower Upper 
1 0.671 *0.671 *1.000 0.120 *0.572 *0.572 
2 *0.706 *0.165 *0.729 *0.919  0.277 0.440 
3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542 
4 0.573 0.332  0.433 0.462 *0.855 0.393 
5 0.023 *0.681  0.470 0.907  0.266 0.059 
6 *0.145 *0.523  0.354 *0.172 *0.336 0.588 
7 0.424 0.722  0.172 *0.736  0.184 *0.842 
8 *0.767 0.507 *0.533 0.437  0.337 0.321 
9 0.480 0.725 *0.753 *0.807 *0.618 0.025 
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344 
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003 
12 *0.979 *0.239 *0.709 0.786  0.171 *0.865 
13 *0.515 0.395  0.192 0.600  0.869 *0.238 
14 0.089 *0.609  0.055 *0.414 *0.286 *0.398 
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300 
16 0.015 *0.946 *0.467 0.459  0.372 *0.793 

I Jenkins96, którego autor artykułu uważa się za doskonałe hash:

 
Jenkins96 

     Uniform keys   Text keys   Sparse keys 

Bits Lower Upper  Lower Upper  Lower Upper 
1 0.888 0.572  0.090 0.322  0.090 0.203 
2 0.198 0.027  0.505 0.447  0.729 0.825 
3 0.444 0.510  0.360 0.444  0.467 0.540 
4 0.974 0.783  0.724 0.971  0.439 0.902 
5 0.308 0.383  0.686 0.940  0.424 0.119 
6 0.138 0.505  0.907 0.103  0.300 0.891 
7 0.710 0.956  0.202 0.407  0.792 0.506 
8 0.031 0.552  0.229 0.573  0.407 0.688 
9 0.682 0.990  0.276 0.075  0.269 0.543 
10 0.382 0.933  0.038 0.559  0.746 0.511 
11 0.043 0.918  0.101 0.290  0.584 0.822 
12 0.895 0.036  0.207 0.966  0.486 0.533 
13 0.290 0.872  0.902 0.934  0.877 0.155 
14 0.859 0.568  0.428 0.027  0.136 0.265 
15 0.290 0.420  0.915 0.465  0.532 0.059 
16 0.155 0.922  0.036 0.577  0.545 0.336 

Answer 2

Oczywiście możesz, ale nie powinieneś. Crc32 słabo rozprowadza bity wejściowe do skrótu. Z pewnością nie powinno być nigdy używane jako mieszanie jednokierunkowe, ponieważ nie jest nim. Bardzo łatwo jest zmodyfikować wiadomość, aby wyprodukować określony kod.

Użyj algorytmu wyznaczania wartości skrótu zaprojektowanego do tego celu, jaki masz na myśli, cokolwiek to jest.

Answer 3

nie wiem dlaczego Mark Adler powiedział, że „CRC32 słabo dystrybuuje bity wejściowe hash” . Nie ma jednego bitu w haśle crc32, który jest dokładnie równy wejściowym bitom. Każdy bit skrótu jest liniową kombinacją bitów wejściowych. Po drugie, crc zawsze równomiernie odwzorowuje tę samą liczbę różnych sekwencji wejściowych na daną wartość skrótu. Na przykład, jeśli masz komunikat o długości 1000 bitów, po crc32 zawsze możesz znaleźć ciągi 2^(1000-32), które dają określoną wartość mieszania, nie więcej, nie mniej.

Jeśli nie potrzebujesz funkcji zabezpieczeń, crc może służyć jako skrót.

Właściwie, myślę, że inne niezabezpieczone funkcje skrótu mogą być prostsze niż crc, jeśli potrzebujesz dłuższego crc, na przykład crc-256.