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 AHS » Kryptoblog

Archive for the ‘NIST AHS’ category

Intressanta kommentarer på NISTs AES-XTS

September 13th, 2008

NIST har publicerat de kommentarer som inkommit på förslaget att standardisera kryptomoden XTS för AES.

XTS är en variant av kryptomoden XEX skapad av Phillip Rogaway. XTS har tidigare standardiserats av IEEE i P1619 för att skydda i blockorienterad lagringsmedia (exempelvis hårddiskar och FLASH-minnnen).

Matthew Ball, som är ordförande i IEEEs Storage Working Group är i sin kommentar, inte helt överraskande, positiv till NISTs XTS-förslag. Matthew påpekar att XTS, till skillnad från exempelvis CBC är en algoritm som går att parallellisera och därmed skalar bra prestandamässigt.

Mer intressant är att kommentarerna från hårddisk-tillverkaren Seagate är så negativa. Seagate ser inga fördelar med XTS, och tycker att den implementationsmässigt är för kostsam. Seagate skriver bland annat:


The XTS encryption mode is not a good choice for storage encryption. There have been simpler, faster or more secure modes in use.

Is XTS a good tradeoff between security and complexity (costs)? NO: There are asymmetric large block encryption modes (e.g. BitLocker of Windows Vista) with similar complexity but better security for storage systems. There are faster, simpler encryption modes used together with access control (e.g. CBC)

Notera att Seagate inte ser ett problem med CBC vad gäller prestanda.

Även övriga kommentarer är på olika sätt negativa till XTS. Inte minst är det intressant att notera att Phillip Rogaway inte ser att XTS säkerhetsmekanismer inte tillför någon egentlig säkerhet.

Ett annat problem, som alla utom Matthew Ball från IEEE påpekar, är att IEEE äger standarden och att den som vill läsa standarden därför måste köpa standarden från IEEE. Som Niels Ferguson och Vijay Bharadwaj från Microsoft skriver i sin kommentar:


The proposal for the approved specification to be available only by purchase from IEEE . We believe that it is highly undesirable to standardize an algorithm whose specification, unlike those of other FIPS approved algorithms, is not freely available.

Ytterligare ett potentiellt problem med XTS är att det finns IP-rättigheter kopplade till standarden. Niels Ferguson och Vijay Bharadwaj återigen:


As stated in the call for comments, the current situation of IP rights with respect to XTS-AES is unclear. We believe that standardizing an algorithm which is so encumbered is undesirable, and that IP issues could inhibit adoption of such a standard.

Det är lite illavarslande att flera duktiga krytopexperter inte ser att XTS mekanismer, med bland annat två olika kryptonycklar tillför någon egentlig säkerhet och att det är oklart vad XTS egentligen är tänkt att lösa för ett säkerhetsproblem.

Men det som gör mig än mer orolig för framtiden är frågan om standardens öppenhet samt IP-problematiken, inte minst i ljuset av den pågående AHS-tävlingen. Finns det en risk att framtidens SHA-algoritm inte kommer att vara öppen, och att implementationer kommer att begränsas av IP-rättigheter? Det skulle inte vara bra för säkerheten.

SHA-3 och referensverktyg

January 3rd, 2008

Det har börjat röra på sig så smått vad gäller NISTs SHA-3-tävling. En sak som diskuteras är valet av referensplattform och kompilatorer för att testa kandidaterna. I specen för SHA-3 står det:


i. NIST Reference Platform: Wintel personal computer, with an Intel Core 2 Duo Processor, 2.4GHz clock speed, 2GB RAM, running Windows Vista Ultimate 32-bit (x86) and 64-bit (x64) Edition.

ii. Compiler (Note that the selection of this compiler is for use by NIST in Rounds 1 and 2, and does not constitute a direct or implied endorsement by NIST.): The ANSI C compiler in the Microsoft Visual Studio 2005 Professional Edition.

Att döma av diskussioner på maillistan är denna uppsättning av OS och kompilator mindre vanlig i kryptolabben på olika universitet där GCC och andra GNU-verktyg verkar vara standard. En person som påpekat detta är Ron Rivest.

Ron Rivest

Att döma av inläggen arbetar han och hans grupp på en kandidat just nu kallad md6.

Lästips för att hänga med i NISTs AHS-tävling

December 6th, 2007

På Bloggen Light Blue Touchpaper från säkerhetsgruppen i Cambridge finns en postning med lästips för att hänga med i NISTs tävling för att få fram nya hashfunktioner.

Det jag skulle vilja komplettera listan med är Jag skulle vilja komplettera listan med de HASH-workshops som NIST och ECRYPT arrangerat de senaste åren.

Ny kategori: NIST AHS

November 12th, 2007

Jag har lagt till en ny kategori till Kryptoblog. NIST AHS avsedd för nyheter relaterade till NISTs AHS-tävling (Advanced Hash Functions) där NIST precis öppnade dörren för kandidater.

En sak vi förhoppningsvis kommer att se en hel del av de närmaste åren och jag vill skriva om är nyheter om nya metoder för analys av hashfunktioenr och resultat från dessa analyser. Ett exempel är den diffusionsanalys som Daniel J Bernstein tidigare gjort på sin kompressorn i Salsa20. Så här ser tillståndet ut vid start:

Salsa20 innan första rond.

Efter en iteration:
Efter en iteration.

Efter två iterationer:
Efter två iterationer.

Efter tre iterationer:
Efter tre iterationer

Efter fyra iterationer:
Efter fyra iterationer.

Ett snyggt sätt att illustrera lavineffekten i en hashfunktion.

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

November 7th, 2007

(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!