SipHash som öppen hårdvara

Hashtabeller är en av de verkliga arbetshästarna bland datastrukturer. Hashtabeller används bland annat i databaser, i mellanlagring av webbtjänster (webcache), DNS-uppslagningar och inte minst som viktig datastruktur i språk som Perl, Python, PHP, Ruby etc.

Hashtabell där en hashfunktion givet en nyckel skapar index in i tabellen.
Hashtabell där en hashfunktion givet en nyckel skapar index in i tabellen. (Bild från Wikipedi)

En Hashtabell gör det möjligt att givet ett värde (ofta kallad nyckel) direkt få fram ett dataelement. Till skillnad mot exempelvis ett sökträd ger en hashtabell ofta kortare och framförallt konstant tid att lagra och hitta element i strukturen. Detta under förutsättning att inte flera nycklar pekar på samma plats i datastrukturen, ett situation som kallas en kollision. När en kollision uppstår finns det flera strategier för att hantera detta, en är att använda närmaste positionerna i tabellen (uppåt/nedåt om man ser tabellen som en vertikal tabell). Effekten av en sådan strategi är att kollisioner omvandlas till långsam linjär sökning.

En förutsättning för att antalet kollisioner hålls låg är att fördelningen av värden i datastrukturen givet alla möjliga nycklar sker på ett likafördelat sätt. Det vill säga, det är lika stor sannolikhet att en position i tabellen pekas ut som alla andra. Och det som avgör fördelningen i tabellen är hashfunktionen, den funktion som tar en nyckel och räknar ut positionen (även kallat index) i hashtabellen.

Traditionellt har kraven på hashfunktionen varit två:

  1. Den ska ge en likafördelning
  2. Den ska vara snabb

Att den är snabb innebär att den inte kan vara speciellt komplicerad. I min gamla algoritmkursbok, den utmärkta Introduction to Algorihms, är ett av de hashfunktioner som presenteras den här:

Enkel hashfunktion från kursbok.

Enkel hashfunktion från kursbok.

Detta är en enkel och snabb hashfunktion som ger hygglig likafördelning. Nackdelen med den här typen av funktion är att det är enkelt att räkna ut vad en given nyckel ska kompletteras med för att få fram ett givet index. Om en tredje person kan påverka nyckeln in kan denne tvinga fram kollisioner som gör att hashtabellen omvandlas till linjära sökningar som till och med kan sänka en tjänst.

Utslagningsattacker mot hashfunktioner
Ett exempel på detta är den attack på ramverk för webbtjänster som Alexander Klink och Julian Wälde presenterade 2011. Dom kunde visa hur dom med enkel indata kunde sänka kraftiga webbservrar genom att tvinga fram kollisioner i webbplatformens hashtabeller. Författarna demonstrerade fungerande attacker på PHP, ASP.Net, Python, Perl, Java m.m, vilket och ledde fram till utslagningsattacker mot ett stort antal ramverk och applikationer.

Det finns mer avancerade hashfunktioner som försöker kombinera snabbhet, bra likafördelning och samtidigt göra det svårare för den typ av attack som Alexander och Julian visade på. Två av dessa är Cityhash och MurmurHash. Tyvärr har båda dessa funktioner visats sig gå att attackera och räkna ut hur man ska agera för att orsaka en kollision.

Det finns en typ av hashfunktioner som ger ett bra skydd mot attacker av den ovan, och det är kryptografiska hashfunktioner exempelvis MD5 (som dock INTE ska användas) SHA-1 och SHA-256.

Dessa funktioner uppfyller väl kraven på likafördelning och funktionerna ger ett bra skydd mot att tvinga fram kollisioner genom att modifiera nyckeln. Det går helt enkelt inte bestämma vad som skall läggas till nyckeln för att få fram ett givet index (snabbare än att pröva ett enormt antal kombinationer, i fallet SHA-1 är det 2**80 försök). Så vad är då problemet, varför inte byta till en kryptografisk funktion. Prestandan, eller snarare avsaknaden av prestanda.

Kryptografiska hashfunktioner är mycket mer komplicerade än exempelvis Cityhash och består oftast av en funktion som upprepas ett stort antal gånger (kallas iterationer eller rounds). I SHA-1 sker 80 iterationer. Att byta ut hashfunktionerna som använts i exempelvis Python och Perl till SHA-1 anses orealistiskt då det skulle göra hashtabellerna mycket, mycket långsammare och därmed negativt påverka prestandan hos applikationer skrivna i dessa språk

Ett annat problem med de hashfunktioner som använts är att dom är gemensamma för alla instanser. Kan du hitta ett sätt att tvinga fram kollisioner i Cityhash kan du attackera alla system där Cityhash används. Hade hashfunktionen varit unik för varje instans skulle effekten av ett sätt att göra kollisioner blir mycket mindre.

Det vi behöver är alltså en hashfunktion som är:

  1. Mycket snabb, helst inte mycket långsammare än dagens hashfunktioner.
  2. Ger minst lika bra likafördelning
  3. Ger ett starkt skydd mot avsktliga kollisioner
  4. Enkelt går att göra unik för en given instans – program, installation, process

SipHash
En sådan funktion som nyligen presenterades är SipHash, skapad av kryptoexperterna Jean-Philippe Aumasson och Daniel J. Bernstein.

SipHash beter sig mycket som en kryptografisk hashfunktion i det att den iterativt kan beräkna ett värde (kondensat) för ett meddelande genom att tugga i sig meddelandet uppdelat i block med en fix storlek. I SipHash är blocken 64 bitar. Siphash tar även emot en nyckel om 128 bitar som gör beräkningen unik.

Den huvudsakliga operationen i SipHash är SipRound. SipRound består av additioner, logiskt XOR samt bitmässig rotation och dessa operationer appliceras på fyra stycken interna 64-bitars variabler (v0, v1, v2, v3) tillsammans med det givna meddelandeblocket (mi). Figuren nedan visar beräkningskedjan för SipRound:

Beräkningskedjan i SipRound.

Beräkningskedjan i SipRound.

Ringarna med kors är XOR-operationer, kvadraterna är addition och vänsterpilarna är bitmässig rotation. Totalt sker fyra additioner, fyra XOR och fyra rotationer per SipRound.

Att bearbeta ett block sker genom att upprepat applicera ett SipRound ett antal gånger. Efter att alla block har beatbetas sker en avslutande fas där SipRound upprepat applicerat ett antal gånger till. Hur många gånger som SipRound utförs för att bearbeta ett block samt under avslut styr hur säker SipHash är. Skaparna av SipHash har föreslagit Siphash-2-4, vilket innebär två SipRounds för varje block samt fyra SipRounds som avslutning.

Skaparna av SipHash ger i sin artikel som presenterar SipHash motivering till designen hos SipHash, en genomgång av säkerheten samt prestandajämförelser. Enligt skaparna bör SipHash ge ett skydd motsvarande att uttömmande pröva samtliga nycklar till funktionen. Prestandamässigt är SipHash inte mycket långsammare än exempelvis Cityhash och mycket snabbare än MD5. Figuren nedan är från artikeln.

Prestanda för SipHash.

Prestanda för SipHash.

Notera att SipHash prestanda skalar linjärt, till skillnad från MD5 som har en kostsam initieringsfas.

En viktig poäng med SipHash som dess skapare framhåller är att eftersom den har en nyckel och ger kryptografiskt starkt skydd går den även att använda för att beräkna äkthetskoder för meddelanden (Message Authentication Code – MAC) på ett mycket snabbare sätt än exempelvis HMAC. Detta gär SipHash mycket intressant för inbyggda system där äkthetsskydd av meddelanden är mycket viktigt.

Det finns redan i dag ett antal programvaruimplementationer av SipHash och SipHash har även integrerats in i flera projekt projekt bland annat OpenDNS, Perl och Ruby. (Tyvärr har Python ännu inte gjort detta och diskussionen om problemet med kollisioner och hur man vill lösa det i Python är en delvis tråkig läsning.)

Siphash_core
Det som ännu inte funnits är en hårdvaruimplementation av SipHash. Secworks har därför utvecklat en hårdvaruimplementation av SipHash avsedd att integreras i FPGA- eller ASIC-konstruktioner kallad siphash_core. Vår implementation är skriven i relativt konservativ Verilog 2001 och bör vara mycket enkel att integrera. Implementationen är släppt som öppen kod under BSD-licens. Vår implementation av SipHash, siphash_core finns för nedladdning på Gitorious.

Den implementation av siphash_core som finns i dag är en semikompakt lösning där SipRound utförs i fyra steg. I varje steg uppdateras tre eller fyra av tillståndsregistren (v0_reg..v3_reg). Den resursmässigt dyraste operationen är 64-bitars addition och implementationen innehåller två adderare som återanvänds under utförandet av SipRound.

Det skulle gå att göra än en mer kompakt implementation där fler av operationerna använder samma hårdvarurs. En sådan implementation skulle dock knappast ge speciellt mycket bättre prestanda än en programimplementation även på en 16- eller 32-bitars processor.

Det skulle även gå att göra en större implementation där flera av stegen i SipRound utförs i samma cykel. På grund av adderarnas djup är det dock tveksamt om det går att nå speciellt hög klockfrekvens för en sådan lösning. Risken är stor att kostnaden i form av lägre klockfrekvens är större än minskningen i latens.

Vi kommer att testa dessa varianter av implementationer, men känslan just nu är att den version av siphash_core som finns i repot på Gitorious i dag ger bra balans mellan storlek, klockfrekvens och antalet cykler för att processa ett meddelandeblock.

I värsta fallet, för ett meddelande om på exakt 64 bitar krävs det med vår implementation 28 cykler, eller ungefär 3,5 cykler/Byte. Detta kan jämföras med MD5 som kräver minst 64 cykler (om man utför en iteration/cykel) eller 8 cykler/Byte.

Vi har testat att implementera siphash_core i en av Alteras FPGA:er, en Cyclone IV GX. I denna krets kräver siphash_core 1451 LEs (Alteras benämning på sina logiska element) samt 332 register. Inga minnen eller andra resurser används. Den klockfrekvens vi når är 117 MHz. Om vi jämför med den implementation av MD5 som finns på OpenCores så kräver den i samma FPGA-krets 1883 LEs, 910 register och når en klockfrekvens på 62 MHz.

Vi kommer att göra en del modifieringar och utökningar av implementationen. Bland annat kommer vi att som tidigare beskrivit skapa några nya versioner för att täcka in fler designtyper. Vi kommer även att utöka med fler testfall samt ta fram en toppnivåwrapper med ett enkelt 32-bitars gränssnitt som underlättar för integration med WISHBONE eller AMBA.

Om ni har några frågor om SipHash och/eller Secworks implementation siphash_core är det bara att höra av sig.

En reaktion på ”SipHash som öppen hårdvara

  1. Pingback: Digital Fanatics

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *

Följande HTML-taggar och attribut är tillåtna: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>