![]() Specializovaný týdeník o výpočetní technice |
|
![]() |
Seriál o bezpečnosti a informačním soukromí |
Část 28 - CW 39/97
Šifrovací algoritmus DESPetr Hanáček
Po úvodu do kryptografických algoritmů v předchozích dílech seriálu přichází v tomto pokračování seriálu popis pravděpodobně nejznámějšího, nejpoužívanějšího a v poslední době nejkontraverznějšího kryptografického algoritmu -- algoritmu DES.
Historie V roce 1972 inicovala americká instituce NBS (National Bureau of Standards, dnes nazývaná NIST -- National Institute of Standards and Technology) program vytvoření standardizovaného kryptografického algoritmu pro zabezpečení počítačových dat. Požadovaný algoritmus musí splňovat především požadavek na vysokou úroveň zabezpečení, musí být přesně specifikován a jeho bezpečnost nesmí záviset na jeho utajení. Algoritmus také musí být snadno implementovatelný pomocí hardwaru a musí být dostupný všem uživatelům. V roce 1974 se objevil slibný kandidát, který splňoval téměř všechny požadavky. Šlo o algoritmus LUCIFER, vyvinutý firmou IBM. Na základě algoritmu LUCIFER byl vyvinut firmou IBM ve spolupráci s americkým národním úřadem pro bezpečnost (NSA) algoritmus DES. V listopadu 1976 byl algoritmus DES přijat jako federální standard. Oficiální popis algoritmu byl zveřejněn na jaře 1977 v publikaci FIPS PUB 46, "Data Encryption Standard".
Standardizace algoritmu Algoritmus DES byl brzy po svém zveřejnění v publikacích FIPS standardizován americkou standardizační institucí ANSI pod názvem DEA (Data Encryption Algorithm) ve standardech ANSI X3.92 (Algoritmus DEA) a ANSI X3.107 (režimy činnosti DEA). Významnější však byla skutečnost, že algoritmus DES byl v USA standardizován i pracovními skupinami pro bankovnictví. Tím vznikly standardy, které na dlouhou dobu ovlivnily používání kryptografie v bankovnictví nejen v USA, ale i v celém světě. Především jde o standardy ANSI X9.8 (zabezpečení PIN), ANSI X9.9 a X9.19 (autentizace bankovních zpráv) a ANSI X9.17 (správa kryptografických klíčů). Mezinárodní organizace pro standardizaci ISO nejdříve odhlasovala přijetí algoritmu DES (přejmenovaného na DEA-1) jako mezinárodní kryptografický standard. Později se však rozhodla, že nebude vůbec provádět standardizaci kryptografických algoritmů a ponechá tuto činnost na národních orgánech.
Princip algoritmu DES je bloková šifra, která šifruje bloky dat o velikosti 64 bitů. Každou operací šifrování se zašifruje jeden blok 64 bitů otevřeného textu na blok 64 bitů zašifrovaného textu. Pro šifrování se používá klíč o velikosti 56 bitů. Tato příliš malá délka klíče je však pravděpodobně největší slabinou algoritmu. Klíč je obvykle vyjádřen jako 64bitová hodnota, avšak každý osmý bit je paritní a je algoritmem ignorován. Algoritmus využívá kombinaci dvou kryptografických technik -- substituce (tj. nahrazení jisté bitové hodnoty jinou hodnotou na základě tabulky) a permutace (tj. jistá záměna pořadí jednotlivých bitů v bloku). Substituce se provádí pomocí takzvaných S-boxů a permutace pomocí P-boxů. Základním stavebním blokem algoritmu DES je jednoduchá kombinace těchto technik (tj. substituce, následovaná permutací), která je modifikována hodnotou klíče. Tento blok se nazývá cyklus. Tento cyklus je na šifrovaný blok bitů aplikován šestnáctkrát. Algoritmus využívá pouze standardních aritmetických a logických operací nad čísly o velikosti nejvýše 64 bitů a byl snadno hardwarově implementovatelný i dřívější technologií. Snadná softwarová implementovatelnost nebyla požadována, neboť v původní definici algoritmu DES je řečeno, že musí být implementován hardwarově. Teprve později se připustila i softwarová implementace algoritmu DES pod názvem DEA (Data Encryption Algorithm). Algoritmus DES je zcela specifikován a jsou zveřejněny všechny podrobnosti o tomto algoritmu. Co však není zveřejněno, je postup návrhu tohoto algoritmu. To, co vypadá na první pohled jako drobný detail, způsobilo později mnoho nepříjemností. Aby byl algoritmus DES bezpečný, je třeba, aby substituční tabulky (zvané S-boxy) neobsahovaly lineární funkci. Pokud by S-boxy obsahovaly lineární funkci, lze velmi snadno celý algoritmus vyjádřit jako soustavu lineárních rovnic a jejich řešením zjistit klíč. Z obsahu S-boxů však nelze zpětně zjistit, zda do nich nebyla nějaká lineární funkce zabudována. Pokud by tomu tak bylo, autor S-boxů (tedy IBM a NSA) by byl schopen velmi rychle a efektivně luštit zprávy, zašifrované tímto algoritmem. Vzhledem k těmto pochybnostem provedl výbor Kongresu USA šetření, jehož výsledek je tajný. Publikováno bylo pouze shrnutí výsledků tohoto šetření, které říká, že do S-boxů nebyla úmyslně zabudována žádná lineární funkce.
Režimy činnosti Algoritmus DES, stejně jako každá jiná bloková šifra, šifruje bloky dat o délce nejvýše 64 bitů. Pro šifrování těchto delších zpráv byly definovány čtyři základní režimy algoritmu DES. Prvním režimem je režim ECB (Electronic Code Book), který znamená, že zpráva se rozdělí na bloky o délce 64 bitů a každý blok se zašifruje nezávisle na ostatních blocích. Tento režim je z důvodu bezpečnosti vhodný pouze pro šifrování velmi krátkých zpráv. Dalším režimem je režim CBC (Cipher Block Chaining), který zprávu opět rozděluje na bloky o délce 64 bitů, ale bloky nejsou šifrovány samostatně. Před zašifrováním každého bloku se provede logická operace XOR tohoto bloku se zašifrovanou hodnotou předchozího bloku. Poslední dva režimy -- režim CFB (Cipher Feedback) a režim OFB (Output Feedback) -- činí z algoritmu DES prakticky proudovou šifru a dovolují šifrovat zprávy, chápané jako proud bitů. Výše zmíněné režimy byly původně definovány pouze pro algoritmus DES. Lze je však použít pro každou blokovou šifru.
Kryptoanalýza a útoky Algoritmus DES byl po celou dobu své existence podroben velmi důkladnému zkoumání předními kryptology celého světa. Pravděpodobně je možno říci, že žádný jiný kryptografický algoritmus nebyl podroben tak zevrubnému zkoumání. Během tohoto zkoumání byly objeveny některé nedostatky algoritmu (například tzv. komplementarita algoritmu, která může pro útočníka zkrátit efektivní délku klíče z 56 bitů na 55 bitů, nebo existence několika "slabých" a "poloslabých" klíčů). Byly objeveny i některé moderní techniky kryptoanalýzy (jako například diferenciální kryptoanalýza nebo lineární kryptoanalýza), které umožňují výrazně zrychlit nalezení klíče, ovšem pouze v teoretických podmínkách za cenu obrovských paměťových nároků. Shrneme-li výsledky těchto útoků, je třeba před autory algoritmu smeknout, protože přes všechno úsilí kryptologů je největší slabinou algoritmu nedostatečná délka klíče a zatím jediný známý realizovatelný (a realizovaný) útok je útok hrubou silou -- tedy vyzkoušení všech možných klíčů. O tomto útoku se nyní zmíníme podrobněji.
Útok hrubou silou Možnost útoku hrubou silou na algoritmus DES, která byla teoreticky rozpracovávána už před mnoha lety, byla prakticky demonstrována na jaře roku 1997. Prvním impulzem byla výzva společnosti RSA DSI, která vypsala cenu 10 000 dolarů tomu, kdo rozluští zprávu, zašifrovanou algoritmem DES. Hozené rukavice se chopil Rocke Verser -- vytvořil program, který je možno distribuovat mezi velké množství počítačů a který během nečinnosti počítače (tj. na pozadí) provádí hledání správného klíče. Tento program zveřejnil v síti Internet a vyzval všechny zájemce, aby si tento program stáhli, spustili jej na svém počítači a tím mu pomohli s nalezením klíče. Program byl zveřejněn 18. února 1997 a na výzvu reagoval poměrně značný počet účastníků. Dne 17. června byl klíč nalezen. Hledání klíče se účastnilo celkem asi 78 tisíc počítačů (současně jich však počítalo nejvíce 14 tisíc) a klíč byl určen s poměrně značnou dávkou štěstí, neboť v okamžiku nalezení byla prozkoumána teprve jedna čtvrtina všech možných klíčů (podrobnější informace lze najít na adrese http://www.rsa.com/des/). Přestože tento útok získal značnou popularitu, jeho praktický dopad není významný. Po několika měsících hledání byl nalezen jediný klíč, avšak tento fakt nijak neusnadní hledání klíčů jiných. Útok rozhodně nelze označit za překvapivý, protože bylo pouze prakticky demonstrováno to, co stejně bylo známo -- totiž že délka klíče 56 bitů by měla být prodloužena, protože soustředěním dostatečné výpočetní síly je možno prozkoumat všechny možné klíče.
Budoucnost algoritmu DES I přes skutečnosti, uvedené v předchozích odstavcích, není budoucnost algoritmu DES tak černá. Nejzávažnější nedostatek algoritmu, kterým je malá délka klíče, je totiž možno odstranit za cenu jistého zpomalení šifrování trojnásobným šifrováním jednoho bloku dat pomocí několika (dvou nebo tří) různých klíčů. Dvojnásobné šifrování bloku dat není dostatečné, protože existuje útok, zvaný "meet in the middle", který způsobuje, že efektivní délka klíče je zvětšena pouze o jeden bit. Nejčastěji se používá trojnásobné šifrování pomocí dvou klíčů, které je realizováno tak, že blok dat je zašifrován prvním klíčem, dešifrován druhým klíčem a opět zašifrován prvním klíčen (tím se získá kompatibilita se stávajícím algoritmem DES -- pokud jsou oba klíče stejné, algoritmus se chová jako klasický DES). Algoritmus se pak nazývá 3-DES, triple-DES nebo DES-EDE. Efektivní délka klíče tohoto algoritmu je pak přibližně 112 bitů. Jediná námitka proti algoritmu 3-DES, totiž jeho trojnásobně menší rychlost oproti algoritmu DES, dnes už díky stále větší rychlosti počítačových systémů ztratila opodstatnění. Pracovní skupina X9F1, která je akreditována Americkým národním úřadem pro standardizaci ANSI pracuje na standardu pro šifrovací algoritmus pro šifrování dat ve finančních institucích, založený na algoritmu 3-DES. 3-DES byl už po mnoho let standardizovaným mechanismem pro šifrování klíčů, definovaným ve standardu ANSI X9.17. Nyní se věnuje pozornost jeho použití pro šifrování běžných dat. Důvodem, proč se obrací pozornost na algoritmus 3-DES, je nedostatek jiných šifrovacích algoritmů, standardizovaných pro použití v bankovních institucích. Novou iniciativou organizace NIST je program AES (Advanced Encryption Standard). V lednu 1997 vyzval NIST odbornou veřejnost a instituce k zaslání návrhů na symetrický kryptografický algoritmus, který se bude nazývat AEA (Advanced Encryption Algorithm). Požadavky na AEA jsou velmi podobné původním požadavkům na DES s dvěma zásadními rozdíly: algoritmus musí být snadno implementovatelný softwarově i hardwarově a musí mít volitelnou délku klíče.
¦Otevřený text ¦64 bitů ¦ V +--------+ Klíč ¦ ¦ ------>¦ DES ¦ 56 bitů¦ ¦ +--------+ ¦Zašifrovaný text ¦64 bitů ¦ V Algoritmus DES
Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/
| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage | |