Találkozás a középső módszerben

A kriptoanalízisben a meet-in-the-middle módszer vagy a " me-in-the-middle attack " a kriptográfiai algoritmusok elleni támadások osztálya, amelyek aszimptotikusan csökkentik a teljes felsorolás idejét az " oszd meg és uralkodj " elv miatt. , valamint a szükséges memória mennyiségének növelése . Ezt a módszert először Whitfield Diffie és Martin Hellman javasolta 1977-ben [1] .

Kiindulási feltételek

A nyílt (titkosítatlan) és a titkosított szövegek megadva. A kriptorendszer titkosítási ciklusokból áll . A ciklikus kulcsok függetlenek, és nem osztoznak közös biteken. A rendszerbillentyű a -ciklikus billentyűk kombinációja . A feladat a kulcs megtalálása . $h$ $K$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $K$

Egyszerű esetmegoldás

Egy egyszerű példa a kettős szekvenciális blokk titkosítás két különböző kulccsal és . A titkosítási folyamat így néz ki: $K_1$ $K_{2}$

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

ahol az egyszerű szöveg, a titkosított szöveg, és az egyszeri titkosítási művelet a kulccsal . Ennek megfelelően a fordított művelet - dekódolás - így néz ki: $p$ $s$ $ENC_{K_{i}}()$ $K_{i}$

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

Első pillantásra úgy tűnik, hogy a kettős titkosítás használata nagyban növeli az egész rendszer biztonságát, mivel most két kulcsot kell rendezni , nem pedig egyet. A DES algoritmus esetén a biztonság ról -ra növekszik . Azonban nem. Egy támadó két táblát hozhat létre: $2^{56}$ $2^{112}$

Minden érték az összes lehetséges értékhez , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Minden érték az összes lehetséges értékhez . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Ekkor már csak egyezéseket kell találnia ezekben a táblázatokban, vagyis olyan értékeket és , hogy . Minden egyezés a feltételnek megfelelő kulcskészletnek felel meg. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ ${\megjelenítési stílus (K_{1}, K_{2})}$

Ez a támadás titkosítási-dekódolási műveleteket igényelt (csak kétszer annyit, mint egy kulcs felsorolásához) és memóriát. További optimalizálás - hash táblák használata , számítások csak a kulcsok feléhez (a DES esetén a kimerítő keresés valójában csak műveleteket igényel) - csökkenthetik ezeket a követelményeket. A támadás fő eredménye, hogy a kétkulcsos szekvenciális titkosítás csak megduplázza a brute force idejét. $2^{57}$ $2^{57}$ $2^{55}$

Általános megoldás

Jelöljük az algoritmus transzformációját így , ahol a nyílt szöveg és a titkosított szöveg. Kompozícióként ábrázolható , ahol ciklikus transzformáció van a kulcson . Minden kulcs egy bináris hosszúságú vektor , a rendszer nyilvános kulcsa pedig egy hosszvektor . $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\times h$

Memória feltöltése

Minden érték ki van rendezve , azaz az első ciklikus billentyűk. Minden ilyen kulcson titkosítjuk a nyílt szöveget - (vagyis titkosítási ciklusokon megyünk keresztül a helyett ). Egy bizonyos memóriacímnek fogjuk tekinteni, és erre a címre írjuk az értéket . Minden értéket át kell ismételni . $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'$

Kulcsdefiníció

Minden lehetséges rendezve van . A kapott kulcsokon a titkosított szöveg dekódolásra kerül - . Ha a cím nem üres, akkor onnan kapjuk a kulcsot, és kapunk egy kulcsjelöltet . $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$

Meg kell azonban jegyezni, hogy az elsőként kapott jelölt nem feltétlenül az igazi kulcs. Igen, a és adatok esetében , de a valódi kulcsból nyert egyszerű szöveges titkosított szöveg egyéb értékeinél az egyenlőség sérülhet. Minden a kriptorendszer sajátosságaitól függ . De néha elég egy ilyen "pszeudo-ekvivalens" kulcsot szerezni. Ellenkező esetben az eljárások befejezése után egy bizonyos kulcskészletet kapunk , amelyek között van az igazi kulcs. $k$ $a$ $b$ $E_{k}(a)=b$ $a'$ $b'$ $a'$ ${\displaystyle {k',k''...))$

Ha egy adott alkalmazást veszünk figyelembe, akkor a rejtjelezett szöveg és az egyszerű szöveg lehet nagy (például grafikus fájlok), és kellően nagy számú blokkot jelenthet egy blokk titkosításhoz . Ebben az esetben a folyamat felgyorsítása érdekében nem a teljes szöveget titkosíthatja és dekódolhatja, hanem csak az első blokkját (ami sokkal gyorsabb), majd miután sok jelöltet kapott, megkeresi benne a valódi kulcsot, ellenőrizve azt. a fennmaradó blokkokat.

Támadás a billentyűsorozat 3 részre bontásával

Egyes esetekben nehéz lehet egy kulcssorozat bitjeit a különböző kulcsokhoz kapcsolódó részekre szétválasztani. Ebben az esetben a Bogdanov és Richberger által 2011-ben javasolt 3 részhalmazból álló MITM támadás Ez az algoritmus akkor alkalmazható, ha a kulcsbitsorozatokat nem lehet két független részre osztani. Két fázisból áll: a kulcsok kivonásából és ellenőrzéséből [2] .

Kulcskivonási fázis

Ennek a fázisnak az elején a rejtjel két alrejtjelre oszlik, és a támadás általános esetéhez hasonlóan lehetővé teszi az egyik alrejtjel egyes biteinek használatát egy másikban. Tehát, ha , akkor ; ebben az esetben az in használt kulcs bitjeit , in — -vel jelöljük . Ezután a billentyűsor három részre osztható: $f$ $g$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $f$ ${\displaystyle k_{f))$ $g$ $k_{g}$

$A_0$ az és a halmazok metszéspontja , ${\displaystyle k_{f))$ $k_{g}$
$A_{1}$ - kulcsbitek, amelyek csak a -ban vannak , ${\displaystyle k_{f))$
$A_{2}$ - kulcsbitek, amelyek csak a -ban vannak . $k_{g}$

Ezután a támadást a középső találkozás módszerével hajtják végre a következő algoritmus szerint:

Minden elemhez $A_0$

Számítsa ki a köztes értéket , ahol a nyílt szöveg, és néhány kulcsbit a és -ból , azaz a kulcson lévő nyílt szöveg közbenső titkosításának eredménye . $i=f(k_{f},a)$ $a$ ${\displaystyle k_{f))$ $A_0$ $A_{1}$ $én$ ${\displaystyle k_{f))$
Számítsa ki a köztes értéket , ahol a privát szöveg, és néhány kulcsbit a és -ből , vagyis a kulcson lévő privát szöveg közbenső visszafejtésének eredménye . $j=g^{-1}(k_{g},b)$ $b$ $k_{g}$ $A_0$ $A_{2}$ $j$ $k_{g}$
Hasonlítsa össze és . Egyezés esetén jelöltet kapunk a kulcsokra. $én$ $j$

Kulcsérvényesítési fázis

A kulcsok ellenőrzéséhez a beérkezett jelölteket több pár ismert nyilvános-magán szöveghez hasonlítják. Általában nem nagyon sok ilyen szövegpárra van szükség az ellenőrzéshez [2] .

Példa

Példaként vegyünk egy támadást a KTANTAN rejtjelcsalád ellen [3] , amely lehetővé tette a kulcs megszerzésének számítási bonyolultságának csökkentését (brute force attack) -ról [1] -re . $2^{80}$ $2^{75 170}$

Támadás előkészítése

A KTANTAN-t használó 254 titkosítási kör mindegyike a kulcs 2 véletlenszerű bitjét használja egy 80 bites készletből. Ezáltal az algoritmus bonyolultsága csak a körök számától függ. A támadás indításakor a szerzők a következő jellemzőket vették észre:

Az 1-től 111-ig terjedő körökben a következő kulcsbiteket nem használták: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
A 131-től 254-ig terjedő körben a következő kulcsbiteket nem használták: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Ez lehetővé tette a kulcsbitek felosztását a következő csoportokra:

$A_0$ - közös kulcsbitek: a fent nem említett 68 bit.
$A_{1}$ - csak a körök első blokkjában használt bitek (1-től 111-ig),
$A_{2}$ - csak a második körben használt bitek (131-től 254-ig).

Első fázis: Kulcskivonás

Probléma adódott a fent leírt és értékeinek kiszámításakor , mivel a 112-től 130-ig terjedő körök hiányoznak a mérlegelésből, de ezután részleges összehasonlításra került sor : a támadás szerzői 8 bites egyezést észleltek. és , normál támadással ellenőrizve őket a találkozó a középső módszerrel a 127. fordulóban. Ebben a fázisban ennek a 8 bitnek az értékeit az alrejtjelekben hasonlították össze . Ez növelte a kulcsfontosságú jelöltek számát, de nem a számítási bonyolultságot. $én$ $j$ $én$ $j$ $én$ $j$

Második fázis: a kulcsok ellenőrzése

A KTANTAN32 algoritmus kulcsjelöltjeinek teszteléséhez átlagosan még két nyilvános-privát szövegpárra volt szükség a kulcs kinyeréséhez.

Eredmények

KTANTAN32: A kulcsfontosságú kitalálás számítási bonyolultsága három nyilvános-privát szövegpár használatára csökkent. $2^{75 170}$
KTANTAN48: A kulcsfontosságú kitalálás számítási bonyolultsága két nyilvános-privát szövegpár használatára csökkent. $2^{75 044}$
KTANTAN64: A kulcsfontosságú kitalálás számítási bonyolultsága két nyilvános-privát szövegpár használatára csökkent. $2^{75,584}$

Ez azonban nem a legjobb támadás a KTANTAN titkosítócsalád ellen. 2011-ben egy támadást hajtottak végre [4] , amely az algoritmus számítási bonyolultságát négy nyitott-zárt szövegpár használatára csökkentette. $2^{72.9}$

Támadás egy teljes kétoldalú gráf ellen

A teljes kétoldalú gráftámadást a proxytámadási kísérletek számának növelésére használják egy teljes kétoldalú gráf felépítésével . Diffie és Hellman javasolta 1977-ben.

Többváltozós algoritmus

A többdimenziós találkozás a közepén algoritmust akkor használják, ha nagyszámú titkosítási ciklust használnak különböző kulcsokkal a blokkrejtjeleken . Ez az algoritmus a szokásos "középen találkozás" helyett a kriptotextus több köztes ponttal való felosztását használja [5] .

Feltételezzük, hogy a támadott szöveget bizonyos számú alkalommal titkosítják egy blokk titkosítással:

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

Algoritmus

Számított:

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

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

sC_{1}

d -vel együtt tárolódik .

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}

d -vel együtt tárolódik .

k_{b_{n+1))

H_{b_{n+1))

Minden lehetséges köztes állapothoz számítsa ki: $s_{1}$

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

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

minden egyezéshez egy elemmel tól ig , és tárolódnak .

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}

a következővel mentve : .

k_{f_{2))

H_2

Minden lehetséges köztes állapothoz számítsa ki: $s_{2}$

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

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

minden egyes találatnál a -ból származó elemmel ellenőrzik a -val való egyezést , majd a és a -ban tárolódnak .

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

sC_{3}

a következővel mentve : .

k_{f_{3))

H_3

Minden lehetséges köztes állapothoz számítsa ki: $s_{n}$

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

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

és minden egyes találatnál a -ból származó elemmel egyezés ellenőrződik a -val , majd a és a -ban tárolódnak .

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

és minden egyezéshez -val , egy meccs -val

sC_{n+1}

H_{n+1}

T_{n}

Ezután a jelöltek talált sorozatát egy másik nyilvános-privát szövegpáron tesztelik, hogy megerősítsék a kulcsok érvényességét. Meg kell jegyezni, hogy az algoritmus rekurzív: az állapot kulcsainak kiválasztása az állapot eredményein alapul . Ez egy exponenciális bonyolultságú elemet vezet be ebbe az algoritmusba [5] . $s_{j}$ $s_{j-1}$

Nehézség

Ennek a támadásnak az időbeli összetettsége az $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}}|}+...))$

Ha már a memóriahasználatról beszélünk, könnyen belátható, hogy ahogy mindegyik növekszik , egyre több korlátozást vezetnek be, ami csökkenti a ráírható jelöltek számát. Ez sokkal kevesebbet jelent . $én$ $T_{i}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

A felhasznált memória felső határa:

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

hol van a kulcs teljes hossza.

k

Az adatok felhasználásának bonyolultsága a hamis kulcs „átadásának” valószínűségétől függ. Ez a valószínűség egyenlő , ahol az első köztes állapot hossza, amely legtöbbször megegyezik a blokk méretével. Tekintettel a kulcsfontosságú jelöltek számára az első fázis után, a bonyolultság . ${\displaystyle 1/2^{l))$ $l$ $2^{|k|-|l|}$

Ennek eredményeként azt kapjuk , hogy hol van a blokk mérete. ${\displaystyle 2^{|k|-2b))$ $|b|$

Minden alkalommal, amikor egy jelölt kulcssorozatot tesztelnek egy új nyilvános-privát szövegpáron, a teszten átmenő kulcsok számát megszorozzák a kulcs átadásának valószínűségével, ami . $1/2^{|b|}$

A brute-force támadás egy része (a kulcsok ellenőrzése az új nyilvános-privát szövegpárok ellen) időbonyolultságú , amelyben nyilvánvalóan a következő kifejezések egyre gyorsabban nullázódnak. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Ennek eredményeként az adatok összetettsége hasonló megítélés szerint megközelítőleg a nyilvános-privát kulcspárokra korlátozódik. $\left\lceil |k|/n\right\rceil$

Jegyzetek

↑ 12 Diffie , Whitfield; Hellman, Martin E. Exhaustive Cryptanalysis of the NBS Data Encryption Standard (angol) // Computer : Journal. - 1977. - június ( 10. évf. , 6. sz.). - 74-84 . o . - doi : 10.1109/CM.1977.217750 . Az eredetiből archiválva : 2009. május 14.
↑ 1 2 Andrey Bogdanov és Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Archiválva : 2018. november 7. a Wayback Machine -nél
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. "KATAN & KTANTAN – Kis és hatékony hardver-orientált blokkrejtjelek családja" archiválva : 2018. április 20. a Wayback Machine -nél
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang és San Ling. "A KTANTAN továbbfejlesztett Meet-in-the-Middle Cryptanalysis" archiválva 2018. november 7-én a Wayback Machine -nél
↑ 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack és alkalmazásai a GOST-hoz, a KTANTAN-hoz és a Hummingbird-2-höz (angol) // eCrypt : folyóirat. – 2011.

Irodalom

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