Wat is een goede hashfunctie? Ik zag veel hash-functies en toepassingen in mijn cursussen over datastructuren op de universiteit, maar ik begreep vooral dat het behoorlijk moeilijk is om een goede hash-functie te maken. Als vuistregel zei mijn professor om botsingen te voorkomen:
function Hash(key)
return key mod PrimeNumber
end
(mod is de %-operator in C en vergelijkbare talen)
waarbij het priemgetal de grootte van de hashtabel is. Ik begrijp dat dit een enigszins goede functie is om botsingen te voorkomen en een snelle, maar hoe kan ik een betere maken? Zijn er betere hash-functies voor snaartoetsen in plaats van numerieke toetsen?
Antwoord 1, autoriteit 100%
Er bestaat niet zoiets als een “goede hashfunctie” voor universele hashes (ed. ja, ik weet dat er zoiets bestaat als “universele hashing”, maar dat bedoelde ik niet). Afhankelijk van de context bepalen verschillende criteria de kwaliteit van een hasj. Twee mensen noemden SHA al. Dit is een cryptografische hash en het is helemaal niet goed voor hashtabellen, wat je waarschijnlijk bedoelt.
Hash-tabellen hebben heel verschillende vereisten. Maar toch, het is moeilijk om universeel een goede hash-functie te vinden, omdat verschillende gegevenstypen verschillende informatie blootleggen die kan worden gehasht. Als vuistregel is het goed om alleinformatie die een type bevat gelijk te beschouwen. Dit is niet altijd gemakkelijk of zelfs mogelijk. Om redenen van statistiek (en dus botsingen) is het ook belangrijk om een goede spreiding te genereren over de probleemruimte, dus alle mogelijke objecten. Dit betekent dat bij het hashen van getallen tussen 100 en 1050 het niet goed is om het meest significante cijfer een grote rol te laten spelen in de hash, want voor ~ 90% van de objecten zal dit cijfer 0 zijn. Het is veel belangrijker om de laatste drie te laten cijfers bepalen de hash.
Evenzo is het belangrijk om bij het hashen van strings alle karakters in overweging te nemen, behalve wanneer van tevoren bekend is dat de eerste drie karakters van alle strings hetzelfde zullen zijn; deze in overweging nemen is dan zonde.
Dit is eigenlijk een van de gevallen waarin ik adviseer om te lezen wat Knuth te zeggen heeft in The Art of Computer Programming, vol. 3. Een ander goed boek is Julienne Walker’s The Art of Hashing.
Antwoord 2, autoriteit 74%
Voor het doen van “normale” hashtabel-lookups op vrijwel alle soorten gegevens – deze van Paul Hsieh is de beste die ik ooit heb gebruikt.
http://www.azillionmonkeys.com/qed/hash.html
Als je cryptografisch veilig of iets anders geavanceerder belangrijk vindt, dan is YMMV. Als je gewoon een snelle hash-functie voor algemene doeleinden wilt voor het opzoeken van een hashtabel, dan is dit wat je zoekt.
Antwoord 3, autoriteit 19%
Er zijn twee belangrijke doelen van hashing-functies:
- om gegevenspunten uniform in n bits te verdelen.
- om de invoergegevens veilig te identificeren.
Het is onmogelijk om een hash aan te bevelen zonder te weten waarvoor je het gebruikt.
Als je gewoon een hash-tabel in een programma maakt, hoef je je geen zorgen te maken over hoe omkeerbaar of hackbaar het algoritme is… SHA-1 of AES is hiervoor helemaal niet nodig, je zou beter af met een variant van FNV. FNV bereikt een betere spreiding (en dus minder botsingen) dan een eenvoudige prime-mod zoals je zei, en het is beter aanpasbaar aan verschillende invoerformaten.
Als je de hashes gebruikt om openbare informatie te verbergen en te verifiëren (zoals het hashen van een wachtwoord of een document), dan moet je een van de belangrijkste hash-algoritmen gebruiken die door het publiek zijn gecontroleerd. De Hash Function Loungeis een goede plek om te beginnen.
Antwoord 4, autoriteit 13%
Dit is een voorbeeld van een goede en ook een voorbeeld van waarom je er nooit een zou willen schrijven.
Het is een Fowler / Noll / Vo (FNV) Hash die zowel geniaal in computerwetenschappen als pure voodoo is:
unsigned fnv_hash_1a_32 ( void *key, int len ) {
unsigned char *p = key;
unsigned h = 0x811c9dc5;
int i;
for ( i = 0; i < len; i++ )
h = ( h ^ p[i] ) * 0x01000193;
return h;
}
unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
unsigned char *p = key;
unsigned long long h = 0xcbf29ce484222325ULL;
int i;
for ( i = 0; i < len; i++ )
h = ( h ^ p[i] ) * 0x100000001b3ULL;
return h;
}
Bewerken:
- Landon Curt Noll beveelt op zijn sitehet FVN-1A-algoritme aan het originele FVN-1-algoritme: het verbeterde algoritme verspreidt de laatste byte in de hash beter. Ik heb het algoritme dienovereenkomstig aangepast.
Antwoord 5, autoriteit 8%
Ik zou zeggen dat de belangrijkste vuistregel is om niet zelf te rollen. Probeer iets te gebruiken dat grondig is getest, bijvoorbeeld SHA-1 of iets dergelijks.
Antwoord 6, autoriteit 2%
Een goede hashfunctie heeft de volgende eigenschappen:
-
Gegeven een hash van een bericht is het rekenkundig onhaalbaar voor een aanvaller om een ander bericht te vinden zodat hun hashes identiek zijn.
-
Gegeven een paar berichten, m’ en m, is het rekenkundig onhaalbaar om er twee te vinden zodat h(m) = h(m’)
De twee gevallen zijn niethetzelfde. In het eerste geval is er een reeds bestaande hash waarvoor u een botsing probeert te vinden. In het tweede geval probeert u elketwee berichten te vinden die botsen. De tweede taak is aanzienlijk eenvoudiger vanwege de verjaardagsparadox.
Als prestaties niet zo’n groot probleem zijn, moet u altijd een veilige hashfunctie gebruiken. Er zijn zeer slimme aanvallen die kunnen worden uitgevoerd door botsingen in een hash te forceren. Als je vanaf het begin iets sterks gebruikt, beveilig je jezelf hiertegen.
Gebruik geen MD5 of SHA-1 in nieuwe ontwerpen. De meeste cryptografen, waaronder ik, zouden ze als kapot beschouwen. De belangrijkste bron van zwakte in beide ontwerpen is dat de tweede eigenschap, die ik hierboven heb geschetst, niet geldt voor deze constructies. Als een aanvaller twee berichten kan genereren, m en m’, die beide naar dezelfde waarde hashen, kunnen ze deze berichten tegen je gebruiken. SHA-1 en MD5 hebben ook last van aanvallen met berichtextensies, die uw toepassing dodelijk kunnen verzwakken als u niet oppast.
Een modernere hasj zoals Whirpool is een betere keuze. Het heeft geen last van deze berichtextensie-aanvallen en gebruikt dezelfde wiskunde als AES gebruikt om de beveiliging tegen een verscheidenheid aan aanvallen te bewijzen.
Hopelijk helpt dat!
Antwoord 7, autoriteit 2%
Wat je hier zegt, is dat je er een wilt hebben die botsingsweerstand heeft. Probeer SHA-2 te gebruiken. Of probeer een (goed) blokcijfer in een eenrichtingscompressiefunctie (nooit eerder geprobeerd), zoals AES in Miyaguchi-Preenel-modus. Het probleem daarmee is dat je moet:
1) een infuus hebben. Probeer de eerste 256 bits van de fractionele delen van de constante van Khinchin of iets dergelijks te gebruiken.
2) een opvulschema hebben. Eenvoudig. Haal het uit een hasj zoals MD5 of SHA-3 (Keccak [spreek uit als ‘ket-chak’]).
Als je niet om de beveiliging geeft (een paar anderen zeiden dit), kijk dan naar FNV of lookup2 van Bob Jenkins (eigenlijk ben ik de eerste die lookup aanbeveelt2) Probeer ook MurmurHash, het is snel (controleer dit: .16 cpb ).
Antwoord 8, autoriteit 2%
Een goede hashfunctie zou moeten
- wees bijectief om, waar mogelijk, geen informatie te verliezen en zorg voor de minste botsingen
- zoveel en zo gelijkmatig mogelijk cascade, d.w.z. elk invoerbit moet elk uitvoerbit omdraaien met een kans van 0,5 en zonder duidelijke patronen.
- indien gebruikt in een cryptografische context, zou er geen efficiënte manier moeten zijn om het om te keren.
Een priemgetalmodulus voldoet aan geen van deze punten. Het is gewoon onvoldoende. Het is vaak beter dan niets, maar het is niet eens snel. Vermenigvuldigen met een geheel getal zonder teken en een macht-van-twee modulus nemen, verdeelt de waarden net zo goed, dat is helemaal niet goed, maar met slechts ongeveer 2 cpu-cycli is het veel sneller dan de 15 tot 40 die een priemmodulus nodig heeft ( ja deling van gehele getallen is echt zo traag).
Om een hash-functie te creëren die snel is en de waarden goed verdeelt, is de beste optie om deze samen te stellen uit snelle permutaties met mindere kwaliteiten zoals ze deden met PCGvoor het genereren van willekeurige getallen.
Nuttige permutaties zijn onder andere:
- vermenigvuldigen met een oneven geheel getal
- binaire rotaties
- xorshift
Volgens dit recept kunnen we onze eigen hashfunctiemaken of we nemen splitmixdie is getest en goed wordt geaccepteerd.
Als cryptografische kwaliteiten nodig zijn, raad ik ten zeerste aan om een functie van de sha-familie te gebruiken, die goed is getest en gestandaardiseerd, maar voor educatieve doeleinden zou je er zo een maken:
Eerst neem je een goede niet-cryptografische hashfunctie, dan pas je een eenrichtingsfunctie toe zoals machtsverheffing op een priemveld of kvele toepassingen van (n*(n+1)/2) mod 2^kafgewisseld met een xorshift wanneer khet aantal bits is in de resulterende hash.
Antwoord 9
Ik raad het SMhasher GitHub-project https://github.com/rurban/smhasherten zeerste aan is een testsuite voor hashfuncties. De snelste state-of-the-art niet-cryptografische hash-functies zonder bekende kwaliteitsproblemen worden hier vermeld: https: //github.com/rurban/smhasher#summary.