Přírodovědecká fakulta Masarykovy univerzity Bakalářská práce Kryptografie v digitálním televizním vysílání Miroslav Šemora Vedoucí práce: doc. RNDr. Jan Paseka, CSc. Prohlášení: Prohlašuji, že jsem tuto bakalářskou práci vytvořil samostatně, pouze s použitím zdrojů uvedených v referencích. V Brně dne 25. 5. 2005, Miroslav Šemora Poděkování: Na tomto místě bych rád poděkoval doc. RNDr. Janu Pasekovi, CSc. za cenné připomínky a rady během psaní, ing. Zdeňku Sehnalovi za zajímavé informace a postřehy z praxe a MgrA. Blance K. Špičákové za ruční vazbu této práce. Obsah 1 Televizní vysílání a kryptografie 6 1.1 Účel kryptografie v televizním vysílání............. 6 1.2 Druhy televizního vysílání.................... 6 1.3 Šifrování analogového vysílání.................. 7 1.4 Digitální televizní vysílání.................... 8 1.5 Conditional Access........................ 9 1.5.1 Scrambling ........................ 9 1.5.2 Control Messages..................... 9 1.5.3 DVB CA Common Interface............... 10 1.5.4 Cryptoworks DVB CA.................. 12 2 Základní pojmy kryptografie 15 2.1 Šifrovací algoritmus, zpráva, klíč, kryptogram......... 15 2.2 Symetrická a asymetrická šifra.................. 15 2.3 Operace xor a one-time pad................... 17 2.4 Bloková šifra............................ 18 2.5 Proudová šifra........................... 20 2.6 Posouvací registry......................... 21 2.7 Kryptoanalýza a napadání šifer................. 22 2.7.1 Algebraické metody u proudových šifer......... 23 2.7.2 Algebraické metody u blokových šifer.......... 24 2.7.3 Metoda postranních kanálů ............... 25 3 DVB Common Scrambling Algorithm 26 3.1 Scrambling............................. 26 3.1.1 Bloková šifra ....................... 27 3.1.2 Proudová šifra....................... 30 3.2 Descrambling........................... 37 3.3 Důkaz korektnosti CSA...................... 39 3.4 Kryptoanalýza a útoky na DVB CSA.............. 41 3.4.1 Proudová šifra....................... 41 4 3.4.2 Bloková šifra ....................... 42 3.4.3 Shrnutí .......................... 43 4 RSA 44 4.1 Popis algoritmu RSA....................... 45 4.1.1 Šifrování zprávy pomocí RSA.............. 45 4.1.2 Dvoustranná komunikace šifrovaná RSA........ 45 4.1.3 RSA podepsiovací schéma................ 46 4.1.4 Útoky na RSA ...................... 46 Kapitola 1 Televizní vysílání a kryptografie 1.1 Účel kryptografie v televizním vysílání Kryptografie má mnoho funkcí. Především však slouží k utajení informace při přenosu k příjemci, k zabezpečení před nežádoucí modifikací během přenosu a konečně k ověření původu - autentizaci Televizní vysílání spočívá v přenosu obrazu a zvuku k divákovi. Zde je primárním úkolem šifrování ochrana duševního vlastnictví Pomocí systémů jako je Subscription-TV nebo (Impulse)-Pay-per-View je zajištěno, že vysílání může sledovat jen divák, který si jej předplatil, popřípadě umožňuje platbu za jednotlivé shlédnuté pořady. 1.2 Druhy televizního vysílání Podle způsobu přenosu můžeme televizní vysílání rozdělit na pozemní, kabelové a satelitní Ve všech třech případech dochází na straně vysílače k namo-dulování obrazu a zvuku na nosný elektromagnetický kmitočet a u koncového uživatele k jeho demodulaci a přehrání. Způsob přenosu bude pro nás nadále nepodstatný, jen poznamenejme, že v případě kabelového vysílání se nepoužívají šifrovací metody, nýbrž se provádí jen nějaká forma filtrování signálu podle toho, co si uživatel předplatí. Naopak v satelitním vysílání by takovéto filtrování bylo neúčinné. Podle formátu dat rozlišujeme vysílání na analogové a digitální V pozemním analogovém se šifrování prakticky nikdy nevyskytovalo, v satelitním analogovém se jednalo (a stále ještě někde jedná) o různé úpravy signálu, které zmíníme jen pro dokreslení situace. 6 Bakalářská práce Kapitola 1. 7 1.3 Šifrování analogového vysílání Televizní signál sestává ze zvukových a obrazových dat. Obraz je rozdělen do řádků a řádky pak do jednotlivých bodů. Body nesou informaci o barvě a jejich sestavením vznikne výsledný obraz. V analogovém případě na straně vysílače dochází k modulaci, kdy na tzv. nosný elektromagnetický signál vysoké frekvence jsou v pravidelných intervalech naneseny informace o jednotlivých obrazových bodech. Provádí se to úpravou síly (tzv. amplitudová modulace, AM) vlnění nebo jeho frekvence (frekvenční modulace, FM). Obdobně zvuk, což je chvění vzduchu v určitých frekvencích. Elektronicky je zaznamenán jako střídavý nepravidelný signál, vzniklý - zjednodušeně řečeno - „sečtením" mnoha sinusoid. Tvar signálu je namodulován do vysokofrekvenčního elektromagnetického vlnění, avšak jiné vlnové délky než jemu příslušný obraz. Na straně přijímače pak dochází k demodulaci, tedy odečtení signálu z nosného vysokofrekvenčního vlnění. Zde byl prostor pro „kryptografii". Každý půlsnímek obrazu analogové televize obsahuje synchronizační signál, řídicí signály a vlastní obrazová data. Provádělo se například odfiltrování synchronizačního signálu nebo inverze řídicího i obrazového signálu a jejich nejrůznější kombinace. Přijímač o těchto změnách věděl a dokázal je napravit. Obrázek 1.1: Analogový televizní signál -jeden půlsnímek K odhalení takovéto úpravy signálu však stačil osciloskop a docházelo k němu často. Provozovatelé se bránili různým obměňováním způsobu zakódování signálu a jeho častějším střídáním. Pro nás je takové šifrování zajímavé možná právě jen jako demonstrace neúčinnosti security by obscurity, tedy systému, kdy dešifrování je založeno jen na znalosti kryptovací metody (a nanejvýš na vyzkoušení několika jednoduchých „klíčů"). Trochu dokonalejší pak byly systémy hybridní, představované systémem Video Crypt [VC-97]. Obraz se pořád přenáší analogově, avšak zašifrovaně a informace o šifře se přenáší digitálně na nevyužité frekvenci původně určené pro zvukový kanál. Zde se již využívá pseudonáhodných posloupností, které říkají, jak jsou obrazové půlsnímky jsou zakódovány. Odkazy: [DRM-02, strana 57-68] Bakalářská práce Kapitola 1. 8 1.4 Digitální televizní vysílání Mnohem zajímavější pak je šifrování digitálního vysílání, neboť, jak v následujícím uvidíme, umožňuje šifrování pro široké spektrum účelů. Vývojem standardů pro digitální vysílání v Evropě se zabývá konsorcium Digital Video Broadcasting Projed (DVB), který sdružuje výrobce a poskytovatele služeb. Jednotlivé větve vývoje nesou označení DVB-T (terrestrial) pro pozemní, DVB-S pro satelitní vysílání a podobně. DVB definuje hlavně technické standardy, mezi nimi formát vysílaných dat a způsob jejich zašifrování před nežádoucím příjemcem, tzv. Conditional Access [WWW-CA]. V následujícím textu naznačím, v jakém formátu takové vysílání probíhá. Zařízení pro digitální snímání obrazu obecně nejdříve produkují nekomprimovaný záznam složeny z jednotlivých snímků (frames). Snímky pak obsahují údaje o barvě a světelnosti jednotlivých bodů - pixelů. Například formátem, který produkuje webová kamera, je YV12, viz [Web-YV]. Ten lze uložit na disk nebo poslat po síti (streamovat) na jiný počítač. Obraz v tomto formátu obsahuje ale obrovské množství dat a proto nastupuje komprese, kdy dochází zjednodušeně řečeno k • vyhledávání a odstranění redundantních informací, • záměrnému vynechávání některých dat tak, aby lidské oko zaznamenalo co nejmenší odchylku od původního nekomprimovaného obrazu. Existuje nepřeberné množství kompresních algoritmů, řada z nich je pak chráněna kontroverzními, a proto dnes tolik diskutovanými patenty. Stejně jako u obrazu, i zvuk je komprimován, byť potřeba zde není tak akutní jako u obrazu. Rozdíl velikostí je patrný u známého formátu MPS oproti nekomprimovanému wav. Obraz i zvuk jsou nakonec rozděleny do paketů a pakety střídavě spojeny do transportního proudu (transport stream), který je možno přenášet k divákovi. Specifikace DVB určují jako formát komprese obrazu a zvuku MPEG-2. MPEG (Moving Picture Experts Group) zahrnuje množství standardů pro kódování audiovizuálních informací v digitálním komprimovaném formátu [Web-MPEG]. MPEG-2 je pak jednou z konkrétních norem, která se uplatní v řadě aplikací [FAQ-MPEG2]. Transportní proud kromě paketů s audiovizuálními daty však ještě obsahuje řídicí data, tzv. Control Messages. V nich se přenášejí údaje pro Conditional Access (CA). Conditional Access specifikuje, jak jsou data zašifrována a který ze zákazníků má právě možnost ten který kanál sledovat. Formát transportního proudu, který používají systémy DVB se nazývá MPEG Transport Stream [MPEG-TS]. Bakalářská práce Kapitola 1. 9 1.5 Conditional Access Conditional Access je označení pro proces šifrování audiovizuálních dat pro digitální televize za účelem autorizace příjmu vysílání. Šifrování probíhá v několika rovinách, jež budou popsány v tomto oddíle. 1.5.1 Scrambling Vlastní zašifrování audiovizuálních dat se nazývá scrambling. Provede se ještě před konečným spojením dat do transportního proudu. Dešifrování na straně příjemce se označuje jako descrambling. Scrambling a descrambling se musí v reálném čase provádět pro velké množství audiovizuálních dat a algoritmus musí být proto velmi rychlý. Scrambling je příklad symetrické šifry, kdy se na šifrování i dešifrování použije stejný klíč. Aby nedocházelo k častému prolamování šifry, klíč pro scrambling a descrambling se obměňuje. To je v praxi realizováno tak, že v přístroji příjemce je současně více klíčů a ty se v pravidelných intervalech (řádově desítky sekund) mění. Jakmile divák vytáhne kartu z přístroje, do deseti sekund mu obraz zmizí, neboť nemá klíč pro jeho dešifrování. Standard pro scrambling používaný prakticky všude v Evropě je definován normou ETSI - European Telecommunications Standards Institute [ETSI] a nazývá se D VB Common Scrambling Algorithm - CS A. 1.5.2 Control Messages Klíč pro scrambling/descrambling se nazývá control word. Vysílání pak probíhá tak, že v přijímači je současně uloženo více klíčů (control word) pro descrambling a v krátkých intervalech je vybírán vždy jeden z nich. Výběr provede vysílací centrála a pošle spolu s audiovizuálními daty transportním proudem přijímači v podobě tzv. řidičích zpráv (control messages). Zprávy, kterými se přenášejí informace o právě použitém klíči, se nazývají EMM -Entitlement management message. Data v EMM zprávách jsou již šifrovány „doopravdy", algoritmem s nízkým rizikem prolomení za cenu delšího šifrování. Přijímající strana potom v závislosti na kanále může a nemusí být oprávněna přijímat daná audiovizuální data a v tom případě dojde nebo nedojde k dešifrování informace, který klíč (control word) má být použit. Klíče pro descrambling jsou navíc v pravidelných delších časových intervalech obměňovány přímo v přístroji. Příkaz k takové obměně - tentokrát spolu Bakalářská práce Kapitola 1. 10 | | Video ........ | | Audio nnnnn Obrázek 1.2: Conditional Acceses System - Přenos šifrovaných dat s klíčem - pošle centrála transportním proudem opět v podobě zašifrované kontrolní zprávy. Ta se nazývá ECM - Entitlement Control Message. 1.5.3 DVB CA Common Interface Konkrétní implementace Conditional Access se označuje jako Conditional Access System. Existuje mnoho Conditional Access systémů od různých výrobců. Aby byla zajištěna interoperabilita, tj. aby poskytovatelé televizního vysílání mohli používat různé CA systémy, byly i zde vyvinuty (a samozřejmě stále se vyvíjejí) standardy. DVB definuje jednotné rozhraní, tzv. DVB CA Common Interface. To Bakalářská práce Kapitola 1. 11 umožňuje aby uživatel nebyl při koupi přístroje vázán na konkrétní implementaci Conditional Access, a tedy aby měl možnost sledování vysílání různých poskytovatelů. Je-li zařízení pro příjem signálu vybaveno slotem kompatibilním s DVB CA Common Interface, může uživatel pouhou výměnou kryptografického modulu využívat služby chráněné jiným systémem CA. Kryptografický modul kompatibilní s DVB CA Common Interface se nazývá Conditional Access Module - CAM. Samotné descramblování se provádí uvnitř přístroje a je pro veškeré digitální vysílání rámci normy DVB univerzální. Přístroj po kryptografickém modulu (Conditional Access Module) nechce nic jiného, než klíč, kterým má audiovizuální data descramblovat. Přitom mu předává Control Messages z transportního proudu, aniž by ho jejich obsah nějak zajímal. Rozhraní DVB Common Interface tedy specifikuje, jakým způsobem přístroj předá Control Messages a dostane klíč. Samotný obsah Control Messages a správa klíčů je plně v režii dodavatele systému pro Conditional Access. Control Messages í vysílání j Scramblovaná data i Descramblovaná data ---------------------► c obrazovka 3 Klíče Control Messages DVB Common Interface Conditional Access Module Obrázek 1.3: Výměna informací mezi přístrojem a Conditional Access Module Tento fakt však s sebou nese velké potenciální riziko. Čas od času dojde Bakalářská práce Kapitola 1. 12 k prolomení některého systému pro Conditional Access. To s sebou může nést nutnost výměny modulů. Pokud by došlo k prolomení samotného CSA, bylo by nutné obměnit všechny přístroje, neboť všichni broadcasteři v Evropě používají stejnou šifru - Common Scrambling Algorithm. CSA samotný dosud prolomen nebyl, vždy selhaly jeho implementace nebo implementace Conditional Access systémů. Standardu D VB CA Common Interface vyhovuje i systém Cryptoworks, na který se v následujícím zaměříme. Odkazy: [DRM-02, strana 69-78] 1.5.4 Cryptoworks DVB CA Systém Cryptoworks DVB CA vyvinutý firmou Royal Philips Electronics zatím jako jediný dosud odolal všem snahám o prolomení. Díky své flexibilitě se kromě televizního vysílání (tedy Conditional Access) dobře uplatní i v dalších oblastech, jako jsou bankovní transakce nebo autorizace v počítačových sítích. Cryptoworks u nás využívá například vysílání UPC Direct. Kryptografický modul systému Cryptoworks je vybaven terminálem pro smartkartu. Smartkarta (Smartcard) je karta velikosti klasické bankovní karty, která obsahuje samostatný čip s procesorem [FAQ-SC, ALT-SC]. Karta Cryptoworks může současně držet sady klíčů pro různé služby různých poskytovatelů a různé kryptografické techniky či šifrovací algoritmy. V případě digitálního vysílání jde o klíče pro descrambling a implementaci v podobě Conditional Access Module s rozhraním DVB Common Interface. Philips dodává ovšem i levné přístroje bez DVB Common Interface pouze s vestavěným dekódovacím systémem Cryptoworks - příkladem je Philips D SX 6010 [Philips], který se standardně dodává se službou UPC Direct. Ten má vstup jen pro smartkartu Cryptoworks. Smartkarta komunikuje s CAM protokolem podle normy ISO/IEC-7816 [Web-CAM], avšak jsou zde některé proprietární (specifické pro výrobce a nezveřejněné) odchylky. Na smartkartě jsou uloženy klíče pro dekódování (descrambling) digitálního obrazového a zvukového signálu. Centrála je čas od času vyměňuje zasláním ECM. Intervaly výměn jsou typicky co měsíc. Pro digitální televizní vysílání bývá na kartě v jednom okamžiku uloženo více klíčů. V pravidelných intervalech během vysílání se střídá klíč, kterým je obraz a zvuk zašifrován a centrála pošle informaci o změně prostřednictvím EMM. Proto pokud uživatel vytáhne kartu z přístroje, příjem do několika desítek vteřin ustane. Systém je velmi propracovaný. Disponuje škálovatelným adresovacím schématem a control messages lze adresovat všem kartám, jednotlivé kartě i různým sdíleným prostorům karet včetně geografických, pro služby typu pay-per-view a video-on-demand nabízí preview funkce apod. [Web-CAM, Bakalářská práce Kapitola 1. 13 LET-CAM] Je nezávislý na šifrovací technologii, kterou přenáší. Nás nyní bude zajímat především Common Scrambling Algorithm. Co bude pro nás podstatné, je způsob komunikace kryptografického modulu s centrálou. Veškeré citlivé informace jsou při přenosu chráněny šifrovacím algoritmem RSA - zejména klíče pro descrambling. Pro realizaci výše zmíněných funkcí a vlastností systému je na každé kartě uložena sada RSA klíčů. Klíče nikdy neopustí kartu. Karta dostává a vydává zprávy pro centrálu v podobě instrukcí zašifrovaných RSA - tento protokol však není veřejně zcela znám. Například pošle-li vysílací centrála ECM s novým klíčem, CAM ji předá kartě jako instrukci uvozenou kódem A4 48 00 00 (přidání/smazání záznamu na skupině karet) a následovánu blokem dat šifrovaných RSA. Control word uložený v datech je stále ještě zašifrovaný RSA. Při descramblingu si přístroj přes D VB Common Interface vyžádá control word od CAM. CAM si jej vyžádá od karty, která odpoví instrukcí s klíčem, pokud má karta příslušné oprávnění. Veškeré RSA šifrování a dešifrování probíhá na kartě, tedy kartu v tomto okamžiku už opouští control word nechráněný RSA - viz [CWFaq] Bakalářská práce Kapitola 1. 14 Přístroj s DVB Common Interface . Protokol definovaný DVB Common Interface Přístroj s vestavěným Cryptoworks CAM Cryptoworks CAM L^........ Protokol ISO/IEC-7816 + proprietární rozšíření Cryptoworks Cryptoworks Smartcard Obrázek 1.4: Znázornění funkce systému Cryptoworks DVB CA Kapitola 2 Základní pojmy kryptografie 2.1 Šifrovací algoritmus, zpráva, klíč, kryptogram Základní metoda utajení dat před neautorizovaným příjemcem se nazývá šifrování. Původní data nazýváme v kryptografii zpráva, data v utajené podobě kryptogram. Převedení kryptogramu zpět na zprávu se nazývá dešifrování. Kromě utajení před neautorizovaným příjmem se kryptografie zabývá též ochranou před nežádoucí modifikací kryptogramu, autentizaci odesilatele apod. Postup, jakým se zpráva převede na kryptogram označujeme jako šifrovací algoritmus nebo jen šifra (cipher). Aby byla data utajena před neautorizovaným příjemcem, používá šifrovací algoritmus datový údaj, který je známý jen chtěnému příjemci. Ten se nazývá klíč. Jedno ze základních pravidel kryptografie je, aby utajení záviselo jen na klíči a nikoli na znalosti šifrovacího algoritmu. 2.2 Symetrická a asymetrická šifra Symetrická šifra používá stejný klíč pro šifrování i dešifrování a matematicky ji lze popsat jako funkci E (encryption) C = E(K,M), kde E je šifrovací funkce (encryption), K je klíč (key), M zpráva (message) a C kryptogram (ciphertext). Dešifrování je pak funkce D (decryption) M = D(C,K), 15 Bakalářská práce Kapitola 2. 16 kde D je inverzní funkce kfía převede data do původní podoby. Zmínili jsme šifrovací a dešifrovací funkce E a D. Aby mělo šifrování smysl, musíme dešifrováním kryptogramu obdržet původní zprávu, tedy D(E(K,M)) = M. Tomuto požadavku říkáme korektnost algoritmu. Asymetrická šifra používá jiný klíč pro zašifrování a jiný klíč pro dešifrování, mluvíme o dvojici klíčů (key pair). K zašifrování se použije veřejný (public) klíč, k dešifrování soukromý (private) neboli tajný (secret) klíč. Někdy též mluvíme o jednom klíči a jeho veřejné a soukromé části. Veřejný klíč se použije pro zašifrování a z jeho znalosti nelze odvodit soukromý klíč a tedy ani dešifrovat zprávu z kryptogramu. Může být veřejný v plném významu slova a jej může mít každý, aniž by šifrou chráněná data byla nějak ohrožena. Šifrování a dešifrování probíhá takto: C = E(Kpub,M), M = D{Kpriv,C). Korektnost asymetrické šifry zapíšeme jako D(KprmE(Kpuh)M)) = M. Nejčastějším případem dvojice klíčů je ten, kdy soukromým klíčem jsou dvě velká prvočísla a veřejným klíčem je součin těchto prvočísel. Problém nalezení privátního klíče z veřejného je tedy problém nalezení rozkladu celého nezáporného čísla na prvočinitele, faktorizace. Faktorizace velkého součinu je časově tak náročná, že přesahuje možnosti současné výpočetní techniky. Výhody asymetrického šifrování proti symetrickému lze shrnout do dvou bodů: • Přenos klíče při symetrickém šifrování je vždy spojen s určitým nepohodlím a rizikem. V případě asymetrické šifry příjemce jednoduše vygeneruje dvojici klíčů a její veřejnou část pošle bez obav a bez potřeby utajení. • Množství klíčů potřebných ke komunikaci se rapidně snižuje. Při symetrické komunkaci mezi n stranami „každý s každým" je třeba n(n —1)/2 klíčů, kdežto pro symetrickou jen 2n klíčů, přesněji n párů (veřejný klíč, tajný klíč). Bakalářská práce Kapitola 2. 17 Podstatnou nevýhodou asymetrických šifer je však časová náročnost šifrování a dešifrování, proto se často používá kombinace asymetrické a symetrické šifry. U protokolu SSH počítače nejdříve naváží asymetricky šifrované spojení (RSA nebo DSA) a jím si pošlou ad hoc vygenerované klíče pro symetrickou šifru DES, jíž je chráněn zbytek spojení. Stejně tak u DVB se asymetrickou šifrou RSA přenáší control word pro symetrickou šifru Common Scrambling Algorithm. 2.3 Operace xor a one-time pad Použijeme-li v šifře jako šifrovací funkci xor zprávy s klíčem, vznikne tzv. one-time pad. xor je logická operace „exkluzivní nebo (exclusive or)", tedy £or(0,0) = 0, xor{l, 0) = 1, xor(0,1) = 1, xor(0,0) = 0. V souladu s konvencí budeme xor na schématech i v textu značit ©: Mn Mi Mn GD-KBGD-KB ■ ■-CJD-KB Co Ci c„ Obrázek 2.1: One time pad xoruje každý bit zprávy jedním bitem klíče Řekněme, že máme zprávu M = (0,1,1, 0,1, 0, 0,1) a klíč K = (K0, ■ (1,1,0,1,1,0,1,1), potom C = M e K = (1,0,1,1,0,0,1,0). Opětovným xorováním kryptogramu a klíče vznikne původní zpráva: M = ce K = (0,1,1,0,1,0,0,1). ..,K7) Bakalářská práce Kapitola 2. 18 Tedy algoritmus je korektní, což můžeme zapsat jako K®(K®M) = M. Operace © je komutativní, neboť 0 © 1 = 1 © 0, tedy a® b = 6 © a, asociativní, neboť (0 © 0) © 0 = = 0©0 = = 0 © (0 © 0) (100)00 = = 100 = = 1 = 001 = 100 = 10 (0 0 0) (10 1)00 = = 000 = = 0 = 101 = 10(10 0) (0 © 0) © 1 = = 001 = = 1 = 001 = 0© (0 0 1) (10 0)01 = = 101 = = 1 © (0 © 1) (101)01 = = 001 = = 100 = 10(10 1). Je-li délka klíče při one-time pad větší nebo rovna délce zprávy, poskytuje systém tzv. perfektní bezpečnost, avšak za cenu nutnosti výměny velkých klíčů. V praxi se proto k zašifrování používají pseudonáhodné posloupnosti vygenerované z klíčů [Laws, Paseka]. Navíc klíč je možné použít jen jednou, neboť pokud se útočník zmocní dvojice (zpráva, kryptogram), prostým xo-rováním dostane klíč (K = M © C). 2.4 Bloková šifra Šifru označíme jako blokovou, jestliže zprávu rozdělí na stejně velké úseky a ty postupně zpracovává do bloků téže velikosti [Klíma-03]. Mějme zprávu M = (M0,..., M/y) o n blocích. Pak šifrujeme Co = E(M0),...,Cn = E(Mn) a kryptogram dešifrujeme M = (Mo,..., Mn) = (D(Co),..., D{Cn)). Tento způsob kódování se nazývá ECB mód - elektronická kódová kniha (Electronic Codebook Mode). Má ovšem tu nevýhodu, že stejné bloky kryptogramu znamenají i stejné úseky původní zprávy. Útočník pak může zprávu kromě dešifrování i nežádoucím způsobem modifikovat, například výměnou nebo vynecháním bloků. Proto se častěji používá zřetězení šifrovaného textu - CBC (cipher block chaining). Zde se v každém kroku šifruje původní text Bakalářská práce Kapitola 2. 19 Mn Mi Mn 3J su klíč šifra šifra i u ■ ■■ šifra I Cn Mn Mi (ZKB CED é C^D Mn •é klíč šifra šifra šifra Co Ci \- Cn Obrázek 2.2: Bloková šifra v ECB a CBC módu Bakalářská práce Kapitola 2. 20 Co ^/J dešifr. CZ3-*© Mr dešifr. ě Mi LH QT) dešifr. ■ T l Mn| Obrázek 2.3: Dešifrování blokové šifry v CBC módu xorovaný s předchozím zašifrovaným textem, přičemž první blok je xorován s tzv. inicializační hodnotou (IV - initial value): C0 = E(K,IV®M0)), d = E(K, Co e MO, Cn = E(K,Cn-1(BMn)). Inicializační hodnota může být součástí klíče, častěji je ovšem přiložena ke kryptogramu. Dešifrování potom vypadá takto: M0 = IV(BD(K,C0)), M^CoeDiK,^), Mn = Cn.1®D(K,Cn)). 2.5 Proudová šifra Proudovou označíme šifru tehdy, jestliže zprávu šifruje postupně bit po bitu a k zašifrování používá pseudonahodnou posloupnost vytvořenou z klíče. Takovouto pseudonahodnou posloupnost označujeme jako heslo. Jednoduchým příkladem je Vigenerova šifra. Zde se však jedná o nejtriviálnější případ - Bakalářská práce Kapitola 2. 21 klíč je prostým způsobem opakován a kryptogram je poměrně snadno roz-luštitelný hledáním délky klíče Kasiského testem [Paseka, strana 28]. Další velmi známá proudová šifra je například algoritmus RC4- Samotné šifrování nejčastěji spočívá v prostém xorování původní zprávy s heslem. Skutečnost, že stejná zpráva se stejným klíčem zašifruje do stejného kryptogramu, se stejně jako v případě blokové šifry eliminuje použitím inicializační hodnoty (nonce - number used once), která potom je součástí klíče nebo kryptogramu. Při generování pseudonáhodné posloupnosti se velmi často používají po-souvací registry. 2.6 Posouvací registry Posouvací registr je posloupnost bitů konečné délky, která se v jednotlivých krocích výpočtu mění posunutím doprava a dosazením nových hodnot na začátek. [Wiki-FSR] Stav registru v čase t budeme označovat X(t) = (X1(t),...,Xn(t)). Na začátku má registr stav X(0) = (Äo,...,Äri). V každém kroku se všechny bity posunou o jednu pozici doprava, tj. Xk(t) = Xk(t-l),k = 2,...,n. Zároveň se na první pozici dosadí hodnota závislá na předchozím stavu X1(t) = f(X0(t-l),...,Xn(t-l)), tedy Xn(t) = (f(X0(t -1),..., Xn(t - 1)), Xx{t - 1),..., *„_!(* - 1)). Stav registru je tedy úplně popsán funkcí / a počátečním stavem. Tím je obvykle právě n-bitový klíč nebo nějaká jiná hodnota závislá na klíči. Bakalářská práce Kapitola 2. 22 f(Xo) Ro Ri Rn KN - \ Xo(l) f(Xi) M Xo(2) Xi(2) ^_A Xi(l) ^A 1 Xn(l) \ Xn(2) Obrázek 2.4: Posouvací registry 2.7 Kryptoanalýza a napadání šifer Útokem na šifru rozumíme činnost, kdy se útočník snaží • jednorázově získat klíč, kterým byla nějaká zpráva zašifrována, • najít obecný postup jak získávat klíč, • najít postup jak z kryptogramu odvodit původní zprávu apod. - mluvíme o prolomeni šifry. Prolomením šifry získává útočník možnost zprávu dešifrovat, případně ji po cestě k původnímu příjemci modifikovat nebo zcela podstrčit a falešně autorizovat apod. Kryptoanalýza označuje proces zkoumání napadnutelnosti šifry, odhalování jejích potenciálních slabin. Podle druhu informace, kterou má útočník k dispozici, lze útoky rozdělit na • Ciphertext only - útočník má k dispozici jen zašifrovaný text; • Known plaintext - útočník má k dispozici dvojici (zpráva, kryptogram) ; Bakalářská práce Kapitola 2. 23 • Chosen plaintext - útočník má přístup k šifrovacímu modulu a k libovolné zprávě je schopen vygenerovat kryptogram; • Chosen ciphertext - útočník má přístup k dešifrovacímu modulu a k libovolnému kryptogramu je schopen získat původní zprávu. Podle způsobu provádění můžeme rozpoznat útoky: • Algebraické. Kryptoanalytické metody, které se snaží přímo najít chybu v algoritmu. Do této skupiny zařadíme Kasiského test [Paseka, strana 28]. Algebraické útoky mohou končit prolomením šifer, ale mnohem častěji pouze odhalením potenciálních slabin algoritmů. Z nich lze dále vycházet při dalších útocích. • Hledání chyb v implementaci šifrovací metody. Může se jednat o implementaci hardwarovou - sem lze zařadit situaci, kdy z bankovní karty nějakým způsobem dostaneme PIN nebo ze smartkarty přečteme RS A klíč. O příklad nalezení chyby v softwarové implementaci půjde tehdy, když SSH serveru podstrčíme svůj klíč a takto se neautorizované dostaneme do cizího účtu. Mimořádný význam měl objev postranních kanálů, kterými se budeme ještě zabývat. • Útok hrubou silou spočívá v ověření nějakého předem definovaného souboru dat, například vyzkoušení všech možných klíčů nebo nějaké velké skupiny klíčů. • Důležitou skupinou, kterou se však zde nebudeme zabývat, je sociálni inženýrství Ta využívá převážně lidský faktor - pohodlnost, neznalost a naivitu. Zavoláme sekretářce, aby nám prozradila heslo do systému kvůli údržbě. Nebo do diskusní skupiny na WWW vložíme příspěvek se skriptem a ten využije chybu v prohlížeči jiného návštěvníka. Do této skupiny také můžeme zařadit útoky typu Man-in-the-middle (např. [MITM]) apod. Všechny postupy lze úspěšně kombinovat. 2.7.1 Algebraické metody u proudových šifer U proudové šifry lze zkoumat předperiodu (preperiod) a periodu generované pseudonáhodné posloupnosti, tedy počet kroků výpočtu, po kterém se posloupnost začne opakovat a počet kroků, pro které se hodnoty donekonečna opakují. Na zjištění periody je založen Kasiského test [Paseka, strana 28] v případě Vigenerovy šifry. Perioda je obecně závislá na dvojici (nonce,klíč). Bakalářská práce Kapitola 2. 24 předperioda perioda 1 perioda 2 V\ Ví Vz a\ a2 a3 ai a2 a3 Dále si všímáme periody stavů na různých místech logických obvodů realizujících algoritmus - posuvných registrů, výstupů S-Boxů apod, a tyto hodnoty algebraicky zkoumáme. Lze vysledovat závislosti mezi těmito místy a popsat je soustavami rovnic. Pokud budeme provádět dostatečný počet pokusů s generovanými dvojicemi (inicializační hodnota, klíč), můžeme výsledky zpracovávat statisticky. Tím výrazně omezíme počet možných stavů na pozorovaných místech oproti všem možným hodnotám, které by se zde mohly vyskytnout. Množina klíčů se potom redukuje na množinu nalezených přípustných stavů1 a další kryptoanalýza nebo útok hrubou silou je potom již mnohem jednodušší. 2.7.2 Algebraické metody u blokových šifer Lineárni kryptoanalýza [DEF-LK] je metoda která využívá lineární závislosti kryptogramu, zprávy a klíče. Jedná se o known plaintext attack ale předpokládá se, že útočník má k dispozici větší množství dvojic (zpráva, kryptogram). Šifrovací funkci nahrazuje soustavami lineárních rovnic, např. Mh e • • • e Mik e ch e • • • e cjt = o, kde Miľ,..., Mik je část zprávy a Cj1,... )Cjl je část kryptogramu. Poté sleduje, s jakou pravděpodobností rovnice budou platit. Soustavou tedy aproximuje šifrovací funkci. Odolnost vůči lineární kryptoanalýze - nelinearita - je důležitým kriteriem kvality šifry. Napadnutelnost lineární kryptoanalýzou můžeme vyjádřit například počtem dvojic (zpráva, kryptogram) které musíme znát, abychom aproximovali šifrovací funkci s daným klíčem. Například algoritmus DES vyžaduje 243 takových dvojic, abychom jej mohli prolomit lineární kryptoanalýzou. Dalším častým útokem je diferenciální kryptoanalýza. Ta zkoumá, jak se změní kryptogram, jestliže změníme zprávu. Diferenciální kryptoanalýza je chosen plaintext útok. Útočník totiž musí zkoušet vybrané dvojice zpráv s malými odchylkami, aby zjistil jejich rozdíl na výstupu. Diferenciální a lineární kryptoanalýza se často používá ve spojení, mluvíme o lineárně-diferenciální kryptoanalýze. Úvod do lineární a diferenciální 1 Množství informace o klíči, kterou poskytuje kryptogram, je jedním ze základních kritérií kvality šifry, viz teorie perfektní bezpečnosti [Paseka, strana 38]. Redukcí počtu klíčů se toto množství informace zvyšuje. Bakalářská práce Kapitola 2. 25 kryptoanalýzy lze najít například v [DL-tut]. Kryptoanalýza však používá spoustu dalších algebraických, statistických a jiných matematických metod [Wiki-CA] ke zkoumání blokových šifer. 2.7.3 Metoda postranních kanálů Postranními kanály (side channels) rozumíme každou nežádoucí výměnu informací mezi kryptografickým modulem a jeho okolím [Klíma-VA]. Typickým příkladem je časový postranní kanál, kde se z časové náročnosti realizace algoritmu odvodí informace o klíči. Tento typ útoků se nazývá timing. Pozorovat lze prakticky všechny fyzikální veličiny, například spotřebu energie šifrovacího zařízení. [Web-ICZ] Dalším typem jsou chybové útoky (fault attacks) [Wirt-04], prováděné hardwarovou modifikací kryptografických modulů. Útočník se může například pokoušet vyřadit nebo pozměnit některé části kryptografického modulu. Následně se pozoruje rozdíl mezi původním a modifikovaným výstupem. Kryptografický modul lze osvětlovat, ovlivňovat laserovým paprskem, vystavovat různým teplotám apod. - známé je zmrazovaní generátoru náhodných čísel u hracích automatů. Objev postranních kanálů je relativně nedávný a a ukázalo se, že představují poměrně silnou hrozbu. Současná kryptografie se jimi proto velmi intenzivně zabývá [Klíma-02]. Kapitola 3 DVB Common Scrambling Algorithm Common Scrambling Algorithm byl zpočátku neveřejný a byl k dispozici pouze na základě tzv. non-dis clo sure agreement - dohody o utajení. Posléze se ale objevil program pro operační systém Windows FreeDec neznámého autora, ze kterého byl reverzním inženýrstvím algoritmus ihned odvozen a vystaven na WWW stránkách [Web-irde.to]. To opět dokazuje neúčinnost „security by obscurity" - ačkoli důvodem bylo spíše ztížit kryptoanalýzu a tím riziko prolomení, než samotné skrytí algoritmu. Přes odtajnění však CSA dosud nijak vážně ohrožen nebyl. CSA je kombinací 64bitové blokové šifry a proudové šifry. Šifra je symetrická - k šifrování i dešifrování se použije stejný klíč. Klíč je shodný pro blokovou i proudovou část šifry a nazývá se control word. Má délku 64 bitů, tedy K = (fc0,..., k63). 3.1 Scrambling Na začátku je zpráva rozdělena na bloky M0,.., Mn_i, R po osmi bytech (1). Poslední blok R může být menší než osm bytů a v tom případě jej nazýváme reziduum (residue) (2). Sekvence bloků je postupně zašifrována blokovou šifrou (3) v opačném pořadí. Tedy začíná se s Mn_\ a končí s M0. Případné reziduum se nezašifrovává a putuje na vstup proudové šifry nezměněno. Blok Mn_i se před šifrováním xoruje s inicializační hodnotou IV v tomto případě složenou z nul (4). Každý další blok Mi se pak před šifrováním xoruje s předchozím kryptogramem Bi+i. Poslední hodnota £>0 se použije jako inicializační hodnota (nonce) pro proudovou šifru (5). Proudová šifra vygeneruje z klíče a nonce pseudonáhodnou posloupnost (6), která se xoruje (7) s vý- 26 Bakalářská práce Kapitola 3. 27 (i) (3) GO e ( * )i e- (2) CD e C"^ Qj^ (iv=(o....o) ^ (4) C kiíč ) (5) Pn-l (6) •e *® UA ^ (7) (8) Obrázek 3.1: Scrambling stupem blokové šifry. Na konci dostaneme kryptogram - scramblovaná data Co, • • • , Cn-i, Cn (8). 3.1.1 Bloková šifra Označíme-li funkci blokového zašifrování Eß, můžeme psát Bi = EB(Bi+1 ®Mi,K) pro i = n - 1,..., 0, přičemž Bn = (0,..., 0) je inicializační hodnota. Osmibytový úsek zprávy Mi se xoruje s přechozím výsledkem Bi+i a nastupuje vlastní bloková šifra EB. Ta sestává z 56 stejných kroků - cyklů. Funkci, která realizuje každý jednotlivý cyklus, budeme označovat tp. Klíč, kterým se v jednotlivých cyklech zašifrovává, je odvozen z původního klíče K - mluvíme o tzv. proměnném klíči (running key) nebo o rozšířeném Bakalářská práce Kapitola 3. 28 klíči (expanded key). Ten má 448 bitů. Označme jej K = (k0 ,..., k447). V každém cyklu budeme potřebovat 8 bitů rozšířeného klíče. Jelikož 448 = 8 x 56, celý rozšířený klíč se postupně vyčerpá. Označme velkým písmenem bloky rozšířeného klíče pro jednotlivé cykly: Ko = (^o j • • • j ^7 ) Kf = (ki,...,kg+7) pro z = l,...,55. Potom použijeme posloupnost bloků v pořadí KE KE Mějme nyní permutaci p definovanou tabulkou 3.1. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 35 8 6 41 48 28 20 27 53 61 49 18 32 58 63 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 23 19 36 38 1 52 26 0 33 3 12 13 56 39 25 40 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 50 34 51 11 21 47 29 57 44 30 7 24 22 46 60 16 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 59 4 55 42 10 5 9 43 31 62 45 14 2 37 15 54 Tabulka 3.1: Scrambling - permutace p pro expanzi klíče blokové části 448bitový rozšířený klíč KE = (fcjf, • ••> ^447) získáme takto: (kQ ,..., k63) = (fco,..., kes) (A;64j-,..., A;64j-+63) = p((%4(j-i;p • • • > %4(j-i)+63)) © P Pro i = 1> • • • > 6> kde p = (0, 0, 0, 0, [7], 0, 0, 0, 0, [7], 0, 0, 0, 0, [7], 0, 0,0, 0, [7]), přičemž [j] jsou čtyři bity čísla j, tj. p je 64bitová konstanta. Nechť S = (So,..., £7) je osm byte výsledku nějakého cyklu j — l.V následujícím cyklu aplikujeme funkci (p s klíčem K j a obdržíme další mezivýsledek (f(S, Kj). Označíme-li (fj(S) = (f(S, Kj), lze všech 56 cyklů psát EB(Bi+1 0 Mi, K) = (/?55(^54(. - - MBi+i © Mi)...)) Bakalářská práce Kapitola 3. 29 pro nějakou část zprávy M^, z = 1,..., n — 1 Funkce (p(S, Kj) pro 64bitový mezivýsledek S = ($o,..., £7) a pro 64bi-tový blok Kj proměnného klíče je definována takto: 0 < z < n - 1. 3.1.2 Proudová šifra Proudová šifra vytvoří z klíče (control word) a posledního výsledku £>0 blokové šifry pseudonáhodnou posloupnost P1?..., Pn, se kterou se xoruje zbytek výsledku B\,..., £>n-i, Ä blokové šifry, abychom dostali kryptogram -scramblovaná data. Proudová šifra využívá ke generování dva posouvací registry FSRA a FSRB Feedback Shift Registers a logický obvod s pamětí, tzv. combiner (combiner with memory). Combiner s pamětí realizuje logickou funkci, přičemž výsledek této funkce je závislý na předchozích hodnotách (proto s pamětí), viz obrázek 3.3. Bakalářská práce Kapitola 3. 31 ■í nonce V- Výstup Obrázek 3.3: Scrambling - přehled proudové části Oba posouvací registry jsou čtyřicetimístné. Označme první registr A — (a- .V=0'->3 y=0,..,3 druhý registr B = (6«)Sá a klíč K = (k0,...,k63). Pak počáteční stav registrů je dán následujícími pravidly - viz tabulka 3.3: a>ij = hi+j pro i = 0,..., 7, clíj = 0 pro i = 8, 9, bij = k32+u+j pro i = 0,..., 7, bij = 0 pro i = 8, 9. Prvních 32 kroků je inicializačních a není odečítán výstup proudové šifry. Proto číslujeme kroky od —31, tak, aby v kroku označeném t = 1 byly odečteny z výstupů první hodnoty. Zpětnovazební funkci a výstupy registru F S RA (obrázek 3.4) lze popsat S-Boxy. S-Box (substitution box) je tabulka popisující nějakou logickou funkci, tj. pro každý stav na vstupech definuje stav výstupů. Podle počtu vstupů a výstupů mluvíme o rozměrech S-Boxu. Bakalářská práce Kapitola 3. 32 Registr A h h h h h k5 h h h kg ho hi fcl2 fcl3 ku fcl5 ho k17 hs ho ho fai k22 k23 k2A k25 ho hi k28 k29 ho h\ 0 0 0 0 0 0 0 0 Registr B h2 ^33 hi &35 ho h7 hs hg ho h\ h2 h3 há Ä45 ho hi hs Ä49 ho hl h2 ^53 há ^55 ho hi hs ^59 ho hi h2 &63 0 0 0 0 0 0 0 0 Tabulka 3.3: Počáteční stav (ŕ = — 31) posouvacích registrů proudové šifry Označme a^ = (a^o,..., 0^3) z-tý řádek matice popisující stav registru A. Výstup S-Boxu je v každém kroku xorován s posledními čtyřmi bity ag = (ag5o, • • •, 09,3) registru a tato hodnota vložena na první čtyři bity registru A. Poté, co je na začátku do registru nahrán klíč, proběhne nejprve 32 inicializačních cyklů bez odečítání výstupů. Na vstupu F S RA je kromě klíče a SBq ještě výstupní registr D combineru. V inicializačním módu se v každém z cyklu pro i = — 31,..., 0 vypočítá další zpětnovazební hodnota aQ(i +1) = A e If (B0) e S (A) 0 a9(z), kde S (A) = iL>(ao,..., clq) = S(a0^^..., a9^) je výstup S-Boxu, a9 poslední čtyři bity registru A, D{ je stav registru D combineru a IA následující funkce inicializační hodnoty: r a _ f $ Bo div 24 pro i lichá, 1 \ SBq mod 24 pro i sudá. Nový stav registru A je po posunutí A{i + 1) = (a0(z + 1), a0(z),..., as(fc))> jde tedy o rotaci 4 bity doprava. První posouvací registr má čtyři výstupy. Vždy jeden čtyřbitový a jeden jednobitový jsou pak vstupem druhého posouvacího registru a combineru. Vstupy a výstupy S-Boxů FSRA jsou popsány tabulkami 3.4. Bakalářská práce Kapitola 3. 33 ^ w °u "i ä/. "ó a4 "D a6 "í a& ay 4bity TYT ■ ■ ■ Y S-BOXY (7 S-BoxS 5x2) i ľ 1 r 1.......... Y P X z Q 1 4 r bity y 1 r bit 4bity 4bity ▼ 1 lbit ▼ C FSRB FSRB ( combiner ) ( combiner j 4bity ^J U "^ 4bity 4 bity CED—► Obrázek 3.4: Scrambling - posouvací registr A proudové části SI ^3,0 ^0,2 «5,1 ^6,3 a8,0 S2 «1,1 ^2,2 ^5,3 a6,0 ^8,1 S3 ^0,3 ^1,0 ^4,1 ^4,3 ^5,2 S4 ^2,3 a0,l «1,3 ^3,2 &7,0 S5 ^4,2 ^3,2 ^5,0 «7,1 a8,2 S6 «2,1 «3,1 ^4,0 a6,2 ^8,3 S7 «1,2 a2,0 a6,l ^7,2 ^7,3 X $4,0 $3,0 $2,1 $1,1 Y $6,0 $5,0 $4,1 $3,1 Z $2,0 $1,0 $6,1 $5,1 P $7,1 q $7,0 Tabulka 3.4: Scrambling - tabulka vstupů a tabulka výstupů S-Boxů posou-vacího registru A proudové části Každý S-Box má pět bitů vstupu. První tabulka definuje pro 7 S-Boxů $i,..., $V, které bity registru A jdou do jejich vstupů, tj. například vstup Sq tvoří pětice (fl2,i; a3,i; ö^4,o; ^6,2; ^8,3)- Každý registr má dva bity výstupní, označené 5^0 a S^i pro i = 1,..., 7. Druhá tabulka říká pro registry proudové šifry, kterými výstupy S-Boxů jsou v každém cyklu výpočtu vytvářeny. Například jednobitový registr p je tvořen výstupem 1 registru 7. Ctyřbitový registr Y je tvořen čtveřicí výstupů (£6}oj £5,0, £4,1, £3,1) z^ šestého, pátého, čtvrtého a třetího registru. Vlastní funkce S-Boxů je popsána tabulkou 3.5. V tabulce jsou ve sloupcích jednotlivé S-Boxy. K pětici bitů vstupu na řádku je uvedena dvojice bitů na výstupu S-Boxu. S-Boxy lze kromě tabulky Bakalářská práce Kapitola 3. 34 Vstup SI S2 S3 S4 S5 S6 S7 10000 10 11 10 11 10 00 00 10001 00 01 00 01 00 01 11 10010 01 00 01 10 00 10 10 10011 01 10 10 11 01 11 10 10100 10 10 10 00 11 01 11 10101 11 11 11 10 10 10 00 10110 11 11 11 01 11 10 00 10111 00 00 01 10 10 00 01 11000 11 01 01 01 00 00 11 11001 10 11 01 10 01 01 00 11010 10 10 00 00 11 11 01 11011 00 01 11 01 11 00 11 11100 01 00 11 11 01 10 01 11101 01 00 00 00 00 11 10 11110 00 01 10 00 10 01 10 11111 11 10 00 11 01 11 01 Vstup SI S2 S3 S4 S5 S6 S7 00000 00 11 01 01 10 10 01 00001 11 01 11 00 11 11 00 00010 11 00 00 11 10 00 11 00011 00 11 01 01 00 10 11 00100 10 11 11 10 00 11 00 00101 10 10 00 11 11 00 01 00110 01 00 10 00 01 01 01 00111 01 10 10 11 01 01 10 01000 10 00 10 00 01 10 10 01001 10 00 00 11 00 01 11 01010 00 01 01 10 11 01 01 01011 11 10 10 00 10 10 00 01100 01 10 00 01 11 00 10 01101 01 01 11 10 01 11 11 01110 11 11 11 10 00 11 00 01111 00 01 01 01 10 00 10 Tabulka 3.5: Scrambling - definice S-Boxů posouvacího registru A proudové části Bakalářská práce Kapitola 3. 35 *Si,o = abce + abc + abd + bde -\- ab -\- ae -\- be-\- ce-\- b -\- d «Si,i = a^cd + a6de + abc + a6d + acd + ade + 6cd + bce -\- ab -\- ac -\- bc-\- bd-\- be-\- cd-\- ce-\- de-\- a -\- d-\- e -\- 1 £2,0 = abce + afrde + ade + 6ce + 6de -\-ab-\-ac-\-ce-\-c-\-d-\-l S2,i = a6de + abc + a6d + afre + acd + cde + cd + ce + 6 + d + e + l £3,0 = ce-\-de-\-a-\-b-\-d S 3,1 = a6c(i + acde + afre + ac + a6c + acd + ace + ade + bed + 6de + ede -\-ad-\-bc-\-bd-\-be-\-cd-\-ce-\-a-\-b-\-d-\-e-\-l S4,0 = afred + abde + acde + afre + abe + 6de + ab + ad + ae + bc + 6e + de + c + d + 1 £4,1 = afred + abde + acde + abc + afre + 6cd + ede + ad + a6 + ae + de + a + 6 + c + e + l £5,0 = afrde + acde + acd + afre + abd + ace + 6ce + ede + a6 + ac + ae + 6d + be + ce + de + c £5,1 = afred + afree + acde + abd + afre + acd + 6cd + 6ce + bde + ede + ac + ad + ae + be + cd + ce + de + 6 + d + e + 1 ^6,0 = afred + abde + acde + acd + ade + 6cd + ede -\- bc-\- bd-\- cd-\- c-\- e Sß,i = ßfre + ade + free + bde -\-bc-\- ce-\- a-\- d £7,0 = afrde + abd + ede + 6c + cd + de + a + 6 + c + e £7,1 = abed + abdebc + acde + acd + ade + 6de + ac + ae + de + 6 + c + d + e Tabulka 3.6: Algebraická definice funkce S-Boxů FSRA popsat též algebraicky. V tabulce 3.6 je každý výstup popsán jako funkce Si j (a, 6, c, --------------v iDity i-------- í FSRA J-------H Z / \ lbit I í FSRA j-------H Q add mod 2~4 4bity 4 bity 4 bity 4 bity C 4 bity f )4— Bout W—f FSRB ) T lbit T outl J ŕ out2 J Obrázek 3.6: Scrambling - combiner proudové části Nakonec výstupní hodnoty out\ a out2 dostaneme jako: outi = d3 © d2 out2 = d\ © do? kde D = (d0, • • •, ds) a £>(z + l) = S(z)0Bouť(z)eZ(z). 3.2 Descrambling Vstupem pro descrambling (obrázek 3.7) je klíč K (1) an bytů scramblova-ných dat (2). První blok Co (8 bytů) descramblovaných dat je inicializační hodnota pro proudovou šifru a na vstup blokového dešifrování jde nezměněna. Proudovou šifrou se vygeneruje heslo P1?..., Pn (3) a tímto se xorují (4) zbylá scram-blovaná data Ci,..., Cn. Zašifrování proběhlo cestou C{ = P{ © B{ a proto platí B i = Pí® C{. To znamená, že v případě proudové šifry s následným xorováním jsou funkce šifrování a dešifrování identické. Blokové dešifrování (5) může nyní probíhat na rozdíl od šifrování v libovolném pořadí, neboť v CBC módu nepotřebujeme mezivýsledky pro řetězení blokové šifry. Reziduum v tomto případě zůstává nezměněno. Každý blok Bi se nejprve dešifruje a poté se xoruje s předchozím blokem B{-\. Totiž při šifrování platilo Bi = EB(K,Mi®Bi-1), Bakalářská práce Kapitola 3. 38 (d S (5) e e- GD e- © e« 3 byte <8 byte *e L+e ■>© Q Cn (2) Pn (3) (4) Qj^-------^ IV=(0,...Q) ^ Obrázek 3.7: Descrambling Bakalářská práce Kapitola 3. 39 nyní tedy MíQBí-^DbÍKiBí) podle definice šifrovací funkce a Mi = DB{K,Bi)@Bi-1 podle pravidel počítání s xor. Dešifrovaný Bn_\ se xoruje s inicializační hodnotou (0,..., 0), tedy již se nemění (Bn_i © (0,..., 0) = Bn_i). Nakonec zbývá popsat blokové dešifrování, tj. úkolem je odvodit funkci DB : (B0,..., Bn_±, R) h- (M0,..., Mn_±, R) inverzní k funkci EB shrnuté přehledně na straně 30, zejména pak nalezení inverze (/?_1 k jednomu cyklu (p šifry. R = R Bn = (0,...,0) M% = ), kde rar7 již známe. Tímto je descrabmling úplně popsán. 3.3 Důkaz korektnosti CSA Je třeba dokázat, že D(K,(E(K,M)) = M, kde E označuje scrambling, D descrambling, K control word a M = (M0,..., M7 je původní zpráva. Označíme-li dále blokové šifrování EB, dešifrování DB a proudovou šifru Ep resp. Dp, dokazujeme DB(K, DP(K, EP(K, EB(K, M)))) = M. Bakalářská práce Kapitola 3. 40 Z vlastností operace © plyne DP(K, EP(K, EB(K, M))) = EB(K, M) (korektnost proudového zašifrování) a vztah se zjednoduší na DB(K,EB(K,M))) = M. Zbývá dokázat korektnost blokové části šifry. Vztah pro zašifrování bloků je Bi = EB(K,Mi®Bi+1) pro z = l,...,rc-l, Bn = (0,..., 0), pro dešifrování Mi = DB(K,Bi)®Bi+1 pro z = l,...,rc-l a tudíž dokazujeme pro každý blok Mi®Bi+1 = DB(K,EB(K,Mi®Bi+1)) pro z = l,...,rc-l, označíme-li Pí = M^ © ß^+i, pak Pi = DB(K,EB(K,Pi)) pro z = l,...,n-l. Platí (viz strany 30 a 39) Pi = 0, který naopak není zašifrován proudovou šifrou. 3.4.1 Proudová šifra Výstup proudové šifry je funkcí stavu registrů a ten je dán celkem 103 bity (A - 40, B - 40, E - 4, F - 4, c - 1, Y - 4, X - 4 Z - 4, p - 1, q - 1), počítáme jen ty registry, jejichž obsah ovlivňují další průběh výpočtu. To znamená, že počet všech stavů šifry, a tím i její perioda je shora omezen číslem 2103. Hledáním algebraických vztahů mezi registry se počet stavů dramaticky sníží. Označme periodu proudové šifry 1. Pozorováním ihned zjistíme, že pro různé páry (klíč,nonce) je l obecně různé. Danému l však odpovídá více dvojic (klíč,nonce). Pro hledání period pro konkrétní dvojice (klíč,nonce) lze použít Floydův algoritmus na hledání délky cyklu. [Wiki-FA] Dále si můžeme všimnout periody registru A - označme jej l&. Zjistíme, že pokud mají různé dvojice (klíč,nonce) stejná /, potom mají stejná Ia a Bakalářská práce Kapitola 3. 42 dokonce celý registr FSRA se chová identicky, tj. prochází stejnými stavy. To znamená, že pro zjištění period stačí zabývat se pouze množinou stavů, kterou může procházet registr FSRA. Provedeme-li dostatečný počet pozorování s různými náhodnými dvojicemi (klíč,nonce) zjistíme, že drtivá většina (v pokuse [WW-04] to bylo 98,4%) dvojic má jako periodu jedno z čísel z malé skupiny. Předpokládejme nyní, že máme k dispozici kryptografický modul provádějící proudovou část šifry CSA a chceme najít klíč, kterým zašifrovává1. Ten se nachází v registrech A a B. Zašifrováním zprávy složené ze samých nul získáme pseudonáhodnou posloupnost. Zjistíme periodu generované pseudo-náhodné posloupnosti a k ní najdeme příslušnou periodu registru FSRA. Pokračujeme zkoumáním možných stavů FSRA s danou délkou. Těch je již podstatně méně než všech možných klíčů. Navíc můžeme pro každý takový stav zjistit, zda je přípustný a tím množinu ještě více omezit. Stav F SRB je plně závislý na stavu FSRA a jeho zpětnovazební funkce je lineární. Z toho vyplývá, že můžeme pro každý uvažovaný stav FSRA vyjádřit stav F SRB soustavou lineárních rovnic a řešit Gaussovou eliminací. Tedy pro každý stav A máme i stav B. Můžeme proto nyní pro každý přípustný stav FSRA generovat pseudonáhodnou posloupnost. Přitom použijeme nonce, které bylo předtím vloženo do kryptografického modulu. Jestliže najdeme shodu s výstupem kryptografického modulu, z A a B odečteme klíč. Popsaný útok je již v silách běžné výpočetní techniky. 3.4.2 Bloková šifra Expanze klíče je nelineární, což vyřazuje lineární kryptoanalýzu. Taktéž ostatní klasické metody se ukazují jako neúčinné. K. Wirt však popsal v [Wirt-04] chosen ciphertext útok na blokovou šifru v situaci, kdyby se provedlo postranním kanálem (například laserovým působením) několik konkrétních změn v kryptografickém modulu pro blokové dešifrování. Za předpokladu, že by se podařilo do dešifrovacího modulu vnést náhodnou chybu do několika posledních kroků tp^1 i = 7,..., 0, lze odvodit posledních osm byte fc384,..., /C447, tedy K±$,..., K^ expandovaného klíče a z něj rekonstruovat samotný control word K. Označme nyní P výsledek blokového dešifrování. Nechť &i = \&i > - - - > &i )-> l = 55,..., 0 xTj. provádíme chosen ciphertext attack, avšak u proudové šifry s xorováním je to totéž jako chosen plaintext attack. Bakalářská práce Kapitola 3. 43 je výsledek z-tého kola tohoto blokového dešifrování, potom P = (P°,..., P7) = $o = ^^(Si) je poslední výsledek. Předpokládejme, že útočník vnese před prováděním posledního kola (po náhodnou chybu do sedmého byte registru, tedy náhodně změní Sf na Sľ a ta se dostane na vstup (/?0- K dispozici pak má původní správný výstup P = (P°,..., P7) a modifikovaný P° = (P°,..., P7) (oba 8 byte). Podle definice funkce p~l (na straně 39) platí: q7 __ q6 __ p7 kJr\ — (Ji — 1 O q — Oi — 1 Zavedeme funkci g jednobytového bloku expandovaného klíče takto: g(kfm)..., kf47) = g(K55) = r(Sf 0 K66) 0 r(Š? © K66) -