NIST väljer Keccak som ny hashalgoritm

I går meddelade standaerdiseringsorganisationen NIST att man valt algoritmen Keccak som ny kryptografisk hashfunktion. Därmed har den fem år långa SHA-3-tävlingen till slut avgjorts. Från 64 kandidater i första omgången ned till fem finalister och nu slutligenen vinnare.

I sin motivering till valet av Keccak skriver NIST:

The NIST team praised the Keccak algorithm for its many admirable qualities, including its elegant design and its ability to run well on many different computing devices. The clarity of Keccak’s construction lends itself to easy analysis (during the competition all submitted algorithms were made available for public examination and criticism), and Keccak has higher performance in hardware implementations than SHA-2 or any of the other finalists.

“Keccak has the added advantage of not being vulnerable in the same ways SHA-2 might be,” says NIST computer security expert Tim Polk. “An attack that could work on SHA-2 most likely would not work on Keccak because the two algorithms are designed so differently.”

Den annorlunda konstruktion Tim Polk pratar om är den svampkonstruktion (sponge construction) som Keccak bygger på. Valet av Keccak blir därmed en stark bekräftelse på att Svampkonstruktionen (pdf), som presenterades första gången 2007, är en bra konstruktion och modell för att skapa kryptografiskt starka funktioner.

NIST pekar på att Keccak är mycket snabbare än SHA-2 och även de övriga finalisterna när den implementeras direkt i hårdvara. Keccak kan verkligen nå imponerande prestanda i hårdvara, vilket inte minst Virginia Techs ASIC-implementation av kandidaterna samt ett antal ASIC- och FPGA-implementationer vittnar om.

Chiplayout av Virginia Techs SHA-3-testchip.

Chiplayout av Virginia Techs SHA-3-testchip.

I sina tester nåddes över 10 Gbit/s och dessutom till bäst prestanda/grind. Även i FPGA-kretsar fungerar Keccak väldigt bra. Jag testade Keccak i ett antal FPGA-kretsar 2008 och kunde konstatera att den inte bara gav bra prestanda utan även en kompakt, kostnadseffektiv storlek.

Det som gör valet av Keccak något kontroversiellt är att NIST ville få fram en algoritm som ger bra prestanda på moderna 64-bitars processorer. Och det gör inte Keccak. Keccak ger sällan bättre prestanda än SHA-2/256 eller SHA-2/512.

Däremot går det att accelerera Keccak programvarumässigt genom att köra på en GPU. Keccak har mycket intern parallellism som är möjlig att applicera på dataparallella arkitekturer (SIMD). Och denna typ av arkitekturer blir i dag allt vanligare, både i datorer och i inbyggda system. Intels processorer innehåller i dag en grafikprocessor. ARMs NEON ger liknande funktionalitet (om än inte med samma prestanda). Så även om Keccak inte ger bättre prestanda i programimplementationer i dag kan Keccak kanske utvecklas bättre än de gamla algoritmerna. Det hade dessutom varit intressant att se hur väl Keccak går att accelerera med instruktioner som i SSEx och AES-NI.

För den som vill börja labba med Keccak finns det en del referensimplementationer. Keccak finns även i kryptobiblioteket Botan. Nästa steg för NIST borde vara att uppdatera sitt FIPS 180-dokument med specifikation av SHA-3 baserad på Keccak inklusive testvektorer.

Valet av Keccak innebär även att kryptoforskaren Joan Daemen nu vunnit tre två stycken öppna kryptotävlingar. Joan var med och skapade Rijndael, algoritmen NIST 1997 valde som det symmetriska kryptot AES. Joan var även med och skapade Trivium, strömkryptot som blev vald till eSTREAM-portföljen av strömkrypton.

Joan Daemen

Joan Daemen

Hur väl Keccak, SHA-3 kommer att bli spridd och använd, på kort och längre sikt är svårt att sia om. NISTs tävling har lett till att en stor mängd forskning på kryptografiska hashfunktioner utförts. Och ett av de saker man kan se är att SHA-2 visat sig stå emot nya tester bättre än vad NIST befarade när tävlingen startade. Så konsekvensen av SHA-3-tävlingen är kanske att SHA-2 istället får ökad användning.

Uppdatering 2012-02-03
SUPERCOP, ramverket för att testa prestandan hos kryptografiska funktioner har även prestandaresultat för ett stort antal implementationer av Keccak. Det finns så otroligt mycket information och gigantiska grafer på SUBPERCOP att det är svårt att enkelt plocka ut jämöfelser. Men om man tittar i den här figuren (bara länk, den är stor) kan man i alla fall se att NEON gör stor skillnad på prestandan för ARM.

Spännande är det i alla fall.

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>