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 1292
April » 2008 » Kryptoblog

Archive for April, 2008

Riktigt elak hårdvara

April 30th, 2008

USENIXkonferensen LargeScale Exploits and Emergent Threats 08 (LEET08!) presenterade Samuel T. King, Joseph Tucek, Anthony Cozzie, Chris Grier, Weihang Jiang och Yuanyuan Zhou en mycket intressant artikel om hårdvarubaserade trojaner.

LEET-logga

Artikeln Designing and Implementing Malicious Hardware, som utsågs till konferensen bästa artikel, är något av det mest intressanta och skrämmande jag läst på länge. Artikelns sammanfattning beskriver väl vad den handlar om:


Hidden malicious circuits provide an attacker with a stealthy attack vector. As they occupy a layer below the entire software stack, malicious circuits can bypass traditional defensive techniques. Yet current work on trojan circuits considers only simple attacks against the hardware itself, and straightforward defenses. More complex designs that attack the software are unexplored, as are the countermeasures an attacker may take to bypass proposed defenses.

We present the design and implementation of Illinois Malicious Processors (IMPs). There is a substantial design space in malicious circuitry; we show that an attacker, rather than designing one specific attack, can instead design hardware to support attacks. Such flexible hardware allows powerful, general purpose attacks, while remaining surprisingly low in the amount of additional hardware.

We show two such hardware designs, and implement them in a real system. Further, we show three powerful attacks using this hardware, including a login backdoor that gives an attacker complete and highlevel access to the machine. This login attack requires only 1341 additional gates: gates that can be used for other attacks as well.

Malicious processors are more practical, more flexible, and harder to detect than an initial analysis would suggest.

Författarna börjar med att beskriva hur olika attacker rört sig nedåt från applikation och OS till firmware och till virtualiseringssystem. Men, frågar sig författarna, hur svårt är det att modifiera en hårdvarukonstruktion, en processor, så att den dels gör systemet som kör på hårdvaran osäkert, och om det går att göra så att systemet inte märker av modifieringen.

Författarna har valt att modifiera open-source-processorn LEON3 från Göteborgsbaserade Gaisler Research.

LEON3-processorn är placerad i ett högst ordinärt och typiskt HW-system med USB-kontroller, VGA-kontroller m.m. På LEON3-processorn kör man sedan ett normalr GNU/Linux-system. Hela klabbet har realiserats på en Xilinx-FPGA.

I LEON3 har man sedan implementerat olika attacker. Den första attacken är en modifiering till LEON3-processorns MMU som gör att en process som känner till modifieringen kan trigga procesorn att ignorera minnesskydd och låta processen ge sig själv rootaccess. Författarna förklarar:


Our memory access mechanism provides hardware support for unprivileged malicious software by allowing access to privileged memory regions. Malicious software triggers the attack by forcing a sequence of bytes on the data bus to enable the memory access circuits. This sequence can be arbitrarily long to avoid false positives, and the particular sequence must be agreed upon before deployment.

Once the sequence is observed, the MMU in the data cache ignores CPU privilege levels for memory accesses, thus granting unprivileged software access to all memory, including privileged memory regions like the operating system’s internal memory. In other words, loading a magic value on the data bus will disable protection checking.

We implement this technique by modifying the data cache of our processor to include a small state machine that looks for the spe-cial sequence of bytes, plus some additional logic in the MMU to ignore privilege levels when malicious software

Författarna beskriver även en shadow-mod som gör det möjligt att gömma trojan genom att skapa en extra processormod, och kod som körs i denna mod döljs från resten av systemet. Denna shadow-mod används sedan av författarna för att implementera en funktion som snor lösenord samt ett sätt att implementera en bakdörr rätt in i OS:et. Mycket imponerande, fräckt och skrämmande.

Det författarna visar är hur lite som krävs för att implementera den här typen av funktioner. Författarna lade till mindre än 200 rader kod till VHDL-koden LEON3 består av. Minnesmodifieringen krävde knappt 1000 gates och shadow-funktionen drygt 1300 gates. Närmast avrundningsfel i en modern HW-konstruktion.

Författarna avslutar sin artikel med en diksussion om hur man kan skydda sig mot den här typen av attacker. Bla om man kan använda sidoeffekter för att detektera om en krets utför operationer man inte tänkt. Författarna konstaterar att det i dag antagligen finns få/inga vettiga skyddmekanismer, vilket jag håller med om.

Frågan man bör ställa sig i det här läget är dock: Men hur stor är risken egentligen?

Som exempel på ett ökande risk för trojaner i hårdvarukonstruktioner citerar författarna en rapport från USAs Department of Defence Science Board som bland annat skriver att


First, it has become economically infeasible to procure high performance ICs other than through commercial suppliers. Second, these commercial suppliers are increasingly moving the design, manufacturing, and testing stages of IC production to a diverse set of countries, making securing the IC supply chain infeasible. Together, commercial-off-the-shelf (COTS) procurement and global production lead to an “enormous and increasing” opportunity for attack

Att det finns problem med äktheten hos kretsar visar om inte annat att det nu bildas organisationef för att försöka stävja den snabbt ökande förekomsten av piratkopierade kretsar.

Det är inte så svårt att tänka sig att dessa kretsar skulle kunna innehålla mer än den piratkopierade konstruktionen. Man får ett mervärde man kanske inte hade tänkt sig. (Tomas Gilså uppmärksammade detta i en artikel om risker med piratkopierade routrar och switchar – ja jag är citerad.

På Cryptography-listan kommenterade Karsten Nohl trenden mot snabbt ökande komplexitet på chipnivå och användningen av IP-cores med:


Hardware designs currently move away from what in software would be open source. Chip obfuscation meant to protect IP combined with the ever increasing size of chips makes it almost impossible to reverse-engineer an entire chip.

Helt sant. I dag bygger man chip med allt fler och allt större IP-cores. Men hur vet man att dom faktiskt bara gör det dom säger att dom gör. Att kontrollera att konstruktionen följer en spec är en sak, men att visa att den även kan göra något mer?

Så möjligheten att modifiera konstruktioner, och den vägen få in en elak HW-funktion finns, frågan är om det finns kompetens och motivation? Kompetens kan man tyvärr köpa, så frågan är om någon är intresserad. Skall man döma av den snabbt ökande ekonomiska IT-brottsligheten finns det en hel del som är beredda att jobba hårt och lägga mycket pengar på att vara elaka.

Den här artikeln har uppmärksammats en del på krypto- och säkerhetslistor. Även Matt Blaze har bloggat kloka tankar som är värda att läsa. I diskussionen på Cryptography påpekades det att mikrokoden i Intels och AMDs processorer går att uppdatera. Hur kontrolleras att den mikrokod som laddas ner är ok? Någon som vet?

Jag tycker att artikeln som presenterades på LEET08 är mycket, mycket intressant. Och jag hoppas att artikeln får uppföljning i form av metodik och verktyg för att inspektera HW-konstruktioner och chip. Jag tror att vi kommer att behöva återkomma till den här frågan.

Bra introduktion till Pythons generatorer

April 30th, 2008

(Det börjar bli en del om Python här…. Jag har skapat en kategori för Pythonrelaterade postningar.)

För några veckor sedan bloggade jag om Pythons generatorer, vilka bland annat är utmärkta för att implementera strömkrypton, slumptalsgeneratorer etc.

För några dagar sedan sprang jag på en bra presentation som ger en introduktion till Pythons generatorer. Den klart bästa förklaring till vad generatorer är och hur man arbetar med dom. Väl värd att bläddra igenom.

NSA publicerar en massa dokument

April 28th, 2008

Genom något som kallas Declassification Initiatives håller NSA på att publicera dokument som tidigare varit hemliga. Dokumenten utgörs i stort sett av scannade dokument publicerade i PDF-form.

Bland samlingarna återfinns bland annat gamla nummer av en publikation kallad Cryptologic Spectrum och en annan publikation kallad Cryptologic Quarterly.

Dessa publikationer innehåller en salig blanding av mer eller mindre intressanta dokument. Bland annat finns det en kul artikel om att studsa radiotrafik på meteorers spår och använda detta för att kommunicera. Ett annat dokument tar upp interoperabilitetsproblematik med epost i UNIX och DOS.

En annan sektion bland de publicerade dokumenten handlar om militär kryptanalys. De publicerade dokumenten tar inte upp speciellt moderna tekniker för kryptanalys. Men materialet är läsbart och intressant ändå.

Pawal pudlar, och jag också.

April 28th, 2008

I förra veckan rapporterade Pawal att flera myndigheter inte längre plockades upp av Creeper. Tanken var då att myndigheterna börjat blockera Creeper. Denna tanke spred jag vidare.

Men nu visar det sig att det var PHP som var boven. Pawal ber om ursäkt och det gör jag också.

Creeper filtreras bort av myndigheter

April 22nd, 2008

Pawal rapporterar att Migrationsverket, FRA, FMV och PTS verkar ha börjat filtrera bort Creeper. Det mest intressanta är att det verkar ske samtidigt från mer än en myndighet. Tydligen är det bara myndigheter som skall få kolla vem som gör vad på nätet.

Men att döma av Creeper-loggarna surfas det fortsatt friskt på Regeringskansliet.

Fin kryptomaskin från 80-talet

April 22nd, 2008

Picasa-användaren Dribbel har postat några fina bilder på en gammal kryptomaskin från 80-talet.

TexTell

TexTell är som namnet säger en maskin som omvandlar text till ljud och från ljud till text. Man håller tydligen maskinen mot telefonen och skickar krypterade meddelanden precis som med ett gammalt 300 bauds modem (eller antagligen mer som 75 baud). Själva hörlusmojen är integrerad i baksidan av enheten:

Baksidan.

På baksidan finns även instruktioner som förklarar hur man kommunicerar säkert med hjälp av TexTell:

Instruktioner för TexTell.

Att döma av texten är maskinen byggd av West-Tec LTD på Irland. Google ger bara en firma kallad Burglar Alarms & Security Systems West-Tec Security Systems på Irland, inget mer (som jag hittar).

Enligt en postning blev TexTell stoppad att visas på CeBIT-mässan i Hannover 1983. Ingen information om hur kryptodelen i TexTell fungerar (fungerade). Är det någon läsare som vet mer om TexTell så posta gärna!

Söt liten 0ldsk00l-maskin är det i alla fall…

MiFare är riktigt trasigt

April 22nd, 2008

Jag har tidigare skrivit om MiFaresystemet och dess uppenbarligen urusla säkerhet. Sedan dess har det kommit ytterligare en attack där forskare från Holland visade att de genom att samla in en mängd data och sedan bearbeta dessa offline kunde återvinna den 48bit långa nyckeln i MiFare Classics krypto CRYPTO1. Men nu har det kommit ett resultat till.

I en artikel på IACR av Nicolas T. Courtois, Karsten Nohl och Sean O’Neil kallad Algebraic Attacks on the Crypto-1 Stream Cipher in MiFare Classic and Oyster Cards visar författarna att säkerheten i MiFare är riktigt, riktigt trasig. Författarna skriver:


MiFare Crypto 1 is a lightweight stream cipher used in London’s Oyster card, Netherland’s OV-Chipcard, US Boston’s CharlieCard, and in numerous wireless access control and ticketing systems worldwide. Recently, researchers have been able to recover this algorithm by reverse engineering [11, 13].

We have examined MiFare from the point of view of the so called algebraic attacks. We can recover the full 48-bit key of the MiFare algorithm in 200 seconds on a PC, given 1 known IV (from one single encryption).

The security of this cipher is therefore close to zero. This is particularly shocking, given the fact that, according to the Dutch press, 1 billion of MiFare Classic chips are used worldwide, including many government security systems.

Som en läsare på Kryptoblog tidigare påpekat används även MiFare Classic i GL:s nya kontaktlösa biljettsystem här i Göteborg.

Egenhackade krypton är ofta en riktig usel idé, Ett egenhackat krypto med 48-bit nyckel känns riktigt brunt. Men det här kanske leder till bättre kravställning vid upphandling av den här typen av system. Man kan väl hoppas i alla fall…

Lite mer tankar om eSTREAM

April 20th, 2008

(Uppdaterad med lite egna åsikter om strömkryptons vara eller inte vara.)

Jag kom att det fanns ett par saker till från avslutningen av eSTREAM värda att nämna.

I slutrrapporten som presenterar eSTREAM-portföljen finns det även med resultatet från den omröstning som genomfördes på workshopen State of the Art Stream Ciphers – SASC 2008.

Deltagarna i workshopen ombads att dela ut poäng till de olika eSTREAM-kandidaterna. +5 för kandidater som ansågs vara very suitable och -5 för kandidater som ansågs vara not very suitable.

För kandidaterna i profil ett blev utfallet så här:


Rabbit 2.80
Salsa20 2.80
Sosemanuk 1.20
HC-128 0.60
NLS v2 -0.60
LEX v2 -1.20
CryptMT v3 -1.40
Dragon -1.60

För kandidaterna i profil två blev utfallet så här:


Trivium 4.35
Grain v1 3.50
F-FCSR-H v2 0.52
MICKEY v2 0.17
Decim v2 -1.38
Edon80 -1.72
Pomaranch v3 -2.24
Moustique -2.50

Som man kan se av detta var det de kandidater som totalt sett fick positiva omdömen som till slut kom med i eSTREAM-portföljen. I Profil ett var det ganska jämt, och inga kandidater som var mycket populärare än andra. I profil två sticker Trivium och Grain ut ordentligt som klart mer populära än de andra.

Slutrapporten avslutas med en diskussion och noteringar de som organiserat eSTREAM har gjort.

Flera av kandidaterna i eSTREAM hade stöd för autenticiering av datat, men ingen av de kandidater som kom med i eSTREAM-portföljen har denna egenskap. Det var bara ett fåtal av kandidaterna som var självsynkroniserande, och ingen av dessa tog sig igenom eSTREAM. Organisatörerna noterar även att den kryptanalys som utförts iaf bitvis har varit ad hoc, snarare än metodisk.

Organisatörerna påpekar även att strömkrypton som Snow 2.0, även om det inte var med i eSTREAM antagligen är ett krypto som borde kunnat vara med i portföljen. Vidare nämner man TPy och Phelix (två kandidater som åkte ut) som intressanta nog att fortsätta utveckla.

Rapporten avslutas med en fråga: Stream ciphers: dead or alive? Min personliga åsikt att från vare sig ett säkerhetsperspektiv eller ett systemperspektiv är det intressant om det symmetriska kryptot är ett strömkrypto eller ett blockkrypto. Det som är intressant är om kryptot är säkert, att det kan leverera den prestanda som krävs och att storleken på implementationen är så liten som möjligt och inte medför några sidoattacker.

Blockkryptot AES med lämplig kryptomod kan erbjuda samma metodmässiga beteende som ett strömkrypto. Men om ett strömkrypto kan ge bättre prestanda än AES är det intressant för applikationer med stora bandbreddskrav – och här har vi med eSTREAM fått HC, Rabbit och Salsa20. För inbyggda system med hårda kostnadskrav är AES en dyr lösning och då är eSTREAMs krypton Grain och Trivium bra tillskott till möjliga lösningar.

Slutligen är jag lite rädd för en på tok för stor homogenitet, mer specifikt att säkerheten beror av att en enskild komponent fortsatt är säker. Några av eSTREAM-kandidaterna lånade mer eller mindre mycket från AES. Vidare har det kommit flera förslag till hashfunktioner som bygger på koncept och komponenter från AES.

Skulle det dyka upp allvarliga problem med AES är det bra att det finns alternativ. Och därför tycker jag att eSTREAM som projekt, den portfölj av kryptot vi fått med eSTREAM samt fortsatt utveckling av strömkrypton (och andra krypton, hashfunktioner etc) är bra.

Vad är din uppfattning?

Och eSTREAM-vinnarna är….

April 19th, 2008

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.)

Slutspurt i eSTREAM

April 17th, 2008

(Uppdaterat med ett citat till från Response to ‘On the Salsa20 core function’. Tack Martin!)

Det är nu ungefär en månad kvar i eSTREAM-tävlingen. Den stora konferensen Fast Software Encryption (FSE) 08 är över och alla workshops är avklarade. Endast målrakan är kvar.

ECRYPT-logga

Daniel J Bernstein har satt samman ett par dokument som försöker summera läget för algoritmerna. (Jag försökte göra något liknande här på Kryptoblog, men DJB:s sammanställning är naturligtvis mycket mer genomarbetad och seriös.).

Artikeln Which phase-3 eSTREAM ciphers provide the best software speeds? försöker bedöma kandidaterna utifrån prestanda. Bernstein skriver:


This paper compares the software speeds of 128-bit 10-round AES, 256-bit 14-round AES, 256-bit CryptMT v3, 256-bit Dragon, 128-bit HC-128, 256-bit HC-256, 128-bit LEX v2, 128-bit NLS v2, 128-bit Rabbit, 256-bit RC4, 256-bit Salsa20/8, 256-bit Salsa20/12, 256-bit Salsa20/20, 256-bit SNOW 2.0, 256-bit Sosemanuk, and 80-bit TRIVIUM.

Artikeln är uppdelad i 10 underkapitel, en för respektive CPU som Bernstein har kört sina prestandatester på (en av dessa är PowerPC-kärnan PPE i Playstation 3). Till stöd för testerna har han använt det ramverk för tester som togs fram i början av eSTREAM och de olika användningfall (trafikfall) som används är:


• “long”: Encrypt one long stream.
• “agility”: Encrypt many parallel streams in 256-byte blocks.
• “1500”: Set up a nonce and encrypt a 1500-byte packet.
• “576”: Set up a nonce and encrypt a 576-byte packet.
• “40”: Set up a nonce and encrypt a 40-byte packet.
• “40k”: Set up a key, set up a nonce, and encrypt a 40-byte packet.

Det som mäts i testerna är cykler/Byte, vilket innebär att ju lägre värde desto bättre. Av kandidaterna verkar Salsa20/8, Trivium, LEX och Rabbit vara de kandidater som mest frekvent ger bäst prestanda. Strömkryptot SNOW 2.0 som används som referens ligger också bra till.

Tyvärr innehåller artikeln ingen bra sammanfattning, utan vi som läsare får själva bläddra igenom kapitlen och försöka skapas oss en bild av vilka kandidatalgoritmer som verkar bra. Det som finns som sammanfattning är kapitel 0.1 Should some ciphers be discarded? som listar säkerhetsmässiga och licensmässiga skäl till att välja bort en del kandidater.

Bernsteins andra artikel är Which eSTREAM ciphers have been broken? som går igenom status för de olika kandidaterna utifrån de säkerhetsanalyser som utförts. Bernstein skriver:


This paper summarizes the impact of known attacks on the stream ciphers submitted to eSTREAM. This paper focuses on “software phase 3” ciphers and “hardware phase 3” ciphers, but it also discusses the eSTREAM submissions that did not advance to phase 3.

En titt artikeln ger att CryptMT, HC, Rabbit, MICKEY-128 v2 är de som klarat sig bäst vad gäller publicerade svagheter. Sedan artikeln publicerades har det kommit en artikel om Grain kallad Cryptanalysis of Grain using Time/Memory/Date Tradeoffs.

I sin artikel har DJB även en länk till en sida på sin webbplats där han försöker samla attackstatus för kända strömkrypton, inte bara för eSTREAM-kandidater. Värd att titta på även om man inte är intresserad av eSTREAM.

Att eSTREAM nu avgörs innebär att några forskningsgrupper och företag får uppleva att det man kämpat för under flera år kröns med framgång. En vinst, få sin kandidat utsedd till eSTREAM-krypto innebär antagligen inte bara prestigemässig vinst, utan antagligen även ekonomisk vinst (exempelvis i form av anslag). Och det här verkar leda att vi befinner oss i något som liknar silly season där skaparna av olika kandidater med mer eller mindre väl underbyggda argument försöker försvara sina skötebarn.

Eli Biham och Jennifer Seberry, skaparna av Py, en kandidat som sållades bort vid slutet av fas två, har publicerat en artikel kallad The Truth on TPy. I artikeln skriver författarna:


In this note we refer to the security of the Py and TPy families, as discussed in several papers in recent years. We investigate the published attacks, and show that no attacks on TPy, TPypy and TPy6 have ever been published, whose complexities are within the bounds set by the security claims of these ciphers.

Also, only a single attack on Py was published which may be considered within the scope of the security claims — as a response to this attack the Py family was tweaked to TPy, TPypy and TPy6.

We conclude that the TPy family of ciphers is highly secure, and recommend using them in applications that require secure stream ciphers.

FSE 2008 publicerades två separata artiklar om svagheter hos Daniel J Bernsteins eSTREAM-kandidat Salsa20. New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba samt On the Salsa20 Core Function som enligt sammanfattningen beskriver.


In this paper, we point out some weaknesses in the Salsa20 core function that could be exploited to obtain up to 2**31 collisions for its full (20 rounds) version.

Skulle detta resultat stämma skulle Salsa20 vara riktigt illa ute. Och uppenbarligen har den här artikeln retat upp DJB ordentligt och han har publicerat ett svar i form av artikeln Response to ‘On the Salsa20 core function’. Och DJB sparar verkligen inte på krutet. Bernstein skriver bland annat:


The paper describes the observation as a “weakness” and “vulnerability” in the Salsa20 core function. In fact, exactly the opposite is true. The observation has no impact whatsoever on security: it bounces off a wall that was built into the Salsa20 design and that was already explained in the original “Salsa20 security” document.
...
The paper claims that it proves that “Salsa20 is not to be used as-is as a hash function.” What the paper means, apparently, is that the 64-byte-to-64-byte Salsa20 core is not to be used as a collision-resistant compression function. But what kind of idiot would think that a 64-byte-to-64-byte function is meant as a collision-resistant compression function?

I understand that the phrase “hash function” confuses some ignorant people— which is why I switched terminology to “Salsa20 core” in May 2007 and added an explicit warning to http://cr.yp.to/salsa20.html saying “The Salsa20 core . . . is not collision-resistant.”

How can someone write a paper several months later claiming novelty for the observation that the Salsa20 core is not collision- resistant? The paper says that “[Bernstein] acknowledges that the Salsa20 core is not collision-free”; the paper inexplicably fails to say that this “acknowledgment” predates the paper.

Även om DJB har rätt och Julio Cesar Hernandez-Castro, Juan M. E. Tapiador och Jean-Jacques Quisquater har fel är detta ett sätt att uttrycka det på jag aldrig sett förut i en vetenskaplig artikel.

En sista sak jag vill ta upp så här i slutet av eSTREAM är hur det ser ut licensmässigt för finalisterna. Vilka patenträttigheter är de olika kandidaterna belastade med:


CryptMT Free for any use if CryptMT Version 3 is in the eSTREAM final portfolio (otherwise free for non-commrecial use).
DECIM Partly patented, but freely available
Dragon Free for any use
Edon80 Free for any use
F-FCSR Free for any use
Grain Free for any use
HC Free for any use
LEX Free for any use
MICKEY Free for any use
Moustique Free for any use
NLS Free for any use
Pomaranch Free for noncommercial use
Rabbit Patented, but free for noncommercial use
Salsa20 Free for any use
SOSEMANUK Free for any use
Trivium Free for any use

Så, nu är det bara att vänta och se vad de kloka kryptologerna kommer fram till.