Krypteringsanalyse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. december 2021; checks kræver 2 redigeringer .

Krypteringsanalyse (fra andet græsk κρυπτός "skjult" + " analyse ") er videnskaben om metoder til at dekryptere krypteret information uden en nøgle beregnet til dette , såvel som selve processen med sådan dekryptering.

I de fleste tilfælde betyder kryptoanalyse at finde ud af nøglen; kryptoanalyse omfatter også metoder til at opdage sårbarheden af kryptografiske algoritmer eller protokoller .

Et forsøg på at bryde en bestemt chiffer ved hjælp af kryptoanalysemetoder kaldes et kryptografisk angreb på denne chiffer. Et kryptografisk angreb, der bryder en chiffer, kaldes et "crack" eller "crack" af chifferen.

Udtrykket blev introduceret af den amerikanske kryptograf William F. Friedman i 1920 som en del af hans bog The Elements of Cryptanalysis [1] .

Oprindeligt var kryptoanalysemetoder baseret på de sproglige mønstre af naturlig tekst og blev implementeret ved kun at bruge blyant og papir. Med tiden vokser rollen som rent matematiske metoder i kryptoanalyse, til implementeringen af hvilke specialiserede kryptoanalytiske computere bruges .

Historien om kryptoanalyse

Kryptanalyse udviklede sig sammen med udviklingen af kryptografi: Nye, mere avancerede chiffer erstattede allerede ødelagte kodesystemer kun for kryptoanalytikere for at opfinde mere sofistikerede metoder til at bryde krypteringssystemer. Begreberne kryptografi og kryptoanalyse er uløseligt forbundet med hinanden: For at skabe et system, der er modstandsdygtigt over for hacking, er det nødvendigt at tage højde for alle mulige måder at angribe det på.

Klassisk kryptoanalyse

Selvom begrebet kryptoanalyse blev introduceret relativt for nylig, blev nogle metoder til hacking opfundet for titusinder af århundreder siden. Den første kendte skriftlige omtale af kryptoanalyse er " Manuskript om dekryptering af kryptografiske meddelelser ", skrevet af den arabiske videnskabsmand Al-Kindi tilbage i det 9. århundrede. Dette videnskabelige arbejde indeholder en beskrivelse af metoden til frekvensanalyse .

Frekvensanalyse er det vigtigste værktøj til at knække de fleste klassiske permutations- eller substitutionscifre. Denne metode er baseret på antagelsen om eksistensen af en ikke-triviel statistisk fordeling af symboler såvel som deres sekvenser, både i klarteksten og i chifferteksten. Desuden vil denne distribution blive bevaret op til udskiftning af tegn både i krypteringsprocessen og i dekrypteringsprocessen. Det er værd at bemærke, at under forudsætning af en tilstrækkelig stor længde af den becifrede meddelelse, er monoalfabetiske cifre let tilgængelige for frekvensanalyse: hvis hyppigheden af forekomsten af et bogstav i sproget og hyppigheden af forekomsten af en bestemt karakter. tilstede i chifferteksten er omtrent ens, så i dette tilfælde kan det antages med en høj grad af sandsynlighed, at dette tegn og vil være det samme bogstav. Det enkleste eksempel på frekvensanalyse ville være blot at tælle antallet af hvert af de tegn, du støder på, og derefter følge proceduren med at dividere det resulterende antal tegn med antallet af alle tegn i teksten og gange resultatet med hundrede for at repræsentere endelige svar i procent. Yderligere sammenlignes de opnåede procentværdier med tabellen over probabilistisk fordeling af bogstaver for det formodede originalsprog.

I løbet af det 15.-16. århundrede blev polyalfabetiske substitutionscifre skabt og udviklet i Europa . Den mest berømte er den franske diplomat Blaise de Vigenères chiffer, som var baseret på brugen af en sekvens af flere Cæsar-cifre med forskellige skiftværdier. I tre århundreder blev Vigenère-cifferet anset for at være fuldstændigt kryptografisk stabilt, indtil Friedrich Kasiski i 1863 foreslog sin egen metode til at bryde denne ciffer. Hovedideen med Kasiska-metoden er som følger: hvis der i almindelig tekst mellem to identiske tegnsæt er en sådan tekstblok, at dens længde er et multiplum af længden af nøgleordet, så er disse identiske sæt almindelig tekst tegn vil gå ind i de samme segmenter af chifferteksten under kryptering. I praksis betyder det, at hvis der er identiske segmenter på tre eller flere tegn i chifferteksten, er der stor sandsynlighed for, at disse segmenter svarer til de samme segmenter af klarteksten. Sådan anvendes Kasiska-metoden: Der søges efter par af identiske segmenter med en længde på tre eller flere i chifferteksten, hvorefter afstanden mellem dem beregnes, det vil sige antallet af tegn, der adskiller startpositionerne for de parrede segmenter. Som et resultat af analysen af alle par af identiske segmenter, vil vi få et sæt af afstande d 1 , d 2 , d 3 , ... Længden af nøgleordet vil være en divisor for hver af afstandene og derfor, for deres største fælles deler.

Det næste trin i udviklingen af kryptoanalyse er forbundet med opfindelsen af roterende chiffermaskiner som for eksempel Enigma opfundet af Arthur Scherbius . Formålet med sådanne enheder var at minimere antallet af gentagne chiffertekstsegmenter, hvis forekomststatistik blev brugt til at bryde Vigenère-chifferet. Det lykkedes polske kryptoanalytikere at bygge en prototype dekrypteringsmaskine til den version af Enigma, der blev brugt af Nazityskland . Maskinen fik navnet " Bomb " for det faktum, at den under drift lavede lyde, der ligner et urs tikkende. Senere blev det færdiggjort og vedtaget af engelske kryptoanalytikere.

Moderne kryptoanalyse

Efterhånden som nye krypteringsmetoder udviklede sig, blev matematik vigtigere og vigtigere. Så for eksempel i frekvensanalyse skal kryptanalytikeren have kendskab til både lingvistik og statistik. Hvorimod det teoretiske arbejde med krypteringsanalysen af Enigma overvejende blev udført af matematikere, såsom Alan Mathison Turing . Ikke desto mindre, takket være den samme matematik, har kryptografi nået en sådan udvikling, at antallet af elementære matematiske operationer, der er nødvendige for hacking, begyndte at nå astronomiske værdier. Moderne kryptografi er blevet meget mere modstandsdygtig over for kryptoanalyse end de engang brugte, forældede teknikker, som var nok til at bryde med en kuglepen og et stykke papir. Det kan se ud til, at ren teoretisk krypteringsanalyse ikke er i stand til at bryde moderne cifre mere effektivt. Ikke desto mindre skriver historikeren David Kahn i sin note om 50-årsdagen for National Security Agency :

"I dag tilbyder hundredvis af virksomheder mange forskellige kryptosystemer, som ikke kan brydes med nogen af de kendte metoder til kryptoanalyse. Sådanne systemer er faktisk modstandsdygtige selv over for et valgt klartekstangreb, det vil sige, at sammenligning af klartekst og dens tilsvarende chiffertekst afslører ikke krypteringsnøglen, der ville tillade andre meddelelser at blive dekrypteret. Således er kryptoanalysen i en vis forstand død. Men dette er ikke enden. Krypteringsanalyse kan være død, men metaforisk set kan en kat blive flået på flere måder."

Yderligere i sit notat beskriver han den øgede betydning af dataaflytning, fejl, sidekanalangreb og kvantecomputere som teknikker, der erstatter traditionelle metoder til kryptoanalyse. I 2010 bemærkede den tidligere CTO for National Security Directorate Brian Snow, at kommerciel kryptografi næsten har nået det teknologiske niveau, der bruges af efterretningstjenesterne, og nu er de sammen "meget langsomt på vej frem i et allerede fuldt udforsket område."

Kryptanalyse er dog stadig for tidligt at afskrive. For det første vides det ikke, hvor effektive de kryptoanalysemetoder, som specialtjenesterne anvender, er, og for det andet er der gennem årene med dannelsen og forbedringen af moderne computerkryptografi blevet fremsat mange krav til både teoretiske og praktiske kryptografiske primitiver:

i 1998 blev en sårbarhed over for chiffertekstbaserede angreb opdaget i blokchifferet MADRYGA , foreslået tilbage i 1984, men ikke meget brugt;
en hel række angreb fra det videnskabelige samfund, hvoraf mange var helt praktiske, ødelagde bogstaveligt talt FEAL -blokchifferet , foreslået som en erstatning for DES som en standard krypteringsalgoritme, men heller ikke udbredt;
det har også vist sig, at med bredt tilgængelige computerværktøjer kan A5/1- , A5/2- , CMEA -blokchiffer og DECT -chiffer, der bruges til at sikre mobiltelefoni og trådløs telefoni, blive ødelagt i timer eller minutter, og nogle gange og i virkeligheden tid;
Det brute-force-angreb hjalp med at bryde nogle af de anvendte sikkerhedssystemer, såsom CSS , et system til beskyttelse af digitalt medieindhold på DVD -medier .

Selvom de sikreste af nutidens chiffer er meget mere modstandsdygtige over for kryptoanalyse end Enigma, spiller kryptoanalyse stadig en vigtig rolle inden for det store område af informationssikkerhed.

Kryptoanalysemetoder

Bruce Schneier identificerer 4 hoved- og 3 yderligere metoder til kryptoanalyse, idet han forudsætter kendskab til krypteringsalgoritmen af kryptoanalytikeren (i overensstemmelse med Kerckhoffs princip ):

Grundlæggende metoder til kryptoanalyse

Chiffertekstbaseret angreb .
Angreb baseret på klartekster og tilsvarende chiffertekster.
Valgt klartekstangreb (evnen til at vælge den tekst, der skal krypteres).
Adaptivt klartekstangreb .

Yderligere metoder til kryptoanalyse

Grundlæggende metoder til kryptoanalyse

Ciphertext- angreb

Antag, at en kryptoanalytiker har et vist antal chiffertekster opnået som et resultat af at bruge den samme krypteringsalgoritme. I dette tilfælde kan kryptanalytikeren kun udføre et chiffertekst-baseret angreb. Målet med et kryptografisk angreb i dette tilfælde er at finde så mange klartekster som muligt, der matcher de tilgængelige chiffertekster, eller endnu bedre at finde nøglen, der bruges til kryptering.

Inputdataene for denne type angreb kan opnås af en kryptoanalytiker som et resultat af en simpel opsnapning af krypterede meddelelser. Hvis transmissionen udføres over en åben kanal, så er implementeringen af dataindsamlingsopgaven relativt let og triviel. Chiffertekst-baserede angreb er de svageste og mest ubelejlige.

Angreb baseret på klartekster og tilsvarende chiffertekster

Lad kryptanalytikeren ikke kun have chiffertekster til sin rådighed, men også de tilsvarende klartekster.

Så er der to muligheder for at indstille problemet:

Find nøglen, der bruges til at konvertere almindelig tekst til chiffertekst.
Opret en algoritme, der er i stand til at dekryptere enhver meddelelse, der er kodet med denne nøgle.

Indhentning af klartekster spiller en afgørende rolle i udførelsen af dette angreb. Almindelige tekster er udtrukket fra en række forskellige kilder. Så for eksempel kan du gætte indholdet af en fil ved dens udvidelse.

I tilfælde af en hacket korrespondance kan vi antage, at brevet har en struktur som:

"Vær hilset";
"hovedtekst";
"den endelige form for høflighed";
"Underskrift".

Derfor kan angrebet orkestreres ved at vælge forskellige typer af "Hilsen" (f.eks. "Hej!", "Goddag" osv.) og/eller "Slutlige former for høflighed" (såsom "Respektfuldt", "Din venlige" Med venlig hilsen" " osv.). Dette angreb er stærkere end et angreb med kun chiffertekst.

Valgt klartekstangreb

For at udføre denne type angreb skal en kryptoanalytiker ikke kun have et vist antal klartekster og chiffertekster afledt af dem. Blandt andet skal kryptanalytikeren i dette tilfælde kunne opfange flere klartekster og få resultatet af deres kryptering.

En kryptoanalytikers opgaver gentager opgaverne for et klartekstangreb, det vil sige at opnå en krypteringsnøgle eller at skabe en dekrypteringsalgoritme for en given nøgle.

Du kan få inputdata til denne type angreb, for eksempel som følger:

Opret og send en falsk, ukrypteret besked, der foregiver at være fra en af de brugere, der normalt bruger kryptering.
I nogle tilfælde kan du få et svar, der indeholder chiffertekst, der citerer indholdet af den falske besked.

Når han udfører et angreb af denne type, har kryptanalytikeren mulighed for at vælge blokke af klartekst, som under visse betingelser kan give mulighed for at få mere information om krypteringsnøglen.

Adaptive klartekstangreb

Denne type angreb er et mere bekvemt specialtilfælde af et valgt-klartekst-angreb. Bekvemmeligheden ved et adaptivt valgt klartekstangreb er, at en kryptoanalytiker ud over at kunne vælge en klartekst kan beslutte at kryptere en eller anden klartekst baseret på resultaterne af kryptering og efterfølgende dekrypteringsoperationer, der allerede er opnået. Med andre ord, i et valgt-klartekst-angreb vælger kryptanalytikeren kun én stor blok af klartekst til efterfølgende kryptering og begynder derefter at analysere systemet baseret på disse data. I tilfælde af organisering af et adaptivt angreb kan kryptanalytikeren modtage resultaterne af kryptering af alle blokke af klartekst for at indsamle data af interesse for ham, som vil blive taget i betragtning ved valg af de næste blokke af klartekst sendt til kryptering, og snart. Tilstedeværelsen af feedback giver et angreb baseret på en adaptivt valgt chiffertekst en fordel i forhold til alle de ovennævnte typer angreb.

Yderligere metoder til kryptoanalyse

Valgt chiffertekstangreb

Antag, at en kryptoanalytiker har midlertidig adgang til et krypteringsværktøj eller -enhed. I dette tilfælde kan kryptanalytikeren i et begrænset tidsrum hente de tilsvarende klartekster fra de chiffertekster, han kender, hvorefter kryptanalytikeren skal begynde at analysere systemet. I denne type angreb er målet med analysen at opnå krypteringsnøglen.

Dette problem kan kort formuleres som følger.

Givet: $C_{1},P_{1}=D_{k}(C_{1});C_{2},P_{2}=D_{k}(C_{2});C_{3}, P_{3}=D_{k}(C_{3});\dots ;C_{n},P_{n}=D_{k}(C_{n}),$

hvor er den tilgængelige chiffertekst, er den tilsvarende almindelig tekst, og er dekrypteringsfunktionen ved hjælp af nøglen . $C_{n}$ $n$ $P_{n}$ $C_{n}$ $D_{k}$ $k$

Find: brugt krypteringsnøgle . $k$

Interessant nok kan et valgt chiffertekstangreb også kaldes et " frokostangreb " eller et " midnatsangreb " . Lad os sige, at titlen " Lunchtime Attacks " afspejler det faktum, at en legitim bruger kan efterlade deres dekrypteringsmaskine uden opsyn under frokosttid, og en kryptoanalytiker kan drage fordel af dette.

Nøgle-gættet angreb

I modsætning til navnet betyder et angreb med valgt nøgle ikke, at kryptanalytikeren er engageret i en simpel opregning af nøgler i håbet om at finde den rigtige. Et angreb af denne type er baseret på det faktum, at en kryptoanalytiker kan observere driften af en krypteringsalgoritme, der bruger flere nøgler. Kryptanalytikeren ved i første omgang ikke noget om nøglernes præcise betydning, men han kender til et matematisk forhold, der forbinder nøglerne. Et eksempel på dette er situationen, hvor en kryptoanalytiker fandt ud af, at de sidste 80 bits af alle nøgler er de samme, selvom værdierne af selve bits kan være ukendte.

Bandit kryptanalyse

En kryptoanalytiker kan bruge den såkaldte " menneskelige faktor ", det vil sige forsøge at bruge afpresning, bestikkelse, tortur eller andre midler til at få information om krypteringssystemet eller endda selve krypteringsnøglen. For eksempel at give en bestikkelse, som en af varianterne af gangsterkryptanalyse, kan kaldes "Åbning med køb af en nøgle." Obduktionsteknikken er således bygget på menneskers svaghed som en integreret del af informationssikkerhedssystemet.

Bandit-krypteringsanalyse anses for at være en meget kraftfuld måde at bryde et system på, og ofte den bedste måde at bryde cifre.

Forskellige typer angreb

Se også

American Cryptogram Association

Noter

↑ David Kahn . Kodebrydere . — M.: Tsentrpoligraf , 2000. — 473 s. — ISBN 5-227-00678-4 .

Litteratur

David Kahn, Bemærkninger om 50-årsdagen for National Security Agency , 1. november 2002.
Schneier B. Kryptanalyse // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 19-22. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Pilidi V. S. Kryptografi. Indledende kapitler . - Rostov ved Don: SFU, 2009. - 110 s.
Alex Biryukov og Eyal Kushilevitz.: Fra differentiel krypteringsanalyse til kun chiffertekstangreb

Links

Krypteringsanalyse: i går, i dag, i morgen | åbne systemer. DBMS | Forlag "Open Systems" (russisk)

Ordbøger og encyklopædier	stor kinesisk Britannica (online)
I bibliografiske kataloger	GND : 4830502-9