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.

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.

Page 1 of 2 | Next page