Meet-in-the-middle attack

Meet-in-the-Middle útok ( MITM ) je obecný šifrovací útok.

[ editovat ]Popis

MITM je obecný útok, použitelné na několika kryptografických systémů. Vnitřní struktura konkrétního systému je proto zanedbatelná na tento útok. To je možné, i když ji kombinovat s jinými druhy útoku, jak tomu bylo.

Přirozeně to vyžaduje schopnost šifrovat a dešifrovat, a držení párů otevřeného a odpovídajících ciphertexts.

Při pokusu o zlepšení bezpečnosti na blokové šifry, lákavá představa je jednoduše použít několik nezávislých tlačítek pro šifrování dat několikrát pomocí posloupnost funkcí (šifrování). Pak by se mohlo zdát, že tato čtyřhra, nebo dokonce n -tice v bezpečnosti s několikanásobným šifrovací schéma, v závislosti na počtu šifrování data musí projít.

Meet-in-the-Middle útok pokusí najít hodnotu pomocí jak o rozsahu (ciphertext) a doménu (plaintext) na složení několika funkcí (nebo blokové šifry), tak, že dopředu mapování během prvních funkcí je stejný jako zpětné mapování (inverzní obraz) přes posledních funkcí, doslova plnění v polovině složené funkce.

Multidimenzionální MITM (MD-MITM) využívá kombinaci několika souběžných útoků MITM-rád popsáno výše, kde se schůzka se děje v různých pozicích ve složení funkce.

Jistě, vyčerpávající hledání na všechny možné kombinace kláves (jednoduchý BruteForce) se 2 ^{K · j} pokusy, jestliže j šifrování se používá s různými klíči v každé šifrování, kde každý klíč je k. bitů. Použití MITM nebo MD-MITM, může to dělat lépe.

[ editovat ]Historie

To byl nejprve vyvinut jako útok na pokus o rozšíření o blokové šifry podle Diffiea Hellman v roce 1977. ^[ 1 ]

Diffie Hellman a, ale vymyslel časově paměti kompromis, který by mohl prolomit režim pouze double době prolomit jedno-šifrovací schéma.

V roce 2011, Bo Zhu a Guang Gong zkoumat multidimenzionální Meet-in-the-Middle útok a představují nové útoky na blokové šifry GOST (bloková šifra) , KTANTAN a Hummingbird-2. ^[ 2 ]

[ editovat ]MITM (1D-MITM)

Předpokládejme, že útočník zná sadu holého P a šifrového C , který splňuje následující:

kde ENC je šifrovací funkce, prosinec dešifrování funkce prosince je definována jako ENC ^-1 (inverzní zobrazení) a k. ₁ a k. ₂ jsou dva klíče.

Útočník pak může vypočítat ENC _k. ₁ (P) ve všech možných klíčů k ₁ . Poté se může dešifrovat ciphertext by výpočetní prosince _k. ₂ (C) pro každý k. ₂ .Veškeré zápasy mezi těmito dvěma výsledných souborů jsou pravděpodobně objeví správná tlačítka. (Chcete-li urychlit srovnání, ENC _k ₁ (P) lze nastavit být uloženy v in-memory lookup tabulky, pak každý prosinec _k ₂ (C) může být porovnávány hodnoty ve vyhledávací tabulce najít kandidáty na klíč)

Tento útok je jeden z důvodů, proč byl DES nahrazena Triple DES - "Double DES" neposkytuje mnoho další zabezpečení proti vyčerpávající klíčový hledání útočník s 2 ⁵⁶ místa. ^[ 3 ] Nicméně, Triple DES s "triple délce" (168-bit) klíč je náchylná k meet-in-the-middle útok na 2 ⁵⁶ prostoru a 2 ¹¹² . ^[ 4 ]

Ilustrace 1D-MITM útoku

Jakmile zápasy najdou, mohou být ověřeny s druhým zkušební sadou otevřeném textu a ciphertext.

[ upravit překlad]MITM algoritmus

Vypočtěte následující:

$SubCipher_1 = ENC_ {f_1} (K_ {f_1}, P)$ ∀ $K_ {f_1}$ ∈ $K$ :

a každou uložit $SubCipher_ {1}$ spolu s odpovídající $K_ {f_1}$ v sadě

$SubCipher_1 = DEC_ {b_1} (K_ {b_1}, C)$ ∀ $K_ {b_1}$ ∈ $K$ :

a porovnat každý nový $SubCipher_1$ se souborem

Pokud je nalezena shoda, mějte k. _f ₁ , k _b ₁ jako kandidát klíč-pair v tabulce T. Zkušební páry v T na nový pár (P, C) pro potvrzení platnosti. Pokud klíč-pair nefunguje na tomto novém páru, to MITM opět na nový pár (P, C) .

[ upravit překlad ]MITM složitost

Pokud KeySize je | k |, tento útok využívá pouze 2 ^{K 1} šifrování (a decryptions) (a O (2 ^ k) paměti v případě, look-up tabulky byly vytvořeny pro soubor vpřed výpočtů) na rozdíl od naivní útok, který potřebuje 2 ^{2 · k} šifrování, ale O (1)space.

[ upravit překlad ]Multidimenzionální-MITM

Zatímco 1D-MITM může být efektivní, je sofistikovanější útok byl vyvinut: Multi-Dimensional-Meet in the Middle útoku , také zkrácený MD-MITM . To je výhodnější, když byla data zašifrována pomocí více než 2 šifrování s různými klíči. Místo setkání ve středu (jedno místo v pořadí), MD-MITM útok se pokouší dosáhnout několika konkrétních dílčích států používajících vpřed a vzad výpočty na několika místech v kódu. ^[ 2 ]

Předpokládejme, že útok má být namontován na blokové šifry, kde je šifrování a dešifrování definované jako předtím:

$C = ENC_ {k_n} ({ENC_ K_ {n-1}} (... (ENC_ {k_1} (P)) ...))$
$P = {DEC_ k_1} ({DEC_ k_2} (... (DEC_ {k_n} (C)) ...))$

že je holý P jsou šifrovány vícekrát pomocí opakování stejné blokové šifry

Ilustrace MD-MITM útoku

MD-MITM byl použit pro dešifrování mezi mnoha, GOST bloková šifra , kde bylo prokázáno, že 3D-MITM výrazně snížila časovou složitost k útoku na něj. ^[ 2 ]

[ upravit překlad ]MD-MITM algoritmus

Vypočtěte následující:

$SubCipher_1 = ENC_ {f_1} (K_ {f_1}, P)$ ∀ $K_ {f_1}$ ∈ $K$ :

a každou uložit $SubCipher_1$ s odpovídajícím $K_ {f_1}$ v sadě $H_1$ .

$SubCipher_ {n +1} = {DEC_ B_ {n +1}} ({K_ B_ {n +1}}, C)$ ∀ $K_ {B_ {n +1}}$ ∈ $K$ :

a každou uložit $SubCipher_ {n +1}$ s odpovídajícím $K_ {B_ {n +1}}$ v sadě $H_ {n +1}$ .

Pro každou možnou odhadem na mezistupni $S_1$ vypočítat následující:

$SubCipher_1 = DEC_ {b_1} (K_ {b_1}, S_1)$ ∀ $K_ {b_1}$ ∈ $K$ :

a pro každé utkání mezi tímto $SubCipher_1$ a souboru $H_1$ , uložte $K_ {b_1}$ a $K_ {f_1}$ do nové sady $T_1$ .

$SubCipher_2 = ENC_ {f_2} (K_ {f_2}, S_1)$ ∀ $K_ {f_2}$ ∈ $K$ :

a každou uložit $SubCipher_2$ s odpovídajícím $K_ {f_2}$ v sadě $H_2$ .

Pro každý možný odhad na mezistupni $S_2$ spočítat následující:

1 $SubCipher_2 = DEC_ {b_2} (K_ {b_2}, S_2)$ ∀ $K_ {b_1}$ ∈ $K$

a pro každé utkání mezi tímto $SubCipher_2$ a sady $H_2$ , zkontrolujte také, zda

se shoduje s $T_1$ a potom uložit kombinace dílčích klíčů dohromady v nové sadě $T_2$ .

2 ...

Pro každý možný odhad na mezistupni $s_n$ spočítat následující:

a) $SubCipher_n = DEC_ {b_n} (K_ {b_n}, s_n)$ ∀ $K_ {b_n}$ ∈ $K$

a pro každé utkání mezi tímto $SubCipher_n$ a sady $H_n$ , zkontrolujte také, zda

se shoduje s $T_ {n-1}$ , uložit $K_ {b_n}$ a $K_ {f_n}$ do nové sady

$T_n$ .

b) $SubCipher_ {n +1} = {ENC_ f_n +1} (K_ {f_n +1}, s_n)$ ∀ $K_ {f_ {n +1}}$ ∈ $K$

a pro každé utkání mezi tímto $SubCipher_ {n +1}$ a sady $H_ {n +1}$ , podívejte se také

zda se shoduje s $T_n$ . Pokud je to ten případ, pak: "

Použít nalezenou kombinaci dílčích klíčů $(K_ {f_1}, {K_ b_1}, {K_ f_2}, {K_ b_2}, ..., K_ {f_ {n +1}}, {K_ B_ {n +1}})$ na jiném páru holého textu / ciphertext k ověření správnosti klíče.

Poznámka: vnořené prvek v algoritmu. Odhad při každé možné hodnotě s _j se provádí pro každý odhad na předchozí s _j-1 . To tvoří prvek exponenciální složitosti k celkové časové složitosti tohoto MD-MITM útoku.

[ upravit překlad ]MD-MITM složitost

Časová složitost tohoto útoku bez hrubé síly, je $2 ^ {| K_ {f_1} |} 2 ^ {| K_ {B_ {n +1}} |} 2 ^ {| S_1 |}$ ⋅ $(2 ^ {| K_ {b_1} |} 2 ^ {| K_ {f_2} |} 2 ^ {| S_2 |}$ ⋅ $(2 ^ {| K_ {b_2} |} 2 ^ {| K_ {f_3} |} + ...))$

Pokud jde o paměti složitosti, je snadné vidět, že $T_2, T_3, ... , T_n$ jsou mnohem menší než první postavené tabulce kandidátských hodnot: $T_1$ jak jsem se zvyšuje, kandidátské hodnoty obsažené v $T_i$ musí splňovat další podmínky, a tím méně kandidáti přejde na konec určení $T_n$ .

Horní mez paměti složitosti MD-MITM je pak

$2 ^ {| K_ {f_1} |} 2 ^ {| K_ {B_ {n +1}} |} 2 ^ {| k | - | s_n |} ...$

kde $k$ označuje délka celého klíče (kombinovaný).

Údaje složitost závisí na pravděpodobnosti, že nesprávný klíč může projít (získat falešně pozitivní), který je $1/2 ^ {| l |}$ , kde $l$ je střední stav v první fázi MITM.Velikost přechodného stavu a velikost bloku je často stejný! Vzhledem k tomu, také kolik klíče, které jsou ponechány pro testování po prvním MITM-fáze, to je $2 ^ {| k |} / 2 ^ {| l |}$ .

Proto po prvním MITM fázi, jsou $2 ^ {| k |-b}$ ⋅ $2 ^ {-b} = 2 ^ {| k |-2b}$ , kde $ | b | $ je velikost bloku.

Pro každou dobu se konečná kandidátem hodnota klíče testována na nové holého / ciphertext-páru, bude množství klíčů, která projde vynásobí pravděpodobnost, že klíč může projít, který je $1/2 ^ {| b |}$ .

Část brute force testování (testování kandidátní klíč na nové (P, C) -pair, mít časovou složitost $2 ^ {| k |-b} 2 ^ {| k |-2b} 2 ^ {| k |-3b} 2 ^ {| k |-4b}$ ...

, Jasně pro zvýšení násobky b v exponentu, číslo blíží nule.

Závěr o datovém složitosti je podle podobné úvahy omezeno, že kolem ⌈ $| K | / n$ ⌉ (P, C) -páry.

Níže je konkrétní příklad toho, jak 2D-MITM je namontován:

[ upravit překlad ]Obecný příklad 2D-MITM

To je obecný popis toho, jak je 2D-MITM montáž na šifrování blokové šifry.

Ve dvou-dimenzionální MITM (2D-MITM) metoda je dosáhnout 2 mezilehlé stavy uvnitř vícenásobné šifrování otevřeného textu. Viz níže obrázku:

Ilustrace 2D-MITM útoku

Vypočtěte následující:

$SubCipher_1 = ENC_ {f_1} (K_ {f_1}, P)$ ∀ $K_ {f_1}$ ∈ $K$

a každou uložit $SubCipher_1$ spolu s odpovídající $K_ {f_1}$ v sadě

$SubCipher_2 = DEC_ {b_2} (K_ {b_2}, C)$ ∀ $K_ {b_2}$ ∈ $K$

a každou uložit $SubCipher_2$ s odpovídajícím $K_ {b_2}$ v souboru B.

Pro každý možný odhad na mezistavu s mezi $SubCipher_1$ a $SubCipher_2$ spočítat následující:

1 $SubCipher_1 = DEC_ {b_1} (K_ {b_1}, y)$ ∀ $K_ {b_1}$ ∈ $K$

a pro každé utkání mezi tímto $SubCipher_1$ a množiny, uložit $K_ {b_1}$ a $K_ {f_1}$ v novém nastavené T.

2 $SubCipher_2 = ENC_ {f_2} (K_ {f_2}, y)$ ∀ $K_ {f_2}$ ∈ $K$

a pro každé utkání mezi tímto $SubCipher_2$ a nastavenou B, zkontrolujte také, zda se shoduje s T pro

v případě, že je případ, pak:

Použít nalezenou kombinaci dílčích klíčů $(K_ {f_1}, {K_ b_1}, {K_ f_2}, {K_ b_2})$ na jiném páru holého textu / ciphertext k ověření správnosti klíče.

[ editovat ]2D-MITM složitost

Časová složitost tohoto útoku bez hrubé síly, je $2 ^ {| K_ {f_1} |} 2 ^ {| K_ {b_2} |} 2 ^ {| s |}$ ⋅ $(2 ^ {| K_ {b_1} |} 2 ^ {| K_ {f_2} |})$ , kde | ⋅ | označuje délku.

Hlavní paměť spotřeba je omezena na stavbu sad A a B , kde T je mnohem menší než ostatní.

Pro dat složitosti viz pododdíl o komplexnosti MD-MITM.