Sammenkædet nøgleangreb

Relateret nøgleangreb [ 1] er en type kryptografisk angreb , hvor en kryptoanalytiker vælger et forhold mellem et par nøgler, men selve nøglerne forbliver ukendte for ham. Dataene er krypteret med begge nøgler. I den kendte klartekstvariant kender kryptanalytikeren klarteksten og chifferteksten af data krypteret med to nøgler. Angriberens mål er at finde de faktiske hemmelige nøgler. Det antages, at angriberen kender eller vælger en matematisk relation, der forbinder nøglerne. Relationen har formen ( ) [2] , hvor er funktionen valgt af angriberen og er de tilhørende nøgler. For hver kryptering vælges forholdet mellem nøglerne individuelt. Der er mange måder at finde dette forhold korrekt på [3] . Sammenlignet med andre angreb, hvor angriberen kun kan manipulere klarteksten og/eller chifferteksten, giver valget af forholdet mellem de hemmelige nøgler angriberen en ekstra grad af frihed. Ulempen ved denne frihed er, at sådanne angreb kan være sværere i praksis. Designere forsøger dog normalt at skabe "ideelle" primitiver, der automatisk kan bruges uden yderligere analyse i det bredest mulige sæt af protokoller eller driftsformer. At modstå sådanne angreb er således et vigtigt designmål for blokcifre, og faktisk var det et af de erklærede designmål for Rijndael- algoritmen . $K$ $B$ $=$ $F$ $K$ $EN$ $F$ $K$ $EN$ $K$ $B$

Nøgleudvidelse

De fleste krypteringsalgoritmer ændrer den originale nøgle til senere brug. Denne modifikation kaldes nøgleudvidelse . Der er eksempler på algoritmer, hvor nøgleudvidelsesproceduren er ekstremt kompleks sammenlignet med den faktiske kryptering, blandt dem er HPC- og FROG- algoritmerne værd at nævne . Navnet på proceduren bestemmes af det faktum, at den indledende krypteringsnøgle normalt har en størrelse væsentligt mindre end det sæt af undernøgler, der bruges i runderne af algoritmen, det vil sige den udvidede nøgle.

Det viser sig, at krypteringsalgoritmen logisk kan opdeles i to subalgoritmer: de faktiske krypteringstransformationer og nøgleudvidelsesproceduren. Der er en række krav til nøgleudvidelsesproceduren [4] :

Det er påkrævet, at nøgleudvidelsesproceduren beregner nøgler parallelt med krypteringstransformationer: dette vil tillade både parallelisering af beregninger i multiprocessorsystemer og ikke spilde hukommelse til at lagre hele den udvidede nøgle ved kryptering under ressourcebegrænsede forhold.
I mange applikationer af symmetriske krypteringsalgoritmer er det ofte nødvendigt at ændre nøglerne i krypteringsværktøjet. Derfor vil en meget kompleks nøgleudvidelsesprocedure ikke tillade brugen af en krypteringsalgoritme i disse tilfælde.
I hvilken grad en algoritme er modtagelig for angreb på relaterede nøgler, afhænger også i høj grad af nøgleudvidelsesproceduren.

Klassisk linket nøgleangreb [1]

Denne type angreb blev først foreslået af den israelske videnskabsmand Eli Biham i 1992 i artiklen New Types of Cryptanalytic Attacks Using Related Keys . Det linkede nøgle-angreb, der er beskrevet af ham, ligner et forskydningsangreb . Shift attack ( engelsk slide attack ) - kryptografisk angreb , som i det generelle tilfælde er et angreb baseret på udvalgt klartekst , som tillader kryptering af blok-multi-runde ciphers, uanset antallet af brugte runder. Foreslået af Alex Biryukov og David Wagner i 1999 [5] . Skiftangrebet bruger to klartekster og opfylder følgende forhold: , hvor er rundefunktionen og er undernøglen til 1. runde . Et relateret nøgleangreb bruger et lignende forhold mellem nøgler. Lad os antage, at den ønskede krypteringsnøgle K efter dens modifikation ved nøgleudvidelsesproceduren giver en sekvens af undernøgler: , hvor er antallet af runder af krypteringsalgoritmen. Antag, at der er en nøgle, hvis udvidelse giver følgende sekvens: , det vil sige, sekvensen af undernøgler, der er oprettet på basis af nøglen , forskydes cyklisk i forhold til sekvensen af den ønskede nøgle med 1 runde [6] . $P$ $P'$ $P'=F(P,k_{1})$ $F()$ $k_{1}$ $Ex(K)$ $Ex(K)=\left\{{k_{1},k_{2},\ldots ,k_{r-1},k_{r}}\right\}$ $r$ $K'$ $Ex(K')=\venstre\{{k_{2},k_{3},\ldots ,k_{r},k_{1}}\right\}$ $K'$ $K$

Essensen af angrebet

Antag, at kryptanalytikeren kender par af klartekster og deres tilsvarende chiffertekster (krypteret med nøglen ), hvor er størrelsen af blokken af krypterede data, repræsenteret i bits . $2^{\frac {n}{2))$ $\left({P,C}\right)$ $K$ $n$
Derudover kender kryptoanalytikeren par af tekster, der er krypteret ved hjælp af nøglen, der er forbundet med ovenstående forhold. $2^{\frac {n}{2))$ $\left({P',C'}\right)$ $K'$ $K$
For hver korrelation af tekster skal kryptanalytikeren finde løsninger til ligningssystemet [7] : $\left({P,C}\right)$ $\left({P',C'}\right)$

${\begin{cases}F(P,k^{*})=P'\\F(C,k^{*})=C'\end{cases))$

Hvilken af teksterne der svarer til hver tekst fra , ved kryptanalytikeren ikke på forhånd. Men sandsynligheden for, at to tilfældigt udvalgte tekster vil opfylde det påkrævede forhold er . Så skal det påkrævede par findes efter at have analyseret mere end tekster, i overensstemmelse med fødselsdagsparadokset . Betingelsen for teksterne er ikke streng, den er et skøn og vil kun blive opfyldt i gennemsnit [8] . $2^{\frac {n}{2))$ $P$ $P$ ${\displaystyle {\frac {1}{2^{n))))$ $\left({P,P'}\right)$ $2^{{\frac {n}{2}}+1}$ $2^{{\frac {n}{2}}+1}$

Nøglen fundet fra ovenstående system er den påkrævede undernøgle . Afhængigt af nøglegenereringsoperationen kan viden give kryptanalytikeren mange muligheder for uautoriseret adgang til information. For eksempel er nøglegenereringen af LOKI89 -algoritmen konstrueret på en sådan måde, at den blot er den venstre 32-bit del af nøglen . Da denne algoritme bruger en 64-bit nøgle, er det efter beregningen nok bare at opregne mulighederne for at finde den. [9] $k^{*}$ $k_{1}$ $k_{1}$ $k_{1}$ $K$ $k_{1}$ $K$ $2^{32}$

Den runde funktion af den angrebne algoritme skal være svag nok til at beregne , hvilket er tilfældet for de fleste moderne krypteringsalgoritmer. Derudover kan kompleksiteten af angrebet reduceres betydeligt i forhold til det ovenfor beskrevne tilfælde, det hele afhænger af den valgte plaintext krypteringsalgoritme. For eksempel er beregninger forenklet for algoritmer baseret på et afbalanceret Feistel-netværk . $F()$ $k^{*}$

Angreb på forskellige krypteringsalgoritmer

Angreb på DES

DES ( data encryption s tandard ) er en algoritme til symmetrisk kryptering udviklet af IBM og godkendt af den amerikanske regering i 1977 som en officiel standard ( FIPS 46-3). Blokstørrelsen for DES er 64 bit . Algoritmen er baseret på et Feistel-netværk med 16 cyklusser ( runder ) og en nøgle på 56 bit . Algoritmen bruger en kombination af ikke-lineære (S-bokse) og lineære (E, IP, IP-1 permutationer) transformationer.

DES-krypteringsalgoritmen er modstandsdygtig over for et sådant angreb. Under krypteringsprocessen for hovedkrypteringsfunktionen er det påkrævet at beregne seksten 48-bit nøgler, som er resultatet af konvertering af den originale 56-bit nøgle ( for flere detaljer, se afsnittet "Nøglegenerering" ). $k_i$ Antallet af skift i nøgleberegningsalgoritmen stemmer ikke overens i alle runder. Typisk forskydes nøgleregistrene to bits efter hver runde, og kun én bit efter den første, niende og femtende runde. Men hvis du ændrer dette skifteskema, skal du indstille skiftet til at være det samme i alle runder, så bliver det resulterende kryptosystem sårbart over for et linket-nøgleangreb. Den mindst sikre at angribe er den modificerede DES, hvor nøglen forskydes med to bits efter hvert trin [10] . $k_i$

Tabellen beskriver antallet af skift før hver runde af nøglegenerering og den modificerede skiftnummervariant, som er sårbar over for et forbundet nøgleangreb. For at knække en sådan variant af algoritmen ville kryptanalytikeren kun have brug for 2 17 valgte klartekster til de valgte nøgler eller 2 33 kendte klartekster til de valgte nøgler. For at bryde den modificerede DES er det nødvendigt at udføre 1,43*2 53 operationer, hvilket er en lille gevinst sammenlignet med den udtømmende søgning, hvor antallet af operationer er 2 56 [11] . I 1998, ved hjælp af en $250.000 EFF DES cracker supercomputer, blev DES knækket på mindre end tre dage [12] . EFF DES cracker brugte en brute-force søgning [13] til cracking . Store krav til tid og datavolumen tillader ikke at implementere et angreb på tilsluttede nøgler uden hjælp fra dyrt udstyr. Men ikke desto mindre er angrebet interessant af to grunde:

Dette er det første forsøg på et kryptoanalytisk angreb på DES-undernøglegenereringsalgoritmen.
Kompleksiteten afhænger ikke af antallet af stadier i den kryptografiske algoritme, den er lige så effektiv mod DES med 16, 32 eller 1000 stadier.

Angreb på AES

Advanced Encryption Standard ( AES ), også kendt som Rijndael (udtales [rɛindaːl] (Randal [14] )) er en symmetrisk blokchifferalgoritme (blokstørrelse 128 bit, nøgle 128/192/256 bit) vedtaget som en krypteringsstandard af USA's regering ifølge resultaterne af AES-konkurrencen . Denne algoritme er blevet godt analyseret og er nu meget brugt, som det var tilfældet med dens forgænger DES . AES kommer i tre varianter, der hver giver et forskelligt sikkerhedsniveau afhængigt af længden af den hemmelige nøgle. Nøglen kan være 128, 192 og 256 bit lang. Siden 2001, efter valget af AES som kryptografisk standard, har fremskridtet i dets kryptoanalyse været ekstremt lavt [15] . De bedste resultater blev opnået i løbet af angreb baseret på relaterede nøgler i 2009. Alex Biryukov , sammen med Dmitry Khovratovich, leverede det første linked-key kryptoanalytiske angreb på fuld-runde AES-192 og AES-256, den udviklede metode er hurtigere end brute force.

Det udviklede angreb på AES-256 er velegnet til alle typer nøgler og har en kompleksitet på omkring 2 96. Et angreb på AES-192 blev også præsenteret. Begge angreb minimerer antallet af aktive S-bokse i nøglegenereringsalgoritmen. Denne operation udføres ved hjælp af et boomerangangreb . Differentielle karakteristika for boomerangen blev etableret ved at søge efter lokale kollisioner i chifferen [16] . Hovedtræk ved AES-256, som er afgørende for de angreb, der overvejes, er, at krypteringsalgoritmen har 14 runder og en 256-bit nøgle, der fordobles i den interne tilstand. Derfor består nøglegenereringsalgoritmen kun af 7 runder, og hver runde har efter tur 8 S-bokse. På samme måde for AES-192, på grund af det faktum, at nøglen bliver halvanden gang større i den interne tilstand, består nøglegenereringsalgoritmen kun af 8, ikke 12 runder. Hver runde har kun 4 S-blokke.

Angreb på AES-256

Det er nødvendigt at udføre følgende trin 2 25,5 gange [17] :

Forbered strukturen af klarteksterne som angivet nedenfor.
Krypter det med nøgler og og gem de resulterende sæt og . $K_{A}$ $K_{B}$ $S_{A}$ $S_{B}$
Det er nødvendigt at udføre operationen for alle chiffertekster i og dekryptere de modificerede chiffertekster med nøglen . - et nyt sæt åbne tekster. $xor~\Delta _{C}$ $S_{A}$ $K_C$ $S_{C}$
Tilsvarende for og nøgle . - et nyt sæt åbne tekster. $S_{B}$ $K_{D}$ $S_{D}$
Sammenligning af alle par af klartekster fra og med en længde på 56 bit. $S_{C}$ $S_{D}$
For resten skal du kontrollere, om der er en forskel i sandsynlighedsværdien ved . Hvis den er ens på begge sider af 16-bit filteret, så for nøglepar, eller også kaldes de en kvartet og vil ved , også være ens på begge sider. $p_{i,0}$ $i>1$ $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$ $\nabla k_{i,7}^{0}=0$ ${\displaystyle \Delta k_{i,0}^{0))$
Det er nødvendigt at vælge kvartetter, hvis forskelle ikke kan påvirkes af aktive S-bokse i første runde og aktive S-bokse i nøglegenereringsalgoritmen.
Ved at filtrere forkerte kvartetter fra, genskaber vi delvist nøglens værdi.

Hver struktur har alle mulige muligheder for kolonne nul, række nul og en konstant værdi i andre bytes. Af de 272 tekster i hver struktur kan 2144 par sammenlignes. Af disse par vil 2 (144−8*9) = 2 72 bestå den første runde. Således får vi 1 påkrævet kvartet af 2 (96-72) = 2 24 strukturer og 3 nødvendige kvartetter af 2 25,5 strukturer. Vi beregner antallet af kvartetter af de seneste 6 trin, der vil være omkring 2 (144-56-16) = 2 72 par. Næste trin er at anvende et 16-bit filter, så vi får det samlede antal mulige kvartetter 2 (72+25,5−6) = 2 91,5 [18] .

Angreb på AES-192

Nøglegenereringsalgoritmen i dette tilfælde har den bedste spredning. Derfor bruger boomerangangrebet to underspor på hver 6 runder. Lad os analysere 2 73 strukturer med 2 48 tekster i henhold til følgende skema [19] :

Sammenlign alle par af mulige klartekster for nøglepar og . $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$
Sammenlign og gem alle chiffertekstkvartetter.
For hver forventet nøglebyte : , og in ; i og : $k^{0,3}$ $k^{2,3}$ $k^{0.5}$ $K_{A}$ $k^{0.5}$ $K_{A}$ $K_{B}$
1. beregn værdierne for disse bytes i alle nøgler fra delta-sporet. Få nøgleforskelle i og ; ${\displaystyle \Delta K^{0))$ $\nabla K^{8}$
2. vælg kvartetter, der modsiger ; $\nabla K^{8}$
3. forberede tællere for uberegnet nøglebytes, der svarer til aktive S-bokse i de første to og sidste: , , , — i tasterne og , , , , — i nøglerne og , 16 bytes i alt; $K^{0,0}$ $k^{0,1}$ $k^{1,2}$ $k^{3,0}$ $K_{A}$ $K_C$ $k^{0,0}$ $k^{0,1}$ $k^{0,2}$ $k^{0,3}$ $K_{A}$ $K_{B}$
4. for hver kvartet skal du indstille de mulige værdier for deres ukendte bytes og øge tællerne;
5. oprette en gruppe på 16 nøglebytes med maksimalt antal;
6. prøv alle mulige værdier af nøglens endnu ukendte 9 bytes og tjek at nøglen er korrekt. Hvis scenariet mislykkes, skal du gå til det første trin [19] . $K^{0}$

Begge præsenterede angreb er hovedsageligt af teoretisk interesse og udgør i praksis ikke en reel trussel mod applikationer, der bruger AES.

Praktisk anvendelse

De beskrevne angreb ved hjælp af relaterede nøgler ser ikke praktiske ud. I mange udviklinger gavner de ikke meget i forhold til udtømmende søgning, derudover kræver de en lang række antagelser. Dette angreb har længe været betragtet som ret kraftigt, men rent teoretisk [20] . Men eksperter som John Kelsey og Bruce Schneier [20] mener nu , at linked-key angreb kan have praktiske anvendelser. Nogle implementeringer af kryptografiske algoritmer eller netværksprotokoller (for eksempel autentificering eller nøgleudvekslingsprotokoller) kan allerede være modtagelige for et forbundet nøgleangreb [20] . En potentiel applikation er hashfunktionsanalyse . Teoretisk set kan linked-key-angreb være farlige, hvis symmetriske krypteringsalgoritmer bruges til at bygge hash-funktioner. På nuværende tidspunkt kendes ingen specifik applikation til hashfunktioner, men designere af hashfunktioner bør tage højde for, når de designer, at en sådan svaghed eksisterer. Under alle omstændigheder anbefales det kraftigt at tage kryptoanalyse på tilknyttede nøgler i betragtning ved udvikling af krypteringsalgoritmer og deres implementering [21] . Det bemærkes i [20] , at hovedbetingelsen for angrebet ser ret mærkelig ud: kryptanalytikeren kan skrive nøglen, det vil sige modificere den ønskede ukendte nøgle på den nødvendige måde, men kan ikke læse den. Nogle implementeringer af kryptografiske algoritmer eller netværksprotokoller kan dog angribes ved hjælp af tilknyttede nøgler. Under alle omstændigheder anbefales det kraftigt at tage kryptoanalyse på linkede nøgler [20] i betragtning ved udvikling af krypteringsalgoritmer og deres implementering. Det bemærkes også, at angreb på relaterede nøgler kan være meget farlige, hvis symmetriske krypteringsalgoritmer bruges til at bygge hash-funktioner.

Der er andre potentielle sårbarheder introduceret i krypteringsalgoritmen af en dårligt designet nøgleudvidelsesprocedure, især [22] :

sårbarhed over for "møde i middelklassen"-klasseangreb, da disse angreb udnytter det faktum, at den første del af krypteringstransformationerne af den angrebne algoritme bruger et andet sæt nøglebits. end anden del.
Svage nøgler er nøgler, der svarer til dechifrering eller har andre egenskaber, der gør det nemmere at knække.
ækvivalente nøgler - forskellige nøgler, men giver det samme krypteringsresultat på et bestemt undersæt af klartekster.
nøgleklasser - opstår, når en kryptanalytiker relativt nemt kan bestemme delmængden af nøglesættet, som den nødvendige nøgle tilhører, og følgelig reducere området for den komplette opregning af nøglen.

Se også

Nøgle-gættet angreb

Noter

↑ 1 2 Panasenko S., 2009 , s. 54.
↑ Biryukov og Khovratovich, 2009 , s. otte.
↑ Bellare, 2003 , s. 491.
↑ Panasenko S., 2009 , s. 53.
↑ Biryukov, Wagner, 1999 , s. 245-259.
↑ Biryukov og Khovratovich, 2009 , s. 7.
↑ Biham, 1994 , s. 16.
↑ Panasenko S., 2009 , s. 55.
↑ Panasenko S., 2009 , s. 56.
↑ Biham, 1994 , s. femten.
↑ Biham, 1994 , s. 17.
↑ Computerworld, 1998 .
↑ DES Cracker Project (downlink) . Eff. — "Onsdag den 17. juli 1998 vandt EFF DES Cracker, som blev bygget for mindre end $250.000, nemt RSA Laboratorys "DES Challenge II"-konkurrence og en pengepræmie på $10.000." Hentet 8. juli 2007. Arkiveret fra originalen 7. maj 2017. (ubestemt)
↑ "... I overensstemmelse med de flamske regler læses navnet som "Randal" - "Computerra", december 1999, nr. 49
↑ Biryukov og Khovratovich, 2009 , s. en.
↑ Biryukov og Khovratovich, 2009 , s. 2.
↑ Biryukov og Khovratovich, 2009 , s. 9.
↑ Biryukov og Khovratovich, 2009 , s. ti.
↑ 1 2 Biryukov og Khovratovich, 2009 , s. 12.
↑ 1 2 3 4 5 John Kelsey, 1996 .
↑ Biham, 1994 , s. 2.
↑ Panasenko S., 2009 , s. 59.

Litteratur

Shnaer B. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog. - Triumf, 2002. - 816 s. - ISBN 5-89392-055-4 , 0-471-11709-9.
Eli Biham . Nye typer kryptoanalytiske angreb ved hjælp af relaterede nøgler // Springer-Verlag: Journal. - 1994. - Nej. 4 . - S. 229-246 . — ISSN 1432-1378 . - doi : 10.1007/BF00203965 .
Alex Biryukov , Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192 and AES-256 // Springer Berlin Heidelberg: Journal. - 2009. - S. 1-18 . — ISSN 978-3-642-10366-7 . - doi : 10.1007/978-3-642-10366-7_1 .
Alex Biryukov, David Wagner. Slide-angreb // Hurtig softwarekryptering. 6th International Workshop, FSE'99 Rom, Italien, 24.-26. marts, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - ISBN 978-3-540-66226-6 . (utilgængeligt link)
Panasenko S. Kryptanalytiske angreb på sammenkædede nøgler // CIO-World : journal. – 2007.
Panasenko S. Krypteringsalgoritmer. Særlig håndbog . - BHV-Petersburg. - 2009. - S. 53-59.
Alexander Tyrenko. DES-algoritmen knækkede på tre dage // Computerworld Russia: magazine. - 1998. - Nr. 28-29 .
John Kelsey, Bruce Schneier, David Wagner. Key-Schedule Cryptanalyse af IDEA, G-DES, GOST, SAFER og Triple-DES // Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 18.-22. august 1996, Proceedings : magasin. – 1996.
Mihir Bellare og Tadayoshi Kohno. En teoretisk behandling af relaterede nøgleangreb: RKA-PRP'er, RKA-PRF'er og applikationer . — EUROCRYPT. - 2003. - S. 491-506.