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] .
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íč .
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:
,
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:
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:
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.
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.
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 .
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 .
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 .
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íč.
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.
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] .
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:
Dále je útok proveden metodou setkání uprostřed podle následujícího algoritmu:
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] .
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] .
Příprava útokuKaž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í:
To umožnilo rozdělit klíčové bity do následujících skupin:
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.
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ýsledkyTo 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ů.
Ú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 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:
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] .
Časová složitost tohoto útoku je
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ě .
Horní limit množství použité paměti:
kde je celková délka klíče.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 .
V důsledku toho dostaneme , kde je velikost bloku.
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 .
Čá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.
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.