Który algorytm mieszania jest najlepszy dla wyjątkowości i szybkości? Przykłady (dobrych) zastosowań obejmują słowniki skrótów.

Wiem, że istnieją rzeczy takie jak SHA-256 i tym podobne, ale te algorytmy są zaprojektowane tak, aby były bezpieczne , co zwykle oznacza, że ​​są wolniejsze niż algorytmy mniej unikalne . Chcę algorytmu skrótu zaprojektowanego tak, aby był szybki, ale pozostać dość unikalny, aby uniknąć kolizji.

Testowałem różne algorytmy, mierząc prędkość i liczbę kolizji.

Użyłem trzech różnych zestawów kluczy:

• Lista 216 553 angielskich słów (małymi literami)
• Liczby "1"do "216553"(pomyśl o kodach pocztowych i o tym , jak słaby hash usunął msn.com )
• 216 553 „losowych” (tj. Identyfikator UUID typu 4 ) GUID

Dla każdego korpusu rejestrowano liczbę kolizji i średni czas haszowania.

Testowałem:

• DJB2
• DJB2a (wariant wykorzystujący xorzamiast +)
• FNV-1 (32-bit)
• FNV-1a (32-bit)
• SDBM
• CRC32
• Murmur2 (32-bit)
• SuperFastHash

Wyniki

Każdy wynik zawiera średni czas mieszania i liczbę kolizji

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

Uwagi :

• Algorytm LoseLose (gdzie hash = hash znak +) jest naprawdę okropne . Wszystko zderza się w tych samych 1375 wiadrach
• SuperFastHash jest szybki, a rzeczy wyglądają na całkiem rozproszone; na mój boże, liczba kolizji. Mam nadzieję, że facet, który to przeportował, coś nie tak; jest całkiem źle
• CRC32 jest całkiem niezły . Wolniej i tablica odnośników 1k

Czy faktycznie dochodzi do kolizji?

Tak. Zacząłem pisać mój program testowy, aby sprawdzić, czy rzeczywiście występują kolizje skrótów - i nie są to tylko teoretyczne konstrukcje. Rzeczywiście się zdarzają:

Zderzenia FNV-1

• creamwove koliduje z quists

Zderzenia FNV-1a

• costarring koliduje z liquid
• declinate koliduje z macallums
• altarage koliduje z zinke
• altarages koliduje z zinkes

Kolizje Murmur2

• cataract koliduje z periti
• roquette koliduje z skivie
• shawl koliduje z stormbound
• dowlases koliduje z tramontane
• cricketings koliduje z twanger
• longans koliduje z whigs

Zderzenia DJB2

• hetairas koliduje z mentioner
• heliotropes koliduje z neurospora
• depravement koliduje z serafins
• stylist koliduje z subgenera
• joyful koliduje z synaphea
• redescribed koliduje z urites
• dram koliduje z vivency

Zderzenia DJB2a

• haggadot koliduje z loathsomenesses
• adorablenesses koliduje z rentability
• playwright koliduje z snush
• playwrighting koliduje z snushing
• treponematoses koliduje z waterbeds

Zderzenia CRC32

• codding koliduje z gnu
• exhibiters koliduje z schlager

Kolizje SuperFastHash

• dahabiah koliduje z drapability
• encharm koliduje z enclave
• grahams koliduje z gramary
• ... snip 79 kolizji ...
• night koliduje z vigil
• nights koliduje z vigils
• finks koliduje z vinic

Randomnessification

Inną subiektywną miarą jest losowe rozmieszczenie skrótów. Odwzorowanie powstałych tabel skrótów pokazuje, jak równomiernie dane są rozmieszczone. Wszystkie funkcje skrótu wykazują dobry rozkład podczas liniowego mapowania tabeli:

Lub jako mapa Hilberta ( XKCD jest zawsze odpowiedni ):

Z wyjątkiem gdy mieszania ciągów numer ( "1", "2", ..., "216553") (na przykład kody pocztowe ), gdzie wzorce zaczynają się pojawiać w większości algorytmów mieszaja:

SDBM :

DJB2a :

FNV-1 :

Wszystkie oprócz FNV-1a , które nadal wyglądają dla mnie dość losowo:

W rzeczywistości Murmur2 wydaje się mieć jeszcze lepszą losowość Numbersniż FNV-1a:

Kiedy patrzę na FNV-1amapę „liczbową”, myślę, że widzę subtelne pionowe wzory. Dzięki Murmurowi nie widzę żadnych wzorów. Co myślisz?

Dodatek *w tabeli wskazuje, jak zła jest losowość. Z FNV-1abycia najlepszym, a DJB2xbędąc najgorsze:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

Pierwotnie napisałem ten program, aby zdecydować, czy w ogóle muszę się martwić o kolizje: tak.

A potem okazało się, że funkcje haszujące były wystarczająco losowe.

Algorytm FNV-1a

Skrót FNV1 występuje w wariantach, które zwracają skróty 32, 64, 128, 256, 512 i 1024 bitów.

Algorytm FNV-1a jest:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Gdzie stałe FNV_offset_basisi FNV_primezależą od żądanego rozmiaru zwracanej wartości skrótu:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Szczegółowe informacje można znaleźć na głównej stronie FNV .

Wszystkie moje wyniki dotyczą wariantu 32-bitowego.

FNV-1 lepszy niż FNV-1a?

Nie. FNV-1a jest lepszy. Podczas używania angielskiego słowa corpus doszło do większej liczby kolizji z FNV-1a:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Teraz porównaj małe i wielkie litery:

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

W tym przypadku FNV-1a nie jest „400%” gorszy niż FN-1, tylko 20% gorzej.

Myślę, że ważniejsze jest to, że istnieją dwie klasy algorytmów, jeśli chodzi o kolizje:

• rzadkie kolizje : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
• typowe kolizje : SuperFastHash, Loselose

A potem jest to, jak równomiernie rozłożone są skróty:

• znakomita dystrybucja: Murmur2, FNV-1a, SuperFastHas
• doskonała dystrybucja: FNV-1
• dobra dystrybucja: SDBM, DJB2, DJB2a
• okropna dystrybucja: Loselose

Aktualizacja

Szmer? Jasne, czemu nie

Aktualizacja

@ whatshisname zastanawiał się, jak będzie działać CRC32 , dodał liczby do tabeli.

CRC32 jest całkiem niezły . Mało kolizji, ale wolniej, i narzut 1-krotnej tabeli odnośników.

Zniszcz wszystkie błędne informacje o dystrybucji CRC - moje złe

Do dzisiaj miałem używać FNV-1a jako mojego de facto algorytmu haszującego tablicę skrótów. Ale teraz przełączam się na Murmur2:

• Szybciej
• Lepsza losowość wszystkich klas danych wejściowych

I naprawdę, naprawdę mam nadzieję, że coś jest nie tak z SuperFastHashalgorytmem, który znalazłem ; szkoda być popularnym.

Aktualizacja: Od głównej MurmurHash3 w Google :

(1) - SuperFastHash ma bardzo słabe właściwości kolizji, które zostały udokumentowane gdzie indziej.

Myślę, że to nie tylko ja.

Aktualizacja: Zrozumiałem, dlaczego Murmurjest szybszy od innych. MurmurHash2 działa na czterech bajtach jednocześnie. Większość algorytmów jest bajt po bajcie :

for each octet in Key
   AddTheOctetToTheHash

Oznacza to, że gdy klucze stają się dłuższe, Murmur ma szansę zabłysnąć.

Aktualizacja

Identyfikatory GUID są zaprojektowane tak, aby były unikalne, a nie losowe

Terminowy post Raymonda Chena potwierdza fakt, że „losowe” identyfikatory GUID nie są przeznaczone do ich losowości. One lub ich część nie są odpowiednie jako klucz skrótu:

Nawet algorytm GUID w wersji 4 nie jest gwarantowany jako nieprzewidywalny, ponieważ algorytm nie określa jakości generatora liczb losowych. Artykuł w Wikipedii dotyczący GUID zawiera podstawowe badania, które sugerują, że przyszłe i poprzednie GUID można przewidzieć na podstawie wiedzy o stanie generatora liczb losowych, ponieważ generator nie jest silny kryptograficznie.

Losowość to nie to samo, co unikanie kolizji; dlatego błędem byłoby wymyślić własny algorytm „mieszający”, przyjmując pewien podzbiór „losowego” przewodnika:

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Uwaga : Znów wstawiłem „przypadkowy GUID” w cudzysłowie, ponieważ jest to „losowy” wariant GUID. Bardziej dokładny opis byłby Type 4 UUID. Ale nikt nie wie, jaki jest typ 4 lub typy 1, 3 i 5. Łatwiej więc nazwać je „losowymi” identyfikatorami GUID.

Lustra wszystkich angielskich słów

• https://web.archive.org/web/20070221060514/http://www.sitopreferito.it/html/all_english_words.html
• https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8/view?usp=sharing

Jeśli chcesz utworzyć mapę skrótów z niezmiennego słownika, możesz rozważyć idealne haszowanie https://en.wikipedia.org/wiki/Perfect_hash_function - podczas budowy funkcji skrótu i ​​tabeli skrótów możesz zagwarantować, dla danego zestawu danych, że nie będzie kolizji.

Oto lista funkcji skrótu, ale krótka wersja to:

Jeśli chcesz po prostu mieć dobrą funkcję skrótu i ​​nie możesz się doczekać, djb2to jedna z najlepszych funkcji skrótu, jakie znam. Ma doskonałą dystrybucję i szybkość dla wielu różnych zestawów kluczy i rozmiarów tabel

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

CityHash firmy Google to algorytm, którego szukasz. Nie nadaje się do kryptografii, ale jest dobry do generowania unikatowych skrótów.

Przeczytaj blog, aby uzyskać więcej informacji, a kod jest dostępny tutaj .

CityHash jest napisany w C ++. Jest też zwykły port C .

O obsłudze 32-bitowej:

Wszystkie funkcje CityHash są dostrojone dla procesorów 64-bitowych. To powiedziawszy, będą działać (z wyjątkiem nowych, które używają SSE4.2) w kodzie 32-bitowym. Nie będą jednak bardzo szybkie. Możesz użyć Murmur lub czegoś innego w 32-bitowym kodzie.

Sporządziłem krótkie porównanie różnych algorytmów haszujących podczas haszowania plików.

Poszczególne wykresy różnią się tylko nieznacznie metodą odczytu i można je tutaj zignorować, ponieważ wszystkie pliki zostały zapisane w pliku tmpfs. Dlatego, jeśli zastanawiasz się, test nie był związany z IO.

• Skala liniowa
• Skala logarytmiczna

Algorytmy obejmują: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Wnioski:

• Niekryptograficzne funkcje skrótu, takie jak Murmur3, Cityhash i Spooky, są dość blisko siebie. Należy zauważyć, że Cityhash może być szybszy na procesorach z CRCinstrukcją SSE 4.2s , których mój procesor nie ma. SpookyHash był w moim przypadku zawsze trochę przed CityHash.
• Wydaje się, że MD5 stanowi dobry kompromis podczas korzystania z funkcji skrótu kryptograficznego, chociaż SHA256 może być bardziej bezpieczny w przypadku luk MD5 i SHA1 w przypadku kolizji .
• Złożoność wszystkich algorytmów jest liniowa - co naprawdę nie jest zaskakujące, ponieważ działają one blokowo. (Chciałem zobaczyć, czy metoda odczytu ma znaczenie, więc możesz po prostu porównać wartości skrajnie prawe).
• SHA256 był wolniejszy niż SHA512.
• Nie badałem losowości funkcji skrótu. Ale oto dobre porównanie funkcji skrótu, których brakuje w odpowiedzi Iana Boydsa . Wskazuje to, że CityHash ma pewne problemy w sprawach narożnych.

Źródło użyte do wykresów:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (przepraszam za brzydki kod)

Algorytmy SHA (w tym SHA-256) są zaprojektowane tak, aby były szybkie .

W rzeczywistości ich prędkość może czasem stanowić problem. W szczególności powszechną techniką przechowywania tokenu pochodnego hasła jest uruchomienie standardowego algorytmu szybkiego hashowania 10 000 razy (przechowywanie skrótu skrótu skrótu skrótu ... hasła).

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

Wynik:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

Wiem, że istnieją rzeczy takie jak SHA-256 i tym podobne, ale te algorytmy są zaprojektowane tak, aby były bezpieczne , co zwykle oznacza, że ​​są wolniejsze niż algorytmy mniej unikalne .

Założenie, że kryptograficzne funkcje skrótu są bardziej unikalne, jest błędne i w rzeczywistości można wykazać, że w praktyce często jest ono cofane. Wprawdzie:

1. Funkcje skrótu kryptograficznego idealnie powinny być nierozróżnialne od przypadkowych ;
2. Ale w przypadku niekryptograficznych funkcji skrótu pożądane jest, aby korzystały one z interakcji z prawdopodobnymi danymi wejściowymi .

Co oznacza, że ​​nieszyfrowa funkcja skrótu może mieć mniej kolizji niż kryptograficzna dla „dobrego” zestawu danych - zestawów danych, dla których została zaprojektowana.

Możemy to właściwie wykazać za pomocą danych zawartych w odpowiedzi Iana Boyda i odrobiny matematyki: problem urodzinowy . Wzór na oczekiwaną liczbę kolidujących par, jeśli wybierzesz nlosowo liczby całkowite ze zbioru, [1, d]jest następujący (wzięty z Wikipedii):

n - d + d * ((d - 1) / d)^n

Podłączając n= 216 553 i d= 2 ^ 32 otrzymujemy około 5,5 oczekiwanych kolizji . Testy Iana przeważnie pokazują wyniki w tej okolicy, ale z jednym dramatycznym wyjątkiem: większość funkcji uzyskała zerową kolizję w kolejnych testach liczbowych. Prawdopodobieństwo losowego wyboru 216 553 liczb 32-bitowych i uzyskania zerowych kolizji wynosi około 0,43%. I to tylko dla jednej funkcji - tutaj mamy pięć różnych rodzin funkcji skrótu z zerowymi kolizjami!

Widzimy więc, że skróty, które testował Ian, działają korzystnie z zestawem danych z kolejnymi liczbami - tzn. Rozpraszają minimalnie różne dane wejściowe szerzej niż idealna funkcja skrótu kryptograficznego. (Uwaga dodatkowa: oznacza to, że graficzną ocenę Iana, że ​​FNV-1a i MurmurHash2 „wyglądają mu losowo” w zestawie danych liczbowych, można odrzucić na podstawie jego własnych danych. Zero zderzeń na zestawie danych tego rozmiaru dla obu funkcji skrótu, jest uderzająco nielosowy!)

Nie jest to niespodzianką, ponieważ jest to pożądane zachowanie dla wielu zastosowań funkcji skrótu. Na przykład klucze tabeli skrótów są często bardzo podobne; Odpowiedź Iana wspomina o problemie, jaki MSN miał kiedyś z tablicami skrótu kodów pocztowych . Jest to zastosowanie, w którym unikanie kolizji na prawdopodobnych danych wejściowych wygrywa z zachowaniem losowym.

Innym pouczającym porównaniem tutaj jest kontrast w celach projektowych między CRC a kryptograficznymi funkcjami skrótu:

• CRC jest przeznaczony do wychwytywania błędów wynikających z głośnych kanałów komunikacyjnych , które prawdopodobnie będą niewielką liczbą bitów;
• Skrypty kryptograficzne są zaprojektowane do przechwytywania modyfikacji dokonywanych przez złośliwych atakujących , którym przydzielono ograniczone zasoby obliczeniowe, ale dowolnie sprytnie.

Więc dla CRC to kolejny dobry mieć mniej kolizji niż losowo minimalnie różnych wejść. W przypadku skrótów kryptograficznych jest to nie-nie!

Użyj SipHash . Ma wiele pożądanych właściwości:

• Szybki. Zoptymalizowana implementacja zajmuje około 1 cyklu na bajt.

• Bezpieczne. SipHash jest silnym PRF (funkcja pseudolosowa). Oznacza to, że nie można go odróżnić od funkcji losowej (chyba że znasz 128-bitowy tajny klucz). W związku z tym:

  • Nie musisz się martwić, że sondy tabeli skrótów staną się liniowe z powodu kolizji. Dzięki SipHash wiesz , że średnio uzyskasz średnią wydajność, niezależnie od danych wejściowych.

  • Odporność na ataki typu odmowa usługi oparte na haszowaniu.

  • Możesz użyć SipHash (szczególnie wersja ze 128-bitowym wyjściem) jako MAC (Message Authentication Code). Jeśli otrzymasz wiadomość i znacznik SipHash, a znacznik jest taki sam, jak po uruchomieniu SipHash z tajnym kluczem, to wiesz, że ktokolwiek stworzył skrót, był również w posiadaniu twojego tajnego klucza i że ani wiadomość, ani hash został zmieniony od tego czasu.

To zależy od haszowanych danych. Niektóre skróty działają lepiej z określonymi danymi, takimi jak tekst. Niektóre algorytmy mieszające zostały specjalnie zaprojektowane tak, aby były odpowiednie dla określonych danych.

Paul Hsieh kiedyś zrobił szybki skrót . Wymienia kod źródłowy i objaśnienia. Ale już zostało pobite. :)

Java używa tego prostego algorytmu wielokrotnego dodawania i dodawania:

Kod skrótu dla obiektu String jest obliczany jako

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

używając int arytmetyczne, gdzie s[i]jest i -tego postaci napisu, nto długość łańcucha, i ^wskazuje potęgowanie. (Wartość skrótu pustego ciągu wynosi zero).

Prawdopodobnie są o wiele lepsze, ale jest to dość powszechne i wydaje się być dobrym kompromisem między szybkością a wyjątkowością.

Po pierwsze, dlaczego musisz wdrożyć swój własny skrót? W przypadku większości zadań powinieneś uzyskać dobre wyniki ze strukturami danych ze standardowej biblioteki, zakładając, że dostępna jest implementacja (chyba że robisz to tylko dla własnej edukacji).

Jeśli chodzi o rzeczywiste algorytmy mieszające, moim ulubionym jest FNV. 1

Oto przykładowa implementacja 32-bitowej wersji w C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}