Kryptanalys

Innan moderna datormetoder användes speciella maskiner för att kryptera och dekryptera textmeddelanden. Närbild av rotorerna i en chiffermaskin

Kryptanalys (från grekiskan kryptós , "dold", och analýein , "att analysera") syftar på processen att analysera informationssystem för att förstå dolda aspekter av systemen. Krypteringsanalys används för att bryta mot kryptografiska säkerhetssystem och få tillgång till innehållet i krypterade meddelanden, även om den kryptografiska nyckeln är okänd.

Förutom matematisk analys av kryptografiska algoritmer inkluderar kryptoanalys studiet av sidokanalsattacker som inte riktar sig mot svagheter i själva kryptoalgoritmerna, utan istället utnyttjar svagheter i deras implementering.

Även om målet har varit detsamma, har metoderna och teknikerna för kryptoanalys förändrats drastiskt genom kryptografins historia, anpassat till ökande kryptografisk komplexitet, allt från det förflutnas penna-och-papper-metoder till maskiner som de brittiska Bombes och Colossus-datorer i Bletchley Park under andra världskriget , till dagens matematiskt avancerade datoriserade system. Metoder för att bryta moderna kryptosystem involverar ofta att lösa noggrant konstruerade problem i ren matematik , den mest kända är heltalsfaktorisering .

Översikt

Vid kryptering skickas konfidentiell information (kallad " klartext " ) säkert till en mottagare genom att avsändaren först konverterar den till en oläsbar form ( " chiffertext " ) med hjälp av en krypteringsalgoritm . Chiffertexten skickas via en osäker kanal till mottagaren. Mottagaren dekrypterar chiffertexten genom att använda en invers dekrypteringsalgoritm , som återställer klartexten. För att dekryptera chiffertexten kräver mottagaren en hemlig kunskap från avsändaren, vanligtvis en sträng av bokstäver, siffror eller bitar , som kallas en kryptografisk nyckel . Konceptet är att även om en obehörig person får tillgång till chiffertexten under överföringen, utan den hemliga nyckeln kan de inte konvertera den tillbaka till klartext.

Kryptering har använts genom historien för att skicka viktiga militära, diplomatiska och kommersiella meddelanden, och används idag mycket i datornätverk för att skydda e-post och internetkommunikation.

Målet med kryptoanalys är att en tredje part, en kryptoanalytiker , ska få så mycket information som möjligt om originalet ( " klartext " ), försöka "bryta" krypteringen för att läsa chiffertexten och lära sig den hemliga nyckeln så att framtida meddelanden kan skickas dekrypteras och läser. En matematisk teknik för att göra detta kallas en "''kryptografisk attack''"Kryptografiska attacker kan karakteriseras på ett antal sätt:

Mängden information tillgänglig för angriparen

Attacker kan klassificeras baserat på vilken typ av information angriparen har tillgänglig. Som en grundläggande utgångspunkt antas normalt att den generella algoritmen är känd för analysändamål; detta är Shannons Maxim "fienden känner systemet" – i sin tur, motsvarande Kerckhoffs princip . Detta är ett rimligt antagande i praktiken – genom historien finns det otaliga exempel på hemliga algoritmer som hamnar i bredare kunskap, olika genom spionage , svek och omvänd ingenjörskonst . (Och ibland har chiffer brutits genom ren deduktion; till exempel det tyska Lorenz-chifferet och den japanska lila-koden , och en mängd klassiska scheman):

Beräkningsresurser krävs

Attacker kan också kännetecknas av de resurser de kräver. Dessa resurser inkluderar:

  • Tid – antalet beräkningssteg (t.ex. testkrypteringar) som måste utföras.
  • Minne – mängden lagringsutrymme som krävs för att utföra attacken.
  • Data – mängden och typen av klartexter och chiffertexter som krävs för ett visst tillvägagångssätt.

Det är ibland svårt att förutsäga dessa kvantiteter exakt, särskilt när attacken inte är praktisk att faktiskt implementera för testning. Men akademiska kryptoanalytiker tenderar att tillhandahålla åtminstone den uppskattade storleksordningen för deras attackers svårighetsgrad, och säger till exempel "SHA-1-kollisioner nu 2 52 ."

Bruce Schneier noterar att även beräkningsmässigt opraktiska attacker kan betraktas som avbrott: "Att bryta ett chiffer betyder helt enkelt att hitta en svaghet i chifferet som kan utnyttjas med en komplexitet som är mindre än brute force. Strunt i att brute-force kan kräva 2 128 krypteringar ; en attack som kräver 2 110 krypteringar skulle betraktas som ett avbrott...enkelt uttryckt kan ett avbrott bara vara en certifieringssvaghet: bevis på att chiffret inte fungerar som det annonseras."

Partiella pauser

Resultaten av kryptoanalys kan också variera i användbarhet. Kryptografen Lars Knudsen (1998) klassificerade olika typer av attacker mot blockchiffer efter mängden och kvaliteten på hemlig information som upptäcktes:

  • Total paus – angriparen härleder den hemliga nyckeln .
  • Global deduktion – angriparen upptäcker en funktionellt likvärdig algoritm för kryptering och dekryptering, men utan att lära sig nyckeln.
  • Instansavdrag (lokalt) – angriparen upptäcker ytterligare klartexter (eller chiffertexter) som inte är kända tidigare.
  • Informationsavdrag – angriparen får Shannon-information om klartexter (eller chiffertexter) som inte tidigare är kända.
  • Särskiljande algoritm – angriparen kan skilja chifferet från en slumpmässig permutation .

Akademiska attacker är ofta mot försvagade versioner av ett kryptosystem, till exempel ett blockchiffer eller hashfunktion med några omgångar borttagna. Många, men inte alla, attacker blir exponentiellt svårare att utföra när rundor läggs till i ett kryptosystem, så det är möjligt för hela kryptosystemet att vara starkt även om varianter av reducerade rundor är svaga. Icke desto mindre kan partiella avbrott som är nära att bryta det ursprungliga kryptosystemet innebära att ett fullständigt avbrott kommer att följa; de framgångsrika attackerna på DES , MD5 och SHA-1 föregicks alla av attacker på försvagade versioner.

I akademisk kryptografi definieras en svaghet eller ett avbrott i ett schema vanligtvis ganska konservativt: det kan kräva opraktiska mängder tid, minne eller kända klartexter. Det kan också kräva att angriparen kan göra saker som många angripare i den verkliga världen inte kan: till exempel kan angriparen behöva välja viss klartext som ska krypteras eller till och med be om att klartext ska krypteras med flera nycklar relaterade till hemligheten nyckel. Dessutom kan det bara avslöja en liten mängd information, tillräckligt för att bevisa att kryptosystemet är ofullkomligt men för lite för att vara användbart för verkliga angripare. Slutligen kan en attack bara gälla en försvagad version av kryptografiska verktyg, som ett blockchiffer med reducerad runda, som ett steg mot att bryta hela systemet.

Historia

Huvudartikel: Kryptografins historia

Kryptanalys har utvecklats tillsammans med kryptografi, och tävlingen kan spåras genom kryptografins historia – nya chiffer som designats för att ersätta gamla trasiga mönster och nya kryptoanalytiska tekniker som uppfunnits för att knäcka de förbättrade systemen. I praktiken ses de som två sidor av samma mynt: säker kryptografi kräver design mot eventuell kryptoanalys.

Klassiska chiffer

Första sidan av Al-Kindis manuskript från 900-talet om att dechiffrera kryptografiska meddelanden
Se även: Frekvensanalys , Index of coincidence , och Kasiski-undersökning

Även om själva ordet " kryptanalys " är relativt nytt (det myntades av William Friedman 1920), är metoder för att bryta koder och chiffer mycket äldre. David Kahn noterar i The Codebreakers att arabiska forskare var de första som systematiskt dokumenterade kryptoanalytiska metoder.

Den första kända registrerade förklaringen av kryptoanalys gavs av Al-Kindi (ca 801–873, även känd som "Alkindus" i Europa), en arabisk polymath från 900-talet, i Risalah fi Istikhraj al-Mu'amma ( A Manuscript on Dechiffrera kryptografiska meddelanden ). Denna avhandling innehåller den första beskrivningen av metoden för frekvensanalys . Al-Kindi betraktas alltså som historiens första kodbrytare. Hans genombrottsarbete var influerat av Al-Khalil (717–786), som skrev Book of Cryptographic Messages , som innehåller den första användningen av permutationer och kombinationer för att lista alla möjliga arabiska ord med och utan vokaler.

Frekvensanalys är det grundläggande verktyget för att bryta de flesta klassiska chiffer . I naturliga språk förekommer vissa bokstäver i alfabetet oftare än andra; på engelska är " E " troligen den vanligaste bokstaven i alla exempel av klartext . På samma sätt digrafen "TH" det mest troliga bokstäverparet på engelska och så vidare. Frekvensanalys bygger på att ett chiffer inte lyckas dölja denna statistik . Till exempel, i ett enkelt substitutionschiffer (där varje bokstav helt enkelt ersätts med en annan), skulle den vanligaste bokstaven i chiffertexten vara en trolig kandidat för "E". Frekvensanalys av ett sådant chiffer är därför relativt enkelt, förutsatt att chiffertexten är tillräckligt lång för att ge ett någorlunda representativt antal bokstäver i alfabetet som den innehåller.

Al-Kindis uppfinning av frekvensanalystekniken för att bryta monoalfabetiska substitutionschiffer var det viktigaste kryptoanalytiska framstegen fram till andra världskriget. Al-Kindis Risalah fi Istikhraj al-Mu'amma beskrev de första kryptoanalytiska teknikerna, inklusive några för polyalfabetiska chiffer , chifferklassificering, arabisk fonetik och syntax, och viktigast av allt, gav de första beskrivningarna om frekvensanalys. Han täckte också metoder för chiffrering, kryptoanalys av vissa chiffrering och statistisk analys av bokstäver och bokstavskombinationer på arabiska. Ett viktigt bidrag från Ibn Adlan (1187–1268) handlade om provstorlek för användning av frekvensanalys.

I Europa var den italienske forskaren Giambattista della Porta (1535–1615) författare till ett framstående arbete om kryptoanalys, De Furtivis Literarum Notis .

Framgångsrik kryptoanalys har utan tvekan påverkat historien; förmågan att läsa andras förmodat hemliga tankar och planer kan vara en avgörande fördel. Till exempel, i England 1587, ställdes Mary, drottning av Skottland inför rätta och avrättades för förräderi som ett resultat av hennes inblandning i tre komplotter för att mörda Elizabeth I av England . Planerna kom fram efter att hennes kodade korrespondens med andra konspiratörer dechiffrerades av Thomas Phelippes .

utvecklades idén om ett polyalfabetisk substitutionschiffer , bland annat av den franske diplomaten Blaise de Vigenère (1523–96). I ungefär tre århundraden Vigenère-chiffret , som använder en upprepande nyckel för att välja olika krypteringsalfabet i rotation, vara helt säkert ( le chiffre indéchiffrable —"det otydliga chifferet"). Icke desto mindre Charles Babbage (1791–1871) och senare, oberoende av varandra, Friedrich Kasiski (1805–81) bryta detta chiffer. Under första världskriget utvecklade uppfinnare i flera länder rotorchiffermaskiner som Arthur Scherbius ' Enigma , i ett försök att minimera upprepningen som hade utnyttjats för att bryta Vigenère-systemet.

Chiffer från första och andra världskriget

Se även: Krypteringsanalys av gåtan och krypteringsanalys av Lorenz-chifferet
Det dekrypterade Zimmermann-telegrammet .

Under första världskriget var brytningen av Zimmermann-telegrammet avgörande för att få USA in i kriget. Under andra världskriget gynnades de allierade enormt av deras gemensamma framgångskrypteringsanalys av de tyska chifferna – inklusive Enigma-maskinen och Lorenz-chifferet – och japanska chiffer, särskilt "Purple" och JN-25 . "Ultra" underrättelser har tillskrivits allt från att förkorta slutet av det europeiska kriget med upp till två år, till att fastställa det slutliga resultatet. Kriget i Stilla havet hjälptes på liknande sätt av "Magic" intelligens.

Kryptering av fiendens meddelanden spelade en betydande roll i de allierades seger i andra världskriget. FW Winterbotham , citerade den västra allierades högsta befälhavare, Dwight D. Eisenhower , vid krigets slut som beskrev Ultra intelligens som att ha varit "avgörande" för allierad seger. Sir Harry Hinsley , officiell historiker för brittisk underrättelsetjänst under andra världskriget, gjorde en liknande bedömning om Ultra och sa att det förkortade kriget "med inte mindre än två år och förmodligen med fyra år"; dessutom sa han att i frånvaro av Ultra är det osäkert hur kriget skulle ha slutat.

I praktiken bygger frekvensanalys lika mycket på språklig kunskap som på statistik, men i takt med att chiffer blev mer komplexa blev matematiken viktigare i kryptoanalys. Denna förändring var särskilt uppenbar före och under andra världskriget , där försök att knäcka axelchiffer krävde nya nivåer av matematisk sofistikering. Dessutom tillämpades automatisering först på kryptoanalys under den eran med den polska Bomba- enheten, den brittiska Bombe , användningen av hålkortsutrustning och i Colossus-datorerna – de första elektroniska digitala datorerna som styrdes av ett program.

Indikator

Med ömsesidiga maskinchiffer som Lorenz-chifferet och Enigma-maskinen som användes av Nazityskland under andra världskriget , hade varje meddelande sin egen nyckel. Vanligtvis informerade den sändande operatören den mottagande operatören om denna meddelandenyckel genom att sända viss klartext och/eller chiffertext före det krypterade meddelandet. Detta kallas indikatorn , eftersom den indikerar för den mottagande operatören hur man ställer in sin maskin för att dechiffrera meddelandet.

Dåligt utformade och implementerade indikatorsystem gjorde att först polska kryptografer och sedan de brittiska kryptograferna vid Bletchley Park kunde bryta Enigma-chiffersystemet. Liknande dåliga indikatorsystem gjorde det möjligt för britterna att identifiera djup som ledde till diagnosen av Lorenz SZ40/42- chiffersystemet, och den omfattande brytningen av dess meddelanden utan att kryptoanalytikerna såg chiffermaskinen.

Djup

Att skicka två eller flera meddelanden med samma nyckel är en osäker process. För en kryptoanalytiker sägs meddelandena då vara "djupgående". Detta kan detekteras av meddelanden som har samma indikator genom vilken den sändande operatören informerar den mottagande operatören om nyckelgeneratorns initiala inställningar för meddelandet.

Generellt sett kan kryptoanalytikern dra nytta av att rada upp identiska krypteringsoperationer bland en uppsättning meddelanden. Till exempel Vernam-chiffret genom bit-för-bit-kombination av klartext med en lång nyckel med operatorn " exklusiv eller ", som också är känd som " modulo-2-addition " (symboliserat med ⊕ ):

Plaintext ⊕ Key = Chiffertext

Dechiffrering kombinerar samma nyckelbitar med chiffertexten för att rekonstruera klartexten:

Chiffertext ⊕ Nyckel = klartext

(I modulo-2 aritmetik är addition detsamma som subtraktion.) När två sådana chiffertexter är justerade på djupet, eliminerar kombinationen av dem den gemensamma nyckeln, vilket bara lämnar en kombination av de två klartexterna:

Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2

De enskilda klartexterna kan sedan utarbetas språkligt genom att pröva troliga ord (eller fraser), även kända som "spjälsängar", på olika platser; en korrekt gissning, när den kombineras med den sammanslagna klartextströmmen, producerar begriplig text från den andra klartextkomponenten:

(Plantext1 ⊕ Plaintext2) ⊕ Plaintext1 = Plaintext2

Det återvunna fragmentet av den andra klartexten kan ofta utökas i en eller båda riktningarna, och de extra tecknen kan kombineras med den sammanslagna klartextströmmen för att utöka den första klartexten. Genom att arbeta fram och tillbaka mellan de två klartexterna, med hjälp av förståelighetskriteriet för att kontrollera gissningar, kan analytikern återställa mycket eller alla de ursprungliga klartexterna. (Med endast två klartexter på djupet kanske analytikern inte vet vilken som motsvarar vilken chiffertext, men i praktiken är detta inte ett stort problem.) När en återställd klartext sedan kombineras med sin chiffertext avslöjas nyckeln:

Plaintext1 ⊕ Ciphertext1 = Nyckel

Kunskap om en nyckel tillåter sedan analytikern att läsa andra meddelanden krypterade med samma nyckel, och kunskap om en uppsättning relaterade nycklar kan tillåta kryptoanalytiker att diagnostisera systemet som används för att konstruera dem.

Utveckling av modern kryptografi

Regeringar har länge insett de potentiella fördelarna med kryptoanalys för underrättelseverksamhet , både militär och diplomatisk, och etablerat dedikerade organisationer som ägnas åt att bryta koder och chiffer från andra nationer, till exempel GCHQ och NSA , organisationer som fortfarande är mycket aktiva idag.

Bomben replikerade handlingen från flera Enigma-maskiner kopplade ihop . Var och en av de snabbt roterande trummorna, på bilden ovan i en Bletchley Park- museumsmockup, simulerade verkan av en Enigma-rotor.

Även om beräkning användes med stor effekt i kryptoanalysen av Lorenz-chifferet och andra system under andra världskriget, gjorde det också möjliga nya metoder för kryptografi i storleksordningar mer komplexa än någonsin tidigare. Sammantaget har modern kryptografi blivit mycket mer ogenomtränglig för kryptoanalys än tidigare penna-och-papperssystem och tycks nu ha övertaget mot ren kryptoanalys. [ citat behövs ] Historikern David Kahn noterar:

Många är de kryptosystem som erbjuds av de hundratals kommersiella leverantörerna idag som inte kan brytas med några kända metoder för kryptoanalys. Faktum är att i sådana system inte ens en vald klartextattack , där en vald klartext matchas mot dess chiffertext, kan inte ge nyckeln som låser upp andra meddelanden. På sätt och vis är alltså kryptoanalys död. Men det är inte slutet på historien. Kryptanalys kan vara död, men det finns – för att blanda mina metaforer – mer än ett sätt att flå en katt.

Kahn fortsätter med att nämna ökade möjligheter för avlyssning, buggning , sidokanalattacker och kvantdatorer som ersättningar för de traditionella metoderna för kryptoanalys. 2010 sa den tidigare tekniska chefen för NSA Brian Snow att både akademiska och statliga kryptografer "går mycket långsamt framåt i ett moget område."

Eventuella obduktioner för kryptoanalys kan dock vara för tidigt. Medan effektiviteten hos kryptoanalytiska metoder som används av underrättelsetjänster fortfarande är okänd, har många allvarliga attacker mot både akademiska och praktiska kryptografiska primitiver publicerats i den moderna eran av datorkryptografi: [ citat behövs ]

Således, även om de bästa moderna chiffern kan vara mycket mer motståndskraftiga mot kryptoanalys än Enigma , förblir kryptoanalys och det bredare området informationssäkerhet ganska aktiva.

Symmetriska chiffer

Asymmetriska chiffer

Asymmetrisk kryptografi (eller kryptografi med offentlig nyckel ) är kryptografi som förlitar sig på att använda två (matematiskt relaterade) nycklar; en privat och en offentlig. Sådana chiffer förlitar sig alltid på "hårda" matematiska problem som grund för sin säkerhet, så en uppenbar attackpunkt är att utveckla metoder för att lösa problemet. Säkerheten för tvånyckelskryptografi beror på matematiska frågor på ett sätt som enkelnyckelkryptografi i allmänhet inte gör, och omvänt kopplar kryptoanalys till bredare matematisk forskning på ett nytt sätt.

Asymmetriska scheman är utformade kring den (förmodade) svårigheten att lösa olika matematiska problem. Om en förbättrad algoritm kan hittas för att lösa problemet är systemet försvagat. Till exempel beror säkerheten för Diffie–Hellman-nyckelutbytesschemat på svårigheten att beräkna den diskreta logaritmen . 1983 Don Coppersmith ett snabbare sätt att hitta diskreta logaritmer (i vissa grupper), och därigenom krävde kryptografer att använda större grupper (eller olika typer av grupper). RSA:s säkerhet beror (delvis) på svårigheten med heltalsfaktorisering – ett genombrott inom factoring skulle påverka RSA:s säkerhet. [ citat behövs ]

1980 kunde man faktorisera ett svårt 50-siffrigt nummer till en kostnad av 10 12 elementära datoroperationer. År 1984 hade teknikens ståndpunkt inom factoringalgoritmer avancerat till en punkt där ett 75-siffrigt tal kunde faktoriseras i 10 12 operationer. Framsteg inom datorteknik innebar också att operationerna kunde utföras mycket snabbare också. Moores lag förutspår att datorhastigheterna kommer att fortsätta att öka. Faktoreringstekniker kan fortsätta att göra det också, men kommer med största sannolikhet att bero på matematisk insikt och kreativitet, vilket aldrig har varit framgångsrikt förutsägbart. 150-siffriga nummer av det slag som en gång användes i RSA har räknats in. Ansträngningen var större än ovan, men var inte orimlig på snabba moderna datorer. I början av 2000-talet ansågs 150-siffriga nummer inte längre vara en tillräckligt stor nyckelstorlek för RSA. Siffror med flera hundra siffror ansågs fortfarande vara för svåra att faktorisera under 2005, även om metoderna troligen kommer att fortsätta att förbättras med tiden, vilket kräver nyckelstorlek för att hålla jämna steg eller andra metoder som elliptisk kurvkryptografi som ska användas. [ citat behövs ]

Ett annat utmärkande drag för asymmetriska scheman är att, till skillnad från attacker på symmetriska kryptosystem, alla kryptoanalyser har möjlighet att använda kunskap som erhållits från den publika nyckeln .

Attackerar kryptografiska hashsystem

Sidokanalattacker

Huvudartikel: Sidokanalattack

Kvantberäkningsapplikationer för kryptoanalys

Kvantdatorer , som fortfarande befinner sig i de tidiga forskningsfaserna, har potentiell användning i kryptoanalys. Till exempel Shor's Algorithm faktorisera stora tal i polynomtid , vilket i själva verket bryter några vanliga former av kryptering med offentlig nyckel.

Genom att använda Grovers algoritm på en kvantdator kan brute-force nyckelsökning göras kvadratiskt snabbare. Detta skulle dock kunna motverkas genom att dubbla nyckellängden.

Se även

Historiska kryptoanalytiker

Citat

Källor

Vidare läsning

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Cryptanalysis&oldid=1137226114 "