Kategoriarkiv: Forskning

Wired gräver efter Bitcoins med hårdvara

(Uppdaterad med länk till artikel om KNCminer.)

I en kommentar till en tidigare postning om bitcoins pekade Robert Andersson på en artikel hos Wired. Wired testar just nu en dedikerad Bitcoin-grävare från Butterfly Labs.

Butterfly Labs Bitcoin-grävare
Butterfly Labs Bitcoin-grävare. En snygg liten maskin.

I artikeln sätter Wired fingret på ett viktigt fenomen med Bitcoin – att det blir svårare och svårare att gräva efter bitcoins. I början räckte det med en vanlig dator. I dag krävs det massiva system av datorer, helst utrustade med kraftiga grafikprocessorer.

Därmed går kostnaden för att gräva upp – både att anskaffa utrustningen och att driva utrustningen, i första hand energiförbrukning. Ett sätt att minska den rörliga kostnaden är att använda allt mer effektiv, dvs specialiserad hårdvara. Det finns i dag både FPGA- och ASIC-baserade bitcoingrävare (Wireds maskin från Butterfly Labs är en sådan maskin). Gizmodo har en artikel som visar lite hur Bitcoin-utrustningen har utvecklats på några få år. Den här gamla utrustningen är inte längre speciellt konkurrenskraftig:

Galet stor Bitcoinmaskin
En system för att gräva Bitcoins som borde ge sysadmin magsår.

Några som håller på och utvecklar FPGA-baserade bitcoingrävare är svenska KnCMiner. Daniel Goldberg och Linus Larsson har skrivit en mycket intressant om KnCMiner och deras maskiner.

Men vad göra för att vara mer effektiv än system med specialiserade Bitcoin ASIC:ar? Lägga kostnaden på någon annan. Tyvärr börjar det dyka upp flera tecken på att Botnets används även för att gräva efter Bitcoins. Tidigare i år fick ett Botnet kallat ZeroAccess gräver efter Bitcoins med hjälp kapade datorer. En synnerligen tråkig om än egentligen inte oväntad utveckling med Bitcoins.

Sedan påpekar Wired och Robert att hela systemet med Bitcoins bygger på säkerheten hos hashfunktionen SHA-256. Och så är det, om vi snabbt kan forcera SHA-256 kommer Bitcoin-systemet att kollapsa. Men då har vi troligen större problem med den digitala säkerheten i vårt samhälle och på Internet än att en digital valuta faller samman.

Introduktion till Bitcoin

För den som vill veta mer om den kryptografiskt baserade, digitala valutan Bitcoin finns det en riktig bra introduktion att läsa.

Bitcoin: A Technical Introduction (pfd), skriven Chris Clark går på ca 40 sidor igenom vad Bitcoin är, hur man använder Bitcoins, den bakomliggande kryptografiska tekniken, digitala valutor inklusive några föregångare. Slutligen tittar den på hur Bitcoin är implementerad samt hur man gräver (mining) efter bitcoins.

Svaga nycklar i strömkryptot RC4

I dag har organisationen IACR, International Association for Cryptologic Research accepterat en artikel av Secworks Joachim Strömbergson samt Simon Josefsson som beskriver en typ av svaga nycklar i strömkryptot RC4.

I artikeln The Perils of Repeating Patterns: Observation of Some Weak Keys in RC4 beskriver vi hur nycklar bestående av ett mönster repeterat två eller flera gånger kan ersättas med en nyckel lika lång som mönstret självt. Följande figur illustrerar vad vi menar:

Olika nycklar i RC4 som genererar samma sekvens
Två olika par med nycklar där nycklarna i varje par får RC4 att generera samma sekvens.

Notera att för de två paren är skillnaden mellan nycklarna att dom är olika långa samt består av olika antal iterationer av samma mönster. I det övre nyckelparet är mönstret 0X55 och i det nedre nyckelparet är mönstret 0X01020304.

Så hur kan det bli så här? Den sekvens RC4 genererar styrs av hur den interna tillståndstabellen S initieras. Detta sker med funktionen KSA (Key Scheduling Algorithm):

RC4:as nyckelberoende initiering.
Den nyckelberoende initieringen i RC4.

Först fylls S med mönstret [0, 1, .. , 255]. Sedan kastas värdena i S om genom att under ett svep över S byta värden på två positioner i taget. Vilka positioner som används är alltid positionerna [0, 1, 2, … 255] (som anges av i) samt positioner som anges av j, vilket beror av nyckeln K. Detta sker på kodrad (5).

Nyckeln består av ett antal bytes och dessa bytes används i tur och ordning för att ge ett positivt bidrag till j. Och när alla bytes i K använts börjar man använda första byten i nyckeln igen tills dess att svepet över S är färdigt.

Boven i dramat är att värdena i nyckeln används på detta cykliska sätt utan att nyckelns längd får vara med och påverka pekaren j. En nyckel som består av två mönster [PP] appliceras på S ger samma bidrag till j som en hälften så lång nyckel som bara består av mönstret [P].

Vi tror inte att vi är dom första som observerat beteendet, det är alldeles för enkelt och dessutom är konstruktionen med att cirkulärt applicera ett mönster relativt vanligt. Det är därför en aning märkligt att vi inte lyckas hitta en beskrivning av beteendet kopplat till RC4. Vi har verkligen försökt så gått vi kan läsa igenom allt om RC4 och nycklar vi kunnat hitta, och det finns rätt många. RC4 är tyvärr ett krypto där det finns många svagheter. Vi har även kontaktat forskare som publicerat några av dessa svagheter men dessa har inte heller känt till beteendet vi beskriver.

Det finns dock en beskrivning av beteendet av Bruce Schneier i sin artikel som introducerar blockkryptot Blowfish. Schneier skriver om hur nyckeln används för att initera Blowfish:

Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

Vi tycker dock att det är omvänt sätt att beskriva det hela. Problemet är inte att för en given nyckel N finns det längre nycklar n*N där n är ett heltal [2, 3, ..]. Nej problemet är att för en nyckel som består av ett mönster N repeterat x gånger finns det ett antal kortare och därmed svagare nycklar.

I exempelvis SSL/TLS genereras nyckeln av en internfunktion med bra kvalitet och sannolikheten att en nyckel som består av ett repeterat mönster används är därför liten. Även i andra tillämpningar där användaren anger nyckel sker ofta en processning av nyckeln genom att köra nyckeln i en kryptografisk hashfunktion (helst många gånger) eller genom ett systen som PBKDF2, bcrypt (som använder Blowfish internt) eller scrypt.

Men jag har tyvärr sett tillämpningar där RC4 används och nyckeln appliceras direkt. Tillämpningar där nyckeln varit av typen 0X0101010101010101 eller 0X0102030405060701020304050607. För dessa är nyckeln inte 64 eller 128 bitar utan 8 respektive 64 bitar.

Vi räknar med att höra av forskare och andra kunniga människor som pekar ut var beteendet och problemet finns beskrivet. Men om det inte sker hoppas vi att den här artikeln hjälper till att sprida kunskapen om beteendet. Vill du undvika de problem vi observerat när du använder kryptp RC4 bör du helt enkelt inte använda nycklar som består av ett repeterat mönster.

Har du synpunkter och information om artkeln får du mer än gärna höra av dig till mig och Simon.

Matasanos kryptoutmaningar

Det få sätt att effektivt lära sig saker som att faktisk sätta sig ner och praktiskt utföra, öva på den man vill lära sig. Det gäller både saker som kanske är tråkiga, exempelvis glosor på tyska och saker som är desto roligare – spela gitarr eller hacka krypton.

Säkerhetsföretaget Matasano Security har insett detta och har därför skapat en serie spännande krypto och IT-säkerhetsutmaningar. Utmaningarna skickas som mail innehållandes åtta olika problem. Totalt finns sex uppsättningar problem. Problemen sträcker sig från grundläggande kodningar och XOR-krypton till slumptalsgeneratorer, strömkrypton, nyckelsystem och mycket mer. Själva utmaningarna är inte problem avsedda att luras, utan bygger på faktiska attacker och svagheter.

Matasano Security

Jag har precis börjat arbeta mig igenom utmaningarna. För att göra det lite svårare för mig själv försöker jag dessutom implementera mina lösningar inte bara i Python och/eller C, utan även i SystemVerilog. Vi får se hur länge det är realistiskt att göra det. Att implementera RSA i hårdvara kräver en hel del arbete – troligen mer än att lösa själva problemen i utmaningarna. Så här långt har det varit både givande och väldigt roligt.

För mer information om utmaningarna och hur du anmäler dig (du skickar ett mail), se Matasanos sida om utmaningarna. Om du genomför samtliga 48 utmaningar lovar Matasano även att donera 20 USD till välgörande ändamål.

Här finns även en sida skriven av en person som genomfört samtliga utmaningar och berättar lite mer om dom. En krav från Matasano är dock att inte ge beskriva utmaningarna i detalj eller dela med sig av sina lösningar, just för att andra också ska få chansen.

Ny draft för att få in Salsa20 i TLS och DTLS

Tillsammans med Simon Josefsson och Nikos Mavrogiannopoulos är Secworks involverade i arbetet att skriva en Internet Draft avsedd att få in strömkryptot Salsa20 i TLS och DTLS.

Skälet till arbetet med draften draft-josefsson-salsa20-tls-01 är att vi ser att det behövs ett bra, säkert strömkrypto i TLS och DTLS. I dag finns bara RC4 som strömkrypto, men RC4 är rejält trasigt. Det finns ett antal blockkrypton, inte minst AES, men de senaste årens säkerhetsproblem har gjort att fler använder RC4.

Att få in ett nytt strömkrypto kräver att det finns en RFC som beskriver hur strömkryptot ska användas i TLS och DTLS och draften är arbetsdokumentet till vad som förhoppningsvis blir denna RFC.

Salsa20 är ett strömkrypto som har kort initieringsfas och därmed ger bra prestanda även för korta meddelanden. Salsa20 går att få att ge bra prestanda på ett flertal olika processorarkitekturer. ARX-strukturen gör att Salsa20 inte öppnar upp för informationsläckage via sidokanaler. Slutligen är Salsa20 relativt väl analyserad då den är en av algoritmerna i eSTREAM-portföljen. Vi tror därför att Salsa20 skulle kunna bli en bra ersättare till RC4 i TLS och DTLS.

Om du har några kommentarer och synpunkter på draften skulle vi som författare uppskatta det mycket. Kontakta oss gärna. Själva arbetet med draften sker på Gitorious.

Security Engineering nu som fri e-bok

Säkerhetsforskaren Ross Anderson har skrivit en av de absolut bästa böckerna om säkerhet – Security Engineering.

Security Engineering hos Amazon

Ross har gjort den tidigare versionen av boken fritt tillgänglig. Och nu har Ross även släppt den senaste versionen (från 2008) fritt tillgänglig på sin sida för boken.

Gissningsvis kommer en uppdaterad, tredje version av boken ut under året. Men den version som nu finns är trots sina fem år på nacken fortfarande en riktigt, riktigt bra bok som vi rekommenderar till alla som vill veta mer om säkerhet.

Hacking the Xbox nu som gratis e-bok

Andrew Bunnie Huang, som Secworks tidigare uppmärksammat för sitt projekt att utveckla en egen laptop, har släppt sin bok Hacking the Xbox i PDF-format fri för nedladdning.

Hacking the xbox, som kom 2003 är en fantastisk bok, som inte bara berättar om hur Bunnie som forskarstudent lyckades knäcka skyddet i Xbox. Boken är istället en mycket bra introduktion till metoder och verktyg för att analysera och plocka isär digitala system.

Hacking the xbox

Även om boken har några år på nacken är den fortfarande mycket läsvärd och relativt unik i sitt fokus på praktiskt arbete, inte bara teori.

Skälet till att Bunnie och bokens förlag släpper boken fritt beror på hur hackern Aaron Swartz behandlades. Bunnie skriver bland annat:

No Starch Press and I have decided to release this free ebook version of Hacking the Xbox in honor of Aaron Swartz. As you read this book, I hope that you’ll be reminded of how important freedom is to the hacking community and that you’ll be inclined to support the causes that Aaron believed in.

I agreed to release this book for free in part because Aaron’s treatment by MIT is not unfamiliar to me. In this book, you will find the story of when I was an MIT graduate student, extracting security keys from the original Microsoft Xbox. You’ll also read about the crushing disappointment of receiving a letter from MIT legal repudiating any association with my work, effectively leaving me on my own to face Microsoft.

The difference was that the faculty of my lab, the AI laboratory, were outraged by this treatment. They openly defied MIT legal and vowed to publish my work as an official “AI Lab Memo,” thereby granting me greater negotiating leverage with Microsoft. Microsoft, mindful of the potential backlash from the court of public opinion over suing a legitimate academic researcher, came to a civil understanding with me over the issue.

Här finns hela motivering till varför Bunnie och förlaget släpper boken.

Nya kryptotävlingar

Knappt har röken från NISTs SHA-3-tävling lagt sig för det är dags igen.

CAESAR
Daniel J Bernstein har med ekonomiskt stöd från NIST i all korthet utlyst en ny tävling. Den nya tävlingen, CAESAR – Competition for Authenticated Encryption: Security, Applicability, and Robustness syftar till att få fram symmetriska kryptoalgoritmer som även ger autenticering av datat som bearbetas.

I dag är det väldigt tydligt att för den överväldigande mängden kommunikation är kryptering (som ger konfidentialitet) oftast mycket mindre viktigt än att veta att meddelanden kommer från rätt sändare och att det inte modifierats under överföring. Inte minst gäller detta industrisystem och inbyggda system där informationen sällan är känslig, men måste vara korrekt. Tyvärr är det få kryptoalgoritmer som ger både konfidentialitets- och autenticitetsskydd och det är vanligt att se system där bara konfidentialitet används.

Kryptot AES exempelvis kräver en kryptomod som GCM för att ge båda egenskaperna, en kryptomod som är relativt kostsam.

CAESAR avser att försöka standardisera en portfölj med bra ström- och blockkrypton samt kryptomoder som ger båda egenskaperna. Ett mycket bra initiativ.

Tidplanen för CAESAR är att kandidater ska vara inlämnade i början av 2014 och sedan sker utvärderingar under flera år för att slutligen 2017 förhoppningsvis leda till en portfölj med flera algoritmer.

Nya hashfunktioner
Det pågår även ett initiativ att starta en tävling motsvarande eSTREAM sponsrat av EU för att få fram nya hashfunktioner som är både kompakta och mycket snabbare än MD5, inte minst på enklare plattformar. Här finns det dock mindre konkreta planer än.

SHA-3 (Keccak) är en snabb algoritm på 64-bitars processorer. Men på 16- eller 32-bitars processorer samt i hårdvara har den visat sig vara svår att få riktigt snabb och samtidigt kompakt. SHA-2-algoritmerna har inte slagit, mycket på grund av att dom är så mycket långsammare än SHA-1 och MD5.

Många hoppades att SHA-3 skulle få fram radikalt snabbare algoritmer, men så blev det inte. Däremot har det efter SHA-3 dykt upp minst en intressant sådan algoritm. BLAKE2, en ny version av SHA-3-finalisten är mycket snabb och finns dessutom i ett par versioner för att möte krav från begränsade plattformar och för de med höga krav på säkerhet.

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.

Presentationer från NISTS sista SHA-3-konferens

I slutet av mars anordnade NIST den sista SHA-3-konferensen. Målet med konferensen var att få in så mycket information som möjligt om finalisterna inför NISTs beslut om vilken algoritm som kommer att blir den nya hashfunktionen SHA-3. NIST har en sida för konferensen och där finns nu alla presentationer och artiklar som presenterades.

Det finns ett flertal intressanta presentationer om implementationer, både i hårdvara och i program. För högpresterande hårdvaruimplementationer i FPGA och ASIC ser finalisten Keccak ut att vara överlägsen, både i ren råprestanda och prestanda viktad mot kostnad. På senaste generationer av CPU:er ser dock BLAKE att vara överlägsen rent prestandamässigt.

För små, inbyggda system ser Gröstl och Blake att ge minimala implementationer med där Keccak återigen ger bäst prestanda viktad mot kostnad. Det finns även intressanta resultat vad gäller sidottacker på implementationer och säkerhetsanalyser av algoritmerna.

På konferensen ställde även NIST frågan till deltagarna om vilka kandidater de föredrar genom att humma. Skaparen av BLAKE, JP Aumasson rapporterde resultatet:

Top: Keccak, then BLAKE. Deafening silence: Skein. Ouch.

När skaparna av finalisterna fick frågan vilken algoritm förutom sin egen de föredrog blev resultatet:

  • Skein -> BLAKE
  • Groestl -> JH
  • JH -> Keccak
  • BLAKE -> Skein
  • Keccak -> Groestl

Om man jämför med humm-frågan ser det ut att vara rätt mycket taktik i de valen.

IETF 83 några dagar efter SHA-3-konferensen höll NIST en mycket intressant presentation om SHA-3 (länken pekar på PPT-fil). För att få en känsla av hur NIST resonerar är den här presentationen väl värd att bläddra igenom. I presentationen pekar man ut att SHA-3 inte kommer att ersätta SHA-2, inte minst då SHA-3 knappast kommer att ge mycket bättre prestanda. NIST ser att SHA-2 är effektiv, inte minst i inbyggda system. Däremot kommer SHA-3 att kunna ge mycket högre prestanda för hashbaserade meddelandekoder (MAC). NIST påpekar även i sin presentation att det analysarbete av kryptografiska hashfunktioner som bedrivits sedan 2005 gör att man i dag är mindre orolig för säkerheten hos SHA-256 och andra SHA-2-algoritmer. NIST ber i sin presentation IETF om synpunkter på hur hashfunktioner bör anpassas för olika protokoll och miljöer, detta för att ta med dessa synpunkter i sitt val av vinnande algoritm.

För den som vill bidra till SHA-3-processen vill NIST få in detta innan den första juni. Sedan är det dags för NIST-juryn att överlägga och berätta vem som är vinnare. (Inte säker på att SHA-3-överläggningen skulle göra sig lika bra i TV som Project Runway.). Enligt NIST kommer vinnaren att utses i slutet av året.

Har du information du anser att NIST bör ta med i sin bedömning är det dags att agera. Sedan blir det spännande att sätta tänderna i den nya, fräscha SHA-3. Nästan som en julklapp.