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.