Archive for the ‘ECRYPT eSTREAM’ category

Uppdaterad eSTREAM-portfölj och nya attacker

November 17th, 2008

eSTREAM-projektet presenterade sin portfölj med strömkrypton i april i år. Portföljen som då presenterades inkluderade fyra krypton i profil ett avsedda i första hand för SW-implementation och fyra krypton i profil två avsedda för inbyggda system och hårdvaruimplementationer. Dessa krypton var:

Profil ett:

HC-128

Rabbit

Salsa 20/12

Sosemanuk

Profil två:

F-FCSR-H v2

Grain v1

Mickey v2

Trivium

Sedan april har det hänt en del. Det mest direkta är att eSTREAM-portföljen har uppdaterats med den stora förändringen att F-FCSR-H plockats bort från profil två.

Skälet till detta är att Hell och Johansson skrivit en artikel kallad Breaking the F-FCSR-H stream cipher som tydligen visar en praktiskt genomförbar artikel mot F-FCSR-H. Artikeln skall presenteras på Asiacrypt i december, men tydligen stämmer resultatet då eSTREAM valt att plocka bort F-FCSR-H.

Några andra eSTREAM-krypton som inte ser ut att må speciellt bra är Trivium och Salsa 20, speciellt Trivium ser ut att må dåligt.

I höstas kom Adi Shamirs kubattack som i artikeln innehåller en allvarlig attack mot Trivium. Under hösten har även kommit ett par andra attacker mot Trivium.

I oktober kom artikeln Transforming chosen IV attack into a key differential attack: how to break TRIVIUM and similar designs med en komplexitet på 2**68.

En annan artikel, Slid Pairs in Salsa20 and Trivium, som attackerar både Trivium och Salsa 20 kom i slutet av september. Författarna Deike Priemuth-Schmid och Alex Biryukov skriver:

The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is slidable, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams.

There are 2**256 and more then 2**39 such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently.

We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks

Det ser allvarligt ut, men läser man Daniel J Bernsteins svar verkar det inte vara en attack som är bättre än brute force:

These claims are entirely without merit. The “attacks” on Salsa20 are vastly more expensive than the standard brute-force attacks discussed in the original Salsa20 documentation.

Vad gäller Trivium, med tre olika attacker på kort tid, skulle jag inte bli förvånad om den åker ut ur eSTREAM-portföljen och jag skulle vara försiktg att använda den.

Det som gör mig en aning bekymrad är att flera attacker alltså dykt upp strax efter att eSTREAM-projektet avslutats och porföljen presenterats – efter fyra år av utvärderingar.

Om man vore lite konspiratoriskt lagd skulle man kunna få för sig att det är mer prestige och publiceringsvärde i att attackera accepterade och utvalda algoritmer snarare än kandidater. Detta är naturligtvis rent trams, men om det skulle vara så vore det bekymmersamt för forskningen och andra försök att ta fram bra algoritmer – exempelvis för NISTs SHA-3-tävling.

En sista sak om eSTREAM värd att notera är att kryptot Rabbit, enligt en postning av Erik Zenner på eSTREAM-forumet, har fått ändrad licens:

On behalf of Cryptico A/S, the company who designed the Rabbit stream cipher, I’m happy to relay the following:

“Rabbit has been released into the public domain and may be used freely for
any purpose.”

So in retrospect, I think that it was a good decision not to make patent issues a key criterion for the eStream portfolio: The patent status can change, the algorithmic properties can’t.

Tyvärr är inte detta det mest officiella av uttalanden, och dessutom saknar jag information om hur Cryptico avser att agera vad gäller sina patent relaterade till Rabbit. Jag har letat på Cryptico A/S webbplats för att hitta ett mer officiellt uttalande, men där finns inte mycket nyheter.

Jag har kontaktat Erik Zenner för att se om det går att få ett mer officiellt uttalande. Hör jag något publicerar jag det här. eSTREAM-projektets text om licensen för Rabbit har i alla fall inte uppdaterats:

Cryptico A/S currently has patents pending on Rabbit. The algorithm is provided royalty-free for non-commectical use. Licenses for commercial use may be obtained from Cryptico A/S.

Om jag själv skall välja krypton från eSTREAM skulle jag i första hand gå på HC-128 och kanske Salsa 20. I profil två skulle jag välja Grain och Mickey, men då använda versionerna med 128 bit nycklar som inte kostar mer i implementation (bortsett från sex Bytes längre nyckel). Inbyggda system förtjänar lika bra skydd som PC-system.

No comments »

Posted in ECRYPT eSTREAM, Forskning, Krypto

Dagens HW-hack: Wolframs 30:e regel

October 13th, 2008

Jag fick en fråga om kryptorelaterade algoritmer som skulle kunna vara lämpliga att köra som exempel i en kurs om system-modellering. Tanken som jag förstod det var att på TLM-nivå simulera SW-funktioner som sedan flyttas till HW.

Intressanta algoritmer behöver både vara enkla att begripa och kunna ge stor skillnad i prestanda, genomströmning etc när funktionen flyttas från SW till HW. Utifrån detta var mitt förslag RC4 (som är enkel, men inte skalar speciellt bra i HW), XTEA, SHA-1 och SHA-2 (256).

Några andra algoritmer man borde kunna sätta i händerna på studenter är eSTREAM-kryptona Grain och Trivium. Båda dessa krypton är relativt enkla att förstå, har intressanta explicita skalbarhetsegenskaper och är välspecificerade med testvektorer, referensmodeller etc.

Sedan slog det mig att en annan, något annorlunda algoritm som skulle kunna användas är Stephen Wolframs cellautomat Rule 30.

Rule 30 är en endimensionell cellautomat som ger upphov till ett slumpmässigt (PRNG) mönster. Rule 30 används som slumptalsgenerator i Wolfram Research Mathematica. En fördel med att använda en endimensionell cellautomat är att den enkelt går att rita upp och grafiskt verifiera.

De första iterationerna av regel 30 samt de styrande tillståndskombinationerna.

En annan kul egenskap är att algoritmen är trivialt parallelliserbar, detta då alla celler kan uppdateras samtidigt. Antagligen går det att göra bra SW-implementationer, inte minst om man tar till SSE-instruktioner alt GPU-acceleration, men en ren HW-implementation blir väldigt enkel.

Jag blev så inspirerad av Rule 30 att jag satte mig ned och hackade ihop ett par implementationer. Först en version i Python (naturligtvis) för att få koll på att jag tänkte rätt. Det blev inte speciellt många rader kod, ca 20 inkl kommentarer. Och jag är säker på att om man är en riktig Pythonista går algoritmen att stampa ner till ett fåtal rader kod, ex med lite list comprehensions.

Sedan hackade jag ihop en RTL-generator (i Python) som kan generera Verilogkod för en Rule30-automat med godtyckligt antal bitar. Den genererade konstruktionen består väsentligen av ett tillståndsregister med en bit för varje cell. För varje cell finns det sedan en enbitars 8-till-1-MUX som implemeterar uppdateringsregeln.

En sak man behöver fundera på är vad som händer för första resp sista biten i arrayen. Jag har valt att göra en ring av arrayen. Detta innebär att vid uppdatering av den högsta biten tittar vi på bit 0 och tvärs om. Implementationsmässigt innebär detta två separata ledningar som går från kant till kant, inte bara lokalt mellan ett cellregisters närmaste grannar.

Jag genererade några stycken versioner av min Rule 30-konstruktion och använde sedan Alteras verktyg Quartus II för att implementera konstruktionen i en Cyclone II-FPGA. Lite resultat:

256 bitar: 687 LEs, 263 MHz 128 bitar: 344 LEs, 358 MHz 64 bitar: 128 LEs, 420 MHz 32 bitar: 64 LEs, 420 MHz 16 bitar: 32 LEs, 420 MHz 8 bitar: 16 LEs, 420 MHz

(Notera att implementationen kräver lika många register som bitar, jag redovisar dock inte det här.)

En snabb analys ger att varje MUX (samt logik för att ladda in ett användarstyrt initialvärde) implementeras med två logikelement (LE). Mellan 64 och 128 bitar ser det ut som att någon form av replikering behöver införas.

Vad gäller klockfrekvensen är 420 MHz max som Cyclone II är specad för. I en annan FPGA, ex Stratix III går det antagligen att få upp klockfrekvensen ytterliggare en bit. Eftersom uppdateringsfunktionen för resp bit består av en 8-1-MUX med ett grinddjup motsvarande ungefär tre NAND2-grindar eller en LE, blir det transportfördröjningen genom FPGA:ns switchnät som sätter gränsen för klockfrekvensen.

Nu är Rule 30 inte en kryptografiskt säker PRNG, men för att vara en PRNG som ger så bra slumpserier så att den duger för Mathematica förbrukar den väldigt lite resurser. Och med 256 PRNG-bitar varje cykel i 263 MHz får vi 67 Gbit/s! (Vilket skulle vara hopplöst att få ut på ett kort och använda utanför FPGA:n.)

Jag tänker slänga upp en version av Verilogkoden, antigen här eller hos InformAsic. Återkommer med det. Nästa steg är att att bygga ut generatorn med stöd för resursdelning, men det gör jag inte i kväll i alla fall.

Att cellautomater har försökt användas i kryptosammanhang finns det flera artiklar som vittnar om. Jag hittade en färsk sådan med titeln LCASE: Lightweight Cellular Automata-based
Symmetric-key Encryption som just tar upp Rule 30. Värd att läsa om du vill veta mer.

4 comments »

Posted in ECRYPT eSTREAM, Forskning, Hårdvara, Krypto, Python

Tags: Forskning Hårdvara Krypto Python

Kubattacker mot kryptografiska funktioner

September 15th, 2008

En av de mest uppmärksammade händelserna på den för ungefär en månad sedan avslutade Crypto-konferensen var en presentation av Adi Shamir om en ny typ av attackmetod mot kryptografiska metoder kallad kubattack.

Adi Shamir

När metoden presenterades fanns inget om den nya metoden publicerat. Detta ledde till en hel del diskussioner och spekulationer på maillistor. Exempelvis diskuterades det mycket om krypton som AES, Twofish är sårbara.

David Wagner skrev ett par längre inlägg på Cryptography-listan (inlägg ett, inlägg två). David skrev bland annat:

Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR).

Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits… but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits.

Nu har artikeln Cube Attacks on Tweakable Black Box Polynomials av Itai Dinur and Adi Shamir publicerats på IACR. Författarna skriver i artikelns (långa) sammanfattning:

Almost any cryptographic scheme can be described by tweakable polynomials over GF (2), which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables.

In this paper we develop a new technique (called a cube attack) for solving such tweakable polynomials, which is a major improvement over several previously published attacks of the same type.

For example, on the stream cipher Trivium with a reduced number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier) requires a barely practical complexity of 2**55 to attack 672 initialization rounds, whereas a cube attack can ﬁnd the complete key of the same variant in 2**19 bit operations (which take less than a second on a single PC). Trivium with 735 initialization rounds (which could not be attacked by any previous technique) can now be broken with 2**30 bit operations, and by extrapolating our experimentally veriﬁed complexities for various sizes, we have reasons to believe that cube attacks will remain faster than exhaustive search even for 1024 initialization rounds.

Whereas previous attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds, and were not expected to succeed on random looking polynomials, cube attacks are provably successful when applied to random polynomials of degree d over n secret variables whenever the number m of public variables exceeds d + logd n. Their complexity is 2d−1 n + n2 bit operations,
which is polynomial in n and amazingly low when d is small.

Cube attacks can be applied to any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing is known about its internal structure) as long as at least one output bit can be represented by (an unknown) polynomial of relatively low degree in the secret and public variables. In particular, they can be easily and automatically combined with any type of side channel attack that leaks some partial information about the early stages of the encryption process (which can typically be
represented by a very low degree polynomial), such as the Hamming weight of a byte written into a register.

Publiceringen av artikeln har skapat nya diskussioner, exempelvis på Bruce Schneiers blog.

Min uppfattning om Adi Shamir är att han är en av världens absolut bästa kryptologer, risken att han skulle missat fullständigt och metoden inte alls fungerar tror jag är liten. Men jag kan villigt erkänna att jag kan för lite krypanalys för att göra en vettig bedömning av den nya metoden.

Om det Itai Dinur och Adi Shamir skriver stämmer borde detta vara ett stort steg framåt för kryptanalysen. Och lackmustestet kommer antagligen att vara om det dyker upp en ny våg av attacker mot olika specifika funktioner så fungerar kubattacken.

Att Trivium, en av de nyligen utsedda algoritmerna i eSTREAM-portföljen (och lite av en personlig favorit) skulle få problem så här nära efter avslutningen av eSTREAM visar hur en ny metod plötsligt kan kullkasta flera år av analysarbete.

Vi kommer med stor sannolikhet att få återkomma till den här nya attackmetoden. Inte minst under AHS-tävlingen kommer kubattacken antagligen att uppmärksammas.

6 comments »

Posted in ECRYPT eSTREAM, Forskning, Krypto

Tags: estream Forskning Krypto

Jag, Python och kryptot HC-128

May 5th, 2008

Jag har ägnat några timmar den senaste dryga veckan med att implementera eSTREAM~~kryptot HC~~128.

Målet är egentligen att skapa en IP-core-generator, dvs ett program som kan generera ett antal olika implementationer, beroende på vilken prestanda som applikationen kräver och vilken storlek på konstruktionen som är acceptabel. Som jag brukar implementera krypton på InformAsic.

När jag bygger en generator av en funktion (ett krypto en hashfunktion etc) brukar jag börja med att skriva en SW-modell utifrån specifikationen. Ja, även om det redan finns en referensmodell. Skälet är helt enkelt att när jag arbetar med att skriva modellen får jag chans att arbeta rent konkret med specifikationen, se om jag begriper den och om den är entydig.

Att bygga en första modell gör även att jag hinner tänka igenom vad en HW-implementation kommer att kräva. Få koll på minnen, register och möjligheter att parallellisera. Se vilka resurser som i en HW-implementation skulle gå att dela på etc.

Själva generatorn skriver jag numera alltid i Python med diverse egenutvecklade klasser för att skapa generatorer för IP-cores. Och SW-modellen brukar jag skriva i C.

Men den här gången tänkte jag testa att göra även SW-implementationen i Python. Eftersom jag inte är ute efter att få en SW-modell som ger maximal prestanda, utan är funktionellt korrekt och uppdelad på ett sätt som stödjer verifieringen av HW-modellerna borde Python fungera bra.

Men Python är inte riktigt som C. En sak som skiljer är vad jag kallar för Pythons butler-inställning till problemlösning. (Om du verkligen vill skjuta dig i foten ställer Python snällt upp utan att klaga, och hjälper till så att du kan skjuta dig i foten på det sätt du vill.) Detta inkluderar att anpassa variabeltyper dynamiskt. Ett exempel på detta är skiftoperatorn:

>>> kalle 42 >>> kalle = kalle < < 33 >>> kalle 360777252864L

Exemplet ovan visar hur jag skapar mig en variabel kalle och tilldelar den ett litet heltal. Sedan skiftar jag kalle bitmässigt 33 bitar åt vänster. Hade detta varit i C och kalle var en (unsigned) int hade värdet på kalle varit noll. Men Python upptäcker att hoppsan! här är vi på väg att skifta bitar över kanten, och lägger helt enkelt till fler bitar i representationen för kalle så ingen information går förlorad.

Det här är en jättebra funktion i Python som gör att man (i stort sett) helt kan ignorera vad som händer internt, utan bara räkna på med godtyckligt stora tal. Det går exempelvis utmärkt att göra så här:

>>> kalle = kalle < < 100 >>> kalle 3241325209585634862861534625792L

Väldigt mycket datalogi och elegant. Men oj vad det inte funkar när man vill pilla runt på bitar – vilket man ofta gör i krypton.

Så nu har jag fått klura ut hur jag skall arbeta runt Pythons hjälpsamhet, något Python också snällt ställer upp på. Det blir en del hjälpfunktioner för att AND:a och MOD:a, men det går framåt. Jag har även sneglat på att använda array-modulen. Över huvud taget är val av representation något jag funderat mycket på. Jag vill få en modell med bra överblick över den interna implementationen, men jag vill även få en modell som är vettig att använda, dvs den får ett bra och normalt/användbart API.

Tyvärr har jag inte helt lyckats. Jag får fram en modell av som snurrar på bra och fint. Dock får jag inte ut rätt svar enligt de testvektorer som finns i specifikationen för HC-128. Modellen är inte korrekt.

I ren desperation/ilska hackade jag då snabbt samman en implementation i C. Den modellen är, trots att den inte är skriven för någon prestanda över huvud taget riktigt snabb. Jag får drygt 3 Gbit/s på min MacBook. Problemet är att den inte heller räknar rätt…

Jag sitter alltså med två SW-modeller, en i objektorienterad iPython och en i fulkodad C. Ingen av modellerna räknar rätt, och dom räknar inte heller lika utan ger olika fel svar på samma testvektorer.

Men jag ger inte upp! Ny vecka och nya tag! Och dessutom har jag klurat ut hur en HW-implementation bör se ut – om jag nu kan få till en sådan som dessutom räknar rätt.

Ang HC-128 och HW-implementation bör jag kanske säga att även om kryptot är rasande snabbt i SW är det ett krypto med bra möjligheter både till parallellism och till resursdelning – så jag tror att en HW-implementation är intressant och kan bli mycket bra. Det är svårt att banta bort de stora registerbankarna P, Q och W, så implementationen kräver rätt mycket register. Vad man kan laborera med är mängden läsportar, och därmed hur P, Q pch Q implementeras.

När jag fått min HW-generator att fungera kommer jag att publicera lite resultat. Och när jag får jag ordning på min Python-modell av HC-128 lägger jag upp koden här på Kryptoblog.

2 comments »

Posted in ECRYPT eSTREAM, Krypto, Python

Tags: Krypto Python

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?

No comments »

Posted in ECRYPT eSTREAM, Forskning, Krypto

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

2 comments »

Posted in ECRYPT eSTREAM, Forskning, Hårdvara, Inbyggda system, Krypto

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.

På 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 oﬀ 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.

4 comments »

Posted in ECRYPT eSTREAM, Krypto

Analys av tidbaserade sidoattacker av eSTREAM-finalister

February 27th, 2008

(Det händer otroligt mycket på krypto- och IT-säkerhetsområdet just nu. Tyvärr hinner jag inte alls med… Men bloggen är inte död, det är jag som är seg…)

I januari anordnades ett seminarie om symmetriska krypton kallat ECS 2008, och det finns en Wiki som dokumenterar vad som skedde på seminariet. En av de saker som presenterades på seminariet var ett arbete av Erik Zenner om sidoattacker mot eSTREAM-kandidater.

I presentationen Cache Timing Analysis of eStream Finalists tittar Zenner på hur känsliga de olika eSTREAM-finalisterna är för varians i exekveringstid som uppkommer på grund av algoritmernas accessmönster gör att minnesaccesser träffar eller missar i cacheminnen. Denna typ av fick stor uppmärksamhet av den attack mot AES Daniel J Bernstein presenterade för några år sedan.

Det Bernstein pekade på är att tabeller (S-boxar) lätt leder till missar i cacheminnen vilket ger upphov till mätbara tidsvarianser. Det är därför värt att titta på vilka av eSTREAM-finalisterna som har S-boxar och det ser ut så här:
Dragon: Två tabeller, 8×32 bit HC-128: Två tabeller, 9×32 bit HC-256: Två tabeller, 10×32 bit LEX-128: En tabell, 8×8 bit (referenskod) Lex-128: Åtta tabeller, 8×32 bit (optimerad kod) NLS: En tabell, 8×32 bit S-Box Rabbit: Ingen tabell Salsa-20: Ingen tabell Sosemanuk: En tabell, 8×32 bit. Åtta tabeller 4×4 bit

Notera att detta bara är finalisterna för profilen avsedd för SW-implementation i modern PC eller server. Jag hade gärna sett att man även undersökt kandidaterna avsedda för inbyggda system och HW-implementation.

Det Erik Zenner kommit fram till är:

Salsa-20 is designed to be resistant to Cache Timing Attacks.

CryptMT and Rabbit are resistant, probably by accident.

LEX falls to the same attacks as AES, since it uses AES for key/IV setup.

Dragon, HC-256/128, NLS, and Sosemanuk have to be analysed.

Och Eriks slutsats så här långt är att:

Surprise: Most candidates seem to withstand analysis even in the generous model surprisingly well (not unbreakable, but complicated).

With the exception of Salsa, the eStream ﬁnalists were not designed to resist cache timing attacks. In addition, the attack model is very generous to the adversary. Nonetheless, they seem to withstand an attack where the adversary learns a lot about the inner state surprisingly well.

Zenners arbete är alltså inte avslutat, men så här långt ser det alltså inte ut som att någon av finalisterna lider svårt av den här typen av attacker. Skönt.

No comments »

Posted in ECRYPT eSTREAM, Krypto

Lite statistik för eSTREAM-kandidater

January 21st, 2008

Jag sitter och söndagsfunderar på vilka eSTREAM-kandidater i fas tre som till slut blir rekommenderade strömkrypton.

Det vi borde kunna göra är att titta på de utvärderingar som gjorts så här långt. Vi behöver titta både på prestanda och komplexitet samt hur man vid avslut av fas två röstat – vilka kandidater som tidigare varit mest populära. Här är en sammanställning av fas tre-kandidaterna och det viktade röstresultatet:

SW-profil
Salsa20 1.80
SOSEMANUK 1.03
HC 128/256 1.08
LEX 0.90
Rabbit 0.88
Dragon 0.47
CryptMT 0.29
NLS -0.60

HW-profil
Grain 1.63
Trivium 1.54
Mickey128 0.66
F-FCSR 0.29
LEX 0.21
Mickey 0.11
Edon80 0.00
Pomaranch −0.38
DECIM −0.39
Moustique −0.65

För de kandidater som förekommer flera gånger (ex Salsa20) har jag valt att ta det värde som är högst. Här ser vi att Salsa20 ligger i topp för SW-profilen följd av SOSEMANUK och HC. CryptMT och NLS är de minst populära SW-kandidaterna.

I HW-profilen ligger Grain i topp, tätt följd av Trivium och MICKEY. I botten ligger DECIM och Moustique.

Ett annat sätt att mäta skulle kunna vara att titta på antalet artiklar med resultat från någon form av kryptanalys samt antalet uppdateringar som har kommit till specifikationen för kandidaten.

Visst, eftersom artiklarna innehåller så otroligt skilda resultat blir det att jämföra apelsiner med lime och chili (eller nåt). Men jag tycker ändå att detta bör vara relevant. Har det uppdagats många svagheter och modifieringar till specifikationen tror jag att den kandidaten är mindre intressant än en som visat sig vara stabil.

Jag gjorde en snabb sammanställning baserad på vad som publicerats hos eSTREAM för respektive kandidat vad gäller kryptanalys och uppdatering av specifikationerna och fick följande:

CryptMT: 2
Dragon: 3
HC: 0
LEX: 3
NLS: 3
Rabbit: 2
Salsa20: 5
SOSEMANUK: 2
DECIM: 2
Edon80: 6
F-FCSR: 3
Grain: 3
MICKEY: 2
Moustique: 2
Pomaranch: 9
Trivium: 5

Här sticker HC ut genom att det inte kommit en enda artikel med kryptanalys som visar på någon svaghet. Pomaranch och Edon80 å andra sidan är de kandidater med flest publicerade resultat från kryptanalys samt uppdateringar till specifikationen. Dock kommer det på FSE 2008 att publiceras två artiklar med analysresultat för Salsa20 samt en för Trivium, vilket gör att dessa seglar upp i statistiken.

Skall man utifrån dessa två datamängder försöka sig på en gissning skulle jag tro att HC kommer att vara en av de krypton från SW-profilen eSTREAM kommer att rekommendera. För HW-profilen skulle jag satsa mina slantar på minst en av Grain, Trivium eller MICKEY.

Vad tror du?

3 comments »

Posted in ECRYPT eSTREAM, Forskning, Krypto

Mer om säkerhet i inbyggda system

October 16th, 2007

Det kommer mycket artiklar just nu om säkerhet i inbyggda system. Det känns som att branschen har börjat vakna till och inse att man behöver tänka på säkerheten – speciellt när man börjar gå från lokala system i ett apparatskåp till system med fjärröverkning och kontroll. En iofs gammal men bra översiktsartikel är Securing wireless MCUs is changing embedded system design från Embedded.com.

Artikeln tar upp just problemställningen att allt fler system kopplas upp – ofta med trådlösa kommunikationstekniker, men att det innebär förändrade säkerhetsmodeller:

Inbyggda system - uppkopplade över Internet.
En sak de tar upp i artikeln är hur (illa) krypton är anpassade till inbyggda system. Till våren kommer förhoppningsvis avslutningen av eSTREAM att ge oss mer än ett krypto som fungerar bra även för inbyggda system.

Förra veckan var det Scanautomatic i Göteborg. Jag var där, och det vimlade av olika typer av PLC:er, styrsystem, kontrollplattformar för industriautomation. Jag hittade en (1) leverantör som kunde svara på frågan hur dom skyddade kommunikationen (med SSL) – alla andra undrade vad jag menade.

Även om deras system-modeller ofta var att maskinerna skulle kopplas in på lokalnätet (LAN) var det påfallande många som pratade om publik IP-adress. Och, naturligvis, allt styrt via ett webbgränssnitt. Det finns mer att göra…

No comments »

Posted in ECRYPT eSTREAM, Hårdvara, Inbyggda system, Internet, Krypto

« Older Entries