Möte i mitten-metoden

Inom kryptoanalys är mötet-i-mitt- metoden eller " möte-i-mitt-attacken " en klass av attacker på kryptografiska algoritmer som asymptotiskt minskar tiden för en fullständig uppräkning på grund av " dela och erövra " -principen samt öka mängden minne som krävs . Denna metod föreslogs först av Whitfield Diffie och Martin Hellman 1977 [1] .

Inledande villkor

De öppna (okrypterade) och chiffertexterna ges. Ett kryptosystem består av krypteringscykler . De cykliska nycklarna är oberoende och delar inte gemensamma bitar. Systemnyckeln är en kombination av -cykliska tangenter . Uppgiften är att hitta nyckeln . $h$ $K$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $K$

Enkel case-lösning

Ett enkelt exempel är dubbelsekventiell blockkryptering med två olika nycklar och . Krypteringsprocessen ser ut så här: $K_1$ $K_{2}$

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

var är klartexten, är chiffertexten och är engångskrypteringsoperationen med nyckeln . Följaktligen ser den omvända operationen - dekryptering - ut så här: $sid$ $s$ $ENC_{K_{i}}()$ $K_{i}$

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

Vid första anblicken verkar det som att användningen av dubbel kryptering avsevärt ökar säkerheten för hela systemet, eftersom nu två nycklar måste sorteras ut, och inte en. När det gäller DES-algoritmen ökar säkerheten från till . Det är det dock inte. En angripare kan skapa två tabeller: $2^{56}$ $2^{112}$

Alla värden för alla möjliga värden , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Alla värden för alla möjliga värden . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Sedan behöver han bara hitta matchningar i dessa tabeller, det vill säga sådana värden och , att . Varje match motsvarar en uppsättning nycklar som uppfyller villkoret. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ $(K_{1},K_{2})$

Denna attack krävde kryptering-dekrypteringsoperationer (endast dubbelt så många som för uppräkning av en nyckel) och minne. Ytterligare optimeringar - användning av hashtabeller , beräkningar för endast hälften av nycklarna (för DES kräver en uttömmande sökning faktiskt bara operationer) - kan minska dessa krav. Huvudresultatet av attacken är att tvånycklars sekventiell kryptering endast fördubblar brute-force-tiden. $2^{57}$ $2^{57}$ $2^{55}$

Allmän lösning

Låt oss beteckna transformationen av algoritmen som , var är klartexten och är chiffertexten. Det kan representeras som en komposition , där är en cyklisk transformation på tangenten . Varje nyckel är en binär längdvektor och systemets publika nyckel är en längdvektor . $E_{k}(a)=b$ $a$ $b$ $E_{k_{1}}E_{k_{2}}...E_{k_{h}}(a)=b$ $E_{k_{i))$ $k_i$ $k_i$ $n$ $n\ gånger h$

Fyller minnet

Alla värden sorteras bort , det vill säga de första cykliska nycklarna. På varje sådan nyckel krypterar vi klartexten - (det vill säga vi går igenom krypteringscykler istället för ). Vi kommer att betrakta det som en viss minnesadress och skriva värdet till denna adress . Det är nödvändigt att iterera över alla värden . $k'=(k_{1},k_{2}...k_{r})$ $r$ $k'$ $a$ $E_{k'}(a)=E_{k_{1}}E_{k_{2}}...E_{k_{r}}(a)=S$ $r$ $h$ $S$ $k'$ $k'$

Nyckeldefinition

Allt möjligt är utsorterat . På de mottagna nycklarna är chiffertexten dekrypterad - . Om adressen inte är tom får vi nyckeln därifrån och får en nyckelkandidat . $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 bör dock noteras att den första kandidaten som tas emot inte nödvändigtvis är den sanna nyckeln. Ja, för data och , men på andra värden i klartextchiffertexten som erhålls från den sanna nyckeln, kan jämlikhet kränkas. Allt beror på kryptosystemets specifika egenskaper . Men ibland räcker det med att få en sådan "pseudo-ekvivalent" nyckel. Annars kommer en viss uppsättning nycklar att erhållas efter att procedurerna har slutförts , bland vilka är den sanna nyckeln. $k$ $a$ $b$ $E_{k}(a)=b$ $a'$ $b'$ $a'$ ${\displaystyle {k',k''...))$

Om vi överväger en specifik applikation kan chiffertexten och klartexten vara stora (till exempel grafiska filer) och representera ett tillräckligt stort antal block för ett blockchiffer . I det här fallet, för att påskynda processen, kan du kryptera och dekryptera inte hela texten, utan bara dess första block (vilket är mycket snabbare) och sedan, efter att ha fått många kandidater, leta efter den sanna nyckeln i den, kontrollera den på de återstående blocken.

Attackera genom att dela upp tangentsekvensen i 3 delar

I vissa fall kan det vara svårt att separera bitarna i en nyckelsekvens i delar relaterade till olika nycklar. I det här fallet används MITM-attackalgoritmen med 3 delmängder som föreslagits av Bogdanov och Richberger 2011 baserat på den vanliga metoden att mötas i mitten. Denna algoritm är tillämpbar när det inte är möjligt att dela upp nyckelbitsekvenserna i två oberoende delar. Den består av två faser: utvinning och verifiering av nycklar [2] .

Nyckelextraktionsfas

I början av denna fas delas chifferen upp i 2 subchiffer och , som i det allmänna fallet med attacken, tillåter dock möjlig användning av vissa bitar av en subcipher i en annan. Så, om , då ; i det här fallet kommer bitarna av nyckeln som används i att betecknas med , och i — med . Sedan kan tangentsekvensen delas in i 3 delar: $f$ $g$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $f$ ${\displaystyle k_{f))$ $g$ $k_{g}$

$A_0$ är skärningspunkten mellan uppsättningarna och , ${\displaystyle k_{f))$ $k_{g}$
$A_{1}$ - nyckelbitar som bara finns i , ${\displaystyle k_{f))$
$A_{2}$ - nyckelbitar som bara finns i . $k_{g}$

Därefter utförs en attack med metoden att mötas i mitten enligt följande algoritm:

För varje element från $A_0$

Beräkna det mellanliggande värdet , där är klartexten, och är några nyckelbitar från och , det vill säga är resultatet av den mellanliggande krypteringen av klartexten på nyckeln . $i=f(k_{f},a)$ $a$ ${\displaystyle k_{f))$ $A_0$ $A_{1}$ $i$ ${\displaystyle k_{f))$
Beräkna det mellanliggande värdet , där är den privata texten, och är några nyckelbitar från och , det vill säga är resultatet av den mellanliggande dekrypteringen av den privata texten på nyckeln . $j=g^{-1}(k_{g},b)$ $b$ $k_{g}$ $A_0$ $A_{2}$ $j$ $k_{g}$
Jämför och . Vid match får vi en kandidat till nycklarna. $i$ $j$

Nyckelvalideringsfas

För att kontrollera nycklarna kontrolleras de mottagna kandidaterna mot flera par kända offentlig-privata texter. Vanligtvis krävs inte ett särskilt stort antal sådana textpar för verifiering [2] .

Exempel

Som ett exempel, låt oss ta en attack på KTANTAN-chifferfamiljen [3] , som gjorde det möjligt att minska beräkningskomplexiteten för att erhålla en nyckel från (brute force attack) till [1] . $2^{80}$ $2^{75,170}$

Förbereder en attack

Var och en av de 254 omgångarna av kryptering med KTANTAN använder 2 slumpmässiga bitar av nyckeln från en 80-bitars uppsättning. Detta gör att komplexiteten hos algoritmen endast beror på antalet omgångar. I början av attacken märkte författarna följande funktioner:

I omgångarna 1 till 111 användes inte följande nyckelbitar: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
I omgångarna 131 till 254 användes inte följande nyckelbitar: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Detta gjorde det möjligt att dela upp nyckelbitarna i följande grupper:

$A_0$ - Vanliga nyckelbitar: de 68 bitarna som inte nämns ovan.
$A_{1}$ - bitar som endast används i det första blocket av omgångar (från 1 till 111),
$A_{2}$ - bitar som endast används i det andra blocket av omgångar (från 131 till 254).

Fas ett: Nyckelextraktion

Det fanns ett problem med att beräkna värdena för och beskrivna ovan , eftersom omgångar från 112 till 130 saknas i övervägandet, men sedan utfördes en partiell jämförelse : författarna till attacken märkte en matchning på 8 bitar in och , kontrollera dem med en normal attack med hjälp av mötet i mitten-metoden vid omgång 127. I detta avseende, i denna fas, jämfördes värdena av dessa 8 bitar i underchiffrorna och . Detta ökade antalet nyckelkandidater, men inte beräkningskomplexiteten. $i$ $j$ $i$ $j$ $i$ $j$

Andra fasen: verifiering av nycklar

För att testa nyckelkandidater för KTANTAN32-algoritmen tog det i genomsnitt ytterligare två offentlig-privata textpar för att extrahera nyckeln.

Resultat

KTANTAN32: Nyckelgissning beräkningskomplexitet reducerad till att använda tre offentlig-privata textpar. $2^{75,170}$
KTANTAN48: Nyckelgissning beräkningskomplexitet reducerad till att använda två offentlig-privata textpar. $2^{75 044}$
KTANTAN64: Nyckelgissning beräkningskomplexitet reducerad till att använda två offentlig-privata textpar. $2^{75,584}$

Detta är dock inte den bästa attacken mot chifferfamiljen KTANTAN. 2011 gjordes en attack [4] som reducerade algoritmens beräkningskomplexitet till att använda fyra öppet-stängda textpar. $2^{72.9}$

Attack mot en komplett tvådelad graf

Den fullständiga tvådelade grafattacken används för att öka antalet proxyattackförsök genom att bygga en hel tvådelad graf . Föreslog av Diffie och Hellman 1977.

Multivariat algoritm

Den flerdimensionella möte-i-mitt-algoritmen används när man använder ett stort antal krypteringscykler med olika nycklar på blockchiffer . Istället för det vanliga "mötet i mitten" använder denna algoritm uppdelningen av kryptotexten med flera mellanliggande punkter [5] .

Det antas att den attackerade texten krypteras ett visst antal gånger med ett blockchiffer:

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

Algoritm

Beräknad:

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

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

{\displaystyle sC_{1))

lagras tillsammans 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}

lagras tillsammans med d .

k_{b_{n+1))

H_{b_{n+1))

Beräkna för varje möjligt mellantillstånd : $s_{1}$

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

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

för varje matchning med ett element från till och lagras .

{\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

{\displaystyle sC_{2))

sparas med i .

k_{f_{2))

H_2

Beräkna för varje möjligt mellantillstånd : $s_{2}$

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

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

för varje matchning med ett element från , kontrolleras en matchning med , varefter och lagras i .

{\displaystyle 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))

sparas med i .

k_{f_{3))

H_3

Beräkna för varje möjligt mellantillstånd : $s_{n}$

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

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

och för varje matchning med ett element från , kontrolleras en matchning med , varefter och lagras 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

och för varje match med , en match med

sC_{n+1}

H_{n+1}

T_{n}

Därefter testas den hittade sekvensen av kandidater på ett annat par offentlig-privat text för att bekräfta nycklarnas giltighet. Det bör noteras att algoritmen är rekursiv: valet av nycklar för staten baseras på resultaten för staten . Detta introducerar ett element av exponentiell komplexitet i denna algoritm [5] . $s_{j}$ $s_{j-1}$

Svårighet

Tidskomplexiteten för denna attack är $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}}|}+...))$

På tal om minnesanvändning är det lätt att se att allt eftersom varje ökar , införs fler och fler begränsningar, vilket minskar antalet kandidater som skrivs till den. Detta betyder mycket mindre . $i$ $T_{i}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

Den övre gränsen för mängden minne som används:

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

var är nyckelns totala längd.

k

Komplexiteten i att använda data beror på sannolikheten att "passera" en falsk nyckel. Denna sannolikhet är lika med , där är längden på det första mellantillståndet, som oftast är lika med blockstorleken. Med tanke på antalet nyckelkandidater efter den första fasen är komplexiteten . $1/2^{l}$ $l$ $2^{|k|-|l|}$

Som ett resultat får vi , var är blockstorleken. ${\displaystyle 2^{|k|-2b))$ $|b|$

Varje gång en kandidatnyckelsekvens testas på ett nytt offentligt-privat textpar, multipliceras antalet nycklar som klarar testet med sannolikheten att klara nyckeln, vilket är . $1/2^{|b|}$

En del av brute-force-attacken (kontroll av nycklar mot nya offentlig-privata textpar) har tidskomplexitet , där efterföljande termer uppenbarligen tenderar att nollställas snabbare och snabbare. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Som ett resultat är datakomplexiteten genom liknande bedömningar begränsad till ungefär offentlig-privata nyckelpar. $\left\lceil |k|/n\right\rceil$

Anteckningar

↑ 12 Diffie , Whitfield; Hellman, Martin E. Exhaustive Cryptanalysis of the NBS Data Encryption Standard (engelska) // Computer : journal. - 1977. - Juni ( vol. 10 , nr 6 ). - S. 74-84 . - doi : 10.1109/CM.1977.217750 . Arkiverad från originalet den 14 maj 2009.
↑ 1 2 Andrey Bogdanov och Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Arkiverad 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 Chiphers" Arkiverad 20 april 2018 på Wayback Machine
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang och San Ling. "Förbättrad Meet-in-the-Middle Cryptanalysis of KTANTAN" Arkiverad 7 november 2018 på Wayback Machine
↑ 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack och dess tillämpningar på GOST, KTANTAN och Hummingbird-2 (engelska) // eCrypt : journal. — 2011.

Litteratur

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