Møde i midten metode

I kryptoanalyse er møde-i-midt- metoden eller " møde-i-midt-angrebet " en klasse af angreb på kryptografiske algoritmer , der asymptotisk reducerer tiden for en fuldstændig opregning på grund af " del og hersk " -princippet samt øge den nødvendige mængde hukommelse . Denne metode blev først foreslået af Whitfield Diffie og Martin Hellman i 1977 [1] .

Indledende betingelser

De åbne (ukrypterede) og chiffertekster er givet. Et kryptosystem består af krypteringscyklusser . De cykliske taster er uafhængige og deler ikke fælles bit. Systemnøglen er en kombination af -cykliske taster . Opgaven er at finde nøglen . $h$ $K$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $K$

Simpel case-løsning

Et simpelt eksempel er dobbelt sekventiel blokkryptering med to forskellige nøgler og . Krypteringsprocessen ser sådan ud: $K_1$ $K_{2}$

$s=ENC_{K_{2}}(ENC_{K_{1}}(p))$ ,

hvor er klarteksten, er chifferteksten og er engangskrypteringsoperationen med nøglen . Følgelig ser den omvendte operation - dekryptering - sådan ud: $s$ $s$ $ENC_{K_{i}}()$ $K_{i}$

$p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))$

Umiddelbart ser det ud til, at brugen af dobbeltkryptering i høj grad øger sikkerheden for hele ordningen, da der nu skal sorteres to nøgler fra, og ikke én. I tilfælde af DES-algoritmen øges sikkerheden fra til . Det er det dog ikke. En angriber kan oprette to tabeller: $2^{56}$ $2^{112}$

Alle værdier for alle mulige værdier , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Alle værdier for alle mulige værdier . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Så mangler han kun at finde matches i disse tabeller, det vil sige sådanne værdier og , at . Hver kamp svarer til et sæt nøgler , der opfylder betingelsen. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ $(K_{1},K_{2})$

Dette angreb krævede krypterings-dekrypteringsoperationer (kun dobbelt så mange som ved opregning af én nøgle) og hukommelse. Yderligere optimeringer - brug af hashtabeller , beregninger for kun halvdelen af nøglerne (for DES kræver udtømmende søgning faktisk kun operationer) - kan reducere disse krav. Hovedresultatet af angrebet er, at to-nøgle sekventiel kryptering kun fordobler brute-force-tiden. $2^{57}$ $2^{57}$ $2^{55}$

Generel løsning

Lad os betegne transformationen af algoritmen som , hvor er klarteksten og er chifferteksten. Det kan repræsenteres som en komposition , hvor der er en cyklisk transformation på tangenten . Hver nøgle er en binær længdevektor , og systemets offentlige nøgle er en længdevektor . $E_{k}(a)=b$ $-en$ $b$ $E_{k_{1}}E_{k_{2}}...E_{k_{h}}(a)=b$ $E_{k_{i))$ $k_i$ $k_i$ $n$ $n\ gange h$

Fylder hukommelsen

Alle værdier er sorteret fra , dvs. de første cykliske taster. På hver sådan nøgle krypterer vi klarteksten - (det vil sige, vi gennemgår krypteringscyklusser i stedet for ). Vi vil betragte det som en bestemt hukommelsesadresse og skrive værdien til denne adresse . Det er nødvendigt at gentage alle værdier . $k'=(k_{1},k_{2}...k_{r})$ $r$ $k'$ $-en$ $E_{k'}(a)=E_{k_{1}}E_{k_{2}}...E_{k_{r}}(a)=S$ $r$ $h$ $S$ $k'$ $k'$

Nøgledefinition

Alt muligt er sorteret fra . På de modtagne nøgler er chifferteksten dekrypteret - . Hvis adressen ikke er tom, så henter vi nøglen derfra og får en nøglekandidat . $k''=(k_{r+1},k_{r+2}...k_{h})$ $b$ $E_{k''}^{-1}(b)=E_{k_{h}}^{-1}...E_{k_{r+1}}^{-1}(b) =S'$ $S'$ $k'$ $(k',k'')=k$

Det skal dog bemærkes, at den første kandidat, der modtages , ikke nødvendigvis er den sande nøgle. Ja, for data og , men på andre værdier af den almindelige tekstchiffertekst , der er opnået fra den sande nøgle, kan lighed blive krænket. Det hele afhænger af kryptosystemets specifikke karakteristika . Men nogle gange er det nok at få sådan en "pseudo-ækvivalent" nøgle. Ellers, efter afslutningen af procedurerne, opnås et bestemt sæt nøgler , blandt hvilke den sande nøgle er. $k$ $-en$ $b$ $E_{k}(a)=b$ $en'$ $b'$ $en'$ ${\displaystyle {k',k''...))$

Hvis vi overvejer en specifik applikation, så kan chifferteksten og almindelig tekst være store (for eksempel grafiske filer) og repræsentere et tilstrækkeligt stort antal blokke til en blokchiffer . I dette tilfælde kan du for at fremskynde processen kryptere og dekryptere ikke hele teksten, men kun dens første blok (som er meget hurtigere) og derefter, efter at have modtaget mange kandidater, se efter den sande nøgle i den, kontrollere den på de resterende blokke.

Angreb med at opdele nøglesekvensen i 3 dele

I nogle tilfælde kan det være svært at adskille bits af en nøglesekvens i dele relateret til forskellige nøgler. I dette tilfælde bruges 3-undersæt MITM-angrebsalgoritmen af Bogdanov og Richberger i 2011 baseret på den sædvanlige metode til at mødes i midten. Denne algoritme er anvendelig, når det ikke er muligt at opdele nøglebitsekvenserne i to uafhængige dele. Den består af to faser: udtrækning og verifikation af nøgler [2] .

Nøgleekstraktionsfase

I begyndelsen af denne fase er chifferen opdelt i 2 subciphers og , som i det generelle tilfælde af angrebet, tillader det dog mulig brug af nogle bits af en subcipher i en anden. Så hvis , så ; i dette tilfælde vil bits af nøglen , der bruges i , blive betegnet med , og i — med . Derefter kan nøglesekvensen opdeles i 3 dele: $f$ $g$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $f$ ${\displaystyle k_{f))$ $g$ $k_{g}$

$A_0$ er skæringspunktet mellem mængderne og , ${\displaystyle k_{f))$ $k_{g}$
$A_{1}$ - nøglebits, der kun er i , ${\displaystyle k_{f))$
$A_{2}$ - nøglebits, der kun er i . $k_{g}$

Dernæst udføres et angreb ved metoden til at mødes i midten i henhold til følgende algoritme:

For hvert element fra $A_0$

Beregn den mellemliggende værdi , hvor er klarteksten, og er nogle nøglebits fra og , det vil sige er resultatet af den mellemliggende kryptering af klarteksten på nøglen . $i=f(k_{f},a)$ $-en$ ${\displaystyle k_{f))$ $A_0$ $A_{1}$ $jeg$ ${\displaystyle k_{f))$
Beregn den mellemliggende værdi , hvor er den private tekst, og er nogle nøglebits fra og , det vil sige er resultatet af den mellemliggende dekryptering af den private tekst på nøglen . $j=g^{-1}(k_{g},b)$ $b$ $k_{g}$ $A_0$ $A_{2}$ $j$ $k_{g}$
Sammenlign og . Ved kamp får vi en kandidat til nøglerne. $jeg$ $j$

Nøglevalideringsfase

For at kontrollere nøglerne, tjekkes de modtagne kandidater mod flere par kendte offentlig-private tekster. Normalt kræves der ikke et meget stort antal af sådanne tekstpar til verifikation [2] .

Eksempel

Lad os som et eksempel tage et angreb på KTANTAN-chifferfamilien [3] , som gjorde det muligt at reducere den beregningsmæssige kompleksitet ved at få en nøgle fra (brute force attack) til [1] . $2^{80}$ $2^{75.170}$

Forbereder et angreb

Hver af de 254 runder af kryptering ved hjælp af KTANTAN bruger 2 tilfældige bits af nøglen fra et 80-bit sæt. Dette gør kompleksiteten af algoritmen kun afhængig af antallet af runder. Da angrebet startede, lagde forfatterne mærke til følgende funktioner:

I runde 1 til 111 blev følgende nøglebit ikke brugt: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
I runde 131 til 254 blev følgende nøglebit ikke brugt: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Dette gjorde det muligt at opdele nøglebittene i følgende grupper:

$A_0$ - Fælles nøglebits: de 68 bits, der ikke er nævnt ovenfor.
$A_{1}$ - bits, der kun bruges i den første blok af runder (fra 1 til 111),
$A_{2}$ - bits, der kun bruges i den anden blok af runder (fra 131 til 254).

Fase 1: Nøgleudtrækning

Der var et problem med at beregne værdierne af og beskrevet ovenfor , da runder fra 112 til 130 mangler i betragtningen, men derefter blev der foretaget en delvis sammenligning : forfatterne til angrebet bemærkede en match på 8 bit ind og , kontrollere dem med et normalt angreb ved hjælp af mødet i midten-metoden ved runde 127. I denne henseende, i denne fase, blev værdierne af disse 8 bit i undercifre og sammenlignet . Dette øgede antallet af nøglekandidater, men ikke den beregningsmæssige kompleksitet. $jeg$ $j$ $jeg$ $j$ $jeg$ $j$

Anden fase: verifikation af nøgler

For at teste nøglekandidater til KTANTAN32-algoritmen tog det i gennemsnit yderligere to offentlig-private tekstpar at udtrække nøglen.

Resultater

KTANTAN32: Nøgle gætte beregningsmæssig kompleksitet reduceret til at bruge tre offentlig-private tekstpar. $2^{75.170}$
KTANTAN48: Nøgle gætte beregningsmæssig kompleksitet reduceret til at bruge to offentlig-private tekstpar. $2^{75.044}$
KTANTAN64: Nøgle gætte beregningsmæssig kompleksitet reduceret til at bruge to offentlig-private tekstpar. $2^{75.584}$

Dette er dog ikke det bedste angreb på KTANTAN-chifferfamilien. I 2011 blev der foretaget et angreb [4] , der reducerede algoritmens beregningsmæssige kompleksitet til at bruge fire åbne-lukkede tekstpar. $2^{72.9}$

Angreb på en komplet todelt graf

Det fulde todelte grafangreb bruges til at øge antallet af proxyangrebsforsøg ved at bygge en fuld todelt graf . Foreslået af Diffie og Hellman i 1977.

Multivariat algoritme

Den multidimensionelle møde-i-midt-algoritme bruges, når der bruges et stort antal krypteringscyklusser med forskellige nøgler på blokcifre . I stedet for det sædvanlige "møde i midten" bruger denne algoritme opdelingen af kryptoteksten med flere mellempunkter [5] .

Det antages, at den angrebne tekst er krypteret et vist antal gange med en blokchiffer:

$C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P)))...))$ $P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C)))...))$

Algoritme

Beregnet:

sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)

\forall k_{f_{1}}\in K

{\displaystyle sC_{1))

opbevares sammen med d .

k_{1}

H_1

sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}}),C)

\forall k_{b_{n+1}}\in K

sC_{n+1}

opbevares sammen med d .

k_{b_{n+1))

H_{b_{n+1))

Beregn for hver mulig mellemtilstand : $s_{1}$

sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})

\forall k_{b_{1}}\in K

for hver kamp med et element fra til og gemmes .

{\displaystyle sC_{1))

H_1

T_{1}

k_{b_{1))

k_{f_{1))

sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})

\forall k_{f_{2}}\in K

sC_{2}

gemt med i .

k_{f_{2))

H_2

Beregn for hver mulig mellemtilstand : $s_{2}$

sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})

\forall k_{b_{2}}\in K

for hvert match med et element fra , afkrydses et match med , hvorefter og gemmes i .

sC_{2}

H_2

T_{1}

T_{2}

k_{b_{2))

k_{f_{2))

sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})

\forall k_{f_{3}}\in K

{\displaystyle sC_{3))

gemt med i .

k_{f_{3))

H_3

Beregn for hver mulig mellemtilstand : $s_{n}$

sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})

\forall k_{b_{n}}\in K

og for hvert match med et element fra , afkrydses et match med , hvorefter og gemmes i .

sC_{n}

H_n

{\displaystyle T_{n-1))

T_{n}

k_{b_{n))

k_{f_{n))

sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})

\forall k_{f_{n+1}}\in K

og for hver kamp med , en kamp med

sC_{n+1}

H_{n+1}

T_{n}

Dernæst testes den fundne sekvens af kandidater på et andet par offentlig-private tekster for at bekræfte nøglernes gyldighed. Det skal bemærkes, at algoritmen er rekursiv: Udvælgelsen af nøgler for staten er baseret på resultaterne for staten . Dette introducerer et element af eksponentiel kompleksitet i denne algoritme [5] . $s_{j}$ $s_{j-1}$

Sværhedsgrad

Tidskompleksiteten af dette angreb er $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}\cdot (2^{| k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}\cdot (2^{|k_{b_{2}}|} +2^{|k_{f_{3}}|}+...))$

Når vi taler om hukommelsesbrug, er det let at se, at efterhånden som hver stigning bliver pålagt flere og flere begrænsninger, hvilket reducerer antallet af kandidater, der skrives til den. Dette betyder meget mindre . $jeg$ $T_{i}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

Den øvre grænse for mængden af brugt hukommelse:

2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+...

hvor er nøglens samlede længde.

k

Kompleksiteten ved at bruge data afhænger af sandsynligheden for at "passere" en falsk nøgle. Denne sandsynlighed er lig med , hvor er længden af den første mellemtilstand, som oftest er lig med blokstørrelsen. I betragtning af antallet af nøglekandidater efter den første fase er kompleksiteten . ${\displaystyle 1/2^{l))$ $l$ $2^{|k|-|l|}$

Som et resultat får vi , hvor er blokstørrelsen. ${\displaystyle 2^{|k|-2b))$ $|b|$

Hver gang en kandidatnøglesekvens testes på et nyt offentligt-privat tekstpar, ganges antallet af nøgler, der består testen, med sandsynligheden for at bestå nøglen, hvilket er . $1/2^{|b|}$

En del af brute-force-angrebet (kontrol af nøgler mod nye offentlig-private tekstpar) har tidskompleksitet , hvor efterfølgende termer naturligvis har en tendens til at nulstilles hurtigere og hurtigere. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Som et resultat er datakompleksitet ved lignende vurderinger begrænset til tilnærmelsesvis offentlig-private nøglepar. $\left\lceil |k|/n\right\rceil$

Noter

↑ 12 Diffie , Whitfield; Hellman, Martin E. Udtømmende krypteringsanalyse af NBS Data Encryption Standard (engelsk) // Computer: tidsskrift. - 1977. - Juni ( bind 10 , nr. 6 ). - S. 74-84 . - doi : 10.1109/CM.1977.217750 . Arkiveret fra originalen den 14. maj 2009.
↑ 1 2 Andrey Bogdanov og Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Arkiveret 7. november 2018 på Wayback Machine
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. "KATAN & KTANTAN - A Family of Small and Efficient Hardware-Oriented Block Ciphers" Arkiveret 20. april 2018 på Wayback Machine
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang og San Ling. "Forbedret Meet-in-the-Middle Cryptanalysis of KTANTAN" Arkiveret 7. november 2018 på Wayback Machine
↑ 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack og dets applikationer til GOST, KTANTAN og Hummingbird-2 (engelsk) // eCrypt : journal. – 2011.

Litteratur

Moore, Stephane. Meet-in-the-Middle-angreb (neopr.) . - 2010. - 16. november. - S. 2 .