Nøgle-gættet angreb

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 21. marts 2015; checks kræver 24 redigeringer .

Valgt nøgleangreb er en af metoderne til kryptoanalytisk angreb , som overvåger driften af en krypteringsalgoritme , der bruger flere hemmelige nøgler . En kryptoanalytiker har i starten kun information om et bestemt matematisk forhold, der forbinder nøglerne.

Beskrivelse

Ifølge Kerckhoffs-princippet har kryptanalytikeren alle de nødvendige oplysninger om det anvendte krypteringssystem, bortset fra et bestemt sæt hemmelige parametre kaldet nøglen. En kryptoanalytiker kender kun forholdet mellem et par nøgler. Den bruger chifferteksten og det givne forhold til at gætte begge nøgler. To typer af valgte nøgleangreb er kendt: den valgte nøgle og det kendte klartekstangreb, hvor kun relationen mellem nøgleparret er specificeret af kryptoanalytikeren, og det valgte nøgle- og klartekstangreb, hvor kryptoanalytikeren sætter både relationen mellem nøglepar og og selve klarteksten, som skal krypteres. [en]

Et angreb baseret på en valgt nøgle udføres på samme måde på alle kryptosystemer, inklusive den såkaldte "black box", hvor alle egenskaber er ukendte. Denne "sorte boks" bruger krypteringsfunktionen , som er valgt på samme måde for tilfældige permutationer af meddelelser. Bits af nøglen er valgt tilfældigt, således at kendskab til chifferteksten ikke kan fortælle os noget om chifferteksten for nøglen . ${\displaystyle E_{k))$ $k$ $E_{k}(m)$ $E_{h}(m')$ $h\neq k$

Angrebsalgoritmen baseret på den valgte nøgle på den "sorte boks" ud over standardoperationer kan på ethvert tidspunkt af beregningen kræve:

krypter eller dekrypter ved hjælp af den hemmelige nøgle og den matchede meddelelse og inversionsvektor , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $m$ $l$
bruge den "sorte boks" til beregning eller ved hjælp af en tast (som ikke er en funktion ) ved at hente en besked . $E_{h}(m)$ $E_{h}^{-1}(m)$ $h$ $k$ $m$

Algoritmen kan også have adgang til en tilfældig bitgenerator. I slutningen af beregningen udlæses den estimerede nøgle . [2] $k$

Således, hvis brugeren bruger en hemmelig nøgle og et offentligt kryptosystem ( public key cryptosystem ), så kan kryptoanalytikeren til enhver tid vælge en besked og en inversionsvektor og udføre kryptering eller dekryptering . Hovedanvendelsen af et gættet nøgleangreb er at verificere systemer, men under visse omstændigheder kan dette angreb anvendes i praksis. Hvis en stream-chiffer bruges til at overføre en sessionsnøgle fra bruger til bruger , og kryptanalytikeren får kontrol over transmissionslinjen, så kan han ændre alle bits af nøglen efter hans smag og vil modtage den ændrede nøgle i stedet for . Derefter, når den starter transmissionen med den forkerte nøgle, vil den modtage en forvansket besked og starte gendannelsesproceduren. I mellemtiden vil kryptanalytikeren modtage teksten krypteret med nøglen. (God kryptobeskyttelse kan afværge sådanne angreb ved at bruge nye uafhængige sessionsnøgler eller ved at tilføje ikke-lineære fejldetektionsbits til sessionsnøglen, når der er behov for en gendannelsesprocedure. Historien viser dog, at god kryptobeskyttelse ikke altid følger dette, og det er ønskeligt at have et system, der ikke går ned under et sådant angreb) [3] . $k$ $E$ $m$ $l$ $E_{{k\oplus l}}$ $E_{{k\oplus l}}^{{-1}}$ $k$ $EN$ $B$ $B$ $k\oplus l$ $k$ $B$ $EN$ $k\oplus l$

Hovedtypen af angreb baseret på en valgt nøgle

I denne del vil vi overveje et angreb, der ikke afhænger af en specifik svaghed i krypteringsfunktionen. Det er et man-in-the-middle-angreb ( MITM ). Denne type angreb giver dig mulighed for at reducere tiden for den avancerede søgning, afhængigt af antallet af tilladte nøgleinversioner [4] .

Sætning. Lad være en blokcifre med en n-bit nøgle. Antag, at kryptoanalytikeren kan udføre inversioner og har hukommelsesord. Så vil han være i stand til at knække chifferen i ekstra trin [4] . $E$ $2^{p}$ $2^{p}$ $E$ $2^{{np}}$

Bevis:

Analytikeren erstatter de sidste bits i nøglen på alle mulige måder. For eksempel krypterer det værdierne $s$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\dots 01)}}(m),\dots ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\dots 011\dots 1)}}(m)

hvor er brugerens private nøgle og enhver passende besked. Det opretter en hash-tabel ud fra værdierne [4] . $k$ $m$ $2^{p}$ $(E_{{k\oplus j}},j)$

Den udfører derefter kryptering ved at ændre de første bits af nøglen og nulstille de sidste bits: $2^{{np}}$ $np$ $s$

E_{{(00\dots 0)}}(m),E_{{(00\dots 10\dots )}}(m),\dots ,E_{{(11\dots 10\ldots 0)}}( m)

Efter alle beregninger kontrolleres hver værdi mod hash-tabellen [4] .

Hvis den originale nøgle er knækket igennem , hvor består af de sidste bits, så vil indtastningen matche resultatet gennem kryptering i anden fase. Når et match er fundet, vil det være en kandidatnøgle. Adskillige falske alarmer er mulige, hvis flere nøgler matcher meddelelsen , men som i et matchet tekstangreb vil en eller to yderligere blokke af kendt klartekst næsten helt sikkert udelukke dem, med ringe indflydelse på kørselstiden [4] . $k$ $(a,b)$ $b$ $s$ $(E_{{k\oplus b}},b)$ $a^{{th}}$ $(a,b)$ $m$

Konklusion: Ved at bruge et ubegrænset antal valgte nøgleangreb kan enhver blokchiffer med en n-bit nøgle brydes ved brug af ikke mere end in-memory beregninger [4] . $O(2^{{n/2}})$

Bevis: Lad os vælge . $p=n/2$

Bemærk: For et stort antal eksempler og en stor mængde tilgængelig hukommelse vil det være meget mere effektivt at bytte de to stadier i beviset for sætningen. Beregn og gem krypteringer i hukommelsen. For hver opgave skal du udføre inversioner og kontrollere tabellen for overholdelse. Der vil således blive brugt iterationer på hver ekstra opgave [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Sårbarhed af blokkode til angreb baseret på valgt nøgle

Vi vil demonstrere mulighederne for denne type angreb på et kryptosystem, som har vist sig at være ekstremt modstandsdygtigt over for et matchet tekstangreb [3] .

Lad være en hemmelig blokcifre med en nøglestørrelse af bits. Lad os definere en ny blokcifre . $E$ $n$ $F$

F_{k}(m)=E_{k}(m)

hvis den første bit er 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

i andre tilfælde, hvor resultatet af inversionen af den første bit er f.eks .

k'

k

k'=k\oplus(1,0,\ldots ,0)

F

legitim blokcifre:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

hvis den første bit af nøglen er 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\oplus k)

, i andre tilfælde

Hvis hovedkrypteringen har god n-bit beskyttelse, kræver det en avanceret søgning i nøglebitrummet at bryde chifferen med et tekstanalyseangreb . Med andre ord, hvis analytikeren ikke har information om chifferen , så kan han få de nødvendige oplysninger, hvis han krypterer eller dekrypterer med nøglerne eller [3] . $E$ $F$ $n-1$ $E$ $k$ $k'$

Selvom chifferen er svær at bryde med et valgt tekstangreb, er det meget nemt at bryde med et valgt nøgleangreb. Analytikeren har brug for to cifre: og for en passende besked . Hvis den første bit er nul, så $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $m$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

I andre tilfælde,

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Således modtager analytikeren straks alle bits af nøglen , undtagen den første, og kan fuldføre operationen, da han kender klarteksten [4] . $k$

Eksempler på angreb

Angreb på LOKI89

I LOKI89-chifferet har hvert valg af to undernøgler , en fra en lige cyklus og en fra en ulige cyklus, en tilsvarende 64-bit nøgle. Da alle algoritmer til at opnå to undernøgler fra de to foregående er de samme, påvirker placeringen af de cyklusser, hvori de to aktuelle undernøgler er placeret, ikke outputtet af de følgende undernøgler. Hvis vi fikser to undernøgler og nøgler og definerer den anden nøgle ved at vælge og , så vil værdierne af nøglens undernøgler være de samme som de følgende undernøgler af nøglen . I så fald . Dette forhold bevares for alle to nøgler valgt på denne måde: hvis informationen før den anden krypteringscyklus med nøglen er den samme som informationen før den første kryptering med nøglen , så er informationen og inputdata for funktionen de samme i begge operationer forskudt med én cyklus. I dette tilfælde, hvis klarteksten er krypteret med nøglen , så vil chifferteksten før den anden cyklus være . De modtagne data er de samme som dem, der blev fundet før den første krypteringscyklus med nøglen , hvis værdi vil være , og dermed i dette par $K2$ $K3$ $K$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ $K(i+1)$ $K$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $K$ $K^{*}$ $F$ $P$ $K$ $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

P ∗ = ( P R , P L ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( P R ⊕ K R , K L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Du kan se, at højre side af udtrykket er den samme som venstre side af udtrykket , og forholdet mellem de to andre dele afhænger af tonearten. I et sådant par er der et lignende forhold mellem chiffertekster:

P

P^{{*}}

C ∗ = ( C R ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( C L ⊕ K R , K L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Graferne beskriver forholdet mellem undernøglerne til de to nøgler og forholdet mellem værdierne under krypteringsprocessen.

ORDNING

Et key-matched-plaintext-angreb, der er afhængigt af disse egenskaber, vælger en 32-bit værdi , klartekster , hvis højre side er , og hvis 32-bit venstre halvdel er tilfældigt valgt, og klartekster , hvis venstre side er , og hvis højre side er valgt tilfældigt. To ukendte tilknyttede nøgler bruges til at kryptere klartekstdata på systemet under undersøgelse: Nøglen bruges til at kryptere de første klartekster, og nøglen bruges til at kryptere de resterende klartekster. For hvert par af klartekster og det er garanteret , og med høj sandsynlighed er der to klartekster, sådan at . For et sådant par forbliver dataene de samme, hvis begge udførelser forskydes med én cyklus. Et sådant par kan let udvælges, hvis det findes, ved at kontrollere ligheden.Sandsynligheden for at bestå denne prøve tilfældigt er , så kun et par par vil kunne bestå den. $P_{R}$ $2^{16}$ $P_{0},...,P_{65535}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $K$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $P_{{i}}$ $P_{j}^{*}$ $P_{jL}^{*}=P_{iR}$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ $2^{-32}$

Par, der har disse egenskaber for almindelig tekst og chiffertekst, opfylder nøglekravene (1) og (2). For dette par er forholdet således opfyldt , hvor værdien er den eneste ukendte . Af alle de mulige værdier er det kun få, der opfylder ligningen. Ved at bruge differentiel krypterings- og optimeringsteknikker kan man finde en værdi i nogle få operationer. Når værdien er fundet , er det nemt at beregne ved hjælp af formlerne (1) og (2) for at få og . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $K$ $K^{*}$

Et lignende valgt-nøgle-kendt-klartekst-angreb bruger kendte klartekster krypteret med en ukendt nøgle og klartekster krypteret med en relateret nøgle . Et par med disse egenskaber kan let identificeres med 32 almindelige stykker almindelig tekst og 32 almindelige bidder af chiffertekst. Dette par kan bruges til at søge efter nøgler på samme måde som i et valgt nøgle og valgt klartekstangreb. [en] $2^{32}$ $P_{{i}}$ $K$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Sammenligning med andre typer angreb

Ifølge Bruce Schneier er der 7 hovedmåder til kryptoanalytisk angreb [5] :

Angreb kun ved hjælp af chiffertekst.
En obduktion ved hjælp af klartekst.
Et angreb med den valgte klartekst.
Adaptivt angreb ved hjælp af klartekst.
Angreb ved hjælp af den valgte chiffertekst.
Åbning med den valgte tast.
Bandit-krypteringsanalyse .

I tilfælde af et chiffertekst-baseret angreb har kryptoanalytikeren kun adgang til chifferteksten. Dette er den sværeste type angreb på grund af den lille mængde information, der er tilgængelig.

I et kendt klartekstangreb kender kryptanalytikeren både klarteksten og chifferteksten. Denne type angreb er mere effektiv end et chiffertekstbaseret angreb på grund af den større mængde kendt information om kryptosystemet.

Et valgt klartekstangreb er en mere kraftfuld type angreb end et kendt klartekstangreb. Muligheden for at forudvælge almindelig tekst giver flere muligheder for at udtrække systemnøglen. Det er også rigtigt, at hvis et kryptosystem er sårbart over for et kendt klartekstangreb, så er det også sårbart over for et valgt almindeligtekstangreb. [en]

Et matchet nøgleangreb er stærkere end et matchet tekstangreb. Den knækker øjeblikkeligt en specialfremstillet blokchiffer, der er sikker mod andre angreb. For enhver blokchiffer kan et valgt nøgleangreb fremskynde den avancerede søgeproces afhængigt af antallet af tilladte nøgleinversioner. For et ubegrænset gættet nøgleangreb kan mængden af arbejde reduceres som en kvadratrod. Disse resultater er de bedst mulige for et generelt angreb, der ikke er afhængig af nogen bestemt blokchiffer.

Noter

↑ 1 2 3 Biham, 1993 .
↑ Winternitz & Hellman, 1987 .
↑ 1 2 3 4 Winternitz & Hellman, 1987 , s. 17
↑ 1 2 3 4 5 6 7 8 Winternitz & Hellman, 1987 , s. atten
↑ Schneier, 2003 .

Litteratur

Robert Winternitz, Martin Hellman . Valgte nøgleangreb på en blokchiffer // Cryptologia : journal. - 1987. - Nej. 11:1 . - S. 16-20 . - doi : 10.1080/0161-118791861749 .
Eli Biham. Nye typer af kryptoanalytiske angreb med relaterede nøgler // Helleseth T. (red) Advances in Cryptology . — EUROCRYPT '93. EUROCRYPT 1993. Lecture Notes in Computer Science, bind 765. Springer, Berlin, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Anvendt kryptografi. - Triumf, 2003. - 816 s. - ISBN 5-89392-055-4 .