Cryptanalysis of Selected Stream Ciphers

Abstract

The aim of this dissertation is to show some cryptanalytical results on a selection of stream ciphers. We have grouped theory and results into three main parts.



The first part focuses on the FCSR-based constructions X-FCSR and F-FCSR-H v3. For the X-FCSR family of stream ciphers we perform a severe state recovery attack. This attack works for both X-FCSR-128 and X-FCSR-256.



We then develop a generalized birthday algorithm for finding linear relations in FCSRs. This algorithm applies to the most recent and general FCSR architecture, the ring FCSR, so it can be used for analyzing the FCSR of any FCSR-based design. We apply the algorithm to produce an efficient distinguisher for F-FCSR-H v3, which was previously unbroken.



The second part of the dissertation covers topics related to the HC family of stream ciphers. First, a very general treatment of sampling methods is presented. Surprisingly, perhaps, a positive result is given. We prove that an efficient sampling method based on sampling vector weights is optimal in a given context. This sampling technique is employed to produce the best known distinguisher for HC-128.



We go on to show a few theoretical results on functions that use word rotation and xor. These results are applied to a modified variant of HC-128, and this application shows how the theory could be used in a cryptanalytical scenario. It also shows the important role of the addition operator in HC-128, without which the cipher would be much less secure.



In the third part of the dissertation we analyze stream ciphers, and block ciphers to a lesser extent, using algebraic methods. We develop a simple and intuitive greedy algorithm for automatic security testing of cryptographic primitives. This is done in a black box fashion, without using any information on the internal structure of the primitives. Despite this, it is shown how structural information is revealed very clearly under certain circumstances. The main features here are some nice results for the well-known stream ciphers Trivium, Grain-128 and Grain v1.

Abstract (Swedish)

Popular Abstract in Swedish

Kryptering kan användas när man vill hålla något viktigt meddelande hemligt, till exempel vid en bankbetalning på Internet. Men hur vet man att krypteringsalgoritmen (sättet att kryptera på) är tillräckligt säker? Hur vet man att ingen kan läsa vårt meddelande eller ändra i det så att, till exempel, en överföring av pengar från ett konto till ett annat går till någon helt annan? Det är detta vi har kryptoanalys till, för att kontrollera att säkerhetskrav som ställs på krypteringsalgoritmen är uppfyllda.



Om två parter snabbt och effektivt ska skicka hemliga meddelanden mellan sig, är det vanligt att dessa två kommer överens om en hemlig nyckel som ingen annan känner till. Att båda sidor har samma hemliga nyckel kallas för ett symmetriskt kryptosystem, och det finns huvudsakligen två typer av symmetriska krypteringsalgoritmer; blockchiffer och strömchiffer.



Ett blockchiffer är som en låda där man stoppar in den hemliga nyckeln och det läsbara meddelandet i ena änden, och ut ur lådan kommer det oläsliga krypterade meddelandet, kryptotexten. Mottagaren kan sedan använda lådan på motsvarande sätt genom att stoppa in den hemliga nyckeln och den oläsliga kryptotexten, och får då ut den ursprungliga läsbara texten. Mottagaren har då dekrypterat meddelandet.



Ett strömchiffer fungerar lite annorlunda. I en strömchifferlåda stoppas huvudsakligen en hemlig nyckel in, och ut kommer en lång sekvens av nollor och ettor som ser slumpmässig ut. Denna sekvens kallas nyckelström, och när man ska kryptera ett meddelande tar man en del av denna nyckelström och lägger ihop med det läsbara meddelandet på ett mycket enkelt sätt. Den som ska dekryptera använder lådan för att först generera samma nyckelström, och lägger sedan ihop denna med kryptotexten. När man lägger ihop samma nyckelström två gånger tar dessa ut varandra så att man får tillbaka den läsbara texten igen.



Mottagare som använder blockchiffer måste ha tillgång till kryptotexten. Med ett strömchiffer kan man, däremot, redan innan man har fått tillgång till kryptotexten, generera en stor mängd nyckelström i förväg. Denna kan sedan används för att mycket snabbt och enkelt få fram klartexten.



Ett strömchiffer kan alltså med fördel användas när man behöver kryptera mycket data snabbt, där man inte kan vänta på att utföra hela dekrypteringen tills kryptotexten anländer. Till exempel används strömchiffer på detta sätt i bakgrunden när vi pratar i mobiltelefon, eller tittar på kabelkanaler på TV.



I denna avhandling undersöks strömchiffer, och man kan analysera dessa på många olika sätt. Det är meningen att strömchiffrens nyckelström ska se helt slumpmässig ut. Även om man får undersöka nyckelström så ska det inte kunna gå att lista ut vilken hemlig nyckeln som använts för att skapa den. Lyckas man rekonstruera nyckeln så räknas det som en mycket kraftfull attack (nyckelattack). Det ska heller inte gå att från nyckelström lista ut vad lådan innehåller, att återskapa dess tillstånd (tillståndsattack). Man ska inte ens med hjälp av statistiska metoder kunna särskilja nyckelström från en äkta slumpmässig sekvens av nollor och ettor (urskiljningsattack).



Avhandlingen består av tre huvuddelar. I den första delen visas det att de välkända strömchiffren X-FCSR och F-FCSR-H inte alls fungerar så bra som man tidigare har trott. På X-FCSR utförs en mycket kraftfull tillståndsattack, och för F-FCSR-H visas hur man effektivt kan hitta matematiska samband i nyckelström (urskiljningsattack). Den sistnämnda attacken, urskiljningsattacken, fungerar inte bara på F-FCSR-H som helhet, utan den fungerar på en av chiffrets byggstenar, FCSRen. Eftersom samma byggsten används i flera andra chiffer, kan denna metod användas för att analysera alla dessa chiffer. Slutsatsen här är att man inte bör använda sig av X-FCSR och F-FCSR-H, och dessutom behöver man tänka sig för om man bygger nya strömchiffer med hjälp av FCSRer.



I den andra delen analyseras strömchiffret HC-128 och dess beståndsdelar. Där utgås det från den analys som designern till HC-128 själv presenterade. Vi byter ut en statistisk metod, en så kallad samplingsmetod mot en annan, och får därmed den bästa urskiljningsattacken som hittills visats för HC-128. Dessutom visas det att denna samplingsmetod är optimal, d.v.s. att den inte går att göra bättre. Trots detta är attacken inte tillräckligt effektiv, slutsatsen blir här att HC-128 fortfarande är användbar. Positivt är att den optimala samplingsmetoden som presenterats är generell, vilket innebär att den går att använda för att analysera andra algoritmer också.



I den sista delen görs en algebraisk analys. Denna går huvudsakligen ut på att ett strömchiffer betraktas som en matematisk funktion eller som ett ekvationssystem. En ny beräkningsmetod presenteras, och det visas hur beräkningsmetoden kan användas på nästan alla strömchiffer, men med varierande resultat. För de två kanske mest kända strömchiffren som är ämnade för hårdvarutillämpningar, Trivium och Grain-128, fungerar denna dock alldeles utmärkt, med nya kryptoanalytiska rekord som resultat. Både i form av olika urskiljningsattacker och liknande metoder.

• author: Stankovski, Paul
• supervisor: Thomas Johansson; Martin Hell
• opponent: Dr. Canteaut, Anne, INRIA Paris-Rocquencourt, France
• organization: Department of Electrical and Information Technology; Crypto and Security-lup-obsolete (research group); ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• publishing date: 2013
• type: Thesis
• publication status: published
• subject: Electrical Engineering, Electronic Engineering, Information Engineering
• keywords: Stream cipher, cryptanalysis, FCSR, state recovery, linear relations, optimal sampling, distinguisher, HC, nonrandomness, greedy bit set algorithm.
• in: Series of licentiate and doctoral dissertations
• volume: 50
• defense location: Lecture hall E:1406, Ole Römers väg 3, Lund University Faculty of Engineering
• defense date: 2013-06-17 10:15:00
• ISSN: 1654-790X
• ISBN: 978-91-7473-526-0 (Online)
• ISBN: 978-91-7473-525-3 (Print)
• language: English
• LU publication?: yes
• id: a86c893d-6bb3-4a92-be10-6c8cc0307985 (old id 3799743)
• date added to LUP: 2016-04-01 13:19:11
• date last changed: 2019-05-24 08:39:31