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
NIST öppnar dörren för AHS-kandidater » Kryptoblog

NIST öppnar dörren för AHS-kandidater

November 7th, 2007 by Joachim Strömbergson Leave a reply »

(Uppdaterad 2007-11-07, 05:10: Nyckelfelstrisse (LinusN) + Vlastimil Klima)

NIST har meddelat att dörren för kandidater till hashfunktionstävlingen nu har öppnats. Tidigare har man pratat om AHS - Advanced Hash Standard, men nu refererar man till de blivande standarden som SHA-3 och anger att vinnande funktion kommer att beskrivas i en uppdaterad version av dokumentet FIPS PUB 180-2. NIST skriver:


NIST has opened a public competition to develop a new cryptographic hash algorithm, which converts a variable length message into a short “message digest” that can be used for digital signatures, message authentication and other applications. The competition is NIST’s response to recent advances in the cryptanalysis of hash functions.

The new hash algorithm will be called “SHA-3” and will augment the hash algorithms currently specified in FIPS 180-2, Secure Hash Standard. Entries for the competition must be received by October 31, 2008.

Notera tidpunkten när dörren för kandidater stängs: 2008-10-31, dvs om ett år. Över huvud taget kan det vara värt att titta på tidplanen. (Jag har bloggat om tävlingen ett tag…)

I mitten av 2006 gick NIST ut med information att man beslutat att arrangera en tävling. I februari ville NIST få in kommentarer på sitt förslag till organisation av tävlingen och krav att ställa på kandidaterna. De till NIST inkomna kommentarer redovisades i somras, kommentarer där bland annat det intressanta konceptet Sponge Functions oväntat dök upp.

Nu tar det alltså ett år innan kandidaterna börjar utvärderas på allvar, och sedan tar det 4-5 år innan vi har SHA-3 publicerad och klar. NIST skyndar långsamt. Men vill vi ha bra hashfunktioner, och inte upprepa de missar som inträffade med AES så skall vi nog skynda långsamt.

Det kan vara intressant att titta lite på de tekniska krav som ställs på kandidaterna. Först av allt ser man att SHA-3 skall kunnna gå in och ersätta SHA-2:


NIST does not currently plan to withdraw SHA-2 or remove it from the revised Secure Hash Standard; however, it is intended that SHA-3 can be directly substituted for SHA-2 in current applications, and will significantly improve the robustness of NIST’s overall hash algorithm toolkit.

Therefore, the submitted algorithms for SHA-3 must provide message digests of 224, 256, 384 and 512-bits to allow substitution for the SHA-2 family. The 160-bit hash value produced by SHA-1 is becoming too small to use for digital signatures, therefore, a 160-bit replacement hash algorithm is not contemplated.

Since SHA-3 is expected to provide a simple substitute for the SHA-2 family of hash functions, certain properties of the SHA-2 hash functions must be preserved, including the input parameters; the output sizes; the collision resistance, preimage resistance, and second-preimage resistance properties; and the “one-pass” streaming mode of execution.

Vidare vill NIST, precis som i fallet med AES (och till skillnad från eSTREAM) till slut landa på en algoritmfamilj:


For interoperability, NIST strongly desires a single hash algorithm family (that is, that different size message digests be internally generated in as similar a manner as possible) to be selected for SHA-3. However, if more than one suitable candidate family is
identified, and each provides significant advantages, NIST may consider recommending more than one family for inclusion in the revised Secure Hash Standard.

Det verkar dessutom vara så att den senaste tidens attacker på Merkle-Damgård-baserade strukturer (MD5, SHA-1 etc) oroar NIST, och att man vill se nya fundamentala sätt att skapa hashfunktioner:


NIST is open to, and encourages, submissions of hash functions that differ from the traditional Merkle-Damgard model, using other structures, chaining modes, and possibly additional inputs.

However, if a submitted algorithm cannot be used directly in current applications of hash functions as specified in FIPS or NIST Special Publications, the submitted algorithm must define a compatibility construct with the same input and output parameters as the SHA hash functions such that it can replace the existing SHA functions in current applications without any loss of security.

De kommentarer på tävlingen som kom in och tog upp behovet av att kunna göra effektiva implementationer av algoritmerna i både HW och SW i stora och små system har NIST tagit fasta på. Som implementatör av krypton till olika typer av inbyggda system blir jag glad när jag ser det här (tack NIST!):


A statement of the algorithm’s estimated computational efficiency and memory requirements in hardware and software across a variety of platforms shall be included.

At a minimum, the submitter shall state efficiency estimates for the “NIST SHA-3 Reference Platform” (specified in Section 6.B) and for 8-bit processors. (Efficiency estimates for other platforms may be included at the submitters’
discretion.) These estimates shall each include the following information, at a minimum:

a. Description of the platform used to generate the estimate, in sufficient detail so that the estimates could be verified in the public evaluation process (e.g., for software running on a PC, include information about the processor, clock speed,
memory, operating system, etc.). For hardware estimates, a gate count (or estimated gate count) should be included.

b. Speed estimate for the algorithm on the platform specified in Section 6.B. At a minimum, the number of clock cycles required to: 1. generate one message digest, and 2. set up the algorithm (e.g., build internal tables) shall be specified for each message digest size required in the Minimum Acceptability Requirements section (Section 3) of this announcement.

c. Any available information on tradeoffs between speed and memory.

De här textsnuttarna är hämtade från det officiella dokumentet som specar upp krav på kandidaterna. Där finns en hel del till om IPR-krav, tidplan, referensplattform etc. Är du intresserad så läs det – ett bra dokument.

Hur det går och vem som skickar in kandidater då? Min personliga förhoppning är att vi får se minst en kandidat med svensk representation, då troligen antingen från LTH (Johansson & Co) eller KTH (Håstad & Co), men det vore även kul om någon från industrin gjorde ett försök.

Vad gäller andra kandidater borde Daemens svampgäng komma med en kandidat. Eli Biham & Co, IBM samt Rivest & Co som alla tidigare visat intresse av tävlingen kommer gissningsvis även de med kandidater. Vidare har Daniel J Bernstein gjort en hel del arbeten på sina hashfunktioner Salsa20 och Rumba20, så han skickar säkerligen in en kandidat.

En annan person (+ kollegor) som troligen skickar in en kandidat är Vlastimil Klima som hittade tunnlarna i MD5 och tidigare i år presenterat en ny familj av hashfunktioner kallad HDN. Och Bruce Schneier försöker nog återigen vara med i en tävling – tredje gången gillt kanske?

Den som lever får se, nu börjar tävlingen på allvar och det kommer att bli spännande att följa hur det går!

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.