Cryptanalysis of Selected Stream Ciphers

Sammanfattning: 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.