it-swarm-eu.dev

Který hashovací algoritmus je nejlepší pro jedinečnost a rychlost?

Který hashovací algoritmus je nejlepší pro jedinečnost a rychlost? Příkladem (dobrého) použití je slovník hash.

Vím, že existují věci jako SHA-256 a podobné, ale tyto algoritmy jsou navrženy tak, aby byly bezpečné , což obvykle znamená, že jsou pomalejší než algoritmy, které jsou méně jedinečné. Chci algoritmus hash navržený tak, aby byl rychlý, ale aby zůstal docela jedinečný, abychom se vyhnuli kolizím.

1444
Earlz

Testoval jsem několik různých algoritmů, měření rychlosti a počtu kolizí.

Použil jsem tři různé sady klíčů:

Pro každý korpus byl zaznamenán počet srážek a průměrná doba strávená hashováním.

Testoval jsem:

Výsledek

Každý výsledek obsahuje průměrnou dobu hash a počet srážek

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

Poznámky :

Dochází ke kolizím?

Ano. Začal jsem psát svůj testovací program, abych zjistil, zda ke kolizím hashů skutečně došlo - a nejde jen o teoretický konstrukt. Stávají se skutečně:

FNV-1 srážky

  • creamwove srazí s quists

srážky FNV-1a

  • costarring srazí s liquid
  • declinate srazí s macallums
  • altarage srazí s zinke
  • altarages srazí s zinkes

kolize Murmur2

  • cataract srazí s periti
  • roquette srazí s skivie
  • shawl srazí s stormbound
  • dowlases srazí s tramontane
  • cricketings srazí s twanger
  • longans srazí s whigs

srážky DJB2

  • hetairas srazí s mentioner
  • heliotropes srazí s neurospora
  • depravement srazí s serafins
  • stylist srazí s subgenera
  • joyful srazí s synaphea
  • redescribed srazí s urites
  • dram srazí s vivency

srážky DJB2a

  • haggadot srazí s loathsomenesses
  • adorablenesses srazí s rentability
  • playwright srazí s snush
  • playwrighting srazí s snushing
  • treponematoses srazí s waterbeds

kolize CRC32

  • codding srazí s gnu
  • exhibiters srazí s schlager

kolize SuperFastHash

  • dahabiah srazí s drapability
  • encharm srazí s enclave
  • grahams srazí s gramary
  • ... odstřihněte 79 kolizí ...
  • night srazí s vigil
  • nights srazí s vigils
  • finks srazí s vinic

Náhodnost

Dalším subjektivním měřítkem je, jak náhodně jsou hash rozděleny. Mapování výsledných tabulek ukazuje, jak rovnoměrně jsou data distribuována. Všechny hašovací funkce vykazují dobré rozdělení při lineárním mapování tabulky:

Enter image description here

Nebo jako Hilbertova mapa ( XKCD je vždy relevantní ):

Enter image description here

S výjimkou hashovacích řetězců čísel ("1", "2", ..., "216553") (například PSČ ), kde se ve většině hashovacích algoritmů začínají objevovat vzorce:

[~ # ~] sdbm [~ # ~] :

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

Všechny kromě FNV-1a , které mi stále vypadají celkem náhodně:

Enter image description here

Zdá se, že Murmur2 má ještě lepší náhodnost s Numbers než FNV-1a:

Enter image description here

Když se podívám na FNV-1a "number" map, I think Vidím jemné vertikální vzory. S Murmurem nevidím vůbec žádné vzory. Co si myslíte?


Extra * v tabulce označuje, jak špatná je náhodnost. S FNV-1a je nejlepší a DJB2x je nejhorší:

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

Původně jsem napsal tento program, abych se rozhodl, jestli jsem dokonce musel worry o kolizích: ano.

A pak se ukázalo, že hashovací funkce byly dostatečně náhodné.

Algoritmus FNV-1a

Hash FNV1 přichází ve variantách, které vracejí 32, 64, 128, 256, 512 a 1024 bitů hashe.

FNV-1a algoritmus je:

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

Kde konstanty FNV_offset_basis a FNV_prime záleží na požadované velikosti hash:

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

Podrobnosti viz hlavní stránka FNV .

Všechny mé výsledky jsou u 32bitové varianty.

FNV-1 lepší než FNV-1a?

Ne. FNV-1a je všude lepší. Při použití korpusu anglického slova došlo k dalším kolizím s FNV-1a:

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

Nyní porovnejte malá a velká písmena:

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

V tomto případě FNV-1a není "400%" horší než FN-1, pouze o 20% horší.

Myslím, že důležitější s sebou je, že existují dvě třídy algoritmů, pokud jde o kolize:

  • vzácné srážky : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • běžné srážky : SuperFastHash, Loselose

A pak je tu, jak rovnoměrně jsou hashe:

  • vynikající distribuce: Murmur2, FNV-1a, SuperFastHas
  • vynikající distribuce: FNV-1
  • dobrá distribuce: SDBM, DJB2, DJB2a
  • hrozné rozdělení: Loselose

Aktualizace

Mumlání? Jistě, proč ne


Aktualizace

@whatshisname přemýšlel, jak by CRC32 provedl přidaná čísla do tabulky.

CRC32 je celkem dobrá . Několik kolizí, ale pomalejší, a režie 1k tabulky vyhledávání.

Vystřihněte všechny chybné informace o distribuci CRC - můj špatný


Až do dneška jsem měl v úmyslu používat FNV-1a jako můj de facto hash-hashovací algoritmus tabulky. Ale teď přecházím na Murmur2:

  • Rychleji
  • Lepší randomnessification všech tříd vstupů

A opravdu, opravdu doufám, že je něco špatného s SuperFastHash algoritmus, který jsem našel ; je příliš špatné na to, aby byl tak populární, jak je.

Aktualizace: Z domovská stránka MurmurHash3 na Googl :

(1) - SuperFastHash má velmi špatné kolizní vlastnosti, které byly dokumentovány jinde.

Takže to nejsem jen já.

Aktualizace: Uvědomil jsem si, proč je Murmur rychlejší než ostatní. MurmurHash2 pracuje na čtyřech bytech najednou. Většina algoritmů je byte byte :

for each octet in Key
   AddTheOctetToTheHash

To znamená, že jak se klíče prodlužují, Murmur dostane svou šanci září.


Aktualizace

GUID jsou navrženy tak, aby byly jedinečné, nikoli náhodné

Včasný příspěvek od Raymonda Chena opakuje skutečnost, že GUID "random" GUID nejsou určeny pro jejich náhodnost. Oni nebo jejich podmnožina jsou nevhodní jako hashovací klíč:

Ani u verze 4 GUID algoritmus není zaručeno, že bude nepředvídatelný, protože tento algoritmus nespecifikuje kvalitu generátoru náhodných čísel. Článek Wikipedia pro GUID obsahuje primární výzkum, který navrhuje , že budoucí a předchozí GUID lze předpovídat na základě znalosti stavu generátoru náhodných čísel, protože generátor není kryptograficky silný.

Náhodnost není totéž jako vyhýbání se kolizi; což je důvod, proč by bylo chybou pokusit se vymyslet svůj vlastní „hashovací“ algoritmus tím, že vezme nějakou podskupinu „náhodného“ průvodce:

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);
}

Poznámka : Znovu jsem v uvozovkách uvedl "náhodné GUID" , protože se jedná o "náhodnou" variantu GUID. Přesnější popis by byl Type 4 UUID. Ale nikdo neví, co je typu 4 nebo typu 1, 3 a 5. Takže je to jednodušší nazvat je „náhodnými“ GUID.

Všechna anglická slova zrcadla

2530
Ian Boyd

Pokud chcete vytvořit hašovací mapu z neměnného slovníku, můžete zvážit dokonalé hašování https://en.wikipedia.org/wiki/Perfect_hash_function - během konstrukce hašovací funkce a hash tabulka, můžete pro daný datový soubor zaručit, že nedojde ke kolizím.

61
Damien

Zde je seznam hash funkcí, ale krátká verze je:

Pokud chcete mít pouze hashovací funkci a nemůžete čekat, djb2 je jedna z nejlepších hašovacích funkcí řetězce, které znám. Má vynikající distribuci a rychlost na mnoha různých sadách klíčů a velikostí stolů

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;
}
34
Dean Harding

CityHash od Google je algoritmus, který hledáte. Není to dobré pro kryptografii, ale je dobré pro generování jedinečných hashe.

Přečtěte si blog pro více informací a kód je k dispozici zde .

CityHash je napsán v C++. K dispozici je také obyčejný port C .

Asi 32bitová podpora:

Všechny funkce CityHash jsou vyladěny pro 64bitové procesory. To znamená, že budou spuštěny (s výjimkou nových, které používají SSE4.2) v 32bitovém kódu. Nebudou však příliš rychlé. Možná budete chtít použít Murmur nebo něco jiného v 32bitovém kódu.

29
Vipin Parakkat

Při hašování souborů jsem vykreslil krátké porovnání rychlosti různých algoritmů hashování.

Jednotlivé grafy se liší jen mírně ve způsobu čtení a lze je zde ignorovat, protože všechny soubory byly uloženy v tmpfs. Z tohoto důvodu nebyla referenční hodnota vázána na IO, pokud vás zajímá.

Algoritmy zahrnují: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Závěry:

  • Nekryptografické hashovací funkce jako Murmur3, Cityhash a Spooky jsou dosti blízko u sebe. Je třeba si uvědomit, že Cityhash může být na procesorech rychlejší s instrukcí SSE 4,2s CRC, kterou můj procesor nemá. SpookyHash byl v mém případě vždy trochu před CityHash).
  • MD5 se zdá být dobrým kompromisem při používání kryptografických hašovacích funkcí, ačkoli SHA256 může být bezpečnější pro zranitelnost kolizí MD5 a SHA1.
  • Složitost všech algoritmů je lineární - což není překvapivé, protože pracují blokově. (Chtěl jsem zjistit, jestli metoda čtení něco nezmění, takže si můžete porovnat hodnoty úplně vpravo).
  • SHA256 byl pomalejší než SHA512.
  • Nezkoumal jsem náhodnost hašovacích funkcí. Ale zde je dobré srovnání hašovacích funkcí, které chybí v Ian Boyds odpověď . To poukazuje na to, že CityHash má některé problémy v rohových případech.

Zdroj použitý pro grafy:

21
Sahib

Algoritmy SHA (včetně SHA-256)) jsou navrženy, aby byly rychlé.

Ve skutečnosti může být jejich rychlost někdy problém. Zejména je běžnou technikou ukládání tokenu odvozeného od hesla spuštění standardního algoritmu rychlého hašování 10 000krát (ukládání hash hash hash hash hash hesla ...).

#!/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

Výstup:

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

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)
18
yfeldblum

Vím, že existují věci jako SHA-256 a podobné, ale tyto algoritmy jsou navrženy tak, aby byly bezpečné , což obvykle znamená, že jsou pomalejší než algoritmy, které jsou méně jedinečné.

Předpoklad, že kryptografické hashovací funkce jsou jedinečnější, je chybný a ve skutečnosti se v praxi může ukázat jako často pozadu. V pravdě:

  1. Kryptografické hashovací funkce by měly být nerozeznatelné od náhodných ;
  2. Ale s nekryptografickými hashovacími funkcemi je žádoucí, aby interagovaly příznivě s pravděpodobnými vstupy .

Což znamená, že nekryptografická hashovací funkce může mít méně kolizí než kryptografická pro „dobrou“ datovou sadu - datové sady, pro které byla navržena .

Ve skutečnosti to dokážeme ukázat na datech v odpovědi Iana Boyda a trochu matematiky: Narozeninový problém . Vzorec pro očekávaný počet kolizních párů, pokud náhodně vyberete n celá čísla z množiny [1, d] je toto (převzato z Wikipedie):

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

Připojením n = 216,553 a d = 2 ^ 32 dostaneme 5,5 očekávaných kolizí . Ianovy testy většinou ukazují výsledky v okolí, ale s jednou dramatickou výjimkou: většina funkcí získala nulové kolize v testech po sobě jdoucích čísel. Pravděpodobnost náhodného výběru 216 553 32bitových čísel a dosažení nulové kolize je asi 0,43%. A to je jen pro jednu funkci - zde máme pět různých rodin hashových funkcí s nulovými srážkami!

Tady vidíme, že hashe, které Ian testoval, interagují příznivě s datovým souborem po sobě jdoucích čísel - tj. Rozptylují minimálně odlišné vstupy více široce než ideální kryptografická hashovací funkce. (Vedlejší poznámka: to znamená, že Ianovo grafické posouzení, že FNV-1a a MurmurHash2 „vypadají náhodně“ v souboru údajů o číslech, lze vyvrátit z jeho vlastních dat. Nulové kolize v datovém souboru této velikosti, obě hashovací funkce, je překvapivě nepravda!)

To není překvapením, protože je to žádoucí chování pro mnoho použití hash funkcí. Například klávesy hash tabulky jsou často velmi podobné; Ianova odpověď zmiňuje problém, který kdysi měla MSN s tabulkami hashového kódu ZIP . Toto je použití, kde vyhýbání se kolizi na vstupech pravděpodobně vyhrává nad náhodným chováním.

Další poučné srovnání zde je kontrast v cílech designu mezi CRC a kryptografickými hashovacími funkcemi:

  • CRC je navržen tak, aby zachytil chyby vyplývající z hlučných komunikačních kanálů , které pravděpodobně budou malým počtem bitů převrácení;
  • Crypto hashe jsou navrženy tak, aby zachytily modifikace provedené škodlivými útočníky , kterým jsou přiděleny omezené výpočetní zdroje, ale svévolně hodně chytré.

Pro CRC je tedy opět dobré mít méně kolizí než náhodně při minimálně odlišných vstupech. U kryptografických hashů je to ne-ne!

15
sacundim

Použijte SipHash . Má mnoho žádoucích vlastností:

  • Rychlý Optimalizovaná implementace trvá přibližně 1 cyklus na byte.

  • Secure. SipHash je silný PRF (pseudonáhodná funkce). To znamená, že je nerozeznatelné od náhodné funkce (pokud neznáte 128bitový tajný klíč). Proto:

    • Není třeba se starat o to, aby se vaše hashovací sondy staly lineárním časem kvůli kolizím. Se SipHash víte , že průměrný výkon případu získáte v průměru bez ohledu na vstupy.

    • Imunita proti útokům útoků založeným na hašování.

    • Jako MAC (Message Authentication Code) můžete použít SipHash (zejména verzi se 128bitovým výstupem). Pokud obdržíte zprávu a značku SipHash a značka je stejná jako u spouštění programu SipHash s vaším tajným klíčem, pak víte, že kdokoli vytvořil hash, měl také svůj tajný klíč a že ani zpráva ani hash byly od té doby změněny.

10
Demi

Závisí to na datech, která hashujete. Některé hashování funguje lépe u konkrétních dat, jako je text. Některé hashovací algoritmy byly specificky navrženy tak, aby byly dobré pro konkrétní data.

Paul Hsieh jednou udělal rychlé hash . Uvádí zdrojový kód a vysvětlení. Ale to už bylo porazeno. :)

9
user712092

Java používá this jednoduchý algoritmus násobení a přidávání:

Hašovací kód pro objekt String je počítán jako

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

pomocí int aritmetiky, kde s[i] je i - třetí znak řetězce, n je délka řetězce a ^ označuje exponentiaci. (Hodnota hash prázdného řetězce je nula.)

Pravděpodobně tam jsou mnohem lepší, ale to je docela rozšířené a zdá se, že je to dobrý kompromis mezi rychlostí a jedinečností.

6
biziclop

Zaprvé, proč potřebujete implementovat vlastní hashování? U většiny úkolů byste měli získat dobré výsledky s datovými strukturami ze standardní knihovny za předpokladu, že je k dispozici implementace (pokud to neděláte pouze pro své vlastní vzdělávání).

Pokud jde o skutečné hashovací algoritmy, můj osobní favorit je FNV. 1

Zde je příklad implementace 32bitové verze v jazyce 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;
}
4
user17754