NIST meddelade för några dagar sedan att de fått in 64 kandidater och att det kommer att dröja till i början av december innan NIST presenterar vilka kandidaterna är. Även om antalet kandidater är mindre än de minst 80 kandidater Bruce Schneier gissade på är det väldigt många.

Även om inte NIST publicerat listan med kandidater finns det en Wikisida kallad The SHA-3 Zoo som listar 28 stycken av kandidaterna inklusive länkar till artikel, webbplatser samt kandidaternas status vad gäller attacker. För attacker och kryptanalysresultat har redan börjat dyka upp.

På den maillista som NIST satt upp är det sedan en tid tillbaka en relativt hög aktivitet med postningar av resultat och diskussioner av hur dessa skall tolkas. Bland annat var några så ivriga att få in ett resultat att de publicerade en attack på kandidaten EnRUPT som är sämre än uttömande sökning. När de sedan fick kritik kom de med följande kommentar som låter väldigt mycket som First Post! på diverse forum:

We started working on the function yesterday. As soon as the paper was finished we sent a message.

Känns inte helt seriöst. Dock gav detta upphov till vad som skall klassificeras som en riktig attack – om attacker som tar längre tid eller kräver mer minne än atomer i hela universum skall anses som allvarliga attacker eller ej. Daniel J Bernstein kom för nÃ¥gra dagar sedan med ett riktigt elegant debattinlägg:

2^185 preimage attack on MD6-256

After the recent flood of attacks on hash functions that I had never heard of before this month, I’m pleased to announce that I’ve found an attack on MD6-256 with time complexity just 2^185.

The attack is a “multiple-preimage attack” that simultaneously attacks 2^{32 legitimate target signatures and successfully forges at least one signed message by finding a preimage of the underlying hash. Surely there will be more than 2}32 signatures generated using SHA-3, so this
is a realistic attack scenario if MD6 is being considered for SHA-3.

Recall from Rivest’s description of MD6 at Crypto that computing MD6 takes a fraction of a millisecond on a single CPU core. The total time for the attack is under 2^185 milliseconds—-I’m talking about actual wall-clock time, not some simplified model. The attack doesn’t fit on a single PC, but is easily implemented on a large cluster of a billion current Core 2 Quad PCs. Memory consumption per PC is negligible. Special-purpose hardware will be even less expensive.

The attack isn’t guaranteed to succeed; a detailed analysis shows that it has only about 1 chance in 100 of succeeding. However, repeating the attack will increase the success probability, and in any event I think we can agree that 1 chance in 100 is already an unacceptable threat for
SHA-3 users. Can we please kick MD6 out of the hash competition now?
—-D. J. Bernstein

Research Professor, Computer Science, University of Illinois at Chicago

P.S. Preliminary analysis suggests that, astonishingly, Skein and Keccak will both succumb to analogous attacks, and that the attack on Skein will be even faster than the attack on MD6. Who would have imagined that three hash-function designs with such different design principles would share a critical weakness?

Räknar man samman vad Bernsteins attack, som har motsvarande upplägg som några av de attacker som kommit på maillistan, ser ut att klara får man en attack på 2^256, dvs uttömande sökning (brute-force).

Det har kommit ett par ordentliga attacker. En av de första att falla var kandidaten NK2SD som är något så ovanligt som en hashfunktion baserad på en tvådimensionell cellautomat inspirerad av Stephen Wolframs A New Kind of Science:

(Fina figurer från NK2SD-automater)

Just nu listar SHA-3 Zoo åtta stycken kandidater som i någon variant har attackerats. Dock verkar SHA-3 Zoo, NISTs egen maillista och andra aktiviteter leva ett eget liv utanför NISTs kontroll. NIST har gjort klart att inga kandidater i detta läget är borträknade. En sidoaktivitet som pågår är ECRYPTs eBASH där man kör och presenterar prestandatester av alla kandidater. Att döma av resultaten så här långt, med enbart ett fåtal kandidater är det ingen som framstår som snabbare än SHA-2. Ett problem med SHA-2, och tävlingen är tänkt att lösa är just att SHA-2-algoritmerna är så mycket långsammare än SHA-1.

En annan aktivitet är insamling av information om implementationer av kandidater i hÃ¥rdvara – ASIC eller FPGA. En av snabbaste ser ut att vara Keccak. Keccak har jag bloggat lite om tidigare och även om den svampfunktion som ligger till grund för funktionen. Kul att se att den verkar ge bra prestanda.

Jag har läst igenom de flesta artiklar som presenterar de (sÃ¥ här lÃ¥ngt kända) kandidaterna. Att presentera resultat om hÃ¥rdvaruimplementationer av sin kandidat verkar vara en trend bland kandidaterna. En annan trend jag tycker mig se är att beskriva skydd mot sidoattacker – Ã¥terigen en implementationsaspekt. BÃ¥de intressant och bra att se att de senaste Ã¥rens sidoattacker börjar slÃ¥ igenom och bli nÃ¥got som beaktas vid design av nya algoritmer.

Sättet som flera av kandidaterna hanterar problematiken med sidoattacker är att gÃ¥ mot enkla grundunktioner – baserade pÃ¥ XOR, rotationer och bitskiftningar samt additioner. Desa grundfunktioner upprepas seda ett (mycket) stort antal gÃ¥nger. Typiskt används inga S-box-liknande strukturer. NÃ¥gra exempel pÃ¥ detta är MD6, Skein (som bygger pÃ¥ Trieefish-kryptofunktionen) och Cubehash.

Påfallande många kandidater försöker även gå ifrån Merkle-Damgård-konstruktionen och mot helt nya principer för att bygga kompressorfunktioner och hashfunktioner. MD6, Keccak och NK2SD är exempel på detta.

Väsentligen alla kandidatbeskrivningar innehÃ¥ller mer eller mindre ordentliga beskrivningar om kandidatens säkerhet och skydd mot olika attacker. Men flera av kandidaterna, bland annat MD6 och Skein innehÃ¥ller bevis – alltsÃ¥ att algoritmen är bevisbart säker. Det skall bli intressant att se huruvida dessa bevis visar sig stämma, och om de antaganden och de villkor under vilka bevisen gäller hÃ¥ller.

Skaparna av kandidaten Skein, skapad av bland andra Bruce Schneier, Niels Ferguson, Stefan Lucks och Doug Whiting, sticker ut för att de har använt ett något annorlunda sätt att argumentera för sin algoritms säkerhet:

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Är Security by Authority en vettig term för den här typen av säkerhet tro?

Om någon undrar vad Skein betyder är det tydligen ett garnnystan, vilket är en bra liknelse för hur Treefish-funktionernas in- och utdata i Skein slingrar sig runt varandra.

Jag räknar med att återkomma med mer info om NISTs tävling när de presenterat samtliga 64 kandidater. Sedan lär det dröja några år innan jag får reda på om min gissning stämmer.