Je DES náchylný k útoku typu meet-in-the-middle?
Data Encryption Standard (DES) je algoritmus symetrického klíče pro šifrování digitálních dat. Byla vyvinuta na počátku 1970. let a později byla přijata jako federální standard ve Spojených státech v roce 1977. DES je bloková šifra, což znamená, že šifruje data v blocích pevné velikosti, konkrétně 64bitových blocích, pomocí 56bitového klíče. . Navzdory svému historickému významu a širokému použití bylo zjištěno, že DES je zranitelný vůči různým formám kryptografických útoků, z nichž jedním je útok typu meet-in-the-middle.
Abychom pochopili zranitelnost DES vůči útoku meet-in-the-middle, je důležité nejprve pochopit základní principy této metody útoku. Útok meet-in-the-middle je typ kryptanalytického útoku, který je zvláště účinný proti šifrovacím schématům, která používají více stupňů nebo vrstev šifrování, jako je dvojité nebo trojité šifrování.
Ve scénáři dvojitého šifrování je prostý text zašifrován dvakrát pomocí dvou různých klíčů. Pokud například označíme šifrovací funkci jako E a dešifrovací funkci jako D a klíče jako K1 a K2, pak dvojité šifrování otevřeného textu P bude reprezentováno jako:
C = E(K2, E(K1, P))
Zde se P nejprve zašifruje klíčem K1, aby se vytvořil mezilehlý šifrový text, který je pak znovu zašifrován klíčem K2, aby se vytvořil konečný šifrový text C. Myšlenkou dvojitého šifrování je zvýšit bezpečnost tím, že bude šifrovací systém odolnější vůči brutálnímu šifrování. silové útoky.
Útok typu meet-in-the-middle však využívá slabinu ve schématu dvojitého šifrování tím, že snižuje efektivní klíčový prostor, který je třeba prohledávat. Útok funguje následovně:
1. Útočník začíná se známým párem otevřeného textu a šifrovaného textu (P, C).
2. Útočník zašifruje otevřený text P se všemi možnými hodnotami K1 a uloží výsledky do tabulky spolu s odpovídajícími hodnotami klíče.
3. Útočník dešifruje šifrový text C se všemi možnými hodnotami K2 a uloží výsledky do jiné tabulky spolu s odpovídajícími hodnotami klíče.
4. Útočník poté hledá shody mezi výsledky kroků šifrování a dešifrování. Ke shodě dojde, když se mezilehlý šifrovaný text vytvořený zašifrováním P kandidátským klíčem K1 rovná přechodnému šifrovanému textu vytvořenému dešifrováním C kandidátním klíčem K2.
Pokud je nalezena shoda, odpovídající klíče K1 a K2 budou pravděpodobně správnými klíči použitými pro dvojité šifrování. Útok meet-in-the-middle účinně snižuje složitost prolomení dvojitého šifrování z 2^112 (což by byla složitost útoku hrubou silou na dva 56bitové klíče) na 2^57, což je součet složitosti dvou samostatných kroků (2^56 pro šifrování P a 2^56 pro dešifrování C, ale protože každý krok je nezávislý, celková složitost je snížena).
Tento útok ukazuje, že dvojité šifrování neposkytuje očekávanou úroveň vylepšení zabezpečení. Stejný princip lze aplikovat na trojité šifrování, i když s přidáním více šifrovacích vrstev narůstá složitost útoku.
V kontextu DES je útok meet-in-the-middle zvláště významný, protože DES používá relativně krátkou délku klíče 56 bitů. Díky tomu mohou útočníci provádět nezbytné výpočty k provedení útoku, zejména s pokroky ve výpočetní síle v průběhu let.
Příklad útoku typu meet-in-the-middle na DES by zahrnoval následující kroky:
1. Předpokládejme, že útočník má známý otevřený text P a jeho odpovídající šifrový text C, přičemž oba mají délku 64 bitů.
2. Útočník vygeneruje všechny možné hodnoty klíče 2^56 pro K1 a zašifruje P s každým klíčem, přičemž výsledky uloží do tabulky.
3. Útočník vygeneruje všechny možné hodnoty klíče 2^56 pro K2 a dešifruje C s každým klíčem a uloží výsledky do jiné tabulky.
4. Útočník poté porovná záznamy v obou tabulkách, aby našel shodu. Pokud je nalezena shoda, odpovídající klíče K1 a K2 budou pravděpodobně správnými klíči použitými pro dvojité šifrování.
Útok meet-in-the-middle zdůrazňuje důležitost používání kryptografických algoritmů s dostatečně velkými klíčovými prostory a robustními konstrukčními principy, které takovým útokům odolají. Zatímco DES byl ve své době významným pokrokem, jeho relativně krátká délka klíče a náchylnost k různým útokům, včetně útoku meet-in-the-middle, vedly k jeho nahrazení bezpečnějšími algoritmy, jako je Advanced Encryption Standard (AES). .
Například AES používá délky klíčů 128, 192 nebo 256 bitů, což poskytuje mnohem větší klíčový prostor a výrazně větší odolnost proti útokům hrubou silou a útokům typu meet-in-the-middle. AES navíc využívá složitější strukturu s několika cykly šifrování, z nichž každé zahrnuje operace substituce, permutace a míchání, díky čemuž je odolnější vůči kryptoanalytickým útokům.
Útok meet-in-the-middle je výkonná kryptoanalytická technika, která využívá slabiny vícestupňových šifrovacích schémat, jako je double DES. Útok účinně snižuje složitost prolomení šifrování tím, že se zaměřuje na mezivýsledky procesů šifrování a dešifrování. Tato zranitelnost podtrhuje potřebu kryptografických algoritmů s většími klíčovými prostory a robustnějšími principy návrhu pro zajištění bezpečnosti šifrovaných dat.
Další nedávné otázky a odpovědi týkající se Data Encryption Standard (DES) – šifrování:
- Byl protokol DES zaveden za účelem zlepšení bezpečnosti kryptosystémů AES?
- Které bity klíče se používají pro kontrolu parity v DES?
- Může být jeden bit šifrovaného textu ovlivněn mnoha bity otevřeného textu v DES?
- Závisí DES na více kombinacích difúze a zmatku?
- Jak mohou podklíče používat šifru DES?
- Lze permutaci považovat za příklad difúze v blokové šifře?
- Existuje ve fázi S-boxů v DES, protože snižujeme fragment zprávy o 50%, záruka, že neztratíme data a zpráva zůstane obnovitelná/dešifrovatelná?
- Jaký význam má lavinový efekt v procesu šifrování DES?
- Jak permutace P přispívá ke konečnému výstupu funkce f v šifrování DES?
- Jaká je role S-boxů v procesu šifrování DES?
Zobrazit další otázky a odpovědi v Data Encryption Standard (DES) – Šifrování