Meet-in-the-middle útok - Meet-in-the-middle attack

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek případně obsahuje syntéza materiálu což ne prokazatelně zmínit nebo týkat se k hlavnímu tématu. Relevantní diskuse je k dispozici na internetu diskusní stránka. (Květen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Meet-in-the-middle attack“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The útok typu „setkat se uprostřed“ (MITM), známý útok prostého textu^[1], je obecný časoprostorový kryptografický útok proti šifrovacím schématům, které se spoléhají na provádění několika šifrovacích operací v pořadí. Útok MITM je hlavním důvodem proč Double DES se nepoužívá a proč a Triple DES klíč (168bitový) může být bruteforced útočníkem s 2⁵⁶ prostor a 2¹¹² operace.^[2][3]

Popis

Při pokusu o zlepšení zabezpečení blokové šifry je lákavou myšlenkou několikrát zašifrovat data pomocí více klíčů. Jeden by si mohl myslet, že se to zdvojnásobuje nebo dokonce n-tuple zabezpečení schématu vícenásobného šifrování, v závislosti na tom, kolikrát jsou data zašifrována, protože vyčerpávající hledání všech možných kombinací klíčů (jednoduchá brute-force) by trvalo 2^n·k pokusy, pokud jsou data šifrována pomocí k-bitové klíče n krát.

MITM je obecný útok, který oslabuje bezpečnostní výhody používání více šifrování ukládáním mezilehlých hodnot ze šifrování nebo dešifrování a jejich použitím ke zkrácení doby potřebné k hrubému vynucení dešifrovacích klíčů. Díky tomu je útok typu Meet-in-the-Middle (MITM) obecným časoprostorovým kompromisem kryptografické Záchvat.

Útok MITM se pokouší najít klíče pomocí rozsahu (ciphertext) a domény (holý text) složení několika funkcí (nebo blokových šifer), takže dopředné mapování prostřednictvím prvních funkcí je stejné jako zpětné mapování (inverzní) obrázek) prostřednictvím posledních funkcí, a to doslova Setkání uprostřed složené funkce. Například i když Double DES šifruje data dvěma různými 56bitovými klíči, Double DES lze rozdělit pomocí 2⁵⁷ operace šifrování a dešifrování.

Multidimenzionální MITM (MD-MITM) používá kombinaci několika simultánních útoků MITM, jak je popsáno výše, kde ke schůzce dochází na více pozicích ve složené funkci.

Dějiny

Diffie a Sakra chlape nejprve navrhl útok typu „setkat se uprostřed“ na hypotetickou expanzi a bloková šifra v roce 1977.^[4]Jejich útok využil a časoprostorový kompromis rozbít schéma dvojitého šifrování pouze za dvojnásobek času potřebného k rozbití schématu jediného šifrování.

V roce 2011 Bo Zhu a Guang Gong vyšetřovali multidimenzionální útok typu meet-in-the-middle a představil nové útoky na blokové šifry GOST, KTANTAN a Kolibřík-2.^[5]

Meet-in-the-middle (1D-MITM)

Předpokládejme, že někdo chce zaútočit na šifrovací schéma s následujícími charakteristikami pro daný prostý text P a šifrovací text C:

${ displaystyle { begin {aligned} C & = { mathit {ENC}} _ ​​{k_ {2}} ({ mathit {ENC}} _ ​​{k_ {1}} (P)) P & = { mathit {DEC}} _ ​​{k_ {1}} ({ mathit {DEC}} _ ​​{k_ {2}} (C)) end {zarovnáno}}}$

kde ENC je funkce šifrování, DEC dešifrovací funkce definovaná jako ENC⁻¹ (inverzní mapování) a k₁ a k₂ jsou dva klíče.

Naivní přístup při brutálním vynucování tohoto šifrovacího schématu spočívá v dešifrování šifrovacího textu všemi možnými způsoby k₂, a dešifrujte každý z mezilehlých výstupů všemi možnými způsoby k₁, celkem 2^k₁ × 2^k₂ (nebo 2^k₁+k₂) operace.

Útok typu „setkat se uprostřed“ využívá efektivnější přístup. Dešifrováním C s k₂, jeden získá následující rovnocennost:

${ displaystyle { begin {aligned} C & = { mathit {ENC}} _ ​​{k_ {2}} ({ mathit {ENC}} _ ​​{k_ {1}} (P)) { mathit { DEC}} _ ​​{k_ {2}} (C) & = { mathit {DEC}} _ ​​{k_ {2}} ({ mathit {ENC}} _ ​​{k_ {2}} [{ mathit {ENC }} _ {k_ {1}} (P)]) { mathit {DEC}} _ ​​{k_ {2}} (C) & = { mathit {ENC}} _ ​​{k_ {1}} ( P) end {zarovnáno}}}$

Útočník může počítat ENC_k1(P) pro všechny hodnoty k₁ a DEC_k2(C) pro všechny možné hodnoty k₂, celkem 2^k₁ + 2^k₂ (nebo 2^k₁+1, pokud k₁ a k₂ jsou stejné velikosti). Pokud je výsledek některého z ENC_k1(P) operace odpovídá výsledku z DEC_k2(C) operace, dvojice k₁ a k₂ je možná správný klíč. Tento potenciálně správný klíč se nazývá a klíč kandidáta. Útočník může určit, který klíč kandidáta je správný, testováním pomocí druhé testovací sady prostého textu a šifrovacího textu.

Útok MITM je jedním z důvodů, proč Standard šifrování dat (DES) byl nahrazen Triple DES a ne Double DES. Útočník může použít útok MITM k bruteforce Double DES s 2⁵⁷ operace a 2⁵⁶ prostoru, což je oproti DES jen malé zlepšení.^[6] Triple DES používá klíč „triple length“ (168-bit) a je také zranitelný vůči útoku typu „meet-in-the-middle“ ve 2⁵⁶ prostor a 2¹¹² operace, ale je považován za zabezpečený kvůli velikosti svého prostoru klíčů.^[2][3]

Ilustrace útoku 1D-MITM

Algoritmus MITM

Vypočítejte následující:

• ${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P), ; pro všechny k_ {f_ {1 }} v K}$:

  a uložit každý ${ displaystyle { mathit {SubCipher}} _ {1}}$ spolu s odpovídajícími ${ displaystyle k_ {f_ {1}}}$ v sadě A

• ${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, C), ; pro všechny k_ {b_ {1 }} v K}$:

  a porovnat každý nový ${ displaystyle { mathit {SubCipher}} _ {1}}$ se sadou A

Když je nalezena shoda, pokračujte k_F1,k_b1 jako dvojice kandidátů v tabulce T. Otestujte páry T na nové dvojici ${ displaystyle (P, C)}$ pro potvrzení platnosti. Pokud pár klíčů na tomto novém páru nefunguje, proveďte MITM znovu na novém páru ${ displaystyle (P, C)}$.

Složitost MITM

Pokud je velikost klíče k, tento útok používá pouze 2^k+1šifrování (a dešifrování) a Ó(2^k) paměť pro uložení výsledků dopředných výpočtů do a. paměti vyhledávací tabulka, na rozdíl od naivního útoku, který potřebuje 2^2·k šifrování, ale Ó(1) prostor.

Vícerozměrný MITM (MD-MITM)

Tato sekce případně obsahuje původní výzkum. Prosím vylepši to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Květen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Zatímco 1D-MITM může být efektivní, byl vyvinut sofistikovanější útok: multidimenzionální útok typu meet-in-the-middle, také zkráceně MD-MITM. To se dává přednost, když byla data šifrována pomocí více než 2 šifrování s různými klíči. Místo setkání uprostřed (jedno místo v pořadí) se útok MD-MITM pokusí dosáhnout několika konkrétních mezilehlých stavů pomocí výpočtů vpřed a vzad na několika pozicích v šifře.^[5]

Předpokládejme, že útok musí být připojen na blokovou šifru, kde je šifrování a dešifrování definováno jako dříve:

${ displaystyle C = { mathit {ENC}} _ ​​{k_ {n}} ({ mathit {ENC}} _ ​​{k_ {n-1}} (... ({ mathit {ENC}} _ ​​{ k_ {1}} (P)) ...))}$

${ displaystyle P = { mathit {DEC}} _ ​​{k_ {1}} ({ mathit {DEC}} _ ​​{k_ {2}} (... ({ mathit {DEC}} _ ​​{k_ { n}} (C)) ...))}$

to je holý text P je několikrát šifrován pomocí opakování stejné blokové šifry

Ilustrace útoku MD-MITM

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

Algoritmus MD-MITM

Vypočítejte následující:

${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P) qquad forall k_ {f_ {1} } v K}$

a uložit každý ${ displaystyle { mathit {SubCipher}} _ {1}}$ spolu s odpovídajícími ${ displaystyle k_ {f_ {1}}}$ v sadě ${ displaystyle H_ {1}}$.

${ displaystyle { mathit {SubCipher}} _ {n + 1} = { mathit {DEC}} _ ​​{b_ {n + 1}} (k_ {b_ {n + 1}}, C) qquad forall k_ {b_ {n + 1}} v K}$

a uložit každý ${ displaystyle { mathit {SubCipher}} _ {n + 1}}$ spolu s odpovídajícími ${ displaystyle k_ {b_ {n + 1}}}$ v sadě ${ displaystyle H_ {n + 1}}$.

Pro každý možný odhad přechodného stavu ${ displaystyle s_ {1}}$ vypočítat následující:

${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, s_ {1}) qquad forall k_ {b_ {1}} v K}$

a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {1}}$ a sada ${ displaystyle H_ {1}}$, Uložit ${ displaystyle k_ {b_ {1}}}$ a ${ displaystyle k_ {f_ {1}}}$ v nové sadě ${ displaystyle T_ {1}}$.

${ displaystyle { mathit {SubCipher}} _ {2} = { mathit {ENC}} _ ​​{f_ {2}} (k_ {f_ {2}}, s_ {1}) qquad forall k_ {f_ {2}} v K}$^{[je nutné ověření ]}

a uložit každý ${ displaystyle { mathit {SubCipher}} _ {2}}$ spolu s odpovídajícími ${ displaystyle k_ {f_ {2}}}$ v sadě ${ displaystyle H_ {2}}$.

Pro každý možný odhad přechodného stavu ${ displaystyle s_ {2}}$ vypočítat následující:

• ${ displaystyle { mathit {SubCipher}} _ {2} = { mathit {DEC}} _ ​​{b_ {2}} (k_ {b_ {2}}, s_ {2}) qquad forall k_ {b_ {2}} v K}$

  a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {2}}$ a sada ${ displaystyle H_ {2}}$, zkontrolujte také zda

  shoduje se s ${ displaystyle T_ {1}}$ a poté uložte kombinaci podklíčů společně do nové sady ${ displaystyle T_ {2}}$.

• Pro každý možný odhad přechodného stavu ${ displaystyle s_ {n}}$ vypočítat následující:

1. ${ displaystyle { mathit {SubCipher}} _ {n} = { mathit {DEC}} _ ​​{b_ {n}} (k_ {b_ {n}}, s_ {n}) qquad forall k_ {b_ {n}} v K}$ a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {n}}$ a sada ${ displaystyle H_ {n}}$, zkontrolujte také, zda se shoduje s ${ displaystyle T_ {n-1}}$, Uložit ${ displaystyle k_ {b_ {n}}}$ a ${ displaystyle k_ {f_ {n}}}$ v nové sadě ${ displaystyle T_ {n}}$.
2. ${ displaystyle { mathit {SubCipher}} _ {n + 1} = { mathit {ENC}} _ ​​{f_ {n} +1} (k_ {f_ {n} +1}, s_ {n}) qquad forall k_ {f_ {n + 1}} v K}$ a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {n + 1}}$ a sada ${ displaystyle H_ {n + 1}}$, zkontrolujte také

zda se shoduje s ${ displaystyle T_ {n}}$. Pokud je to váš případ, pak: „

Použijte nalezenou kombinaci podklíčů ${ displaystyle (k_ {f_ {1}}, k_ {b_ {1}}, k_ {f_ {2}}, k_ {b_ {2}}, ..., k_ {f_ {n + 1}}, k_ {b_ {n + 1}})}$ na jiné dvojici holého textu / šifrovacího textu k ověření správnosti klíče.

Všimněte si vnořeného prvku v algoritmu. Odhad každé možné hodnoty na s_j se provádí pro každý odhad předchozího s_j-1. Toto tvoří prvek exponenciální složitosti k celkové časové složitosti tohoto útoku MD-MITM.

Složitost MD-MITM

Časová složitost tohoto útoku bez hrubé síly je ${ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {n + 1}} |} + 2 ^ {| s_ {1} |}}$⋅${ displaystyle (2 ^ {| k_ {b_ {1}} |} + 2 ^ {| k_ {f_ {2}} |} + 2 ^ {| s_ {2} |}}$⋅${ displaystyle (2 ^ {| k_ {b_ {2}} |} + 2 ^ {| k_ {f_ {3}} |} + cdots))}$

Pokud jde o složitost paměti, je snadné to vidět ${ displaystyle T_ {2}, T_ {3}, ..., T_ {n}}$ jsou mnohem menší než první sestavená tabulka kandidátských hodnot: ${ displaystyle T_ {1}}$ jak se zvyšuje, kandidátské hodnoty obsažené v ${ displaystyle T_ {i}}$ musí splňovat více podmínek, tím méně kandidátů předá konečnému cíli ${ displaystyle T_ {n}}$.

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

${ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {n + 1}} |} + 2 ^ {| k | - | s_ {n} |} cdots}$

kde k označuje délku celého klíče (kombinovaná).

Složitost dat závisí na pravděpodobnosti, že může chybný klíč projít (získat falešně pozitivní výsledek), což je ${ displaystyle 1/2 ^ {| l |}}$, kde l je přechodný stav v první fázi MITM. Velikost přechodného stavu a velikost bloku je často stejná! Vzhledem k tomu, kolik klíčů zbývá k testování po první fázi MITM, je ${ displaystyle 2 ^ {| k |} / 2 ^ {| l |}}$.

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

Pokaždé, když je konečná kandidátská hodnota klíčů testována na novém páru prostého textu / ciphertextu, bude počet klíčů, které projdou, vynásoben pravděpodobností, že klíč může projít, což je ${ displaystyle 1/2 ^ {| b |}}$.

Část testování hrubou silou (testování kandidátského klíče na novém ${ displaystyle (P, C)}$- páry, mají časovou složitost ${ displaystyle 2 ^ {| k | -b} + 2 ^ {| k | -2b} + 2 ^ {| k | -3b} + 2 ^ {| k | -4b} cdots}$, jasně pro zvýšení násobků b v exponentu má číslo tendenci k nule.

Závěr o složitosti dat je podobným uvažováním omezen tím kolem ${ displaystyle lceil | k | / n rceil}$ ${ displaystyle (P, C)}$- páry.

Níže je uveden konkrétní příklad způsobu připojení 2D-MITM:

Obecný příklad 2D-MITM

Toto je obecný popis toho, jak je 2D-MITM připojen k šifrování blokové šifry.

V dvojrozměrném MITM (2D-MITM) je metodou dosažení 2 mezilehlých stavů uvnitř vícenásobného šifrování prostého textu. Viz obrázek níže:

Ilustrace útoku 2D-MITM

Algoritmus 2D-MITM

Vypočítejte následující:

${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P) qquad forall k_ {f_ {1} } v K}$

a uložit každý ${ displaystyle { mathit {SubCipher}} _ {1}}$ spolu s odpovídajícími ${ displaystyle k_ {f_ {1}}}$ v sadě A

${ displaystyle { mathit {SubCipher}} _ {2} = { mathit {DEC}} _ ​​{b_ {2}} (k_ {b_ {2}}, C) qquad forall k_ {b_ {2} } v K}$

a uložit každý ${ displaystyle { mathit {SubCipher}} _ {2}}$ spolu s odpovídajícími ${ displaystyle k_ {b_ {2}}}$ v sadě B.

Pro každý možný odhad přechodného stavu s mezi ${ displaystyle { mathit {SubCipher}} _ {1}}$ a ${ displaystyle { mathit {SubCipher}} _ {2}}$ vypočítat následující:

• ${ displaystyle { mathit {SubCipher}} _ {1} = { mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, s) qquad forall k_ {b_ {1} } v K}$

  a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {1}}$ a sada A, uložte ${ displaystyle k_ {b_ {1}}}$ a ${ displaystyle k_ {f_ {1}}}$ v nové sadě T.

• ${ displaystyle { mathit {SubCipher}} _ {2} = { mathit {ENC}} _ ​​{f_ {2}} (k_ {f_ {2}}, s) qquad forall k_ {f_ {2} } v K}$

  a pro každý zápas mezi tím ${ displaystyle { mathit {SubCipher}} _ {2}}$ a množinu B, zkontrolujte také, zda odpovídá T pro

  pokud tomu tak je, pak:

Použijte nalezenou kombinaci podklíčů ${ displaystyle (k_ {f_ {1}}, k_ {b_ {1}}, k_ {f_ {2}}, k_ {b_ {2}})}$ na jiné dvojici holého textu / šifrovacího textu k ověření správnosti klíče.

Složitost 2D-MITM

Časová složitost tohoto útoku bez hrubé síly je

${ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {2}} |} + 2 ^ {| s |} cdot left (2 ^ {| k_ {b_ {1}} |} + 2 ^ {| k_ {f_ {2}} |} vpravo)}$

kde | ⋅ | označuje délku.

Spotřeba hlavní paměti je omezena konstrukcí sad A a B kde T je mnohem menší než ostatní.

Složitost dat viz pododdíl o složitosti pro MD-MITM.

Viz také

• Narozeninový útok
• Bezdrátové zabezpečení
• Kryptografie
• Útok typu 3 set-in-the-middle
• Částečně odpovídající útok typu meet-in-the-middle

Reference