HC-128, Rabbit, Salsa20/12, SOSEMANUK, F-FCSR-H v2, Grain v1, Mickey v2 och Trivium!
För ett par dagar sedan skrev jag en bloggpostning om slutspurten i eSTREAM och avslutade med att nu är det bara att vänta och se vad de kloka kryptologerna kommer fram till. Det visade sig att väntan blev kort.
Samtidigt som jag skrev min postning blev eSTREAM klar och dagen samtidigt med att jag postade uppdaterades eSTREAM. SÃ¥ kan det gÃ¥. Och tack till den läsare som pÃ¥pekade att resultatet var klart – jag hängde inte alls med.
Nå, resultatet är klart och vad skall vi då säga om det? Massor!
En första spontan kommentar är att det är kul att det blev sÃ¥ mÃ¥nga algoritmer som fick en plats i den slutgiltiga eSTREAM-portföljen. Det blev inte en algoritm i vardera profilen (profil ett – snabba SW-algoritmer och profil tvÃ¥ – effektiva i HW och inbyggda system), nej vi fick fyra algoritmer i respektive profil!
Detta gör iofs att det inte blir en algoritm som alla kommer att använda (jämför med AES), men samtidigt öppnar det upp att kunna välja utifrån krav och preferenser. Om man exempelvis inte kan leva med att Rabbit bara får användas fritt i icke-kommersiella tillämpningar finns det tre andra algoritmer i profil ett.
De ansvariga, kloka kryptologer som organiserat eSTEAM har publicerat en rapport kallad The eSTREAM Portfolio som beskriver arbetet som utförts i eSTREAM, varför de algoritmer som inkluderats i portföljen har valts samt varför andra algoritmer inte valdes. Vad gäller eSTREAM som aktivitet skriver de att:
The goal of eSTREAM was to stimulate work in the area of stream ciphers. In this, undoubtedly, the project has been a success. While eSTREAM has much of the appearance of a competition such as that used to establish the AES (or the forthcoming SHA-3) this comparison should be resisted.
We prefer not to use the word “winnersâ€, or to necessarily pick one (or even two) algorithms as the sole outcome of eSTREAM. Rather, we are conscious that most of the stream ciphers in the portfolio are very new and while we believe them to be promising—for a variety of reasons—we must leave it to others to decide when analysis is sufficiently mature for an algorithm to be considered in standards or used in a deployment.
Jag personligen vill ändå kalla algoritmerna som valdes in i portföljen som vinnare. De har genomgått ett ganska rejält stålbad och bland de 30+ kandidater blivit en av åtta som tog sig hela vägen fram. Vad gäller Profil ett-algoritmerna skriver eSTREAM-arrangörerna att:
The goal for ciphers submitted to Profile 1 was that they should be “good†in software. By this we meant that they should significantly outperform the AES when used in a suitable stream cipher mode and all the final phase ciphers in Profile 1 achieve this.
Our vision wasn’t necessarily of a stream cipher that had a good all-round profile; our focus was on raw encryption speed with a bias towards encrypting large amounts of data after a single initialisation. Our intended security level was set to 128 bits which we believe to be adequate for contemporary applications.
Det man lyckats med bland profil ett-algoritmerna är att få en bra spridning på typen av algoritm, dvs basen för hur kryptot fungerar. HC-128 är ett extremt snabbt krypto som arbetar med stora tabeller (som iofs tar lång tid att initiera) vilket gör den intressant för bulk-kryptering.
Rabbit är ett gammalt krypto (visades publikt på FSE 2003) och har klarat sig utan större problem sedan dess. Rabbit är även ett snabbt krypto, och utan omfattande initieringsfaser.
Salsa20/12 är ett snabbt och skalbart krypto, men bygger pÃ¥ delvis nya principer – även om det klarat sig bra genom eSTREAM. Sosemanuk Ã¥ sin sida bygger pÃ¥ delar frÃ¥n gamla krypton.
Vad gäller Profil två-algoritmerna skriver eSTREAN-organisatörerna att:
The goal for ciphers submitted to Profile 2 was that they should be “good†in constrained hardware environments. By this we meant that ciphers should significantly out-perform the AES in a restricted environment in at least one significant regard. The final phase candidates in Profile 2 were chosen because we believed they had the potential to achieve this.
We were anticipating that ciphers in Profile 2 might be suitable for deployment on passive RFID tags or low-cost devices such as might be used in sensor networks. Such devices are exceptionally constrained in computing potential because of the number of logic gates available or the amount of power that might realistically be available.
Our intended security level for this profile was 80 bits which we believe to be adequate for the lower-security applications where such devices might be used.
Som jag skrivit tidigare tycker jag att det är bra att man hade en separat profil för inbyggda system och att HW-implementationer togs i beaktande. Men jag tycker att det var synd att man hade 80 bitar som säkerhetsnivå för denna profil, något som många andra uttryckt som ett problem under hela eSTEAM-arbetet.
Jag ser inte att inbyggda system klarar sig med sämre säkerhet. Snarare är det så att dessa system är i användning under längre tid och uppdateras mycket mer sällan än PC-system. Detta, anser jag talar snarare för att inbyggda system behöver högre säkerhet, inte minst för att många av dessa system används för att automatisera, dvs styra och reglera den infrastruktur vi alla är beroende av.
Slutligen, att 48 bitar dvs sex Bytes skulle kosta för mycket för ett inbyggt system köper jag inte. Det som är intressant är hur mÃ¥nga bitar som interntillstÃ¥ndet i kryptot kräver – RC4 som exempel kräver 256 Bytes (plus minst 16 bitar till för pekare).
Av de algoritmer som till slut hamnade i portföljen är det dock bara Trivium som har en nyckellängd på 80 bitar, de andra (F-FCSR, Grain och Mickey) har alla 128 bitars nycklar. Bra.
Bland profil två-algoritmerna är spridningen av nytänkande och konservatism stor. F-FCSR-H bygger på principer som testats sedan 90-talet. Grain å sin sida är imponerande, både i sin grundläggande enkelhet och sin skalbarhet (något jag gillar skarpt). Mickey är väsentligen två (stora) skiftregister, men har stått upp bra mot alla attacker som kastats mot den. Trivium slutligen är ett experiment i enkelhet och nytänkande som visade sig hålla hela vägen. Kul!
Det jag kan tycka är lite synd är ingen av de kandidater som skickades in till båda profilerna fick vara kvar hela vägen. Salsa20 skickades in som kandidat till båda profilerna, men fick bara fortsätta som profil ett-algoritm, även om den går bra att implementera i HW. Grain å sin sida är mycket snabb även i SW, och Grain borde (anser jag) fått vara med som profil ett-krypto.
eSTREAM har lett till en stor hög med forskning, undersökningar och artiklar. Bara eSTREAMs egen artikelsida listar 205 olika artiklar, och till det skall läggas allt som publicerats på konferenser och andra ställen. På eSTREAMs diskussionsforum har det varit aktivitet under hela arbetet, ett forum där diskussionerna (speciellt när DJB varit inblandad) gått höga. Jag inbillar mig att detta varit bra för kryptoforskningen över huvud taget.
En sak jag noterar är att fyra av vinnar-algoritmerna är representerade bland de som organiserat eSTREAM. Steve Babbage (Mickey), Christophe De Canniére (Trivium), Anne Canteaut (SOSEMANUK), Henri Gilbert (SOSEMANUK), Thomas Johansson (Grain) och Bart Preneel (Trivium). Jag tror inte att det handlar om att eSTREAM letts av några av de bästa kryptologerna, vilka naturligvis har rätt att skicka in kandidater.
En annan sak jag noterar är att forskningsorganisationen COSIC är starkt representerad, både i organisationskommitén (med bland annat Vincent Rijmen och Bart Preneel) i de vinnande bidragen. Hongjun Wu (HC), Bart Preneel (Trivium), har alla COSIC som arbetsplats. COSIC är antagligen Europas, kanske världens just nu bästa institution för kryptoforskning.
Hur var det då med den internationella aspekten på eSTREAM? Rätt bra tycker jag att det ser ut som. De krypton som hamnade i portföljen kommer från Frankrike (SOSEMANUK, F-FCSR), Belgien (HC, Trivium), England (Mickey), Danmark (Rabbit), Sverige (Grain), Schweiz (Grain) och USA (Salsa20/12). Inga från Asien och få personer från USA.
Så, eSTREAM är över. Vad skall man göra nu? Jag tänker göra två saker: Bevaka NISTs AHS-tävling samt börja jobba med att göra bra HW-implementationer av eSTREAM-algoritmerna.
Jag har tidigare byggt testimplementationer av Salsa20, Grain, Mickey och Trivium och tycker att de är trevliga algoritmer. Jag skall försöka bygga implementationer av de andra algoritmerna i portföljen. Men Rabbit skuttar jag över – pÃ¥ grund av dess licens.
Vad jag har sett är Salsa20 är något problematisk vid routing (dra ledningar på chip). Min erfarenhet är även att Mickey är mycket lättare att skala än vad de flesta som beskrivit HW-implementationer för eSTEAM hävdar. Förhoppningsvis kan jag publicera lite siffror på implementationsresultat för eSTREAM-algoritmer senare under 2008.
Det var det hele. Tack eSTREAM för den tid som varit! Nu skall jag äta frukost.
(BTW: Nu är även Wikipedias sida om eSTREAM uppdaterad.)
