Kryptanalys

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 december 2021; kontroller kräver 2 redigeringar .

Krypteringsanalys (från andra grekiska κρυπτός  "dold" + " analys ") är vetenskapen om metoder för att dekryptera krypterad information utan en nyckel avsedd för detta , såväl som själva processen för sådan dekryptering.

I de flesta fall innebär kryptoanalys att ta reda på nyckeln; kryptoanalys inkluderar också metoder för att upptäcka sårbarheten hos kryptografiska algoritmer eller protokoll .

Ett försök att bryta ett visst chiffer med hjälp av kryptoanalysmetoder kallas en kryptografisk attack på det chiffer. En kryptografisk attack som bryter ett chiffer kallas en "crack" eller "crack" av chifferet.

Termen introducerades av den amerikanske kryptografen William F. Friedman 1920 som en del av hans bok The Elements of Cryptanalysis [1] .

Ursprungligen baserades kryptoanalysmetoder på de språkliga mönstren av naturlig text och implementerades endast med penna och papper. Med tiden växer rollen för rent matematiska metoder i kryptoanalys, för implementeringen av vilka specialiserade kryptoanalytiska datorer används .

Historia om kryptoanalys

Kryptanalys utvecklades tillsammans med utvecklingen av kryptografi: nya, mer avancerade chiffer ersatte redan trasiga kodsystem endast för kryptoanalytiker för att uppfinna mer sofistikerade metoder för att bryta krypteringssystem. Begreppen kryptografi och kryptoanalys är oupplösligt förbundna med varandra: för att skapa ett system som är resistent mot hackning är det nödvändigt att ta hänsyn till alla möjliga sätt att attackera det.

Klassisk kryptoanalys

Även om begreppet kryptoanalys introducerades relativt nyligen, uppfanns vissa metoder för hackning för tiotals århundraden sedan. Det första kända skriftliga omnämnandet av kryptoanalys är " Manuskriptet om dekryptering av kryptografiska meddelanden ", skrivet av den arabiska vetenskapsmannen Al-Kindi redan på 900-talet. Detta vetenskapliga arbete innehåller en beskrivning av metoden för frekvensanalys .

Frekvensanalys  är huvudverktyget för att knäcka de flesta klassiska permutations- eller substitutionschiffer. Denna metod är baserad på antagandet om förekomsten av en icke-trivial statistisk fördelning av symboler, såväl som deras sekvenser, både i klartext och i chiffertext. Dessutom kommer denna distribution att bevaras fram till utbyte av tecken både i krypteringsprocessen och under dekrypteringsprocessen. Det är värt att notera att, under förutsättning av en tillräckligt stor längd av det chiffrerade meddelandet, är monoalfabetiska chiffer lätt mottagliga för frekvensanalys: om frekvensen av en bokstavs förekomst i språket och frekvensen av utseendet av en viss karaktär närvarande i chiffertexten är ungefär lika, då kan det i detta fall antas med hög grad av sannolikhet att denna karaktär och kommer att vara samma bokstav. Det enklaste exemplet på frekvensanalys skulle vara att helt enkelt räkna antalet av vart och ett av de påträffade tecken, sedan följa proceduren att dividera det resulterande antalet tecken med antalet av alla tecken i texten och multiplicera resultatet med hundra för att representera slutligt svar i procent. Vidare jämförs de erhållna procentvärdena med tabellen över probabilistisk fördelning av bokstäver för det förmodade originalspråket.

Under perioden av 1400- och 1500-talen skapades och utvecklades polyalfabetiska substitutionschiffer i Europa . Den mest kända är den franske diplomaten Blaise de Vigenères chiffer, som byggde på användningen av en sekvens av flera Caesar-chiffer med olika skiftvärden. I tre århundraden ansågs Vigenère-chifferet vara helt kryptografiskt stabilt, tills Friedrich Kasiski 1863 föreslog en egen metod för att bryta detta chiffer. Huvudidén med Kasiska-metoden är följande: om det i vanlig text mellan två identiska teckenuppsättningar finns ett sådant textblock att dess längd är en multipel av längden på nyckelordet, då är dessa identiska uppsättningar av vanlig text tecken kommer att gå in i samma segment av chiffertexten under kryptering. I praktiken betyder det att om det finns identiska segment med tre eller fler tecken i chiffertexten är det stor sannolikhet att dessa segment motsvarar samma segment av klartexten. Hur Kasiska-metoden tillämpas: par av identiska segment med längd tre eller fler söks i chiffertexten, sedan beräknas avståndet mellan dem, det vill säga antalet tecken som skiljer startpositionerna för de parade segmenten. Som ett resultat av analysen av alla par av identiska segment kommer vi att få en uppsättning avstånd d 1 , d 2 , d 3 , ... Längden på nyckelordet kommer att vara en divisor för vart och ett av avstånden och därför, för deras största gemensamma delare.

Nästa steg i utvecklingen av kryptoanalys är förknippat med uppfinningen av roterande chiffermaskiner som till exempel Enigma som uppfanns av Arthur Scherbius . Syftet med sådana anordningar var att minimera antalet repeterande chiffertextsegment vars förekomststatistik användes för att bryta Vigenère-chifferet. Polska kryptoanalytiker lyckades bygga en prototyp dekrypteringsmaskin för versionen av Enigma som användes av Nazityskland . Maskinen fick namnet " Bomb " för det faktum att den under drift gjorde ljud som liknar tickande av en klocka. Senare slutfördes den och antogs av engelska kryptoanalytiker.

Modern kryptoanalys

I takt med att nya krypteringsmetoder utvecklades blev matematiken allt viktigare. Så till exempel i frekvensanalys måste kryptoanalytikern ha kunskap om både lingvistik och statistik. Medan det teoretiska arbetet med krypteringsanalysen av Enigma huvudsakligen utfördes av matematiker, såsom Alan Mathison Turing . Ändå, tack vare samma matematik, har kryptografi nått en sådan utveckling att antalet elementära matematiska operationer som krävs för att hacka började nå astronomiska värden. Modern kryptografi har blivit mycket mer motståndskraftig mot kryptoanalys än de en gång använda, föråldrade teknikerna, som räckte för att bryta med en penna och ett papper. Det kan tyckas att ren teoretisk kryptoanalys inte är kapabel att bryta moderna chiffer mer effektivt. Ändå skriver historikern David Kahn i sin anteckning om 50-årsdagen av National Security Agency :

"Idag erbjuder hundratals företag många olika kryptosystem som inte kan brytas av någon av de kända metoderna för kryptoanalys. I själva verket är sådana system resistenta även mot en vald klartextattack, det vill säga att jämföra klartexten och dess motsvarande chiffertext avslöjar inte krypteringsnyckeln som skulle tillåta att andra meddelanden dekrypteras. På sätt och vis är alltså kryptoanalysen död. Men detta är inte slutet. Kryptanalys kan vara död, men metaforiskt sett kan en katt flåas på flera sätt."

Vidare i sin anteckning beskriver han den ökade betydelsen av dataavlyssning, buggar, sidokanalattacker och kvantdatorer som tekniker som ersätter traditionella metoder för kryptoanalys. 2010 noterade tidigare CTO för National Security Directorate Brian Snow att kommersiell kryptografi nästan har nått den tekniknivå som används av underrättelsetjänsterna, och nu går de tillsammans "mycket långsamt framåt i ett redan fullt utforskat område."

Kryptanalys är dock fortfarande för tidigt att skriva av. För det första är det inte känt hur effektiva kryptoanalysmetoderna som används av specialtjänsterna är, och för det andra, under åren av bildandet och förbättringen av modern datorkryptografi, har många anspråk gjorts på både teoretiska och praktiska kryptografiska primitiver:

Således, även om de säkraste av dagens chiffer är mycket mer motståndskraftiga mot kryptoanalys än Enigma, spelar ändå kryptoanalys fortfarande en viktig roll inom det stora området informationssäkerhet.

Kryptoanalysmetoder

Bruce Schneier identifierar fyra huvudsakliga och tre ytterligare metoder för kryptoanalys, förutsatt att kryptoanalytikern känner till chifferalgoritmen (i enlighet med Kerckhoffs princip ):

Grundläggande metoder för kryptoanalys

  1. Chiffertextbaserad attack .
  2. Attack baserad på klartext och motsvarande chiffertexter.
  3. Vald klartextattack (möjligheten att välja texten att kryptera).
  4. Adaptiv klartextattack .

Ytterligare metoder för kryptoanalys

  1. Vald chiffertextattack .
  2. Nyckelgissad attack .
  3. "Gangster"-krypteringsanalys .

Grundläggande metoder för kryptoanalys

Chiffertextattacker _

Anta att en kryptoanalytiker har ett visst antal chiffertexter som erhållits som ett resultat av att använda samma krypteringsalgoritm. I det här fallet kan kryptoanalytikern bara utföra en chiffertextbaserad attack. Målet med en kryptografisk attack i det här fallet är att hitta så många klartexter som möjligt som matchar de tillgängliga chiffertexterna, eller ännu bättre, att hitta nyckeln som används vid kryptering.

Indata för denna typ av attack kan erhållas av en kryptoanalytiker som ett resultat av en enkel avlyssning av krypterade meddelanden. Om överföringen utförs över en öppen kanal är implementeringen av uppgiftsinsamlingen relativt enkel och trivial. Chiffertextbaserade attacker är de svagaste och mest obekväma.

Attack baserad på klartext och motsvarande chiffertexter

Låt kryptoanalytikern ha till sitt förfogande inte bara chiffertexter, utan också motsvarande klartexter.

Sedan finns det två alternativ för att ställa in problemet:

  1. Hitta nyckeln som används för att konvertera klartext till chiffertext.
  2. Skapa en algoritm som kan dekryptera alla meddelanden som är kodade med denna nyckel.

Att erhålla klartext spelar en avgörande roll för att genomföra denna attack. Vanliga texter utvinns från en mängd olika källor. Så, till exempel, kan du gissa innehållet i en fil genom dess förlängning.

I fallet med en hackad korrespondens kan vi anta att brevet har en struktur som:

  • "hälsningar";
  • "huvudtext";
  • "den slutliga formen av artighet";
  • "signatur".

Därför kan attacken orkestreras genom att välja olika typer av "Hälsningar" (till exempel "Hej!", "God eftermiddag" etc.) och/eller "Slutliga former av artighet" (som "Respektfullt", "Din" Med vänlig hälsning" " osv.). Denna attack är starkare än en attack med endast chiffertext.

Vald klartextattack

För att utföra denna typ av attack behöver en kryptoanalytiker inte bara ha ett visst antal klartexter och chiffertexter som härrör från dem. Bland annat i det här fallet måste kryptoanalytikern kunna plocka upp flera klartexter och få resultatet av deras kryptering.

En kryptoanalytikers uppgifter upprepar uppgifterna för en klartextattack, det vill säga att erhålla en krypteringsnyckel, eller att skapa en dekrypteringsalgoritm för en given nyckel.

Du kan få indata för denna typ av attack, till exempel enligt följande:

  1. Skapa och skicka ett falskt, okrypterat meddelande som utger sig vara från en av de användare som normalt använder kryptering.
  2. I vissa fall kan du få ett svar som innehåller chiffertext som citerar innehållet i det falska meddelandet.

När en attack av denna typ utförs har kryptoanalytikern möjligheten att välja block av klartext, som under vissa förhållanden kan göra det möjligt att få mer information om krypteringsnyckeln.

Adaptiva klartextattacker

Denna typ av attack är ett bekvämare specialfall av en attack med vald klartext. Bekvämligheten med en adaptivt vald klartextattack är att, förutom att kunna välja en klartext, kan en kryptoanalytiker bestämma sig för att kryptera en eller annan klartext baserat på resultaten av kryptering och efterföljande dekrypteringsoperationer som redan erhållits. Med andra ord, i en attack med vald klartext väljer kryptoanalytikern bara ett stort block av klartext för efterföljande kryptering och börjar sedan analysera systemet baserat på dessa data. I fallet med att organisera en adaptiv attack kan kryptoanalytikern ta emot resultaten av kryptering av alla block av klartext för att samla in data av intresse för honom, som kommer att beaktas vid val av nästa block av klartext som skickas för kryptering, och så vidare. Närvaron av feedback ger en attack baserad på en adaptivt vald chiffertext en fördel jämfört med alla ovanstående typer av attacker.

Ytterligare metoder för kryptoanalys

Vald chiffertextattack

Antag att en kryptoanalytiker har tillfällig tillgång till ett krypteringsverktyg eller -enhet. I det här fallet, under en begränsad tidsperiod, kan kryptoanalytikern erhålla motsvarande klartexter från de chiffertexter som han känner till, varefter kryptoanalytikern måste börja analysera systemet. Vid denna typ av attack är målet med analysen att få fram krypteringsnyckeln.

Detta problem kan kortfattat formuleras enligt följande.

Given:

var  är den tillgängliga chiffertexten,  är motsvarande klartext och  är dekrypteringsfunktionen med nyckeln .

Hitta: använd krypteringsnyckel .

Intressant nog kan en vald chiffertextattack också kallas en " lunchattack " eller en " midnattsattack " . Låt oss säga att titeln " Lunchtime Attacks " återspeglar det faktum att en legitim användare kan lämna sin dekrypteringsmaskin obevakad under lunchtid, och en kryptoanalytiker kan dra fördel av detta.

Nyckelgissad attack

I motsats till dess namn, innebär en attack med vald nyckel inte att kryptoanalytikern är engagerad i en enkel uppräkning av nycklar i hopp om att hitta den rätta. En attack av denna typ är baserad på det faktum att en kryptoanalytiker kan observera driften av en krypteringsalgoritm som använder flera nycklar. Kryptanalytikern vet till en början ingenting om nycklarnas exakta betydelse, men han känner till något matematiskt förhållande som länkar nycklarna samman. Ett exempel på detta är situationen när en kryptoanalytiker fick reda på att de sista 80 bitarna av alla nycklar är desamma, även om värdena på själva bitarna kan vara okända.

Bandit cryptanalysis

En kryptoanalytiker kan använda den så kallade " mänskliga faktorn ", det vill säga försöka använda utpressning, mutor, tortyr eller andra medel för att få information om krypteringssystemet eller till och med själva krypteringsnyckeln. Till exempel att ge en muta, som en av varianterna av gangsterkryptanalys, kan kallas "Öppning med köp av en nyckel." Obduktionstekniken bygger alltså på människors svaghet som en integrerad del av informationssäkerhetssystemet.

Bandit kryptoanalys anses vara ett mycket kraftfullt sätt att bryta ett system, och ofta det bästa sättet att bryta chiffer.

Olika typer av attacker

Se även

Anteckningar

  1. ↑ David Kahn . Kodbrytare . — M.: Tsentrpoligraf , 2000. — 473 sid. — ISBN 5-227-00678-4 .

Litteratur

  • David Kahn, Anmärkningar om 50-årsdagen av National Security Agency , 1 november 2002.
  • Schneier B. Kryptanalys // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumf, 2002. - S. 19-22. — 816 sid. - 3000 exemplar.  - ISBN 5-89392-055-4 .
  • Pilidi V. S. Kryptografi. Inledande kapitel . - Rostov-on-Don: SFU, 2009. - 110 sid.
  • Alex Biryukov och Eyal Kushilevitz.: Från differentiell krypteringsanalys till attacker endast med chiffertext

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk
I bibliografiska kataloger