COMPUTERWORLD
Specializovaný týdeník o výpočetní technice
o Internetu
(CW 29/97)

DES je mrtev, DES Challenge zná svého vítěze

Daniel Lukeš, Jan Stoklasa

Do análů světové kryptografie jednou provždy vstoupil nový mezník. 17. července v 10.39 pacifického času dorazila do sídla společnosti RSA následující zpráva: "Strong cryptography makes the world a safer place."

Zpráva je výsledkem "zlomení" zašifrované zprávy bez znalosti klíče a její odesílatel Rocke Verser z Colorada se stal vítězem soutěže DES Challenge. Vítězství mu přineslo 10 000 dolarů a slávu, do americké vlády možná tato událost přinese změnu postoje k vývozu šifrovacích technologií.

Krátké zprávy o této události se na stránkách CW už objevily, tento článek nabízí podrobnější pohled.

Lámání DES

Použitou šifrou byla šifra DES s délkou klíče 56 bitů. DES je od roku 1977 standardně používaná státní šifra Spojených států. DES a jeho modifikace používají prakticky všechny nevojenské subjekty (banky, firmy) pro ochranu dat při vzájemném elektronickém styku. Za dobu jejího používání byla nesčíslněkrát zkoumána a je to pravděpodobně nejlépe teoreticky prozkoumaná šifra, která se používá v praxi. Její věk však také hovoří proti ní. Šifra stará 20 let nestačí rostoucímu výkonu počítačů, stále větší okruh lidí má reálnou možnost jejího prolomení.

Donedávna bylo lámání šifer doménou rozvědek. Nyní se to poprvé povedlo i lidem bez kryptografických znalostí a přístupu k superpočítačům -- uživatelům Internetu.

Internetový superpočítač

Internet umožnil spolupráci několika desítek tisíc počítačů, které společným výkonem dokázaly zprávu vyluštit už 140 dnů od vyhlášení. Vlastně se podařilo pomocí softwarových prostředků "sestrojit" internetový superpočítač. Podívejme se nyní na princip jeho funogování.

Software, který pracoval na dešifrování tajného textu a splnění DES Challenge, byl založen na jednoduchém principu -- postupně bral všechny možné šifrovací klíče (dvojková čísla s 56 číslicemi), zkoušel s nimi dešifrovat začátek zašifrovaného textu a výsledek porovnal se známým začátkem tajného textu. Pokud výsledek souhlasil a zbytek textu také dával smysl, našli jsme určitě řešení, jinak bylo nutné pokračovat ve výpočtu.

Tento jednoduchý popis algoritmu by byl namístě, pokud by se jednalo o jeden celistvý počítač. Nesmíme ale zapomenout, že se pohybujeme v rámci celého Internetu, ve kterém byla propojena spousta samostatných počítačů. Proto se pro ně musela práce rozdělit a potom prostřednictvím Sítě složit všechny výsledky do jednoho.

Každý zájemce o výpočet dostal blok po sobě jdoucích klíčů (konkrétně 2 na 29) a centrální autoritě sdělil, jak jeho výpočet dopadl. Centrální autorita se jmenuje masterserver, stará se o rozdělování práce a také o to, aby pokud možno žádné dva počítače v Internetu nezkoušely stejný blok klíčů.

Co se týče technických upřesnění, servery měly dvě úrovně -- nejvyšší autoritu (tzv. masterserver) a prostředníky (tzv. servery). Klientské programy nekomunikovaly s masterserverem, ale pouze se servery. Ty sebraly jejich výsledky a předaly je masterserveru.

Komunikace mezi servery a klienty používá veřejný klíč pro ověření pravosti komunikujících programů. Pokud by komunikace byla zcela otevřená, někdo by mohl celý systém narušit podstrčením falešných dat.

Motivaci k tomu, aby uživatelé na svých počítačích spouštěli software potřebný pro výpočet, poskytla finanční cena, vypsaná pro DES Challenge. Uživatelé tedy mohli ke své účasti v luštění přistupovat jako k loterii.

Nátlak na vládu

Celkový výkon týmů v posledních dnech činil úctyhodných 1 010 klíčů. Při udržení tohoto výkonu s použitím nejlepších známých algoritmů by příští zpráva mohla být vyluštěna v několika dnech. Americká vláda však stále považuje DES za naprosto bezpečný. Proto zakazuje jeho export z USA s poukazem na to, že bezpečná šifra v rukách nepřítele je nebezpečím pro stát. Vyhlášení DES Challenge bylo nátlakem na vládu USA, aby tato exportní omezení zrušila, nebo vážně revidovala pojem bezpečných šifer ve smyslu předchozí věty.

Česká účast se ctí i s ostudou

V soutěži o prolomení DESu až do konce vydržely 3 týmy -- 2 americké a 1 švédský. Většina Evropy pracovala v rámci švédského týmu. Česká republika se své účasti na projektu zhostila s vervou a dosáhla neočekávaně vysokého místa na žebříčku zemí podle dodaného výkonu -- 6. místo rozhodně nikdo nečekal. Dokonce jsme měli absolutně nejlepší poměr mezi počítači, luštícími šifru a všemi počítači, připojenými k Internetu.

Bohužel to není jediné prvenství, kterým se můžeme pochlubit -- naši zemi provází i velká ostuda. Studenti SPŠ sdělovací techniky "upravili" lušticí program tak, aby výsledky hlásil bez skutečného výpočtu. Tím sice zdánlivě stoupnul výkon jejich školy i celé ČR na trojnásobek, ale mohla být narušena integrita dat v celém projektu (zvláště pokud by se jejich program rozšířil). Naštěstí byl tento hloupý útok rychle odhalen a všechna data spočítaná na útočících strojích i na strojích v jejich okolí byla eliminována.

Poučení pro budoucnost

Dnes je více než jisté, že při troše námahy a přiměřené motivaci lze z Internetu udělat výpočetní stroj obrovského výkonu. Tyto události mohou být mementem pro vlády a parlamenty, jejichž snahy o omezení šifrování jsou vedeny snahou mít pod kontrolou elektronickou korespondenci občanů. Je tu další nebezpečí -- vaše utajované zprávy si může přečíst nejen vlastní vláda, ale kdokoli.

DES je mrtev a na scénu nastupují bezpečnější šifry. Každá z dalších devíti vypsaných dešifrovacích soutěží se zabývá šiframi s delším a delším klíčem. Bude zajímavé sledovat, kolik výpočetního výkonu Internet dokáže poskytnout a kolik šifer se tak podaří zlomit.


| <<< | CW o Internetu | COMPUTERWORLD | IDG CZ homepage |