╚ßst 28 - CW 39/97

èifrovacφ algoritmus DES

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