Setkání ve střední metodě

V kryptoanalýze je metoda setkání uprostřed nebo „ útok setkání uprostřed “ třídou útoků na kryptografické algoritmy , které asymptoticky zkracují dobu úplného výčtu díky principu „ rozděl a panuj “ , stejně jako zvýšení množství požadované paměti . Tuto metodu poprvé navrhli Whitfield Diffie a Martin Hellman v roce 1977 [1] .

Počáteční podmínky

Jsou uvedeny otevřené (nešifrované) a šifrované texty. Šifrovací systém se skládá z šifrovacích cyklů . Cyklické klíče jsou nezávislé a nesdílejí společné bity. Systémový klíč je kombinací -cyklických klíčů . Úkolem je najít klíč . $h$ $K$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $K$

Jednoduché řešení případu

Jednoduchým příkladem je dvojité sekvenční blokové šifrování se dvěma různými klíči a . Proces šifrování vypadá takto: $K_1$ $K_{2}$

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

kde je prostý text, je šifrovaný text a je jednorázová operace šifrování s klíčem . Obrácená operace - dešifrování - tedy vypadá takto: $p$ $s$ $ENC_{K_{i}}()$ $K_{i}$

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

Na první pohled se zdá, že použití dvojitého šifrování výrazně zvyšuje bezpečnost celého schématu, protože nyní je třeba vytřídit dva klíče a ne jeden. V případě algoritmu DES se bezpečnost zvyšuje z na . Nicméně není. Útočník může vytvořit dvě tabulky: $2^{56}$ $2^{112}$

Všechny hodnoty pro všechny možné hodnoty , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Všechny hodnoty pro všechny možné hodnoty . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Pak už jen potřebuje v těchto tabulkách najít shody, tedy takové hodnoty a , že . Každá shoda odpovídá sadě klíčů , která splňuje podmínku. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ $(K_{1},K_{2})$

Tento útok vyžadoval operace šifrování a dešifrování (pouze dvakrát tolik než pro výčet jednoho klíče) a paměť. Dodatečné optimalizace - použití hash tabulek , výpočty pouze pro polovinu klíčů (pro DES , vyčerpávající vyhledávání ve skutečnosti vyžaduje pouze operace) - mohou tyto požadavky snížit. Hlavním výsledkem útoku je, že dvouklíčové sekvenční šifrování pouze zdvojnásobuje dobu hrubou silou. $2^{57}$ $2^{57}$ $2^{55}$

Obecné řešení

Označme transformaci algoritmu jako , kde je otevřený text a je šifrový text. Může být reprezentován jako skladba , kde je cyklická transformace na tónině . Každý klíč je binární délkový vektor a veřejný klíč systému je délkový vektor . $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$

Plnění paměti

Všechny hodnoty jsou seřazeny , tj. první cyklické klíče. Na každém takovém klíči zašifrujeme otevřený text - (to znamená, že místo cyklů procházíme šifrovacími cykly ). Budeme to považovat za určitou adresu paměti a na tuto adresu zapíšeme hodnotu . Je nutné iterovat přes všechny hodnoty . $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'$

Definice klíče

Vše možné je vyřešeno . Na přijatých klíčích je šifrovaný text dešifrován - . Pokud adresa není prázdná, získáme klíč odtud a získáme klíčového kandidáta . $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$

Je však třeba poznamenat, že první obdržený kandidát nemusí být nutně tím pravým klíčem. Ano, pro data a , ale na jiných hodnotách šifrovaného textu s otevřeným textem získaným ze skutečného klíče může být rovnost porušena. Vše závisí na konkrétních vlastnostech kryptosystému . Někdy ale stačí pořídit si takový „pseudoekvivalentní“ klíč. V opačném případě bude po dokončení postupů získána určitá sada klíčů , mezi nimiž je skutečný klíč. $k$ $A$ $b$ $E_{k}(a)=b$ $A'$ $b'$ $A'$ ${\displaystyle {k',k''...))$

Pokud vezmeme v úvahu konkrétní aplikaci, pak šifrovaný text a prostý text mohou být velké (například grafické soubory) a představují dostatečně velký počet bloků pro blokovou šifru . V tomto případě, abyste proces urychlili, můžete zašifrovat a dešifrovat ne celý text, ale pouze jeho první blok (což je mnohem rychlejší) a poté, co jste obdrželi mnoho kandidátů, vyhledejte v něm skutečný klíč a zkontrolujte jej zbývající bloky.

Útok s rozdělením sekvence kláves na 3 části

V některých případech může být obtížné oddělit bity sekvence kláves na části související s různými klávesami. V tomto případě je použit algoritmus 3-subset MITM attack navržený Bogdanovem a Richbergerem v roce 2011 na základě obvyklé metody setkání uprostřed. Tento algoritmus je použitelný, když není možné rozdělit sekvence bitů klíče na dvě nezávislé části. Skládá se ze dvou fází: extrakce a ověření klíčů [2] .

Fáze extrakce klíče

Na začátku této fáze je šifra rozdělena na 2 podšifry a jako v obecném případě útoku však umožňuje případné použití některých bitů jedné podšifry v jiné. Takže, když , tak ; v tomto případě budou bity klíče použité v in označeny a v — pomocí . Poté lze klíčovou sekvenci rozdělit na 3 části: $F$ $G$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $F$ ${\displaystyle k_{f))$ $G$ $kg}$

$A_0$ je průsečíkem množin a , ${\displaystyle k_{f))$ $kg}$
$A_{1}$ - klíčové bity, které jsou pouze v , ${\displaystyle k_{f))$
$A_{2}$ - klíčové bity, které jsou pouze v . $kg}$

Dále je útok proveden metodou setkání uprostřed podle následujícího algoritmu:

Pro každý prvek z $A_0$

Vypočítejte střední hodnotu , kde je otevřený text a jsou některé bity klíče od a , to znamená, že je výsledkem středního šifrování otevřeného textu na klíči . $i=f(k_{f},a)$ $A$ ${\displaystyle k_{f))$ $A_0$ $A_{1}$ $i$ ${\displaystyle k_{f))$
Vypočítejte střední hodnotu , kde je soukromý text a jsou některé bity klíče od a , to znamená, že je výsledkem středního dešifrování soukromého textu na klíči . $j=g^{-1}(k_{g},b)$ $b$ $kg}$ $A_0$ $A_{2}$ $j$ $kg}$
Porovnejte a . V případě shody získáme kandidáta na klíče. $i$ $j$

Fáze ověření klíče

Pro kontrolu klíčů jsou přijatí kandidáti porovnáni s několika páry známých veřejně-soukromých textů. Obvykle není k ověření potřeba příliš velký počet takových dvojic textů [2] .

Příklad

Jako příklad si uveďme útok na rodinu šifer KTANTAN [3] , který umožnil snížit výpočetní náročnost získání klíče z (brute force attack) na [1] . $2^{80}$ $2^{75,170}$

Příprava útoku

Každé z 254 kol šifrování pomocí KTANTAN používá 2 náhodné bity klíče z 80bitové sady. Díky tomu je složitost algoritmu závislá pouze na počtu kol. Při zahájení útoku si autoři všimli následujících vlastností:

V kolech 1 až 111 nebyly použity následující klíčové bity: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
V kolech 131 až 254 nebyly použity následující klíčové bity: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

To umožnilo rozdělit klíčové bity do následujících skupin:

$A_0$ - společné bity klíče: těch 68 bitů, které nejsou uvedeny výše.
$A_{1}$ - bity použité pouze v prvním bloku kol (od 1 do 111),
$A_{2}$ - bity použité pouze ve druhém bloku kol (od 131 do 254).

Fáze jedna: Extrakce klíčů

Při výpočtu výše popsaných hodnot došlo k problému , protože v úvahu chybí kola od 112 do 130, ale poté bylo provedeno částečné srovnání : autoři útoku zaznamenali shodu 8 bitů v a , zkontroluje je normálním útokem pomocí metody setkání uprostřed ve 127. kole. V tomto ohledu byly v této fázi porovnány hodnoty těchto 8 bitů v subšifrách a . Tím se zvýšil počet klíčových kandidátů, ale ne výpočetní náročnost. $i$ $j$ $i$ $j$ $i$ $j$

Druhá fáze: ověření klíčů

K otestování klíčových kandidátů pro algoritmus KTANTAN32 bylo k extrakci klíče zapotřebí průměrně dalších dvou párů veřejného a soukromého textu.

Výsledky

KTANTAN32: Výpočetní složitost hádání klíče snížena na použití tří párů veřejného a soukromého textu. $2^{75,170}$
KTANTAN48: Výpočetní složitost hádání klíče snížena na použití dvou párů veřejného a soukromého textu. $2^{75,044}$
KTANTAN64: Výpočetní složitost hádání klíče snížena na použití dvou párů veřejného a soukromého textu. $2^{75,584}$

To však není nejlepší útok na rodinu šifer KTANTAN. V roce 2011 byl proveden útok [4] , který snížil výpočetní složitost algoritmu na použití čtyř otevřených a uzavřených textových párů. $2^{72.9}$

Útok na kompletní bipartitní graf

Útok s plným bipartitním grafem se používá ke zvýšení počtu pokusů o proxy útok vytvořením úplného bipartitního grafu . Navrhli Diffie a Hellman v roce 1977.

Vícerozměrný algoritmus

Vícerozměrný algoritmus meeting-in-the-middle se používá při použití velkého počtu šifrovacích cyklů s různými klíči na blokových šifrách . Namísto obvyklého „setkání uprostřed“ tento algoritmus využívá rozdělení kryptotextu několika mezilehlými body [5] .

Předpokládá se, že napadený text je několikrát zašifrován blokovou šifrou:

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

Algoritmus

Vypočteno:

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

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

{\displaystyle sC_{1))

je uložen spolu s 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}

je uložen spolu s d .

k_{b_{n+1))

H_{b_{n+1))

Pro každý možný mezistav vypočítejte: $s_{1}$

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

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

pro každou shodu s prvkem od do a jsou uloženy .

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

uloženo s v .

k_{f_{2))

H_2

Pro každý možný mezistav vypočítejte: $s_{2}$

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

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

pro každou shodu s prvkem z je zaškrtnuta shoda s , po které jsou a uloženy v .

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

uloženo s v .

k_{f_{3))

H_3

Pro každý možný mezistav vypočítejte: $s_{n}$

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

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

a pro každou shodu s prvkem z je zaškrtnuta shoda s , po které jsou a uloženy v .

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

a pro každou shodu s , shoda s

sC_{n+1}

H_{n+1}

T_{n}

Dále je nalezená sekvence kandidátů testována na jiném páru veřejného a soukromého textu, aby se potvrdila platnost klíčů. Je třeba poznamenat, že algoritmus je rekurzivní: výběr klíčů pro stav je založen na výsledcích pro stav . To vnáší do tohoto algoritmu prvek exponenciální složitosti [5] . $s_{j}$ $s_{j-1}$

Obtížnost

Časová složitost tohoto útoku je $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}}|}+...))$

Když už mluvíme o využití paměti, je snadné vidět, že s každým zvýšením jsou uvalována další a další omezení, což snižuje počet kandidátů, kteří jsou do ní zapsáni. To znamená mnohem méně . $i$ $T_{i}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

Horní limit množství použité paměti:

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

kde je celková délka klíče.

k

Složitost použití dat závisí na pravděpodobnosti „předání“ falešného klíče. Tato pravděpodobnost je rovna , kde je délka prvního mezistavu, který se nejčastěji rovná velikosti bloku. Vzhledem k počtu klíčových kandidátů po první fázi je složitost . ${\displaystyle 1/2^{l))$ $l$ $2^{|k|-|l|}$

V důsledku toho dostaneme , kde je velikost bloku. ${\displaystyle 2^{|k|-2b))$ $|b|$

Pokaždé, když je kandidátská klíčová sekvence testována na novém páru veřejného a soukromého textu, počet klíčů, které testem projdou, se vynásobí pravděpodobností úspěšného předání klíče, což je . $1/2^{|b|}$

Část útoku hrubou silou (kontrola klíčů proti novým veřejným a soukromým textovým párům) má časovou složitost , ve které mají samozřejmě následující výrazy tendenci nulovat rychleji a rychleji. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

V důsledku toho je složitost dat podle podobných úsudků omezena přibližně na páry klíčů veřejného a soukromého sektoru. $\left\lceil |k|/n\right\rceil$

Poznámky

↑ 12 Diffie , Whitfield; Hellman, Martin E. Vyčerpávající kryptoanalýza standardu šifrování dat NBS (anglicky) // Počítač: časopis. - 1977. - Červen ( roč. 10 , č. 6 ). - str. 74-84 . - doi : 10.1109/CM.1977.217750 . Archivováno z originálu 14. května 2009.
↑ 1 2 Andrey Bogdanov a Christian Rechberger. „At 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN“ Archived 7. listopadu 2018 na Wayback Machine
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. „KATAN & KTANTAN – rodina malých a účinných hardwarově orientovaných blokových šifer“ Archivováno 20. dubna 2018 na Wayback Machine
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang a San Ling. „Vylepšená kryptoanalýza Meet-in-the-Middle of KTANTAN“ Archivováno 7. listopadu 2018 na Wayback Machine
↑ 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack a jeho aplikace na GOST, KTANTAN a Hummingbird-2 (anglicky) // eCrypt: journal. — 2011.

Literatura

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