Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
NISTs statusrapport för SHA-3 » Kryptoblog

NISTs statusrapport för SHA-3

October 4th, 2009 by Joachim Strömbergson Leave a reply »

NIST arrangerar en tävling för att få fram en ny hashfunktion avsedd att komplettera SHA-2, en hashfunktion som kommer att kallas SHA-3. Tävlingen har pågått sedan hösten 2007 och i slutet av juli 2009 avslutades den första omgången av tävlingen och den andra omgången startade. För ett par veckor sedan publicerade NIST en statusrapport med lägesbeskrivning för tävlingen efter första omgången..

När tävlingen startade begärde NIST in kandidater och fick totalt in 64 stycken kandidater. Av dessa kandidater ansåg NIST att 51 uppfyllde minimikraven och accepterades som kandidater i slutet av oktober 2008. Det senaste året har dessa kandidater undersökts och attackerats av såväl NIST som kryptosamfundet i stort. För den som är intresserad listar SHA-3 Zoo status för alla kandidater vad gäller attacker.

En av de saker rapporten beskriver är vilka kriterier NIST har satt upp för att bedöma de olika kandidaterna. Dessa är uppdelade i tre kategorier:

  1. Säkerhet. Den nya hashfunktionen måste vara minst lika säker som SHA-2-funktionerna.
  2. Prestanda och kostnad. Ett problem med SHA-2 är att dessa funktioner är väldigt mycket långsammare än SHA-1 och den nya funktionen måste därför vara snabbare än SHA-2. Prestandan mäts både på referensplattformen Intel Core 2 Duo i 32- och 64-bitarsmod, men man tittar även på 8-bitplattformar och HW-implementationer. Kostnaden handlar om mängd program- och dataminne samt storlek vid HW-implementationer.
  3. Algoritm och implementation. Detta kriterie handlar mer om ifall algoritmen är mer eller mindre flexibel, kan utnyttja nya arkitekturer som SIMD-instruktioner eller AES-instruktioner, går att parallellisera samt om algoritmen är enkel eller invecklad.

Utifrån sina egna bedömningar och andras analyser vad gäller säkerhet och prestanda (exemeplvis eBASH-projektets prestandamätningar) har NIST valt ut 14 algoritmer som går vidare till andra omgången. Dessa är:


BLAKE, BLUE MIDNIGHT WISH (BMW), CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, Skein

Rapporten innehåller en kortfattad beskrivning av varje kandidatalgoritm där NIST beskriver grundläggande idé och struktur, hur olinjäritet skapas i algoritmen, vad NIST ser som det unika med algoritmen, prestanda samt säkerhetsläget. Utifrån dessa beskrivningar kan man göra några enklare observationer:

  • Tre grundläggande idéer/strukturer återkommer hela tiden. Tre är baseade på HAIFA, sex är olika varianter och utökningar av Merkele-Damgård (MD) och övriga fem är baserade på de relativt nya svampfunktionerna (Sponge functions). Det är skönt att se att det inte bara är MD-baserade kandidater kvar, utan att det finns kandidater med rejält olika utgångspunkt kvar i tävlingen.
  • Fyra av kandidaterna använder på något sätt AES som en del av sin funktionalitet. Vissa återanvänder S-boxen, andra återanvänder delar eller hela round-funktionen från AES.
  • Flera av kandidaterna behöver väsentligen implementeras med SIMD- eller AES-specialiserade instruktioner för att ge riktigt bra prestanda.
  • Antalet kandidater med substitutionstabeller är ganska få, och dessa är förhållandevis små. Detta kan antagligen ses som ett resultat av de senaste årens uppmärksammade problem med att göra implementationer utan sidoeffekter av algoritmer med S-boxar.
  • Förhållandevis många kandidater bygger på att använda enkla funktioner (XOR, modulär addition, skiftoperationer) som upprepas ett stort antal gånger, gärna med möjlighet till parallellism. Ingen verkar använda multiplikationer eller andra typer av mer avancerade transformer, ex FFT som en av de andra kandidaterna använde.

NISTs förhoppning är att det begränsade antalet kandidater i andra omgången skall göra att samtliga kandidater blir rejält genomlysta. NIST noterar i sin beskrivning av kandidaterna att det skiljer ganska väsentligt i hur mycket analys som skett av de olika kandidaterna så här långt.

Den andra omgången är planerad att pågå i ett år och hösten 2010 avser NIST att välja ut fyra-fem stycken av de 14 kandidaterna som finalistkandidater. Detta innebär att tävlingen pågått i två år och kommer att hålla på i ett, troligen två år till. Det tar tid att skaka fram en hashfunktion.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

Leave a Reply

You must be logged in to post a comment.