Bankovní institut vysoká škola Praha Katedra informatiky a kvantitativních metod
Nejpoužívanější kryptografické algoritmy Diplomová práce
Autor:
Bc. Pavel Vojtěch Informační technologie a management
Vedoucí práce:
Praha
Ing. Vladimír Beneš, Ph.D.
Březen, 2014
Prohlášení Prohlašuji, že jsem diplomovou práci zpracoval samostatně a v seznamu uvedl veškerou použitou literaturu. Svým podpisem stvrzuji, že odevzdaná elektronická podoba práce je identická s její tištěnou verzí a jsem seznámen se skutečností, že se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze elektronických vysokoškolských prací.
V Praze dne 14. 4. 2014
Bc. Pavel Vojtěch
Poděkování Chtěl bych velice poděkovat svým rodičům za podporu. Především za to, že mě oba po celou dobu studia psychicky a finančně podporovali. Dále bych chtěl poděkovat svému vedoucímu diplomové práce panu Ing. Vladimíru Benešovi, Ph.D. za velmi cenné rady a čas, který mi věnoval při osobních a emailových konzultacích. Na závěr bych chtěl poděkovat své přítelkyni za to, že se mnou měla trpělivost během dlouhé doby zpracovávání diplomové práce.
Anotace Diplomová
práce
se
v teoretické
rovině
zaobírá
nejpoužívanějšími
symetrickými
a asymetrickými kryptografickými algoritmy. Charakterizuje je a rozebírá jejich klady, zápory, implementační omezení a studuje kryptoanalytické útoky. Práce se zaměřuje na proudovou šifru RC4, blokovou šifru AES a asymetrickou šifru RSA. V praktické rovině byl navržen a realizován programový kód v jazyce C++ na prolomení šifry RC4 hrubou silou. Z naměřených hodnot byla zpracována statistická studie potvrzující časovou závislost prolomení šifry s ohledem na délku šifrovacího klíče. Klíčová slova Symetrická kryptografie, proudové šifry, RC4, blokové šifry, AES, asymetrická kryptografie, RSA. Abstract Thesis deals with most widely used symmetric and asymmetric cryptographic algorithms. They are characterized and analyzed their pros and cons, implementation constraints and studying cryptanalytic attacks. The thesis focuses on the stream cipher RC4, block cipher AES and asymmetric cipher RSA. In practical terms, has been designed and implemented a program code in C + + to break the cipher RC4 brute force. The measured values were processed by statistical studies confirming the time dependence of breaking ciphers with regard to the length of the encryption key. Keywords Symmetric cryptography, stream ciphers, RC4, block ciphers, AES, asymmetric cryptography, RSA.
Obsah Obsah .................................................................................................................................... 5 Úvod ...................................................................................................................................... 7 Zvolené metody zpracování ................................................................................................ 9 1
Terminologie kryptografie ........................................................................................ 10 1.1 Pojmy kryptografie, kryptoanalýza a kryptologie .................................................... 10 1.2 Definice kryptografie................................................................................................ 11 1.3 Šifra a klíč................................................................................................................. 11 1.4 Cíle kryptografie ....................................................................................................... 11 1.4.1
Integrita dat ......................................................................................................... 12
1.4.2
Autentizace entit a dat ........................................................................................ 12
1.4.3
Autorizace........................................................................................................... 12
1.4.4
Důvěrnost dat...................................................................................................... 12
1.4.5
Nepopiratelnost................................................................................................... 12
1.4.6
Důvěryhodné vyznačení času a monitoring........................................................ 12
1.4.7
Řízení přístupu.................................................................................................... 12
1.5 Základní kryptografická primitiva ............................................................................ 13 1.6 Pojmy transformace, kryptogram, zobrazení, kryptografický algoritmus, kryptografický systém .............................................................................................................................. 14 1.6.1
Definice kryptografického systému .................................................................... 15
1.7 Stupeň zabezpečení kryptografických systémů ........................................................ 15 1.7.1
Nepodmíněná bezpečnost ................................................................................... 15
1.7.2
Dokazatelná bezpečnost ..................................................................................... 16
1.7.3
Výpočetní bezpečnost ......................................................................................... 16
1.8 Kryptoanalytické útoky ............................................................................................ 16 1.8.1
Útok hrubou silou ............................................................................................... 16
1.8.2
MITM útok ......................................................................................................... 17
1.8.3 2
Biclique útok ...................................................................................................... 17
Kryptografické algoritmy ......................................................................................... 19 2.1 Symetrické šifrovací algoritmy ................................................................................ 19 2.1.1
Klady symetrických šifrovacích algoritmů......................................................... 20
2.1.2
Zápory symetrických šifrovacích systémů ......................................................... 20
2.2 Proudové symetrické šifry ........................................................................................ 21 2.2.1
Operace XOR ..................................................................................................... 22
2.2.2
Synchronní proudové šifry ................................................................................. 22
2.2.3
Asynchronní proudové šifry ............................................................................... 23
2.2.4
Klady proudových šifer ...................................................................................... 24
2.2.5
Zápory proudových šifer .................................................................................... 24
2.2.6
RC4 ..................................................................................................................... 25
2.3 Blokové symetrické šifry .......................................................................................... 28 2.3.1
Definice blokové šifry ........................................................................................ 29
2.3.2
Difúze, konfúze a náhodné permutace ............................................................... 30
2.3.3
Módy blokových šifer......................................................................................... 31
2.3.4
DES..................................................................................................................... 35
2.3.5
AES..................................................................................................................... 36
2.4 Asymetrické šifrovací algoritmy .............................................................................. 62 2.4.1
Výhody asymetrických šifrovacích algoritmů .................................................... 64
2.4.2
Nevýhody asymetrických šifrovacích algoritmů ................................................ 65
2.4.3
RSA .................................................................................................................... 65
2.4.4
Algoritmus RSA ................................................................................................. 65
2.4.5
Výhody a nevýhody RSA ................................................................................... 66
2.5 Kryptografie z pohledu svět a ČR ............................................................................ 67 2.5.1
Kryptografie v USA ........................................................................................... 67
2.5.2
Kryptografie v České republice z pohledu legislativy........................................ 67
3
Návrh a realizace programového kódu na prolomení šifry RC4 hrubou silou .. 68 3.1 Návrh programového kódu ....................................................................................... 68 3.2 Realizace a spouštění programového kódu .............................................................. 71 3.2.1
Software využitý při realizaci a spouštění programu ......................................... 71
3.2.2
Hardware využitý při realizaci a spouštění programu ........................................ 71
3.3 Nejdůležitější proměnné, funkce, procedury a další části programového kódu ....... 73 3.3.1
Soubor Prolomeni ............................................................................................... 73
3.3.2
Soubor main........................................................................................................ 74
3.4 Výstupy z programu ................................................................................................. 76 4
Studie vypracovaná na základě výstupních hodnot programového kódu ........... 77 4.1 Výstupní hodnoty z programového kódu na prolomení šifry RC4 hrubou silou ..... 77 4.2 Časová závislost prolomení šifry s ohledem na délku šifrovacího klíče .................. 82
Závěr ................................................................................................................................... 83 Literatura ........................................................................................................................... 86 Seznam zkratek .................................................................................................................. 90 Seznam obrázků................................................................................................................. 92 Seznam tabulek .................................................................................................................. 93 Příloha A............................................................................................................................... 1 Příloha B ............................................................................................................................... 1 Příloha C............................................................................................................................... 1 Příloha D............................................................................................................................... 1 Příloha E ............................................................................................................................... 1 Příloha F ............................................................................................................................... 1 Příloha G .............................................................................................................................. 1
Úvod Diplomová práce „Nejpoužívanější kryptografické algoritmy“ provází čtenáře tajuplným světem šifrovaných zpráv a přináší náhled do moderních kryptografických algoritmů a technologií. V dnešní době nepříliš bezpečného internetu by měl přehled o možnostech šifrování komunikace a citlivých dat patřit k základním znalostem každého uživatele, či zájemce o bezpečný provoz dat a aplikací. Kryptografie prochází v období posledních třiceti let velikým vývojem. Podstatně vzrůstá mohutnost jejího záběru. Neustále vznikají nové symetrické a asymetrické šifry, ale ne všechny kryptografické algoritmy jsou opravdu kvalitní a v praxi neprolomitelné. V uplynulých čtyřiceti letech se zásadně změnili oblasti, ve kterých je kryptografie uplatňována. Kromě klasického užití ve vojenství a diplomacii, kde se uplatňují především utajované kryptografické algoritmy (tzv proprietální šifry). Dochází k využití kryptografie veřejností pro komerční účely, především spojené s příchodem internetové komunikace a elektronického bankovnictví. S příchodem WWW kolem roku 1990 dochází ke změně situace. Výkonnost počítačů dospěla do stádia, kde procesy šifrování a dešifrování již nejsou problémem. Aplikace pro elektronický obchod mají přesně ty vlastnosti, které vyžadují užití kryptografie. Ze své podstaty nemá webová síť centrální řízení bezpečnosti: Každý, kdo chce prostřednictvím webové sítě prodávat jakékoli zboží, potřebuje chránit citlivá data. Mnoho zákazníků by přestalo nakupovat prostřednictvím elektronických obchodů, kdyby riskovaly svoje čísla kreditních karet nebo jiné velice citlivá data. Kryptoanalytik (útočník na kryptografický algoritmus) má při prolamování zašifrovaných dat ztíženou roli, pokud zpočátku ani neví, jaký algoritmus byl pro zašifrování použit. Avšak tento moment utajení použité šifry se při současných aplikacích stává nereálným. Především z důvodu komunikace mezi účastníky v rozsáhlých sítích, je zapotřebí aby byly prostředky zajištující ochranu informace během přenosu unifikovány. Takováto unifikace vedla k vytvoření kryptografických norem.
7
Kryptografických norem je veliké množství, diplomová práce popisuje a hodnotí jednu z nejpoužívanějších norem současnosti FIPS 197, jedná se o blokovou šifru AES. Práce popisuje kryptografický algoritmus AES z hlediska šifrovacích a dešifrovacích operací. Zaměřuje se na její silné a slabé stránky. Studuje nejúspěšnější kryptoanalytické útoky na šifru AES a hodnotí její využití v blízké budoucnosti. Cílem diplomové práce je v neposlední řadě vytvořit programový kód v jazyce C++, který dokáže prolomit v minulosti nejpoužívanější proudovou šifru RC4 hrubou silou. Každý kryptografický algoritmus lze teoreticky prolomit hrubou silou. Vytvořený program umožní prakticky dokázat, že v závislosti na velikosti šifrovacího klíče, dochází k velikému znesnadnění prolomení šifry hrubou silou a že při delším šifrovacím klíči se prolomení šifry hrubou silou ve využitelné době stává prakticky nereálné.
8
Zvolené metody zpracování Výběr metod a technik navázal na dřívější zkušenosti získané během zpracování Bakalářské práce a dalších prací. Volba metod se řídila stanovenými cíli a byla do značné míry podmíněna charakterem studovaných zdrojů. Většina důvěryhodných kryptografických zdrojů, pramenů a literatury je psána v anglickém jazyce. Myšlenkový obsah vědeckých poznatků je původní, citace a odkazy jsou uvedeny v souladu s autorským zákonem. Metoda číslování zdrojů probíhala prostřednictvím Správce pramenů v MS Word, jako norma byla zvolena ISO 690 číselná reference. Obecně se při zpracování Diplomové práce postupovalo od nejznámějšího k méně známému. Autor diplomové práce nejprve prostudoval danou tématiku v českém jazyce (pokud v českém jazyce byla), a když jí porozuměl, našel si zdroj většinou přímo od autora šifry nebo jiného věhlasného kryptoanalytika či kryptografa. Vlastní hodnocení silných, slabých stránek, implementačních omezení a dalších vlastností jednotlivých kryptografických algoritmů je autorem Diplomové práce argumentačně podloženo. Samotnému vývoji programového kódu předcházela analýza problému. Postup vytvoření programového kódu v C++ probíhal od jednoduššího programování ke složitějšímu. Během hledání chyb, testování a ladění programu bylo využíváno krokování. Nejdříve byla vytvořena jednoduchá třída umožňující šifrování a dešifrování algoritmem RC4. Poté byly programovány další funkce včetně samotného prolomení šifry. Programový kód je řádně okomentován v českém jazyce (v některých jiných vývojových prostředích než Visual studio by se mohl objevit problém s diakritikou). Sběr dat z výstupu programového kódu je velice časově náročný, protože prolomení šifry hrubou silou může trvat od desetin vteřiny, po několik dní, až po velice dlouhou dobu (v závislosti na délce šifrovacího klíče). Spuštění programu na delší dobu (několik dní) vyžaduje hardware s dobrým chladícím systémem, aby nedošlo k přehřátí a případnému poškození hardwaru. Práce je ukončena shrnutím dosažených poznatků a uvedením jejich možností využitelnosti v budoucnu. Dosažené výsledky jsou přezkoumané a srozumitelně vyjádřené. Autor potvrzuje tvrzení o dosažení cíle. 9
1 Terminologie kryptografie Kryptografie je věda, která se zabývá konstrukcí matematických metod, sloužících k zajišťování bezpečnosti dat. Základní kryptografické metody se nazývají šifrování a dešifrování. Metody šifrování převádí pomocí kryptografického algoritmu (šifry) otevřený text (zpráva, data) na zašifrovaný text (kryptogram). Naopak metody dešifrování převádí zašifrovaný text zpět na otevřený text. Odborný výraz kryptografie pochází původem z řečtiny, kde „kryptós“ znamená skrytý a „gráphein“ znamená psát. Kryptografické technologie se nachází všude kolem nás a využívají je například: •
desktopy a notebooky na ochranu dat,
•
mobilní telefony,
•
v bankovnictví,
•
platební terminály a systémy platebních karet,
•
satelitní televizní kanály,
•
počítačové sítě
•
virtuální měny,
•
internetové obchodní transakce.
1.1 Pojmy kryptografie, kryptoanalýza a kryptologie Zatím co kryptografie se zabývá návrhem a implementací šifrovacích systémů, tak kryptoanalýza je vědní obor zabývající se metodami získávání obsahu zašifrovaných informací. Kryptografie tvoří spolu s kryptoanalýzou vědní obor nazývající se kryptologie. Můžeme říci, že kryptologie je věda, která se zabývá šifrováním ze všech úhlů pohledu. Velkým rozmach zažívala kryptografie a kryptoanalýza v období druhé světové války. Dříve zatajovaným i opomíjeným vědním oborům věnovaly pozornost vojenské generální štáby. Kryptografie byla obraným štítem, který umožňoval dopravovat zprávy na frontu a do týlu nepřítele. Zatímco kryptoanalýza přinášela informace z nejvyšších míst nepřátelského velení bez jediného výstřelu. (1)
10
1.2 Definice kryptografie Přední světový kryptograf, autor řady publikací a člen Centra Aplikovaného Kryptografického Výzkumu (CACR) Alfred Menezes definuje kryptografii jako: „Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication.“ (2) Definice v překladu znamená, že: „Kryptografie se zabývá studiem matematických metod v souvislosti s aspekty informační bezpečnosti, jako jsou důvěrnost, integrita dat, autentizace subjektu a ověřování původu dat.“ (2)
1.3 Šifra a klíč Výrazem šifra je označován kryptografický algoritmus, který převádí čitelnou zprávu na její nečitelnou podobu. Cílem šifrování je skrýt obsah zprávy před každým, komu tato zpráva není určena. Dešifrování je opačný postup vzhledem k šifrování, je to převedení šifrového textu zpět do podoby otevřeného textu. (2) Výraz klíč značí tajnou informaci, bez níž nelze zašifrovanou zprávu přečíst. Délkou klíče obvykle rozumíme počet bitů jednotlivého klíče, počet bitů je roven logaritmu se základem dva velikosti množiny klíčů. Tajný klíč nebo také šifrovací klíč, je výraz pro klíč používaný v symetrické kryptografii (viz. kapitola 2.1 Symetrické šifrovací algoritmy), je znám zúčastněným stranám, ale nesmí být znám neoprávněným stranám. Sdílený tajný klíč je klíč sdílený více stranami, obvykle bývá výsledkem dohody na klíči. Veřejný klíč je jedním z dvojice klíčů užívané v asymetrické kryptografii (viz. kapitola 2.2 Asymetrické šifrovací algoritmy), obvykle bývá široce dostupný a je využíván k šifrování zpráv, zatímco soukromý klíč je vlastnictvím pouze jedné entity a nesmí být nikomu jinému sdělován a je využíván k dešifrování zpráv. Autentizovaný klíč je vázán cestou autentizace na svého uživatele, například digitálním certifikátem. (3)
1.4 Cíle kryptografie Základním cílem kryptografie je rozvíjet kryptografické algoritmy. Tyto algoritmy se používají ke skrytí obsahu zprávy přede všemi (kromě vysílající a přijímající strany) a k ověření správnosti zprávy přijímající stranou.
11
Kryptografie se ale nezabývá pouze utajením dat, může sloužit také k zajištění následujících cílů:
1.4.1 Integrita dat Kryptografie zajišťuje celistvost dat tak, aby se zamezilo úmyslné nebo neúmyslné změně dat neoprávněným uživatelem. Změna dat může být v podobě smazání, pozměnění, substituce stávajících dat jinými daty. Důležitá je schopnost výše zmíněné modifikace detekovat.
1.4.2 Autentizace entit a dat Autentizace entit znamená identifikaci totožnosti entit, například uživatele, procesu, PC. Autentizace dat znamená prokázání identity dat, například jejich obsah, původ a čas jejich vzniku. Autentizace může probíhat na základě znalosti hesla, binomické informace, vlastnictví například kreditní kary, atd...
1.4.3 Autorizace Autorizace slouží k tomu, aby konkrétní činnosti mohli vykonávat pouze subjekty k této činnosti určené. Také je to potvrzení původu dat a prokázání, že autorem dat je skutečně ten,o němž si myslíme, že autorem je.
1.4.4 Důvěrnost dat Důvěrnost dat znamená bezpečnost zprávy. Jedná se o udržení obsahu zprávy v tajnosti před neoprávněnými uživateli.
1.4.5 Nepopiratelnost Zajišťuje, aby autor nemohl popřít své autorství. Nepopíratelnost může být více typů, například znalosti (subjekt se seznámil s obsahem zprávy), odeslání, přijmu, původu, přenosu, podání (doručovatel zprávu přijal).
1.4.6 Důvěryhodné vyznačení času a monitoring Garantuje, že událost nastala v daný čas a garantuje záznam událostí.
1.4.7 Řízení přístupu Řízení přístupu je proces ověřování subjektů (uživatelů, skupin, počítačů, atd...) pro přístup k objektům pomocí oprávnění a uživatelských práv. (1)(2)(3)
12
1.5 Základní kryptografická kryptografická primitiva Bezpečnostní cíle kryptografie zajišťuje řada kryptografických nástrojů (primitiv), (primitiv), které rozšiřují původně jediný cíl a jediný nástroj. Původním cílem bylo utajení a nástrojem byly šifry. Kryptografická primitiva zobrazuje Obrázek 1.
Obrázek 1 - Kryptografická primitiva Zdroj:: upraveno na základě (2), strana 5
Použití konkrétních konkrétních kryptografických primitiv můžeme můžeme hodnotit podle více kritérií. kritéri Kritéria mohou být z hlediska úrovně bezpečnosti, funkcionality, složitosti implementace, implementace činnosti,, výkonu a cíle, pro které jsou určeny. určeny. Důležitost rozdílných kritérií závi závisí sí na konkrétním typu použité aplikace a dostupných zdrojích. Například, pokud p ud existuje požadavek na zvýšený výpočetní výkon, lze redukovat velmi vysokou úroveň zabezpečení ve prospěch celkového lepšího výkonu systému (například užít místo blokových šifer proudové atd atd...). (1) (2)
13
1.6 Pojmy transformace, kryptogram, zobrazení, kryptografický algoritmus, kryptografický systém Obrázek 2 zobrazuje základní schéma kryptografického systému. Na vysílací straně existují dva informační zdroje, těmi jsou zdroj zprávy M a zdroj klíče K. Zdroj klíče vytváří klíč, který je přenášen hypoteticky nezachytitelnými prostředky, například kurýrem, na přijímací straně. Zdroj zprávy vytváří zprávy, které jsou následně zašifrovány. Zašifrované zprávy jsou označovány jako kryptogram (zašifrovaná zpráva) E.
{1}
Kryptogram je odeslán pomocí možno zachytitelných prostředků, například rádiem. Na konci je kryptogram dešifrován pomocí klíče na původní zprávu. .
{2}
Obrázek 2 - Základní schéma kryptografického systému Zdroj: upraveno na základě (4)
Kryptografická transformace označovaná jako TK je funkce, která definuje zpracování dat
pomocí daného konkrétního klíče. , Transformace TK, jenž je aplikovaná na
zprávu M, vytváří kryptogram E. Kryptogram je text se skrytým údajem. Kryptografické zobrazení je zobrazení, které každému klíči nebo jinému parametru kryptografického systému
přiřadí konkrétní kryptografickou transformaci. Kryptografický algoritmus je souhrn všech kryptografických zobrazení a transformací daného kryptografického systému. (1)(4)
Vzorce {1} a {2} a příslušné komentáře byly inspirovány zdroji (1) a (4).
14
1.6.1 Definice kryptografického systému Kryptografický systém je obecný termín množiny kryptografických primitiv (viz. kapitola 1.5 Základní kryptografická primitiva) používaných k poskytování bezpečnostních informačních služeb. Je to matematická metoda zahrnující celý proces zpracování dat a klíče a všechny jeho okolnosti. (2)
Kryptografický systém lze z matematického hlediska definovat jako pětici (M, C, K, E, D), kde: •
M (Message, zpráva) je konečná množina otevřených zpráv,
•
C (Cipher, šifra) je konečná množina zašifrovaných zpráv,
•
K (Key, klíč) je konečná množina klíčů,
•
E (Encryption, šifrování), D (Decryption, dešifrování) je dvojice zobrazení.
E a D každému klíči k ∈ K přiřazují transformaci pro zašifrování zpráv Ek a transformaci
pro dešifrování zpráv Dk.
pro každé k∈ K a m ∈ M platí .
Šifrovací funkce Ek: M → C: m → c, dešifrovací funkce Dk: C → M: c → m, přičemž
(1)
1.7 Stupeň zabezpečení kryptografických systémů Na šifry je kladen požadavek, aby na základě jakéhokoliv útoku nemohl útočník získat zprávu (otevřený text), kterou přenášejí. Typů kryptoanalytických útoků přibývá a požadavky na ochranu dat se stále zvyšují. Nejspolehlivější míra bezpečnosti je založena na informačním a teoretickém přístupu. Stupeň zabezpečení kryptografických systému můžeme klasifikovat třemi odlišnými způsoby, těmi jsou:
1.7.1 Nepodmíněná bezpečnost Nepodmíněné bezpečnosti se někdy také říká absolutní bezpečnost. Otevřený text nelze nikdy jednoznačně určit bez ohledu na zachycení jakéhokoliv množství informace. Kryptografický systém zůstává bezpečný, i když útočník má k dispozici neomezené materiální prostředky k dešifrování,
ale
nemá
k jeho
dešifrování
dostatek
kryptografických systémů není absolutně bezpečná. (1)
15
informací.
Naprostá
většina
1.7.2 Dokazatelná bezpečnost Prolomení dokazatelně bezpečného kryptografického systému vyžaduje vyřešení velice těžkého výpočetního problému. Kryptografický systém je dokazatelně bezpečný, je-li jeho složitost velmi vysoká, například faktorizace nebo diskrétní logaritmus. (1)
1.7.3 Výpočetní bezpečnost Výpočetně bezpečný kryptografický systém nelze prolomit systematickou analýzou s použitím dostupných zdrojů nebo v rozumné době. Jeho prolomení s použitím nejefektivnějších útoků je natolik složité, že převyšuje zdroje a výpočetní možnosti útočníka. Za výpočetně bezpečné systémy pro vojenské užití se považují kryptografické systémy s výpočetní složitostí minimálně 2256. Pro komerční účely se nachází výpočetní složitost v rozmezí 280 až 2256. (1)
1.8 Kryptoanalytické útoky Typů útoků je v kryptologii nepřeberné množství1, jedná se o metody získávání obsahu šifrovaných zpráv nebo šifrovacích klíčů. Následující podkapitoly zmiňují útok hrubou silou, MITM útok a Biclique útok. Kapitola 2.3.5.9 Studie kryptoanalytických útoků na AES dále nastiňuje Square (Čtvercový) útok a Impossible Differential (Nemožný diferenciál) útok.
1.8.1 Útok hrubou silou Útok hrubou silou může být teoreticky použit proti jakémukoliv šifrovacímu algoritmu. Je založen na systematickém prohledávání všech možných šifrovacích klíčů nebo hesel (jedná se o variace s opakováním), dokud nebude nalezen ten správný. Po nalezení správného šifrovacího klíče může kryptoanalytik snadno dešifrovat jakýkoli šifrovací text zašifrovaný tímto klíčem. V nejhorším případě vyžaduje útok prohledání celého vyhledávacího prostoru. Praktickou proveditelnost útoku hrubou silou určuje délka klíče daného kryptografického algoritmu. Delší šifrovací klíče je exponenciálně těžší prolomit, než ty kratší. Kryptografický algoritmus s délkou klíče n bitů může být prolomen v nejhorším případě ve složitosti 2n a průměrná doba prolomení šifrovacího klíče je poloviční. (5)
1
seznam útoků zde: http://www.pocitacovysvet.ic.cz/Pocitacovy%20utok/kryptograficky.utok.menu.html
16
Například útok hrubou silou na 128 bitovou šifru (například AES-128 ) by vyžadoval maximálně 2128 = 3,4028236692093846346337460743177e+38 operací prohledávání, což je při současných technologiích v praktické rovině neproveditelný úkol.
1.8.2 MITM útok MITM (Meet-in-the-middle) útok byl poprvé aplikován na blokovou šifru (viz. kapitola 2.3 Blokové šifry) s názvem „Diffie and Helmann“. Základní idea útoku spočívá v tom, že bloková šifra Ek může být viděna jako kaskáda, složená ze dvou „podšifer“: ∘
{3}
Pro pár otevřeného textu a šifrovaného textu (P, C) kryptoanalytik odhaduje šifrové klíče K1, K2 a kontroluje, zda:
{4}
Pokud podmínka platí, tak útočník může mít správný klíč, jinak musí být hádaný klíč špatný. MITM útok bude pomalejší než útok hrubou silou, pokud sjednocení K1 a K2 je větší než K: ( ∪
{5}
Nicméně útočník může použít TMTO (Time-memory-trade-off) techniku pro předem vypočítanou hodnotu v rámci každého K1 a uloží je do hašovací tabulky. Potom hádá
K2 a vypočítává a dívá se do předem vypočítané tabulky. Pro blokovou šifru
s dobrým rozvrhnutím klíčů (key schedule) je počet rund, které mohou být prolomeny stále omezen. Další informace o MITM obsahuje kapitola 2.3.5.9 Studie kryptoanalytických útoků na AES. (6) Vzorce {3}, {4}, {5} a příslušné komentáře byly inspirovány zdrojem (6).
1.8.3 Biclique útok
Nechť je pod šifra, která mapuje vnitřní stav S šifrovaného textu C: .
spojuje 2d vnitřních stavů {Sj} na 2d šifrovacího textu {Ci} s 22d šifrovacího klíče {K[i,j]}: 0,0! 0,1! ⋯ ⋮ ⋱ 2% & 1,0! 2% & 1,1! ⋯
0, 2% & 1! ) ⋮ 2% & 1, 2% & 1!
{6}
Trojice {Sj}, {Ci} a {K[i,j]} je nazývána d-dimenzionální biclique pokud: * *,+! + pro všechna ,, - ∈ .0, … , 2% & 10. 17
{7}
Jinými slovy v biclique útoku mapuje klíč K[i,j] vnitřní stav pole Si na šifrovaný text Cj a naopak (viz. obrázek 3). (7) Vzorce {6}, {7} a příslušné komentáře byly inspirovány zdrojem (7).
. Obrázek 3 - d-dimenzionální biclique Zdroj: (7), strana 5
1.8.3.1 Postup Biclique kryptoanalýzy Ještě před zahájením samotného postupu je třeba příprava. Podle mohutnosti klíče 22d rozdělí útočník oddíly klíčového prostoru do skupin. Pro každé d považuje blokovou šifru jako složení dvou pod šifer 1 ∘ 2, kde vyplývá z 2. Šifrovací klíč je ve skupině indexován
jako součást 2% 3 2% matice K[i,j] (která je uvedená výše).
1. Pro každou skupinu šifrovacích klíčů vytvoří útočník strukturu 2d šifrovacího textu Ci a 2d vnitřních stavů Sj vzhledem ke skupině klíčů {K[i,j]} tak, aby dílčí dešifrování Ci klíčem K[i,j] přinášelo Sj. Jinými slovy struktura splňuje následující podmínku: *,+!
∀,, -: + 6778 + , pro š,=> .
{8}
2. Útočník dešifruje šifrový text Ci tajným klíčem K a obdrží 2d čistého textu Pi. * 68 * @
{9}
3. Jestliže je jeden z testovaných klíčů K[i,j] tajný klíč K, potom vnitřní stav Sj mapuje čistý text Pi. Následně útočník zkontroluje, zda: *,+!
∃,, -: * 6778 + , pro š,=> 2.
{10}
Platný pár navrhuje K[i,j] jako kandidáta na šifrovací klíč. (7) Vzorce {8}, {9}, {10} a příslušné komentáře byly inspirovány zdrojem (7). Další informace o Biclique útoku obsahuje kapitola 2.3.5.9 Studie kryptoanalytických útoků na AES. Nejnovější Biclique útoky jsou schopné teoreticky zaútočit na plný počet rund kryptografického algoritmu AES (viz. kapitola 2.3.5 AES) za cenu použití úplné smyčky na všech bitech klíče.
18
2 Kryptografické algoritmy V dnešní době neustálého nebezpečí a také hrozby teroristických útoků dochází často k rozepřím mezi dvěma stranami. Na jedné straně stojí zástupci ochrany soukromí, na druhé pak zastánci toho názoru, že by se člověk měl vzdát části svého tajemství ve prospěch celkové bezpečnosti. Existují snahy o omezování poskytování kryptografie z obavy jejího zneužití zločinci a teroristy a naopak je silná snaha veřejnosti o uvolňování kryptografie z důvodu ochrany osobního soukromí. Spojení kryptografie a státní moci vyvolává časté diskuze a obchodní bariéry ve vývozu aktuálních a kvalitních šifrovacích technologií.
2.1 Symetrické šifrovací algoritmy transformací Ek a dešifrovacích transformací Dk , kde pro každé k ∈ K (prostor tajných klíčů)
Symetrický šifrovací algoritmus je takový algoritmus, který obsahuje množiny šifrovacích
lze z transformace zašifrování Ek určit transformaci dešifrování Dk a naopak. Díky této
symetrii se algoritmy nazývají symetrické. (8) Symetrický kryptografický systém lze popsat matematickou rovnicí (popis proměnných viz. kapitola 1.6.1 Definice kryptografického systému):
{11}
Symetrické šifrovací algoritmy využívají pro šifrování a dešifrování tentýž tajný klíč. Všechny klíče musí zůstat skryty, aby bylo zajištěno, že neoprávněné strany nemůžou použít tajný klíč k dešifrování tajných zpráv. Tudíž si musí odesílatel a příjemce mezi sebou vyměnit klíč nějakým zabezpečeným kanálem (viz. systém přenosu tajných klíčů na obrázku 3). Tajný klíč by měl být náhodný a měl by být často měněn. Délky klíčů jsou různé, v závislosti na použitém kryptografickém algoritmu. Čím delší je tajný klíč, tím bývá obvykle větší zabezpečení před prolomením. (3) Symetrické šifrovací algoritmy se dále dělí na proudové šifry (popsané v kapitole 2.2) a blokové šifry (popsané v kapitole 2.3). Základní schéma symetrického šifrovacího systému znázorňuje obrázek 4. Vzorec {11} a příslušné komentáře byly inspirovány zdrojem (8). 19
Obrázek 4 - Základní schéma symetrického šifrovacího systému Zdroj: vytvořeno na základě (8)
2.1.1 Klady symetrických šifrovacích algoritmů Poskytují autentizaci, dokud zůstane šifrový klíč utajen. Umožňují šifrování a dešifrování se stejným šifrovým klíčem. Hlavní výhodou symetrického šifrování je, že je obecně velmi rychlé a dá se použít pro šifrování velkého objemu dat. Uživatel, který šifru zašifroval, může tuto šifru i dešifrovat (na rozdíl od asymetrických šifrovacích systémů). V případě, že chceme zašifrovat vlastní data, je nejlepší užít symetrické šifry, protože není třeba vytvářet veřejný a soukromí klíč jako v případě asymetrických šifer. Symetrické šifry mají menší nároky na systémové prostředky (hardware), než asymetrické šifry.
2.1.2 Zápory symetrických šifrovacích systémů Veliká nevýhoda symetrických šifrovacích algoritmů spočívá vtom, že odesílatel musí nějakým způsobem distribuovat tajný klíč příjemci. Odesílatel musí zaručit, že tajný klíč nebude zachycen neautorizovanou osobou. Problém se ještě zvyšuje v systémech s velkým počtem uživatelů. Přenosem, generováním, zálohováním a destrukcí klíčů (jakmile klíč jednou splní svoji funkci, měl by být zničen, aby nemohl mít žádnou cenu pro narušitele) se zabývá takzvané klíčové hospodářství. (3)
20
Pokud dojde k odhalení nebo odcizení tajného šifrového klíče, narušitel může data okamžitě dešifrovat a může produkovat falešné zprávy, které vydává za odesílatele. Částečným řešením může být častá změna šifrového klíče, ale tato metoda nemusí ve většině situací fungovat. Bezpečná distribuce (přenos) klíčů bývá často problémem, zvláště v případě dochází-li ke změně klíče příliš často. Klíče musí být přenášeny velice obezřetně, protože umožňují přístup ke všem datům zašifrovaných těmito klíči. Pro aplikace probíhající po internetové síti může být toto velmi složitý úkol. •
Jedním z řešení tohoto problému může být distribuovat šifrové klíče osobně („tváří v tvář“), ale tento způsob není efektivní, zvláště ve větších skupinách.
•
Dalším z řešení může být využití kurýrních služeb.
•
V neposlední řadě může být distribuce šifrového klíče rozdělena na více přenosů, tím že bude klíč přenášen po částech. Například jedna část bude odeslána e-mailem a druhá část bude odeslána hlasovou zprávou, ale i tento způsob může být náchylný na útoky.
V případě, že by distribuce klíče probíhala prostřednictvím symetrické kryptografie v PC síti a tato síť měla n navzájem propojených uživatelů, bylo by třeba užít
B ∙ B D
různých
šifrových klíčů, které by si uživatelé mezi sebou vyměňovali. Pokud by se například n = 500, bylo by nutno uchovávat v systému 125 000 různých šifrových klíčů. Vzhledem k obnově klíčů za nové by tato situace představovala prakticky špatně realizovanou situaci. Proto je výhodnější užívat pro distribuci klíčů asymetrické kryptografické algoritmy (viz. kapitola 2.4 Asymetrické šifrovací algoritmy). (9) Symetrické šifrové klíče bývají předmětem útoků hrubou silou, kdy jsou systematicky prohledány všechny klíče v klíčovém prostoru. Řešením může být například využití asymetrického šifrování nebo hybridních šifer.
2.2 Proudové symetrické šifry Proudové šifry jsou důležitou kategorií šifrovacích algoritmů, zpracovávají vstupní otevřený text po znacích. Zpracování probíhá bit po bitu nebo bajt po bajtu v jednom časovém momentu, kde je vstupní otevřený text kombinován většinou pomocí funkce XOR s pseudonáhodným proudem bitů vytvořeným pomocí tajného klíče a šifrovacího algoritmu. (2) 21
Základní popis proudových šifer: •
Otevřený text je zpracováván bajt po bajtu P1, P2, P3, ..., Pn.
•
Klíč K je využíván pro generování sekvence pseudonáhodného proudu bajtů K1, K2, K3, ..., Kn.
• •
Šifrový text je C1, C2, C3, ..., Cn, kde * PF ⊕ K F .
Díky symetrii můžeme získat otevřený text PF * ⊕ K F .
Variace proudových šifer se liší především způsobem, jakým je generován pseudonáhodný proud znaků. (2) Mezi proudové šifry patří například RC4, A5, SEAL, E0, VEST, FISH, CryptMT, ISAAC.
2.2.1 Operace XOR Název operace XOR pochází z anglického eXclusive OR, tedy „výlučně nebo“. Pravdivostní tabulku XOR zobrazuje tabulka 1.
y a XOR b a ⊕ b a 0 0 1 1
b 0 1 0 1
{12}
y 0 1 1 0
Tabulka 1 - Pravdivostní tabulka XOR Zdroj: Autor Diplomové práce
2.2.2 Synchronní proudové šifry Synchronní proudová šifra je taková šifra, kde je proud pseudonáhodných čísel nezávisle generován na otevřeném nebo šifrovém textu. K šifrování dochází během kombinace pseudonáhodného proudu a čistého textu (zprávy). Příjemce a odesílatel musí být přesně synchronizováni, protože výpadek jednoho znaku šifrového textu při dešifrování naruší veškerý následující otevřený text, který může být obnoven prostřednictvím technik pro re-synchronizaci. Bezpečné použití synchronní proudové šifry vyžaduje, aby nikdy nebyl použit stejný šifrovací klíč dvakrát. (8)
22
Proces šifrování synchronní proudové šifry lze popsat následujícími rovnicemi rovnicemi: {13}} {14}} {15}} Kde: •
je počáteční stav, stav, který je stanoven klíčem klíče k,
•
f je další stav funkce,
•
g je funkce, která vytváří pseudonáhodný proud
•
h je výstupní funkce, která kombinuje pseudonáhodný proud a čistý text
, , produkuje
šifrový text . Šifrovací a dešifrovací procesy synchronní proudové proudové šifry znázorňuje obrázek 55.
Obrázek 5 - Procesy šifrování a dešifrování synchronní synchro ní proudové šifry Zdroj: upraveno na základě (2) strana 193
Vzorce {13},, {14}, {15} a příslušné komentáře byly inspirovány zdrojem (2).
2.2.3 Asynchronní proudové šifry Asynchronní proudové šifry se také nazývají samo-synchronizující samo synchronizující se šifry šifry,, protože u nich dochází v krátké době k synchronizaci a správné dešifraci otevřeného textu. Proud pseudonáhodných znaků je generován pomocí klíče k a n předcházejících znaků šifrového textu Proces šifrování asynchronní proudové šifry lze popsat následující rovnicí: textu. , kde: •
h je výstupní funkce,
•
f je další stav funkce,
•
k je šifrový klíč,
•
c je šifrový text. 23
{16}
Výpadek některého znaku šifrového textu se projeví celkem na n sousledných znacích otevřeného textu, ale další otevřené znaky budou již správně dešifrovány. Z výše uvedeného vzorce vyplývá, že k synchronizaci dojde hned, jakmile se přijme souvislá posloupnost n+1 správných znaků šifrového textu. Šifrovací a dešifrovací procesy asynchronní proudové šifry znázorňuje obrázek 6. (8)
Obrázek 6 - Procesy šifrování a dešifrování asynchronní proudové šifry Zdroj: http://access.feld.cvut.cz/storage/200908101111_fig5.gif
Vzorec {16} a příslušné komentáře byly inspirovány zdrojem (8).
2.2.4 Klady proudových šifer Proudové šifry jsou stále v praxi používány a jsou stále aktuálním tématem problematiky ochrany dat. Jejich klady spočívají především v malém času potřebném pro zpracování, v rychlosti a relativní jednoduchosti hardwarové implementace. Využití proudových šifer je nejlepší tam, kde je množství dat kontinuální (souvislé), například v počítačových sítích. Výhoda proudových šifer oproti blokovým šifrám je v malé propagaci chyby. Vzniklá chyba na komunikačním kanálu v jednom znaku šifrového textu se projeví u proudových šifer pouze v jednom odpovídajícím znaku otevřeného textu, u blokové šifry má tato chyba vliv na celý blok znaků.
2.2.5 Zápory proudových šifer Proudové šifry jsou náchylnější k útoku než blokové šifry. Bezpečné použití synchronní proudové šifry vyžaduje, aby nikdy nebyl použit stejný šifrovací klíč dvakrát. Je možné dešifrovat libovolný bajt, který je třeba uprostřed zprávy. Na proudové šifry lze obecně lépe útočit než na blokové šifry, stačí změnit jediný bajt, pokud známe formát zprávy. Proudové šifry neposkytují ochranu datové integrity nebo autentizace, zatímco blokové šifry ano (záleží na módu, viz. kapitola 2.2.3 Módy blokových šifer). 24
2.2.6 RC4 RC4 je jednoduchá, rychlá, symetrická, proudová, synchronní, silná šifra, která se v minulosti stala jednou z nejpoužívanějších šifer v internetové a komerční kryptografii. Byla vytvořena v roce 1987 americkou společností RSA Security. Na návrhu šifry se podílel Ron Rivest, kterým je jedním ze zakladatelů společnosti RSA (Rivest Shamir Adleman). RC znamená v překladu Riverst Cypher. Šifra RC4 je někdy také označován, jako „Ron Code 4“. (10) Fakta o RC4: •
variabilní délka klíče,
•
proudová šifra orientovaná na šifrování po bajtech,
•
utajovaná do roku 1994,
•
složená převážně ze dvou algoritmů KSA a RPGA,
•
využívána převážně pro webové a bezdrátové komunikace.
2.2.6.1 Rozluštění RC4 RC4 byla rozkryta 9. 7. 1994 anonymním kryptoanalytikem, který zaslal její zdrojový kód v jazyce C (uveden v Příloze A) do elektronické schránky skupiny CypherPunks a odtud se začal volně šířit volně internetem. Získání zdrojového kódu šifry znehodnotilo obchodní tajemství společnosti, ale šifra byla dál chráněna obchodním názvem RC4. Proto vznikly alternativní názvy, jako ARCFOUR nebo ARC4. (11) Předtím, než byl kód šifry RC4 rozkryt a veřejně rozšířen, patřila šifra do skupiny takzvaných proprietárních algoritmů. Na světě existuje velký počet proprietárních šifrovacích algoritmů, o kterých nemáme ani tušení. Jsou to utajované šifry používané například v bankovnictví, ozbrojených silách, v diplomacii atd... Jejich utajení je bezpečnostní opatření, které znesnadňuje jejich prolomení. To byl důvod, proč byla RC4 utajená. Jejím úkolem bylo chránit citlivá data. (11) 2.2.6.2 Využití RC4 Šifra je určena na rychlé šifrování velkého objemu dat. Příklad aplikací, technologií a protokolů, kde se RC4 šifra používala: WEP, WPA, RDP, PDF, SSL, TLS, Oracle SQL, Microsoft Office, Skype, BitTorrent, Kerberos a mnoho dalších. Dnes se již doporučuje šifru neužívat, protože byla mnohokrát prolomena. Například http://rc4.online-domain-tools.com/ umožňuje vyzkoušet šifrování a dešifrování pomocí RC4.
25
2.2.6.3 Popis algoritmu RC4 Základní princip symetrického proudového šifrování popisují kapitoly 2.1.2 a 2.1.2.2. RC4 se skládá převážně ze dvou algoritmů, těmito algoritmy jsou KSA (Key Scheduling Algorithm) a PRGA (Pseudo Random Generation Algorithm). Algoritmus KSA inicializuje permutace pole S. Permutace množiny, která obsahuje n-prvků, je jedno z možných uspořádání těchto prvků, přičemž výsledná uspořádaná n-tice má stejný počet prvků jako původní množina. Klíčový proud je nezávislý na otevřeném textu. Klíč K je složen ze slova volitelné délky, kde každé slovo má n bitů, nejčastěji využívaná hodnota je n = 8, z toho vyplývá, že v algoritmu uvedeném níže se 2n=256. Pracujeme se dvěma čítači i a j, které se inicializují na 0 (i = 0, j = 0). Funkce mod znamená modulo dělení. Pseudokód KSA: for i from 0 to 2n - 1 K[i] = k[i mod l] for i from 0 to 2n - 1 Set S[i] = i Set j = 0 for i from 0 to 2n - 1 Set j = (j + S[i] + K[i]) mod 2n Swap S[i] and S[j] 1. Šifrovací klíč K opakujeme tolikrát za sebou, až naplníme pole K[i] 256 bajty. 2. Zvolíme identickou počáteční permutaci S[i]. 3. Nastavíme čítač j na 0. 4. V každém kroku se vyměňují na pozicích i a j prvky permutace S. Index i je průběžný, zatímco j závisí na klíči. Aby se eliminovalo opakování v posloupnosti K, index j závisí nejen na K, ale na všech průběžných hodnotách j, S a K. Díky tomu je závislost na klíči velmi složitá, náhodná a periodičnost je odstraněna. Algoritmus RPGA následuje po algoritmu KSA a v každém kroku produkuje jeden bajt pseudonáhodného proudu.
26
Pseudokód algoritmu RPGA: Set i = 0 and j = 0 while //dokud je požadován keystream Set i = (i + 1) 1 mod 2n Set j = (j + S[i]) S mod 2n Swap S[i] S and S[j] . K = S[( [(S[i]+S[ [j]) mod 2n] Output K Je prováděno mnoho iterací, generátor generátor upravuje stav a výstupy baj bajtů v pseudonáhodném proudu bajtů.. V každé iteraci generátor k přírůstku i přidává hodnotu S, na kterou ukazuje i a j a vymění hodnoty S[i] a S [j], [ , každý prvek S se tak vymění s jiným prvkem alespoň jednou za 256 iterací. Výsledným bajtem iterace je další slovo pseudonáhodného proudu bajtů (vv překladu keystream) keystream) K. Obrázek 7 zobrazuje smyčku generátoru RPGA graficky. Výstupní pseudonáhodný proud bajtů K tvoří hodnoty S[i] + S[j],, na které se aplikuje modulo dělení 2n ((28=256).
Obrázek 7 - Princip RPGA Zdroj: upload.wikimedia.org/wikipedia/commons/e/e9/RC4.svg
Šifrový text C vznikne aplikováním operace XOR na pseudonáhodný proud K a otevřený text P:
(viz. Kapitola 2.1.2 2. 2 Proudové symetrické šifry). (9) (10) (11)
27
2.2.6.4 Klady RC4 Kladem proudové šifry je především rychlost zpracování, která z ní dělá šifru využitelnou u mnoha komerčních produktů. Proudová šifra RC4 je řádově desetkrát rychlejší než bloková šifra DES. RC4 kóduje jen tolik bytů, kolik jich má otevřený text, tudíž se neprodlužuje délka dat. Je to zajímavá, výjimečná šifra, která je jedna z mála velice rozšířitelných proprietálních šifer, zůstávala 7 let tajná. Vymyká se obecně oblíbenému omylu, že proprietální šifry jsou slabé. (11)(9) 2.2.6.5 Zápory RC4 Některé aplikace využívající proudovou šifru RC4 mohou být napadnutelné kvůli nedostatkům v klíčových nastaveních. Klíč může být teoreticky dlouhý 256 bajtů, ale ve skutečnosti nemůže být využit zcela, klíč poskytuje maximálně 455 bitů (57 bajtů) entropie, to je způsobeno prácí s klíčovým polem. (12) Výsledkem výzkumu vytváření pseudonáhodného proudového klíče bylo zjištění, že některé bity tajného klíče mají větší vliv na několik prvních bytů výsledného proudového klíče než ostatní. Tyto klíče jsou nazývány slabými. Slabých klíčů lze využít při útoku na několik prvních bajtů šifry, proto by první bajty šifrovacího klíče měly být z důvodu bezpečnosti vynechány. Přestože šifra RC4 má slabiny, lze ji využívat s jejich vědomím a drobnými úpravami, je třeba se ujistit, že všechny klíče jsou jedinečné a ideálně nesouvisející, například mohou být klíče generované pomocí hašovací funkce. (12)
2.3 Blokové symetrické šifry Blokové šifry jsou třídou symetrických šifrovacích systémů, které zpracovávají otevřený a šifrový text po blokách pevné délky (64 nebo 128 bitů). Šifry tedy obvykle definují vzájemně jednoznačné zobrazení z množiny 64bitových čísel na množinu 64bitových čísel. Symetrické blokové šifry jsou významnými a důležitými prvky v mnoha kryptografických systémech, využívají se nejen pro zabezpečení důvěrnosti dat šifrováním, ale i pro konstrukci jiných kryptografických prvků (například hašovacích funkcí, MAC, pseudonáhodných generátorů, atd.). Dále mohou sloužit jako ústřední součást metod pro ověřování zpráv, jako části ověřovací (autentizačních) protokolů, mechanizmů datové integrity nebo digitálních podpisových schémat. Mezi blokové šifry patří například DES, AES, FEAL, IDEA, SAFER, RC5,BLOWFISH, KASUMI, LOKI89, XTEA. (2) (3) 28
Blokové šifry využívají principy algoritmů tzv Feistelova typu, který umožňuje postupnými aplikacemi relativně jednoduchých transformací na bázi nelineárních posuvných registrů vytvořit složitý kryptografický algoritmus. Během návrhu blokových šifer je třeba splnit současně několik častokrát protichůdných požadavků. Základní požadavky jsou bezpečnost, výkon a paměťové nároky. Bezpečnost je nedůležitější požadavek, šifrovací systém musí být odolný proti všem známým útokům. Z hlediska výkonu je potřeba, aby šifrování a dešifrování dat bylo na zvolené implementační platformě co nejefektivnější. Odolnost šifrovacího algoritmu můžeme zlepšovat navyšováním vrstev zpracování otevřeného textu, ale na druhou stranu méně transformací otevřeného textu urychlí proces šifrování. Paměťové nároky kryptografického systému by měli být co nejmenší. (13)
2.3.1 Definice blokové šifry
Nechť A je abeceda q symbolů, t ∈ N a M = C je množina všech řetězců délky t znaků nad abecedou A, kde: •
M (Message) je konečná množina otevřených zpráv,
•
C (Cipher) je konečná množina zašifrovaných zpráv,
•
K (Key) je konečná množina klíčů,
•
E (Encryption), D (Decryption) je dvojice zobrazení.
pro každé k ∈ K transformaci zašifrování EK a dešifrování DK.
Bloková šifra je kryptografický systém (M, C, K, E, D), kde E a D jsou zobrazení, definující
Šifrování bloků otevřeného textu m(1), m(2), m(3), ..., m(n), kde m(i) ∈ M pro každé i ∈ N
probíhá podle vztahu:
Dešifrování podle vztahu:
O , , , pro každé i ∈ N
, O , , pro každé i ∈ N.
{17}
{18}
Všechny bloky otevřeného textu jsou šifrovány toutéž transformací EK a všechny bloky šifrového textu jsou dešifrovány toutéž transformací DK. (8) Vzorce {17}, {18} a příslušné komentáře byly inspirovány zdrojem (8).
29
2.3.2 Difúze, konfúze a náhodné permutace Historické šifry se většinou dají luštit přímo ze šifrového textu. Důvod je ten, že šifrový text u nich příliš dobře a přímočaře odráží statistické charakteristiky otevřeného textu. Claude E. Shannon navrhl metody difúzi a konfúzi, které tomu zabraňují. Vlastnosti konfúze a difúze by měly zabránit tomu, aby ze znalosti otevřeného i šifrovacího textu mohl být odvozen použitý šifrovací klíč. Při návrhu šifry je takovýto požadavek velice složitý. (8) 2.3.2.1 Difúze Difúze si klade za cíl rozprostřít statistické charakteristiky otevřeného textu do delších úseků šifrového textu. Jestliže jeden znak otevřeného textu ovlivňuje více znaků šifrového textu, potom se závislosti jazyka mohou projevit až v delších úsecích šifrového textu. Čím větší je difúze otevřeného textu do šifrového textu, tím je obtížnější tyto závislosti zkoumat. Ideálně každý bit otevřeného textu ovlivňuje každý bit šifrového textu. (8) 2.3.2.2 Konfúze Konfúze je metoda, jejímž cílem je učinit vztah mezi statistickými vlastnostmi šifrového textu a klíčem co nejsložitější a zahrnující co největší části šifrového textu a klíče. Konfúze zajišťuje difúzi klíče do šifrového textu tak, aby tato difúze byla složitá. (8) 2.3.2.3 Náhodné permutace Kvalitní n-bitové blokové šifry se jeví jako náhodné permutace na množině n-bitových bloků. Blokové šifry by měly mít takovou vlastnost difúze a konfúze, že bez znalosti tajného šifrovacího klíče by měly být nerozeznatelné od náhodných permutací na množině {0,1}n (Obrázek 8).
Obrázek 8 - Náhodné permutace Zdroj: upraveno na základě (8)
Tato vlastnost způsobuje, že znalost jakékoli dvojice otevřeného a šifrovacího textu nepomáhá k odvození dalších možných šifrových textů pro blízké otevřené texty nebo naopak možných šifrových textů pro blízké otevřené texty. (8) 30
2.3.3 Módy blokových šifer Mody blokových šifer vznikly, protože požadavky na blokové šifry jsou takové, že je potřeba šifrovat nejen celé n-bitové bloky, ale obecně jakoukoliv posloupnost bitů. Blokové šifry se
používají v kryptografických systémech různými způsoby. Tyto způsoby se projeví v případě, že má otevřený text více než jeden blok. Způsobům použití se říká také módy použití blokových šifer, mezi módy patří ECB, CBC, CFB, OFB, CTR a MAC. 2.3.3.1 ECB ECB (Electronic Codebook) je základní mód přímočarého použití blokové šifry. Šifry v tomto módu jsou bezpečné především proto, že jejich tabulka je velmi velká. U moderních šifer s délkou bloku 128 bitů má šifrovací tabulka 2128 položek. Z důvodu této velikosti nelze tabulku celou vypočítat ani uložit. Ukládá se pouze algoritmus výpočtu, nikoli tabulka této transformace. (14) Bloky otevřeného textu jsou šifrovány nezávisle na sobě. Pokud není integrita dat zabezpečena jiným způsobem, může nepřátelský kryptoanalytik některé bloky dat vynechat, vkládat, změnit jejich pořadí, atd. Toto ilustruje často opomíjený fakt, že integrita otevřeného textu se šifrováním nezajistí. Algoritmus ECB módu:
•
Vstupy: k-bitový klíč K; n-bitový otevřený text bloků x1, x2, ..., xt.
•
Shrnutí: produkce bloků šifrovaného textu c1, c2, ..., ct; dešifrování zpátky na čistý text.
• •
Šifrování: 1 P - P Q, O+ ← S+ .
Dešifrování: 1 P - P Q, S+ ← O+ .
(2)
Šifrování v ECB módu zobrazuje následující obrázek 9.
Obrázek 9 - ECB mód n-bitových blokových šifer Zdroj: upraveno na základě (2), strana 229
31
Nevýhodou ECB je, že stejné bloky otevřeného textu mají vždy stejný šifrový obraz. Několik shodných bloků šifrového textu může odkrývat hodnotu otevřeného textu. Mód ECB nezajišťuje integritu otevřeného textu, proto se tímto módem nedoporučuje šifrovat velké objemy dat. (13) 2.3.3.2 CBC CBC (Cipher Block Chaining) mód neobsahuje některé bezpečnostní nedostatky ECB módu. V současnosti je jedním z nejpoužívanějších módů blokových šifer. Jedná se o řetězovou závislost na otevřeném a šifrovém textu. Každý blok otevřeného textu se nejprve modifikuje předchozím blokem šifrového textu, až teprve poté dochází k šifrování. Protože šifrový text je náhodný, stává se také modifikovaný otevřený text náhodným. Správné dešifrování bloku
otevřeného textu vyžaduje správný předchozí blok šifrového textu. (14) CBC mód využívá inicializační vektor IV (n-bitový řetězec). Inicializační vektor IV je generován a přenáší jako první (nultý) blok šifrového textu. Důležité je zabezpečit jeho integritu.(13) Algoritmus CBC módu (obrázek 10): •
Vstupy: k-bitový klíč K; n-bitový inicializační vektor IV; n-bitový otevřený text bloků x1, x2, ..., xt.
•
Shrnutí: produkce bloků šifrovaného textu c1, c2, ..., ct; dešifrování zpátky na čistý text.
• •
Šifrování: OT ← UV, W=X 1 P - P Q, O+ ← O+ ⊕ S+ .
Dešifrování: OT ← UV, W=X 1 P - P Q, S+ ← O+ ⊕ O+ .
Obrázek 10 - CBC mód n-bitových blokových šifer Zdroj: upraveno na základě (2), strana 229
32
(2)
Další vlastností CBC je samo synchronizace (stejný princip jako v kapitole 2.3.4. Asynchronní proudové šifry). Pokud ztráta celého bloku šifrového textu zapříčiní chybné dešifrování následujícího bloku, tak další bloky již jsou dešifrované správně. Záporem z hlediska difúze a zároveň kladem z hlediska samo synchronizace je, že závislost běžného šifrového bloku je pouze na předchozí šifrový blok. (13) 2.3.3.3 CFB Zatím co režim CBC zpracovává otevřený text n-bitů najednou (s použitím n-bitové blokové šifry), některé aplikace vyžadují, aby r-bity otevřeného textu byly šifrovány a předávány bez zpoždění pro některé fixní r < n (nejčastěji r = 1 nebo r = 8). V tomto případě se využívá mód CFB (Cipher Feedback). Algoritmus CFB módu (ilustrovaný na obrázku 11): •
Vstupy: k-bitový klíč K; n-bitový inicializační vektor IV; r-bitový otevřený text bloků x1 ,x2 , x3, ..., xu (1 ≤ r ≤ n).
•
Shrnutí: produkce r-bitových bloků šifrovaného textu c1, c2, ..., cu; dešifrování zpátky na čistý text.
•
Šifrování: U ← UV (Ij je vstupní hodnota posuvného registru), pro 1 P = P Y: 1. OZ ← E\ IZ výpočet výstupu blokové šifry.
2. Q+ ← r-bity nejvíce vlevo Oj (Předpokládáme, že bit nejvíce vlevo je označen jako bit 1).
3. O+ ← S+ ⊕ Q+ (přenos r-bitů šifrového bloku cj).
4. U+D ← 2^ . U+ _ O+ X` 2B (Posun cj na pravý konec posuvného registru).
•
Dešifrování: U ← UV, W=X 1 P - P >, po obdržení cj:
S+ ← O+ ⊕ Q+ , kde tj, Oj a Ij jsou počítány podle výše uvedených bodů.
(2)
Mezi důležité vlastnosti CFB patří samo synchronizace na úrovni bloků (chybný blok zaviní výpadek celého bloku. CFB využívá pouze transformaci EK (transformace DK není vůbec použita). Existuje řetězová závislost na otevřeném a šifrovém textu. Ke správnému dešifrování je nutný předposlední a poslední blok šifrového textu. Mód CFB převádí blokovou šifru na synchronní proudovou šifru. (14)
33
Obrázek 11 - CFB mód n-bitových n bitových blokových šifer Zdroj: upraveno na základě (2), strana 229
2.3.3.4 OFB Módy OFB (Output (Output Feedback) Feedback) a CFB (zmíněný výše) využívají blokové šifry k vygenerování hesla
, které aplikuje operaci XOR (binárně načítá) na otevřený text
(
).
Používají náhodný inicializační vektor IV, který nastavuje odpovídající konečný automatu do náhodné polohy. Konečný automat produkuje posloupnost hesla . První blok hesla se získá zašifrováním vektoru IV.. Konečný automat posílá vzniklé heslo na vstup blokové šifry a jeho zašifrováním je produkován následující blok hesla. (14) Inicializační vektor IV nemusí být tajný, tajný ale musí být změněn, pokud je znovu použít stejný stejný klíč K. K Jinak můžeme dostat identické výsledky pseudonáhodného proudu bitů s aplikování operace XOR na odpovídající vídající šifrový text, může sloužit k zjištění klíče nepřátelským kryptoanalytikem. Algoritmus OFB módu (ilustrovaný na obrázku 12): 12 OFB má vlastnosti synchronní proudové šifry (kapitola 2.2.2), protože heslo je generováno zcela autonomně bez vlivu otevřeného a šifrového textu. Samo-synchronizaci Samo synchronizaci umožňují stejně jako v případě CBC a CFB dva za sebou jdoucí správné bloky šifrového textu. (2) •
Vstupy: y: k-bitový klíč K; K n-bitový bitový inicializační vektor IV; r-bitový bitový otevřený text bloků x1, x2, x3, ..., xu (1 ≤ r ≤ n). n)
•
Shrnutí: hrnutí: produkce r--bitových bloků šifrovaného textu c1, c2, ..., cu; dešifrování zpátky na čistý text. 34
•
Šifrování ifrování:
, 5. 6.
, vzhledem k bloku čistého textu: výpočet výstupu blokové šifry. r-bity bity nejvíce vlevo Oj (Předpokládáme, že bit nejvíce vlevo
je označen jako bit 1). 7. 8. •
Dešifrování ešifrování:
(přenos r-bitů r bitů šifrového bloku cj). (Aktualizace Aktualizace vstupu blokové šifry pro další blok). po obdržení cj:
, kde tj, Oj a Ij jsou počítány, podle výše uvedených bodů. (2)
Obrázek 12 - OFB mód n-bitových bitových blokových šifer Zdroj: upraveno na základě (2), strana 229
2.3.4 DES Během sedmdesátých let došlo k velikému rozvoji elektronických bankovních systémů, exekutiva Spojených států amerických dospěla k závěru, že je třeba zajistit standard pro bezpečný transfer dat. Zatím to účelem byl vytvořen algoritmus DES ((Data Data Encryption Standard a ve Spojených státech amerických byl zvolen za standard FIPS 46-3. Standard) 46 . Tento standard se stal v minulosti nejpoužívanějším nejpoužívanější šifrovacím šifrovacím algoritmem na světě světě. Byl součástí mnoha průmyslových, internetových internetových a bankovních standardů (například ANSI standard X9.32 X9.32).
35
Jedná se o blokovou šifru, kde je otevřený text zpracováván po blokách délky 64 bitů. Algoritmus DES byl v minulosti různě modifikován. Došlo například ke vzniku algoritmu Triple DES, kdy je algoritmus DES aplikován trojnásobně. V současnosti (rok 2014) je již šifra považována za prolomitelnou a nespolehlivou. Roku 2002 nahradil DES kryptografický standard AES. (8) (9)
2.3.5 AES Kryptografický algoritmus AES (Advanced Encryption Standard) schválený standardem FIPS 197 (Federal Information Processing Standards) může být použit pro ochranu elektronický dat. Algoritmus AES je symetrická bloková šifra, která dokáže zpracovat datové bloky o délce 128 bitů a je schopna užívat šifrovací klíče délky 128, 192 a 256 bitů. Prognóza je taková, že 128 bitů zaručuje utajení minimálně na několik desítek let dopředu. (15) Norma FIPS PUB 197 může být přijata a používána nevládními organizacemi a její použití se v současnosti (rok 2014) doporučuje při poskytování požadované bezpečnostní jistoty pro komerční a soukromé organizace. Algoritmus AES uveden ve zmíněné normě muže být implementován v softwaru, firmwaru, hardwaru nebo v jakékoli jejich kombinaci. Konkrétní implementace závisí na faktorech jako je například aplikace, použité technologie, životní prostředí, atd... Implementace algoritmu AES byly testovány a ověřeny v akreditovaných laboratořích.(15) Algoritmus AES se používá ve spojení s normou FIPS schválenou federálním úřadem NIST (National Institute of Standards and Technology), který doporučuje její provoz. Identifikátory objektů a všechny související parametry pro AES používané v těchto režimech jsou k dispozici v registru objektů počítačové bezpečnosti CSOR2 (Computer Security Objects Register).(15) 2.3.5.1 Výběrové řízení AES Úřad Spojených státu amerických NIST (National Institute of Standards and Technology) vyhlásil 2. 1. 1997 plně veřejné a otevřené výběrové řízení, které si kladlo za cíl výběr blokového šifrovacího algoritmu. Tento kryptografický algoritmus nahradil DES a slouží k ochraně citlivých informací. V roce 1998 NIST oznámil přijetí patnácti kandidátů a požádal o pomoc s analýzou komunitu pro kryptografický výzkum. Analýza zahrnovala počáteční posouzení bezpečnosti, účinnosti a vlastnosti každého algoritmu. Po přezkoumání výsledků
2
CSOR (Computer Security Objects Register) se nachází zde: http://csrc.nist.gov/csor.
36
tohoto předběžného výzkumu byly vybrány jako finalisti šifry MARS, RC6 ™, Rijndael, Serpent a Twofish. Po přezkoumání další veřejné analýzy se NIST rozhodla navrhnout Rijndael jako Advanced Encryption Standard (AES)3. Od 26. 5. 2002 se AES stává federálním standardem Spojených státu amerických jako FIPS PUB 197. (16) Hodnotící kritéria výběrového řízení AES se týkají 1. Bezpečnosti: •
Skutečná bezpečnost ve srovnání s ostatními hodnocenými algoritmy.
•
Výstupní šifrový text musí být nerozeznatelný od náhodné permutace stejného vstupního bloku.
•
Algoritmus musí být podložen dostatečnými matematickými základy.
•
Bezpečnostní otázky od odborné veřejnosti.
•
Praktická demonstrace odolnosti proti kryptografickým útokům.
2. Ceny •
Cenově dostupný.
•
Licenční požadavky se musí týkat jak softwarové, tak hardwarové implementace.
•
Rychlost provádění algoritmů pod různými platformami.
•
Paměťové nároky jak u hardwarové, tak softwarové implemetace.
3. Implementace •
Bezpečná a efektivní implementace v rozsáhlém spektru vývojových prostředí a aplikací. Například bankomaty, satelitní komunikace, počítačové sítě.
•
Umožnění práce s delšími klíči (128- 256 bitů).
•
Možnost implementace generátorů MAC (Message Authentication Code) a PRN (Pseudo-Random Number).
•
Jednoduchost návrhu a implementace. (16)
3
Výsledky výzkumu a zdůvodnění výběru šifry Rijndael jako AES, podrobně popisuje zpráva uvedená zde http://csrc.nist.gov/archive/aes/round2/r2report.pdf.
37
Vítězný algoritmus Rijndael je pojmenován po svých tvůrcích, tvůrcích, Belgičanech Vincentu Rijmenovi a Joan Daemenovi z COSIC COSIC laboratoře (Computer Computer Security and Industrial Cryptography) na KU Leuven, Cryptography) Leuven, v Belgii. Belgii. AES není přesné kopie Rindaelu, protože Rijndael podporuje větší rozsah délky bloku, délky klíčů a má jinak pojmenované pojmenované některé metody. (9) 2.3.5.2 Matematický základ AES Vstupní, výstupní bitové sekvence a šifrovací ifrovací klíč jsou zpracovávány jako pole bajtů, které vznikají rozdělením těchto sekvencí do skupin po osmi sousedních bitech bitech. Vstup, výstup nebo šifrovací klíč je označen jako a,, bajty v poli jsou označeny an nebo a[n] a[n], kde n je v jednom z následujících rozsahů: Délka élka klíče= 128 bitů, 0 ≤ n < 16;
Délka bloku = 128 bitů, 0 ≤ n < 16;
Délka klíče= 192 bitů, 0 ≤ n < 24; Délka klíče= 256 bitů, 0 ≤ n < 32. Vnitřní operace algoritmu AES jsou prováděny ve dvourozměrném rozměrném poli bajtů nazývaném Stav. tav. Vstup je tvořen polem m bajtů
, které jsou zkopírovány do pole Stav.
Šifrovací operace jsou prováděny v tomto poli a jejich konečné hodnota je poté zkopírována do výstupního pole bajtů
. Tento proces je zobrazen na obrázku 13. 13.
(15) (17)
Obrázek 13 - Vstup, stup, výstup, pole Stav Zdroj: upraveno na základě (15), strana 13
38
2.3.5.2.1 Pole GF (28) Konečné těleso GF (pk) je označováno jako tzv Galoisovo těleso, kde p označuje prvočíslo a k, značí kladné přirozené číslo. Většina operací šifry AES je definována na úrovni bajtů. Tyto bajty představují prvky konečného pole GF (28). Prvky konečného pole GF (28) mohou být zastoupeny několika různými způsoby. Pro každý primární výkon je jediné konečné pole, tedy všechny reprezentace GF (28) jsou izomorfní (vzájemně jednoznačné). Navzdory této rovnocennosti má zastoupení konečného pole vliv na složitost implementace. Autoři algoritmu vybrali klasické polynomiální zastoupení. (17) 2.3.5.2.2 Polynomy AES je nelineární. Všechny hodnoty bajtů v algoritmu AES jsou prezentovány jako zřetězení jednotlivých
bitových
hodnot
(0
nebo
1)
mezi
složenými
závorky
v
pořadí
{b7, b6, b5, b4, b3, b2, b1, b0}, tyto bajty jsou interpretovány jako konečné prvky pole vyjádřené pomocí polynomu stupně 7:
ab S b _ ac S c _ ad S d _ ae S e _ af S f _ a S _a S_aT ∑b*hT a* S *
Příklad polynomu: polynomiální zápis binární zápis hexadecimální zápis
{19}
S c _ S e _ S _ S _ 1 .010101110 .570
(17) Vzorec {19} a příslušné komentáře byly inspirovány zdroji (9) a (15). 2.3.5.2.3 Operace sčítání V polynomiální reprezentaci je dán součet dvou prvků polynomem s koeficienty, které jsou dány součtem modulo 2 (1+1=0) koeficientů dvou prvků. Součet modulo 2 je operace XOR (kapitola 2.2.1).
39
Příklad sčítání: polynomiální zápis binární zápis hexadecimální zápis
S c _ S e _ S _ S _ 1 _ S b _ S _ 1 S b _ S c _ S e _ S .010101110 ⊕ .100000110 .110101000 .570 ⊕ .830 .40
(17) 2.3.5.2.4 Operace násobení V polynomiální reprezentaci je násobení v GF (28) označováno • a odpovídá násobení polynomů modulo ireducibilním polynomem stupně 8. Ireducibilní polynom je takový polynom, který nelze rozložit na součin jednodušších polynomů a je označován, jako m(x). Pro AES algoritmus je ireducibilní polynom:
S S n _ S e _ S f _ S _ 1
{20}
Hexadecimální zápis vzorce uvedeného výše: Příklad násobení .570 ∙ .830 .C10:
m(x) = {01}{1b}
S c _ S e _ S _ S _ 1 ∙ S b _ S _ 1
S f _ S _ S p _ S n _ S b _ S b _ S d _ S f _ S _ S _ S c _ S e _ S _ S
_ 1 S f _ S _ S p _ S n _ S c _ S d _ S e _ S f _ 1 a
S f _ S _ S p _ S n _ S c _ S d _ S e _ S f _ 1 X` S n _ S e _ S f _ S _ 1 S b _ S c _ 1 (17) Modulární redukce m(x) zajišťuje, že výsledkem násobení bude binární polynom stupně méně než 8 (může být reprezentován bajty). Na rozdíl od sčítání neexistuje na úrovni bajtů žádná jednoduchá operace, která by odpovídala tomuto násobení. Množina 256 možných hodnot bajtů, využívá operaci XOR jako doplněk pro násobení uvedené výše, má strukturu konečného pole GF (28). (15) Vzorec {20} a příslušné komentáře byly inspirovány zdrojem (15). 40
2.3.5.3 Specifikace algoritmu AES AES je lineární substituční transformace s 10, 12 nebo 14 rundy (záleží na velikosti klíče). Bloky dat, které mají být zpracovávány, jsou rozděleny v poli bajtů a každá ze šifrových operací je bajtově orientovaná. Rundovní funkce jsou složeny ze čtyř vrstev. V první vrstvě je S-box (nelineární substituční funkce měnící jednotlivé bity) aplikován na každý bajt. Druhá a třetí vrstva jsou lineární míchání, ve kterém jsou řádky pole posouvány a sloupce míchány. Ve čtvrté vrstvě je na klíč bajtů aplikována operace XOR do každého bajtu pole, v poslední rundě je míchání sloupce vynecháno. (16) Všechny operace algoritmu AES se provádějí v dvourozměrném poli zvaném Stav (obrázek 13). Algoritmus AES má velikost vstupního bloku, výstupního bloku a bloku Stav 128 bitů. Blok Stav může být zobrazen jako obdélníkové pole bajtů. Toto pole má čtyři řádky, počet sloupců je označován proměnou Nb a je roven délce bloku / 32. Velikost bloku Nb reflektuje počet 32-bitových slov v bloku Stav (Nb = 128 / 32 = 4). Délka šifrovacího klíče je 128 nebo 192 nebo 256 bitů. Délku klíče určuje proměnná Nk = 4 nebo 6 nebo 8, která reflektuje počet 32-bitových slov v šifrovém klíči. Počet rund, které jsou prováděny v průběhu algoritmu AES, záleží na délce klíče Nk a jsou určeny proměnnou Nr. Nr = 10, pokud Nk = 4, Nr = 12, pokud Nk = 6 a Nr =14, pokud Nk = 8. Kombinace délky klíče, velikosti bloku a počet rund v souladu s normou FIPS PUB 197 určuje následující tabulka:
AES 128 192 256
délka klíče Nk 4 6 8
velikost bloku Nb 4 4 4
počet rund Nr 10 12 14
Tabulka 2 - Specifikace AES, počet rund v závislost na délce klíče a velikosti bloku Zdroj: vytvořeno na základě (15), strana 18
AES algoritmus využívá pro šifrování i dešifrování rundovní funkce, které se skládají ze čtyř různých bajtově orientovaných transformací: 1. Bajtová substituce využívající substituční tabulku (S-box). 2. Přesun řádků pole Stav (za pomocí různých „offsetů“). 3. Míchání dat v každém sloupci pole Stav. 4. Přidáním Rudovního klíče do pole Stav. (9)(15)(17)
41
Na začátku šifrování je vstup zkopírován do pole Stav (obrázek 13). Po inicializaci rundovního klíče je pole Stav za pomocí rundovních funkcí desetkrát nebo dvanáctkrát nebo čtrnáctkrát transformováno (v závislosti na délce klíče). Na konci je obsah pole Stav zkopírován do výstupu. (15) Algoritmus AES lze rozdělit na procesy, kterými jsou samotné šifrování a tvorba klíčů. Šifrování využívá především čtyři procedury, které jsou prováděny v každé rundě. Tyto operace jsou SubBytes(), ShiftRows(), MixColumns(), AddRoundKey(). Všechny rundy jsou identické, kromě poslední rundy, která neobsahuje MixColumns() transformaci. (9) 2.3.5.4 Zpracování klíče algoritmu AES Ještě před započetím vlastního šifrovacího procesu je třeba na začátku zadat šifrovací klíč (šifrovací klíč je obecně vysvětluje kapitola 1.3). Zadaný šifrovací klíč může mít různou délku, počet provedených rund závisí na délce tohoto šifrovacího klíče. Šifrovací klíč kratší délky urychluje šifrovaní i dešifrování a spoří čas. Zato delší klíč zvyšuje bezpečnost, ale procesy šifrování a dešifrování trvají déle. Klíč je zapisován do matice q 3 4 (viz.
kapitola 2.3.5.3 Specifikace algoritmu AES), N = 4 nebo 6 nebo 8 pro délku klíčem 128 nebo 196 nebo 256 bitů (viz. tabulka 2). (9) 2.3.5.4.1 Procedura KeyExpansion() KeyExpansion() je operace (procedura), která vytváří nové šifrovací klíče v algoritmu
AES. Procedura generuje celkem Nb (Nr + 1) slov (proměnné popsány v kapitole 2.3.5.3 Specifikace algoritmu AES). Algoritmus vyžaduje počáteční soubor Nb slov a pro každou rundu Nr vyžaduje Nb slova klíčových dat. Výsledný klíč je rozvržen v lineárním poli čtyřbajtových slov, označeného [wi], kde i je v rozsahu 0 P , P qr q^ _ 1 .
42
Vytvoření zašifrovaného klíče algoritmu AES lze popsat v následujících krocích (obrázek 14): 14):
Obrázek 14 - Nastínění astínění procedury KeyExpansion() v 6 krocích Zdroj: droj: vytvořeno na základě (9), strana 255 a 256
1. Nový klíč je vytvářen z námi zadaného klíče (následující následující klíče se vytvářejí dle nově vytvořených klíčů) klíčů) a je uložen v hexadecimálním poli. poli 2. Poslední sloupec sloupec nově vytvořeného klíče vezmeme a prvky posuneme o nahoru tak, že se první prvek přesune na spodek sloupce. Tuto operaci provádí procedura RotWord(), jedná o cyklickou rotaci čtyřbajtového slova o bajt, kde slovo RotWord(), slov [a0, a1, a2, a3] transformuje na čtyřbajtové slovo [a1, a2, a3, a0]. 3. Na tento sloupec je dále aplikována operace SubWord() Sub (viz. kapitola 2.3.5.5 Šifrovací proces AES). AES) Tato procedura aplikuje na všechny čtyři bajty S S-box. box. 4. Následně je aplikována operace XOR ( ) tak, že je „náš“ sloupec z kroku 3 je sečten se sloupcem s menším indexem (tento index se každé rundovní kolo mění mění). 5. V posledním kroku je na vzniklý sloupec aplikována operace XOR s příslušným sloupcem tabulky Rcon[i]. Rcon Tabulka (pole) konstantních slov Rcon[i] obsahuje prvky [xi-1, 00, 00, 00]. 00] 6. Následující sloupce jsou vytvářeny analogicky podle kroků 2 až 5. Sčítá se vždy nově vytvořený sloupec se sloupcem o index menší a tyto kroky se několikrát opakují. (9) (15)
43
Pseudokód procedury KeyExpansion() zobrazují následující řádky: Pseudokód KeyExpansion(byte KeyExpansion byte key[4*Nk], key ], word w[ [Nb*(Nr+1)], )], Nk) begin word temp i = 0 while (i ( < Nk) w w[i] = word(key[4* word *i], key[ [4*i+1], key[4*i+ +2], key[ [4*i+3]) i = i+1 end while i = Nk while ( (i < Nb * (Nr+1)] )] temp = w[ [i-1] if (i i mod Nk = 0) temp = SubWord(RotWord SubWord RotWord(temp)) )) xor Rcon Rcon[i/Nk] else if (Nk ( > 6 and i mod Nk = 4) temp = SubWord(temp) SubWord ) end if w w[i] = w[ [i-Nk] xor temp i = i + 1 end while end
(15) Zmíněný něný pseudokód je implementovaných šest kroků procedury KeyExpansion() popsaných výše do kódové ódové podoby (obrázek obrázek 14 a obrázek 15). 15
Obrázek 15 - Procedura rocedura KeyExpansion() algoritmu AES Zdroj: ftp://ftp.kemt.fei.tuke.sk/KEMT414_AK/_materialy/Cvicenia/kryp_6.pdf ftp://ftp.kemt.fei.tuke.sk/KEMT414_AK/_materialy/Cvicenia/kryp_6.pdf, strana 5
Další grafický pohled na proceduru KeyExpansion() poskytuje obrázek 15 15.. Pole w[i] obsahuje bsahuje expandovaný klíč.
44
2.3.5.5 Šifrovací proces AES Celý šifrovací a dešifrovací proces probíhá podle následujícího následujícího schématu, vyobrazeném na obrázku 16.. Na začátku se pole Stav, Stav ve kterém je uložena šifrovací zpráva zpráva, sečte operací XOR s námi zadaným šifrovacím šifrovacím klíčem. Následuje provádění deseti, dvanácti nebo čtrnácti čtrná ti rund (podle velikosti klíče). Během provádění těchto rund se opakují procedury popisované v následujících podkapitolách.
AES šifrování využívá v jedné rundě čtyři transformace.
Jedná se o jednu permutaci a tři substituce. Tyto operace jsou SubBytes(), ShiftRows(),
MixColumns(),
AddRoundKey( . Poslední runda vynechává AddRoundKey().
operaci MixColumns(). MixColumn
Obrázek 16 – Šifrovací Šifrovací a dešifrovací procesy AES Zdroj: upraveno na základě (18), strana 23
45
2.3.5.5.1 Jedna runda šifrovacího procesu a její tranformace Z obrázku 17 vyplývá, že transformace SubBytes(), ShiftRows(), MixColumns() a AddRoundKey()operují na poli Stav, které je dvourozměrné (obrázek 13). Komponenty transformace jsou specifikovány v následujících kapitolách. Obrázek 17 zobrazuje jednu rundu šifrování algoritmem AES graficky:
Obrázek 17 - Jedna runda šifrovacího procesu AES Zdroj: upraveno na základě http://flylib.com/books/3/190/1/html/2/images/05fig03.jpg
1. Na začátku šifrování každé rundy je postupně naplněn vstup 16 bajtů do matice 4 x 4 (jedná se o dvourozměrné pole Stav), plnění probíhá zleva doprava po řádcích a od shora dolů po sloupcích. 2. V kroku 2 je na každý bajt pole Stav je aplikována substituce SubBytes(). 3. Následně operace ShiftRows()cyklicky posune prvky pole Stav o nula až tři bajty doleva. První řádek je posunut o nula bajtů, druhý o jeden bajt, třetí o dva bajty a čtvrtý o tři bajty doleva. Tímto krokem dochází k transpozici na úrovni bajtů. 4. V dalším kroku je na každý jednotlivý sloupec dvourozměrného pole aplikována procedura MixColumns(), která každý bajt změní na novou hodnotu. 5. Poslední operace rundy se nazývá AddRoundKey(), která na jednotlivé sloupce aplikuje operaci XOR s odpovídajícími rundovními klíči. (18) 46
2.3.5.5.2 Procedura SubBytes Transformace SubBytes()je nelineární bajtová substituce, která transformuje jednotlivé bajty pole Stav. Využívá substituční tabulku (S-box)4. Tento S-box je invertibilní (regulární) a je tvořen dvěma složenými transformacemi: 1. Na každý bajt je v konečném poli GF (28) (viz. kapitola 2.3.5.2.1 Pole GF (28)) aplikována multiplikativní (zesilující) inverze. 2. Na každý bajt je v konečném poli GF (2) aplikována afinní transformace:
a*´ a* ⊕ b FDe tuvn b FDe tuvn ⊕ b FDd tuvn ⊕ b FDc tuvn ⊕ cF
Pro 0 P , P 8, kde bi je i-tý bit v bajtu.
{21}
ci je i-tý bit v bajtu c s hodnotou {63} hexadecimálně nebo {01100011} binárně.
V maticové podobě mohou být afinní transformace prvku S-boxu vyjádřeny jako: a´ z T´ } 1 ya | z1 ya´ | y 1 y ´| y a y f | y1 yae´ | y1 ya ´ | y0 y d´ | y0 yac | x0 xab´ {
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
aT´ 1 z ´} 1 a | z } } y 1 ´ 1 y | y | 1| a 0 |y ´| y | a 1| y f | y0| _ 0| yae´ | y0| 0| ya ´ | y1| d 0| y ´ | y1| a 1{ y c´ | x0{ xab {
{22}
Vzorce {21},{22} a příslušné komentáře byly inspirovány zdroji (9) (15) (17). Obrázek 18 ilustruje efekt transformace SubBytes()na dvourozměrné pole Stav.
Obrázek 18- ByteSub() působí na jednotlivé bajty pole Stav Zdroj: http://imps.mcmaster.ca/courses/SE-4C03-07/wiki/siaa/se4c03_aes_wiki(7)_html_4c9f4601.gif 4
S-box použitý v proceduře SubBytes()je uveden v hexadecimálním tvaru v Příloze B.
47
2.3.5.5.3 Procedura ShiftRows Během procedury ShiftRows()dochází k posunu bajtů v rámci řádků v dvourozměrném poli Stav. První řádek není posouván (r=0), druhý řádek je posunut o jednu pozici vlevo, třetí řádek o dvě pozice vlevo a čtvrtý řádek je posunut o tři pozice. ShiftRows()transformace probíhá takto:
~^, ~^,D* ^,r
% r W=X 0 = 4 0 P O qr ]
{23}
Kde hodnota posunu ~,Q =, qr závisí na počtu řádků r a se mění takto (Nb = 4): ~,Q 1,4 1; ~,Q 2,4 2; ~,Q 3,4 3
(15) Velikost posunu je přímo úměrná velikosti šifrového bloku. Základním cílem transformace je zajištění vysoké difůze mezi sloupci (viz. kapitola 2.3.2.1 Difúze).
Obrázek 19 – ShiftRows() cyklicky posouvá poslední tři řádky pole Stav Zdroj: (15), strana 21
Obrázek 19 zobrazuje proceduru ShiftRows()graficky, jedná se o variantu s blokem délky 128 bitů, 4 3 4 bajtů.
Vzorec {23} a příslušné komentáře byly inspirovány zdrojem (9).
48
2.3.5.5.4 Procedura MixColumns V operaci MixColumns()dochází ke změně jednotlivých sloupců dvourozměrného pole Stav. Každý jednotlivý bajt je měněn na novou hodnotu, která je funkcí všech čtyř bajtů sloupce. Sloupce pole Stav jsou považovány za polynomy nad Galoisovým tělesem5 GF (28) (kapitola 2.3.5.2.1 Pole GF (28)) a násobeny modulo x4 + 1, s fixním polynomem a (x), který je vyjádřen jako:
S .030S f _ .010S _ .010S _ .020
Procedura převede sloupec sc na sloupec ~´ :
~´ ~ S ∙ S X` S e _ 1
{24}
{25}
Tento proces může být zapsán také jako násobení matic: ~´ z T, } z02 ´ y~, | y01 y~ ´ | y y , | y01 ´ x~f, { x03
03 02 01 01
01 01} z~T, } 03 01| y~, | | y | W=X 0 P O qr 02 03| y~, | 01 02{ x~f, {
{26}
Výsledkem tohoto násobení matic (této procedury) jsou ve sloupcích dvourozměrného pole Stav nahrazené čtyři bajty (obrázek 20).
Obrázek 20 - Procedura MixColumns() na dvourozměrném poli Stav Zdroj: upraveno na základě http://flylib.com/books/3/190/1/html/2/images/05fig05.jpg
Implementace operace na všech sloupcích pole Stav vykoná příkaz MixColumns(Stav). Vzorce {24}, {25}, {26} a příslušné komentáře byly inspirovány zdroji (9) (17). 5
Galoisovo těleso, je takové těleso, které má konečný počet prvků.
49
2.3.5.5.5 Procedura AddRoundKey Tato transformace přičte pomocí operace XOR jednotlivé prvky pole Stav k prvkům příslušného rundovního klíče. Rundovní klíč je určen pomocí klíčového plánovacího algoritmu (key schedule). Každý rundovní klíč je složen Nb slov, na tyto slova je aplikována operace XOR se sloupci pole Stav sc:
•
´ ´ ´ ´ ~T, , ~, , ~, , ~f, T, , , , , f, ⊕ ^B%DrD !W=X 0 P O qr
{27}
Proměná round (runda) je hodnota mezi 0 až Nr (Nr popisuje kapitola 2.3.5.6 Specifikace algoritmu AES).
•
W[i] je lineární pole čtyřbajtových slov, ve kterém jsou uloženy klíče (popsané v kapitole 2.3.5.6 Zpracování klíče algoritmu AES).
Cílem transformace AddRoundKey() je, aby operace v rundě byly závislé na rundovním klíči. Pohledem na obrázek 17 můžeme zjistit, že tato operace je poslední transformací šifrovacího procesu AES algoritmu. Vzorec {27} a příslušné komentáře byly inspirovány zdroji (9) (15). 2.3.5.5.6 Implementace šifrovacího procesu AES Implementaci šifrovacího algoritmu AES popisuje následující pseudokód, obsahující procedury a proměnné popsané v předchozích kapitolách. Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
50
(15) 2.3.5.6 Dešifrovací proces AES Během dešifrování jsou používány operace inverzní k operacím použitých při šifrování, protože všechny jsou reverzibilní (schopné zpětného procesu). Tyto operace probíhají v opačném pořadí než při šifrování (obrázek 16 a obrázek 21). Při provádění dešifrování je nezbytné, aby jediná nelineární operace InvSubBytes() byla první transformace v rundě. Je třeba, aby byly řádky posunuty ještě před použitím operace InvMixColumns(). (17)
Obrázek 21 - Dešifrovací proces AES Zdroj: upraveno na základě http://flylib.com/books/3/190/1/html/2/images/05fig07.jpg
Individuální transformace, které využívají dešifrovací proces, jsou InvShiftRows(), InvSubBytes(), InvMixColumns() a AddRoundKey()(operace popsána výše, v kapitole 2.3.5.5. Procedura AddRoundKey). W[i] je lineární pole, ve kterém jsou uloženy klíče. Expanze klíče je popsána v kapitole 2.3.5.4 Zpracování klíče algoritmu AES. 51
2.3.5.6.1 Implementace dešifrovacího procesu AES Implementaci dešifrování nastiňuje následující pseudokód: InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) for round = Nr-1 step -1 downto InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) InvMixColumns(state) end for InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[0, Nb-1]) out = state end (15)
Uvedený pseudokód popisuje grafickou formou obrázek 21. Přestože transformace InvMixColumns()operuje na dvourozměrném bajtovém poli, zatím co rundovní klíče jsou uloženy v jednorozměrném poli slov. Volání procedury InvMixColumns()v tomto pseudokódu zahrnuje změnu typu, vstup do InvMixColumns(Stav)zajišťuje pole Stav, který je považován za dvourozměrné pole bajtů, přičemž vstup zde je vypočítáván jako jednorozměrné pole. (15) 2.3.5.7 Bezpečnostní vlastnosti AES Autoři šifry pojednávají o třech nedostatcích v matematické struktuře AES a potenciální zranitelnosti, ke které vedou. Za prvé uvádí, že všechny operace šifrovacího procesu pracují s bajty, ne s bity. Tato vlastnost umožňuje čtvercový útok na redukování rundovních variant. Kromě toho algoritmus může mít téměř symetrický pohyb bajtů, jediné přerušení symetrie je používání různých rundovních konstant v klíčovém plánování. Pro prvních osm rund je tato konstanta pouze jeden bit. Pokud v AES dojde k vynechání těchto rundovních konstant, pak šifrování může být kompatibilní s otáčením každého slova dat a rundovních klíčů o bajt. (16) AES je převážně lineární, využívá XOR operace a operace běžného sčítání. Aplikuje lineární mapu na bity s běžnými operacemi sčítání. Aplikuje lineární mapu na bity v každém bajtu, 52
aniž by měnil celkový algoritmus. Galoisovo pole (které je základem S-boxu) může být zastoupeno různými bazickými vektory nebo může být transformováno na jiné Galoisovo pole (kapitola 2.3.5.2.1 Pole GF (28)) s různými definovanými polynomy. Jinými slovy matematická struktura AES umožňuje řadu ekvivalentních formulací. Autoři naznačují, že provedením řady manipulací na S-boxu by mohl být útočník schopný najít využitelnou slabinu. (16) AES obsahuje relativně jednoduchý algebraický vzorec pro S-box. Tento vzorec je polynom stupně 254 nad Galoisovým polem, ale v tomto polynomu je pouze devět podmínek, což je mnohem méně, než by se dalo očekávat v typickém náhodně generovaném S-boxu (nelineární substituční funkce měnící jednotlivé bity) stejné velikosti. Matematický výraz opakovaný v několika rundách by mohl být složitější, ale autoři uvádí několik příkladů výpočtů v tomto prostředí, pokud by měl výraz jen pět rund, ukázalo se, že útok na něj by vyžadoval, aby útočník shromáždil dva miliony párů otevřeného a šifrového textu. (16) Útočník, který zpětně získá nebo odhadne vhodné bity AES pod-klíče, bude schopen vypočítat další bity pod-klíče (V případě algoritmu DES tato schopnost pomáhala ke konstrukci lineárních a diferenciálních útoků). Autoři považují tuto vlastnost za znepokojující a naznačují, že na rozdíl od prohlášení ve specifikaci Rijndaelu6 klíčové plánovaní nemá vysoký rozptyl. Zdá se, že AES má dostatečnou bezpečnostní rezervu. Tuto rezervu je trochu obtížné měřit, protože počet rund se mění s velikostí klíče. AES přijal některou kritiku a to, že jeho matematická struktura může vést k útokům. Nicméně jeho struktura je poměrně jednoduchá, což usnadňuje analýzu bezpečnosti během specifického časového horizontu vývojového procesu vylepšení AES. Šifra AES umožňuje výpočet pod-klíče současně se šifrováním, ale ne s dešifrováním. Výpočet pod-klíče je kompatibilní a přístupný zřetězení do určité míry, která není v manuálech přesně specifikována. Efektivní výpočet pod-klíče produkuje poměrně nízkou šifrovací latenci (zpoždění). Nicméně pro dešifrování vyžaduje pod-klíč výpočet buď ve vyrovnávací paměti, nebo vygenerování kompletního klíčového plánu, ještě před započetím vlastního dešifrování. (16)
6
specifikace Rijndaelu (původní název algoritmu AES) viz. (17)
53
2.3.5.7.1 Maskování AES AES je relativně snadné maskovat, protože používá pouze logické operace a tabulky vyhledávání. Vyhledávací tabulka je dostatečně malá, aby byla maskována a uložena v paměti RAM. Všechny operace maskování jsou nezávislé na datech, což umožnuje předběžný výpočet hodnot masky. AES je velice rychlý v maskovém režimu a má malé požadavky na ROM a RAM. (16) 2.3.5.7.2 OTFE „On-the-fly“ (OTFE) znamená, že data jsou dostupné ihned po zadání šifrovacího klíče. AES podporuje „on-the-fly“ výpočet podklíče pro šifrování i dešifrování. Nicméně není možné produkovat první dešifrovací podklíč přímo z originálního šifrovacího klíče v jediném výpočtu. Proto ještě před prvním dešifrováním šifrovým klíčem AES vyžaduje provedení jednorázového klíčového plánování, cyklování přes všechny podklíče generuje první dešifrovací podklíč a poté všechny ostatní dešifrovací podklíče mohou být přepočítány „on the-fly“. Tento způsob minimálně zatěžuje zdroje a je výkonný. (16) 2.3.5.7.3 Útoky na implementaci Operace využívané AES patří mezi nejjednodušší obranu proti útokům hrubou silou. Použití maskovaných technik poskytuje AES algoritmu obranu proti těmto útokům a nezpůsobuje značné snížení výkonu a požadavky na RAM růstávají přiměřené. Nicméně AES má implementaci náchylnou na analytické útoky. 2.3.5.8 Implementační omezení AES Variant implementací je mnoho, může být využita v mnoha případech. Nabízí výkon a další výhody. 2.3.5.8.1 Flexibilní implementace Dešifrování může být prováděno se stejnou strukturou jako šifrování, pouze s různými komponenty (viz. obrázek 16). Chceme-li optimalizovat propustnosti procesorů s délkou slova na 32 bitů. Rundovní funkce mohou být kombinovány do množiny čtyř vyhledávacích tabulek. Jedna tabulka může nahradit ostatní vyhledávací tabulky na úkor dalších rotačních operací. Stejná optimalizace platí i pro dešifrování rundovní funkce, ačkoli s jinými tabulkami.
Operace
MixColumns()je
navržena
tak,
aby
umožňovala
efektivní
implementaci na osmibitových procesorech. AES klíčové plánování využívá S-box, který nabízí příležitosti pro sdílení zdrojů v hardwarové implementaci.
54
2.3.5.8.2 Softwarová a hardwarová implementace AES je vhodný pro hardwarovou implementaci. Implementace AES využívá logické funkce a vyhledávací tabulky. Dochází však k asymetrii mezi šifrováním a dešifrováním. Inverzní funkce procedury InvMixColumns() MixColumns()
používá složitější konstantní hodnoty, než
(kapitola 2.3.5.5.4). Z tohoto důvodu je kritická cesta delší pro
dešifrování. Tabulku vyhledávání představuje zhruba z poloviny zpoždění. Nastavení klíče trvá asi o 85% déle v případě dešifrování než u šifrování. (16) AES umožňuje velmi dobré šifrování a dešifrování na celé řadě platforem, včetně osmi bitových a šedesáti-čtyř bitových platforem a DSP (Digitální signálový procesor). Avšak při větších velikostech klíčů dochází z poklesu výkonu a to z důvodu zvýšení počtu rund, které jsou prováděny. Další důležitou vlastností AES je paralelizmus, který umožňuje efektivní využívání prostředků procesoru, což má za následek velice dobrý softwarový výkon. AES má samostatné šifrovací a dešifrovací jednotky. Tyto jednotky sdílí šestnáct vyhledávacích tabulek a jsou implementovány na Galoisově poli GF (28). Tyto jednotky jsou nezávislé a vyhledávací tabulky zabírají kolem 40 % šifrovacího prostoru. Implementace šifrování i dešifrování současně vyžaduje o 60 % více hardwarových požadavků, než pouze implementace šifrování samostatně. Paměť ROM je na bází plně paralelní vyhledávací tabulky, implementace poskytuje nízkou latenci
a
vysokou
propustnost.
Využití
oddělených
hodin
pro
nastavení
klíče
a kryptografického jádra latenci nepatrně zvyšuje. Logické zdroje nejvíce využívají S-boxy. Každý S-box využívá osm bitů vyhledávací (lookup) tabulky, šestnáct jeho kopií je vyžadováno za rundu. Další operace jsou jednodušší, plné rozbalování smyček a vnější řetězení jsou neproveditelné z hlediska prostorových omezení. V režimu zpětné vazby dosahuje nejlepších výkonů druhé kolo rozbalování smyček. Nicméně zatím co zlepšení propustnosti na základní architektuře je mírné, tak nárůst velikosti oblasti je asi o 50%. Všechny formy zřetězeného zpracování produkují menší propustnost. V režimu zpětné vazby je asi polovina zpoždění rundovní funkce vytvářena substitucí S-boxů. (16)
55
2.3.5.9 Studie kryptoanalytických útoků na AES Kapitola je pojmenována studie kryptoanalytických útoků na šifru AES, ale časová složitost prolomení AES je stále tak vysoká (viz. tabulky 3, 4 a 5), že je žádné současné nejmodernější technologie nemůžou prolomit AES v praxi. Tudíž se útoky na AES pohybují stále v teoretické rovině. Kryptoanalytické útoky na AES lze rozdělit do tří kategorií. První kategorie obsahuje útoky na oslabený AES, kde je omezený počet rund. Druhá kategorie obsahuje matematické vyjádření vlastností dílčích komponent AES, které by mohly vést ke kryptoanalytickým útokům. Třetí kategorie tvoří útoky postraními kanály, které se zaměřují na nedostatky v hardwarové a softwarové implementaci. Do studie autor diplomové práce nezahrnuje slabé modifikované verze AES s malým počtem rund a snaží se analyzovat kryptoanalytické útoky především na „silnější verze“ AES. Veličina data v tabulkách 3, 4 a 5 představuje velikosti otevřeného textu. Veličina čas představuje výpočetní složitost, zatím co veličina paměť představuje paměťovou náročnost. Hodnota počet rund říká, až do jaké rundy byl veden útok (viz. kapitola 2.3.5.10 Specifikace algoritmu AES) a zdroj (v tabulkách 3, 4 a 5) prezentuje, z jakých materiálů byly hodnoty nejúspěšnějších teoretických útoků čerpány. 2.3.5.9.1 Nejúspěšnější kryptoanalytické útoky na 128 bitovou AES Šifra AES-128 Počet rund Typ útoku Data Čas Impossible 7 Differential 2112,2 2117,2 Impossible 7 Differential 2106,2 2110,2 7 MITM 2116 2116 7 MITM 2105 299 88 8 Biclique 2 2125,3 10 (úplná šifra) Biclique 288 2126,2
Paměť Zdroj 2112,2
(19)
290,2 2116 290 28 28
(20) (21) (22) (7) (7)
Tabulka 3 - Shrnutí nejúspěšnějších teoretických útoků na šifru AES-128 Zdroje: (19) (7) (20) (21) (22)
V tabulce 3 si můžeme všimnout jednoho úspěšného teoretického útoku na 128 bitový AES se sedmi rundami od autorů Derbeze, Fouque a Jeana, kterým se podařilo snížit časovou složitost až na 299. (22) Biclique útok na úplnou 128 bitovou šifru AES od Andrey Bogdanova, Dmitryho Khovratoviče a Christiana Rechbergera (7) umožňuje najíst šifrový klíč v maximálním počtu 2126,2 operací, což je 3,5 rychleji než při útoku hrubou silou, ale stejně je útok těžko prakticky proveditelný. 56
2.3.5.9.2 Nejúspěšnější kryptoanalytické útoky na 192 bitovou AES Počet rund 7 7 8 8 8 9 9 12 (úplná šifra)
Šifra AES-192 Typ útoku Data MITM 2105 Imposible Differential 291,2 MITM 2113 MITM 2113 MITM 2113 Biclique 280 MITM 2121 Biclique 280
Čas 299 2101 2172 2172 2140 2188,8 2185 2189,4
Paměť Zdroj 290 (22) 2139,2 2129 282 2130 28 2185 28
(19) (21) (22) (23) (7) (6) (7)
Tabulka 4 - Shrnutí nejúspěšnějších teoretických útoků na šifru AES-192 Zdroje: (6) (19) (7) (22) (21) (23)
Jedním z neúspěšnějších teoretických útoků na 192 bitovou AES je MITM útok na prvních osm rund algoritmus od kryptoanalytiků Patricka Derbeze a Pieerre Alaina při velikosti dat 2140 dosáhli časové náročnosti 2140. Biclique útok na úplnou 192 bitovou AES má náročnost 2189,4, což umožňuje dešifrování šest krát efektivněji, než útok hrubou silou, ale tato časová složitost je stále moc velká, než aby se dal útok v současnosti prakticky realizovat. 2.3.5.9.3 Nejúspěšnější kryptoanalytické útoky na 256 bitovou šifru AES Počet rund 7 7 7 8 8 8 9 9 14 (úplná šifra)
Šifra AES-256 Typ útoku Data MITM 2116 MITM 297 MITM 28 MITM 2113 MITM 2113 MITM 2113 Biclique 2120 MITM 2120 Biclique 240
Čas Paměť Zdroj 2116 2116 (21) 99 98 2 2 (22) 170,34 186 2 2 (23) 196 129 2 2 (21) 2196 282 (22) 156 130 2 2 (23) 251,9 8 2 2 (7) 2203 2203 (22) 2254,4 28 (7)
Tabulka 5- Shrnutí nejúspěšnějších teoretických útoků na šifru AES-256 Zdroje: (7) (21) (22) (23)
Úspěšným teoretickým útokem je MITM útok na devět rund 256 bitové AES od Patricka Derbeze, Pieerre Alaina a Jérémyho Jeana. Podařilo se jim při velikosti dat 2120 dosáhnout časové složitosti 2203. (22) Biclique útok na úplnou 256 bitovou AES má náročnost 2254,4, což umožňuje dešifrování třikrát rychleji, než jak dlouho by trval útok hrubou silou, ale stejně je složitost tak veliká, že je praktické prolomení nemožné. 57
2.3.5.9.4 Kryptoanalytický útok hrubou silou na AES Útok hrubou silou na žádnou z verzí AES není z praktického hlediska vůbec možný. I kdyby bylo požito pro útok hrubou silou na „plnou verzi“ 256 bitové AES (složitost 2256) padesát super počítačů, které by kontrolovaly triliony (1018) AES klíčů za vteřinu (v případě, že by takové zařízení existovaly) by útok trval 3 · 1051 let, než by byl vyčerpán 256 bitový prostor. 2.3.5.9.5 Útoky na 192 a 256 bitovou AES založené na podobnosti klíčů V roce 2009 prezentovali Alex Biryukov a Dmitry Khovratovich z Univerzity v Lucemburku dva teoretické útoky založené na podobnosti klíčů (related-key útoky), tyto útoky byly založeny na pokročilé variantě diferenciální kryptoanalýzy. Autoři ukázali, že optimální trasy rozvrhnutí klíče by měly být založeny na nízké váze kódových slov v rozvrhnutí klíče (key schedule). Teoretické útoky probíhaly na plnou verzi AES. Oba útoky se nazývaly boomerangové útoky, které jsou založeny na myšlence najít lokální kolize v blokové šifře a vylepšit tak boomerangovou přepínací techniku, jak získat uprostřed šifry volné rundy. Oba útoky byly pouze teoretické a nebyly realizovány prakticky. (24) Pro 256 bitovou AES dosáhl útok časové a datové složitosti 299,5, což je historicky neúspěšnější teoretický útok. Druhý útok byl na 192 bitovou AES a dosáhl paměťové složitosti 2152, datové 2123 a časové složitosti 2176, což byl opět neúspěšnější teoretický útok na plnou 192 bitovou AES. (24) Výše zmíněné výsledky by znamenaly, že se jedná o historicky nejúspěšnějších teoretické útoky na plné verze AES a hodnoty časové složitosti by ukazovaly, že může být algoritmus AES prakticky prolomen. Jenže útoky byly následně podrobněji zkoumány mnoha kryptoanalytiky a bylo shledáno, že by prakticky vůbec nefungovaly7. Proto autor diplomové práce jejich výsledky vůbec nezahrnul do následující studie (tabulky 3, 4 a 5). 2.3.5.9.6 MITM útok na AES Základní princip Meet-in-the-middle útoku obsahuje kapitola 1.8.2 MITM útok. Z tabulek 3, 4 a 5 můžeme vyčíst, že MITM je jeden z nejúspěšnějších současných útoků na AES.
7
Důkazy toho, proč nejsou uvedené related-key útoky z praktického hlediska možné. Uvádějí autoři AES Joan Daemen a Vincent Rijmen zde: http://www.acad.ro/sectii2002/proceedings/doc2012-4/14-Daemen.pdf
58
2.3.5.9.7 Nemožný diferenciál kryptoanalytický útok na AES Tabulka 3 a 4 obsahuje hodnoty s Impossible differential (Nemožný diferenciál) útoky na některé oslabené verze AES. Všechny uvedené Impossible differential útoky využívají velmi podobné algoritmy a jsou založeny na čtyř rundovém nemožném diferenciálu útoku na AES (obrázek je uveden v příloze C).
Nechť ∆ S* označuje vstupní diferenci rundy i a nechť ∆ S*Df označuje diferenci po
operaci ShiftRows() rundy i+3. V případě, že platí dvě následující podmínky: 1. ∆ S* má pouze jeden nenulový bajt,
2. V ∆ S*Df nejméně jedna ze čtyř množin bajtů SR(Col(i)), pro čtyři různé možné
sloupce je rovna nule,
poté ∆ S* → ∆ S*Df je nemožný diferenciál pro každé čtyři po sobě jdoucí rundy AES.
Nastínění těchto nemožných diferenciálů obsahuje Příloha C. Jestliže je v rundě i+3 pořadí operací MixColumns() a AddRoundKey() vyměněno, poté obsahuje nemožný diferenciál ∆ S* → ∆ S*Df . Jestliže ∆ S* má jenom jeden nenulový bajt, poté ∆ S*D má
nenulovou hodnotu v jednom sloupci, a proto ∆ S*D má nenulové hodnoty ve všech
16 bajtech tabulky (v návaznosti na základní difúzní vlastnosti AES, což je skutečnost, používaná v mnoha kryptoanalytických útocích na AES). (19) 2.3.5.9.8 Biclique kryptoanalytický útok na AES Následující kapitola prezentuje výsledky biclique útoků na šifrovací algoritmus AES (popsaný v kapitole 1.8.3 Biclique útok) uvedené v Tabulkách 3, 4 a 5: •
Útok na plnou 128 bitovou AES dosáhl výpočetní složitosti 2126,2.
•
Útok na plnou 192 bitovou AES dosáhl výpočetní složitosti 2189,4.
•
Útok na plnou 256 bitovou AES dosáhl výpočetní složitosti 2254,4.
•
Útoky s nižší složitostí, včetně útoku na 8 rundu 128 bitové AES se složitostí 2126,2, nejsou považovány za velký krok vpřed.
Na rozdíl od jiných zkrácených útoků na varianty AES biclique útok nepotřebuje žádné související klíče a vyžaduje jen velmi malou část kódové knihy (codebook) a má malou náročnost na paměť. Biclique útoky dosahují stále ohromné výpočetní složitosti a prakticky AES v žádném případě neohrožují. (7) 59
2.3.5.9.9 Čtvercový kryptoanalitický útok na AES Vlastnost AES, kterou využívá Čtvercový (Square) útok, spočívá vtom, že vezmeme-li dva čisté texty, jejichž XOR diference (rozdíl) je nenulová v jednom bajtu, pak tato diference bude expandovat pomocí známých způsobů. Po provedení první rundy algoritmu XOR diference mezi mezilehlými stavy bude ukazovat, že jeden sloupec matice stav má nenulovou diferenci (viz. následující matice). Tato vlastnost se bude šířit do všech bajtů v matici (dvourozměrném poli) Stav, dle stejné úvahy i po druhé rundě algoritmu. Příklad, kde je diference ve dvou čistých textech: Šíření jedno bajtové diference ve dvou rundách AES zobrazují následující matice: 0 0 0
2 3 0 0 0 2 0 0 0 3 2 3 0 0 0 0 0 0 → → 3 2 0 0 0 0 0 0 3 2 0 0 0 0 0 0 čistý text první runda druhá runda
{28}
Je tedy možné, že XOR diference mezi dvěma čistými texty bude po dvou rundách v každém bajtu nula. Tato vlastnost bude trvat až to příští operace MixColumns() (viz. kapitola 2.3.5.5.4 Procedura MixColumns) a používá se pro kryptoanalytický útok nemožnými diferenciály, protože XOR diference po dvou kolech nemůže být nula. Zmíněná vlastnost se využívá i při konstrukci útoku označovaný jako Square (čtvercový) útok. (25) typ AES AES-128 AES-128 AES-128 AES-192 AES-192 AES-192 AES-256 AES-256 AES-256
počet rund 4 5 6 5 6 7 5 6 7
data 29 211 240 2·28 2·232 232 2·28 2·232 232
čas 26 240 232 238,5 242,5 2155 239 243 2192
paměť 242 232 232
Tabulka 6 - Čtvercové kryptoanalytické útoky na AES Zdroj: (25)
Z tabulky 6 vyplývá, že výpočetní složitost (veličina čas) uvedených hodnot je velice dobrá (protože je nízká). Jenže při pohledu na počet rund a velikost dat si můžeme všimnout, že se nejedná o „plné nebo silné verze“ AES, tudíž žádná z hodnot čtvercového útoku nebyla autorem diplomové práce zařazená do tabulek 3, 4 a 5 nejúspěšnějších útoku na AES a nemůžeme říci, že by čtvercový útok na AES byl nějakým způsobem efektivní v praxi. Matice {28} a příslušné komentáře byly inspirovány zdrojem (25). 60
2.3.5.10 Klady AES Rijndael prošel velice dlouhým, složitým a přísným výběrovým řízením proto, aby mohl být přejmenován na AES a stát se standardem Spojených státu amerických jako FIPS PUB 197. Byl hodnocen jak pracovníky NIST, tak odbornou veřejností. NIST analyzoval všechny komentáře v papírové i slovní podobě, byl analyzován na konferencích a v laboratorních studiích. Proto je u něj mnohem jednodušší hledat silné stránky než ty slabé. AES šifrování využívají tisíce jednotlivců, korporací a i několik oddělení uvnitř vlády Spojených států amerických. Je to velice silný šifrovací nástroj, je to „open source“ a je poskytován zdarma v mnoha programovacích jazycích. Algoritmus AES má velikou výhodu v rychlosti před svými konkurenty. Zajišťuje trvale špičkový výkon pro šifrování, dešifrování a umožňuje nastavení klíče, i když výkon mírně klesá s 192 bitovou a 256 bitovou délkou klíče. AES má velmi nízké RAM a ROM požadavky a je velmi vhodný pro omezené diskové prostředky, kde se provádí buď šifrování, nebo dešifrování. AES má trvale velmi dobrý výkon v hardwarové i softwarové implementaci, bez ohledu na jeho použití v režimech se zpětnou vazbou nebo bez zpětné vazby. Nastavení klíče je vynikající, operace AES patří mezi tu nejjednodušší obranu proti útokům hrubou silou a časovým útokům. Kromě toho tyto obrany se poskytují bez výrazného dopadu na výkon. AES je navržen s určitou pružností, jedná se o velikosti bloků a délku klíče. Algoritmus může přizpůsobit změny v počtu rund. Interní rundovní struktura umožňuje využívat instrukce na úrovni paralelismu. (16) Existuje mnoho neznámého ohledně budoucích počítačových platforem. AES byl navržen tak, aby mohl být realizován v široké škále prostředí. AES kombinuje bezpečnost, výkon, účinnost, proveditelnost a flexibilitu. AES je vhodná šifrovací technologie pro použití dnes (rok 2014) i v blízké budoucnosti.
61
2.3.5.11 Zápory AES Nevýhodou je, že se požadavky na ROM zvýší (konkrétně dvojnásobně), pokud jsou šifrování a dešifrování prováděny současně, i když algoritmus AES stále zůstává vhodný pro omezené prostory na disku. AES je bajtově orientovaná šifra na základě dynamického čtvercového pole. Prezentace vývojářů na „Square“ útok slouží jako výchozí bod pro další analýzu. Typy substitučních a permutačních operací používané v AES jsou standardní. S-box má matematickou strukturu založenou na kombinaci inverze na Galoisově poli a afinní transformaci. I když matematická struktura může teoreticky napomáhat útoku, tato struktura není skryta a mohl by to být případ zadních vrátek. AES specifikace tvrdí, že v případě, že by S-box obsahoval zadní vrátka, mohl by být tento S-box nahrazen jiným. Pipelining (zřetězené zpracování) omezuje atomická povaha přístupu k S-boxům. V roce 2002, kdy se šifra Rijndael stala standardem AES, nebyly známé žádné úspěšné útoky na tento algoritmus. Dnes (rok 2014) jsou známy teoretické útoky na některé verze šifrovacího algoritmu AES (viz. kapitola 2.3.5.9 Studie útoků na AES). V praxi ještě nebyl algoritmus AES prolomen, respektive se nepodařilo autorovy diplomové práce nikde najít pádné důkazy, že by byl algoritmus AES mohl být prolomen v praktické rovině, protože se zatím nepodařilo najít a provést vhodný útok na šifru tak, aby byla časová náročnost algoritmu rapidně snížena a mohla být prolomena superpočítači. NSA zahájila plán na vybudování utajovaného superpočítače v Utahu, určeného speciálně pro dešifrování algoritmu AES. NSA očekává, že bude moci prolomit šifrové klíče 256 bitového AES kolem roku 2018. NSA tvrdí, že bude schopna prolomit 256 bitovou AES ve „využitelné lhůtě“ a klade si za cíl číst a zpracovávat zašifrované data diplomatické a vojenské komunikace. (26)
2.4 Asymetrické šifrovací algoritmy Asymetrické algoritmy jsou též nazývány jako algoritmy s veřejným klíčem. Hlavní princip spočívá v existenci dvou šifrových klíčů, jeden je označován jako veřejný a druhý se nazývá soukromý (privátní, tajný) viz. obrázek 22. Ze znalosti veřejného klíče nelze zjistit soukromý klíč.
62
Asymetrický šifrovací algoritmus je takový algoritmus, kde pro všechna k ∈ K (prostor tajných klíčů) nelze z transformace šifrování Ek, určit transformaci dešifrování Dk.
Transformace vygeneruje dvojici šifrových klíčů, které se nazývají veřejný (e) a privátní (d) klíč. Tyto klíče parametrizují transformace šifrování a dešifrování tak, že Ek = Ee a Dk = Dd. (8) Jestliže chce odesílatel B předat zprávu m příjemci A, obdrží autentickou kopii veřejného klíče e odesílatele A, využitím šifrovací transformace (zašifrováním) dostane šifrový text c, poté odešle šifrový text c příjemci A.
O @
{29}
Pro dešifrování šifrové zprávy c aplikuje příjemce A dešifrovací transformaci Dd (příjemce využije svůj privátní klíč d) na šifrovou zprávu c a získá původní zprávu (otevřený text) m, kde:
% O
{30}
Vzorce {29}, {30} a příslušné komentáře byly inspirovány zdrojem (2).
Obrázek 22- Základní princip asymetrického šifrování Zdroj: upraveno na základě http://www.infosectoday.com/Articles/Intro_to_Cryptography/CryptoFig05b.jpg
Asymetrický kryptografický systém lze popsat matematickou rovnicí (popis proměnných viz. kapitola 1.6.1 Definice kryptografického systému).
Kde:
@ %
m - message (otevřený text, zpráva), E - transformace šifrování, D - transformace dešifrování. 63
{31}
Někdy také můžeme asymetrický systém definovat jako:
% @
{32}
Vzorce {31}, {32} a příslušné komentáře byly inspirovány zdrojem (27). Veřejný klíč e nemusí být udržován v absolutní tajnosti, ve skutečnosti může být široce dostupný, ale jeho pravost musí být garantována. Příjemce A musí být jediný skupině, kdo ví o odpovídajícím soukromém klíči d. Hlavní výhodou těchto systémů je to, že poskytování autentických veřejných klíčů e je o mnoho jednodušší, než distribuce šifrových klíčů vyžadovaná v symetrických kryptografických systémech. Hlavním cílem asymetrické kryptografie je zajištění soukromí a důvěrnosti. Asymetrické šifrování je nejlépe využitelné při šifrování malého objemu dat, jako jsou například čísla kreditních karet a PIN kódy. (2) Mezi asymetrické šifry patří například RSA, ElGamal, Diffie Hellman, ECC (kryptografie eliptických křivek), DSA, Cramer–Shoup system, Paillieriho kryptografický systém
2.4.1 Výhody asymetrických šifrovacích algoritmů V asymetrickém šifrování má každý uživatel pouze jeden pár šifrových klíčů, to znamená, že veřejný klíč je měněn pro celou skupinu uživatelů. Distribuce šifrových klíčů je lépe řešená než v symetrickém šifrování, protože veřejný klíč může být sdílen s kýmkoli. Hlavní výhoda oproti symetrickým kryptografickým algoritmům je, že není potřeba častá výměna klíčů. Je tedy umožněna bezprostřední komunikace bez potřeby složité distribuce klíčů. Asymetrické šifry jsou velmi dobré pro účely „otevřené komunikace“.(9) Počet šifrových klíčů je roven v asymetrických systémech dvojnásobku uživatelů (entit), na rozdíl od symetrických algoritmů, kde je počet šifrových klíčů kvadraticky větší (viz. kapitola 2.1.2 Zápory symetrických šifrovacích systémů). Při vstupu nového uživatele do komunikace v asymetrických systémech není potřeba, aby dřívější (starší) uživatelé aktualizovali data na rozdíl od symetrických kryptografických systémů, kde si musí všichni dřívější účastníci vyměnit s novým účastníkem šifrový klíč.
64
2.4.2 Nevýhody asymetrických šifrovacích algoritmů Asymetrické šifrovací systémy jsou o mnoho pomalejší než symetrické šifrovací systémy. Z tohoto důvodu se asymetrické šifrování nejčastěji využívá pro distribucí klíčů. Tyto šifrové klíče jsou následně využity pro šifrování pomocí symetrických algoritmů (například AES). Asymetrická kryptografie neposkytuje záruky ověřování původu dat nebo datové integrity. Tyto záruky musí být poskytovány prostřednictvím dalších technik a služeb, zajištující autentizaci zprávy a digitální podpisy. (2) Některé asymetrické algoritmy jsou vhodné pouze pro distribuci klíče. Asymetrických algoritmů, které jsou bezpečné a zároveň využitelné v praxi (rychlé), není mnoho. Řešením může byt využití hybridních kryptografických systémů.
2.4.3 RSA Kryptografický algoritmus RSA je jedna z nejpoužívanějších asymetrických šifer (algoritmy s veřejným klíčem). Byla vyvinuta roku 1978 R. L. Rivestem, A. Shamirem a L. Adlemanem v MIT (Massachusetts Institute of Technology). Hlavní princip bezpečnosti RSA, je založen na výpočetní a technické imunitě vůči faktorizaci celého čísla. (28)
2.4.4 Algoritmus RSA Veřejný klíč v kryptografickém systému RSA obsahuje proměnnou n, která je nazývána modus a proměnnou e, která je nazývána veřejný exponent. Privátní klíč obsahuje modus n a hodnotu d, která je nazývána privátní exponent. Pár veřejného a soukromého klíče může být generován pomocí následujících kroků: 1. Vygenerování páru velkých náhodných prvočísel p a q (je třeba je držet v tajnosti). 2. Vypočítat celé číslo n:
Y W∙
{33}
3. Vybrat lichý veřejný exponent e mezi 3 a n-1, který je nesoudělný (nesoudělná jsou čísla, která mají pouze jednoho kladného společného dělitele a to číslo 1) s p-1 a q-1. 4. Vypočítat privátní exponent d z e, p a q. Platí vztah:
1 ∙ ` 1 mod W & 1 ∙ & 1)
5. Výstup (n, e) je poté veřejný šifrovací klíč a (n, d) je privátní šifrovací klíč. Vzorce {33}, {34} a příslušné komentáře byly inspirovány zdroji (9) (29).
65
{34}
2.4.4.1 Šifrování RSA Operace šifrování je v kryptosystému RSA umocnění e-tého exponentu mondulo n: O ENCRYPT @ mod Y
•
Vstup je zpráva m.
•
Výstup je zašifrovaný text c.
{35}
V praxi bývá zpráva m obvykle nějaký vhodně naformátovaný šifrovací klíč, který má být posléze sdílen. Vlastní zpráva je šifrována pomocí tohoto sdíleného klíče některým tradičním symetrickým algoritmem. Tato konstrukce umožňuje zašifrování zprávy libovolné délky pouze s jedním umocňováním. Vzorec {35} a příslušné komentáře byly inspirovány zdrojem (29). 2.4.4.2 Dešifrování RSA Operace dešifrování je umocnění d-tého exponentu modulo n:
DECRYPT O O % mod Y
{36}
Vztahy mezi exponenty e a d zajišťují, že šifrování i dešifrování jsou inverzní operace, takže dešifrování obnoví původní zprávu m. Bez privátního klíče (n, d) je velmi obtížné obnovit otevřený text m ze zašifrovaného textu c. Proto mohou být zveřejněny n a e, bez toho aby byla ohrožena bezpečnost, která je základním požadavkem na šifrovací systémy s veřejným klíčem. Vzorec {36} a příslušné komentáře byly inspirovány zdroji (28) (29).
2.4.5 Výhody a nevýhody RSA Kryptografický algoritmus RSA z hlediska šifrování a dešifrování pomalý, proto je jeho hlavní přínos především pro distribuci klíčů mezi symetrickými šiframi a pro elektronické podpisy. Během tvorby elektronického podpisu je využívána komprese, proto není nutno šifrovat velké soubory. Některé zprávy nasvědčují tomu, že RSA s délkou klíče 1024 bitů již může být prakticky prolomena8 (například americkou NSA). Bezpečná délka šifrovacího klíče je v součastné době (rok 2014) minimálně 2048 bitů.
8
Bližší informace o prolomení RSA na video přednášce zde: https://www.youtube.com/watch?v=IuSnY_O8DqQ
66
2.5 Kryptografie z pohledu svět a ČR Současným světovým trendem v komerční kryptografii je používání veřejných šifer. Tyto šifry zajišťují různé bezpečnostní služby v podobě důvěrnosti, autentizace, integrity, atd ... (viz. kapitola 1.4 Cíle kryptografie). Je správné, aby jejich kvalita byla veřejně posuzována. Takovýchto šifer nejí mnoho, ale v komerční sféře mají velice silné zastoupení. Můžeme říci, že o jiných šifrách se v podstatě neví. (11)
2.5.1 Kryptografie v USA Jedna ze současných norem Spojených státu amerických FIPS 197 a její algoritmus AES je uveden v kapitole 2.3.5. Některé šifrovací zařízení a technické údaje o nich jsou předmětem federálních kontrol vývozu. Vývoz kryptografických modulů a implementace těchto standardů a technické údaje musí být v souladu s federálními předpisy a licencovány úřady exportní administrativy amerického ministerstva obchodu. Kontrola vývozu a dovozu je uvedena v CFR9 (Code of Federal Regulations) hlava 15, část 740.17 a hlava 15, část 742 a hlava 15 část 774, kategorie5, část 2. (15)
2.5.2 Kryptografie v České republice z pohledu legislativy V České republice existuje tzv. NBÚ10 (Národní bezpečnostní úřad), který zajišťuje kryptografický vývoj, výzkum a řídí kryptografické ochrany utajovaných skutečností V České republice byl vydán Zákon o ochraně utajovaných informací a o bezpečnostní způsobilosti
11
., jedná se o Předpis č.412/2005 Sb. Certifikace kryptografické technologie,
která je využívána k ochraně utajovaných informací, je prováděna v souladu s tímto zákonem. Základní přístupy k certifikaci kryptografických prostředků upravuje Předpis č. 432/2011 Sb. Vyhláška o zajištění kryptografické ochrany utajovaných informací12. Problematiku elektronického podpisu řeší zákon 227/2000 Sb. Zákon o elektronickém podpisu13. (30) (31) 9
elektronická podoba CFR dostupná zde: http://www.ecfr.gov/cgi-bin/ECFR?page=browse Webové stránky NBÚ a jeho hlavní úkoly dostupné zde: http://www.nbu.cz/cs/o-nas/hlavni-ukoly-nbu/ 11 Zákon o ochraně utajovaných informací a o bezpečnostní způsobilosti, veznění pozdějších předpisů (jeho novely) je dostupný zde: http://www.nbu.cz/cs/pravni-predpisy/zakon-c-4122005/ 12 Vyhláška o zajištění kryptografické ochrany utajovaných informací (včetně novel) dostupná zde: http://www.nbu.cz/cs/pravni-predpisy/provadeci-pravni-predpisy/vyhlaska-c-4322011/ 13 Zákon o elektronickém podpisu dostupný zde: http://www.mvcr.cz/clanek/zakon-c-227-2000-sb-o-elektronickem-podpisu.aspx
10
67
3 Návrh a realizace programového kódu na prolomení šifry RC4 hrubou silou Byl navrhnut a realizován program v C++ na lámání RC4 pomocí útoku hrubou sílou. Přičemž byl programový kód realizován tak, aby bylo možné ověřit závislost délky šifrovacího klíče na čase prolomení šifry hrubou silou. Výchozí požadavky na prolomení byly takové, že útočník (autor diplomové práce) bude znát otevřený text, šifrový text a délku šifrového klíče a z těchto hodnot bude pomocí vyzkoušení všech různých variací s opakováním hledat správný šifrový klíč. Návrh a realizaci a další podrobnosti popisují následující kapitoly, zaměřené na praktickou rovinu diplomové práce. Přílohy D, E, F a G obsahují okomentovaný naprogramovaný kód, přílohy jsou rozděleny podle jednotlivých souborů, přičemž Příloha D obsahuje main.h, Příloha E obsahuje Prolomeni.h, Příloha F obsahuje main.cpp a Příloha G obsahuje Prolomeni.cpp.
3.1 Návrh programového kódu Během návrhu programu na prolomení proudové šifry RC4 (šifru popisuje kapitola 2.2.6 RC4) se vycházelo z obecných principů lámání šifry hrubou silou (viz. kapitola 1.8.1 Útok hrubou silou). Hrubou silou je teoreticky možné prolomit jakýkoli šifrovací algoritmus, ale v drtivém případě to není možné dokázat ve využitelném čase. Takže je v praxi tento útok nepoužitelný, vytvořený program umožňuje pracovat s malými délkami klíčů. Pokud bude použit pro zašifrování otevřeného textu klíč s malou délkou, lze šifru RC4 prolomit ve využitelném čase. Šifrovací klíč je na začátku algoritmu vygenerován náhodně a jeho rozsah je v programu nastaven tak, že může nabývat hodnot v rozsahu písmen malé abecedy (a-z). Od rozsahu hodnot, který může klíč nabývat, se taky odvíjí doba prolamování šifry RC4. Nejvíce však dobu lámání šifry ovlivňuje délka toho šifrovacího klíče, nastavení jeho délky je jedno z nejdůležitějších nastavení v programovém kódu, aby mohla být vytvořena statistická studie na závislost délky klíče na čase prolomení šifry RC4. Příklad šifrového klíče vytvořeného náhodným generátorem v programu: jdgfhuqoqu Můžeme vidět, že se opravdu jedná o znaky malé abecedy a šifrovací klíč má délku 10. Tímto klíčem je následně zašifrován kryptografickým algoritmem RC4 otevřený text, který zní: 68
Toto je otevreny text, ktery bude zasifrovan pomoci sifry RC4 Šifrový text (kryptogram) v hexadecimálním formátu bude, po využití zmíněného šifrovacího klíče a zmíněného otevřeného text vypadat takto: d7 ab ea 2c
4a 69 72 53
8b 50 e1 c1
e4 a2 82 75
94 d6 9b 95
b1 6c ba 6e
3c 94 98 bf
56 3b 65 0c
0b 2d 1d 4c
39 c1 6e fd
70 9f df f3
16 99 b3 f9
2d 7c 5e e1
d7 73 10 d5 ab 82 51 7e ea cb 40 24 2c
Tabulka 7 - Příklad šifrového textu zašifrovaného RC4 v hexadecimálním formátu Zdroj: vytvořený programový kód
Programový kód vychází ze znalosti otevřeného a šifrovacího textu a pomocí těchto nejdůležitějších indicií hledá správný šifrový klíč. Podaří-li se získat správný šifrový klíč, znamená to, že je šifra RC4 prolomena hrubou silou. Tento šifrový klíč se díky útoku hrubou silou, ve kterém jsou zkoušeny všechny varianty klíče, podaří získat naprosto vždy, ale tato operace může trvat například i stovky let, proto bylo při spuštění programu pracováno s pouze malými délkami šifrovacích klíčů, aby bylo možné měření hodnot v diplomové práci vůbec dokončit. V případě vyhledání správného šifrovacího klíče se jedná o zkoušení jednotlivých variací s opakováním. Jedná se o variace s opakováním, protože variace jsou vždy uspořádané, tzv. záleží u nich na pořadí prvků. Opakování znamená, že jeden prvek (v tomto případě znak malé abecedy) může být v šifrovacím klíči zahrnut vícekrát. Byl vytvořen rekurzivní algoritmus (rekurze je funkce, která volá sama sebe), který postupně prochází všechny hodnoty, kterých může šifrovací klíč nabývat, dokud tento klíč neobjeví. Vždy když je vygenerován nový potenciální klíč, je pomocí tohoto klíče dešifrován algoritmem RC4 zašifrovaný text, to znamená, že dostaneme nový otevřený text, který se porovná s původním otevřeným textem. Pokud budou oba otevřené texty naprosto shodné, znamená to, že byl objeven správný šifrový klíč a vyhledávání bude ukončeno. V případě, že tyto otevřené texty nejsou shodné, je generována další variace s opakováním (další možný klíč) a postup je opakován. Během běhu programu je měřen čas, měření času je spuštěno vždy v okamžiku zahájení hledání správného šifrovacího klíče a skončí ihned ve chvíli, kdy je správný klíč nalezen. Měření času je v programu prováděno v jednotkách sekundy.
69
Vývojový diagram vytvořeného programového kódu na prolomení RC4 hrubou silou (obrázek 23) znázorňuje jednotlivé nejdůležitější kroky algoritmu, uvedené symboly charakterizují jednotlivé procesy a šipky určují tok řízení.
Obrázek 23 - Vývojový diagram vytvořeného programu na prolomení RC4 hrubou silou formátu Zdroj: Autor Diplomové práce
70
3.2 Realizace a spouštění programového kódu Následující podkapitoly diplomové práce se věnují programovému kódu (uveden v Příloze D, E, F, G), dále zmiňuje software a hardware, na kterém byl program realizován a spouštěn.
3.2.1 Software využitý při realizaci a spouštění programu Použité softwarové technologie zobrazuje následující tabulka: Programovací jazyk Kryptografický algoritmus Operační systém Vývojové prostředí Potřebné knihovny14
C++ RC4 Windows 7 Ultimate 64 bitový Visual Studio 2008 Crypto++ 5.5.2
Tabulka 8 - Použité softwarové technologie pro lámání RC4 hrubou silou Zdroj: Autor Diplomové práce
K vytvoření a následnému spouštění programového kódu na prolomení šifry RC4 hrubou silou byl použit operační systém Windows 7 64- bit. Program byl vytvářen ve vývojovém prostředí Microsoft Visual Studio 2008. Programování probíhalo v programovacím jazyce C++. V současné době patří C++ mezi nejrozšířenější programovací jazyky. Pro certifikované šifrování a dešifrování kryptografickým algoritmem RC4 byla stažena freeware C++ knihovna Crypto++ verze 5.5.2 (pozor novější verze Crypto++ již neobsahují šifru RC4). Pro spuštění programu je třeba tuto knihovnu správně nainstalovat do vývojového prostředí.
3.2.2 Hardware využitý při realizaci a spouštění programu Programový kód byl vyvíjen a spouštěn na notebooku autora diplomové práce, nejdůležitější parametry notebooku zobrazuje následující tabulka: notebook procesor operační paměť grafická karta
MSI GT640 Inter Core(TM) i7 CPU Q 720 @ 1.60GHZ 4GB GeForce GTS 250M
Tabulka 9 - Použitý hardware pro lámání šifry RC4 hrubou silou Zdroj: Autor Diplomové práce
Všechny uvedené komponenty měly nejnovější softwarové ovladače. Více jádrový procesor umožnil spouštění programu vícekrát najednou. Respektive se jednalo o naprosto stejné programy pod různým jménem (aby se proces v paměti nejmenoval stejně). Jedno jádro procesoru, obsluhuje vždy jeden program, což je celkově 12% - 13% (průměr 12,5% ) 14
Crypto++ je freewarová C++ knihovna kryptografických schémat, ke správnému spuštění programu je třeba stáhnout a „naincludovat“ do Visual studia verzi 5.5.2, ke stažení zde: http://www.cryptopp.com/#download
71
z celkového výkonu procesoru PC (viz. obrázek 24). Vícenásobné sp spuštění uštění programu umožnilo sběr více dat v kratším čase, čase, než kdyby byl program pro prolomení šifry spuštěn pouze jednou, jednou viz. následující obrázek. obrázek
Obrázek 24 - Zatížení atížení procesoru během běhu programů na prolomení šifry RC4 Zdroj: Autor Diplomové práce
Na obrázku 24 uvedeném výše, výše je vidět celkové zatížení procesoru i jeho jednotlivých jader, při běhu čtyř stejných programů na prolomení šifry RC4 (programy se liší názvem, aby jich mohlo být spuštěno více najednou). najednou). Pět stejných programů na lámání šifry RC4 najednou nebylo spouštěno, jelikož je při spuštění pěti programů nepatrně snížen výkon všech jader a mohlo by to nepatrně znehodnocovat naměřené hodnoty. hodnoty. Z důvodu, že prolamování šifry RC4 s hrubou silou trvá s kratší délkou klíče klíče i několik dní. dní Každý program láme kryptografický algoritmus RC4 hrubou silou, silou o jiné délce šifrového klíče. Z údaje zatížení procesoru celkem (vpravo nahoře), je vidět, že procesor je převážně zatížen pouze běhy programů na prolomení šifry RC4.
72
3.3 Nejdůležitější proměnné, funkce, procedury a další části programového kódu Celý programový kód v jazyce C++ obsahují Přílohy D, E, F, G. Program byl zhotoven jako projekt s názvem ProlomeniRC4PavelVojtech. Vznikl ve vývojovém prostředí Visual studio 2008 a je rozdělen do čtyř souborů, jedná se o zdrojové soubory main.cpp, Prolomeni.cpp a k nim přidružené hlavičkové soubory main.h a Prolomeni.h. Program je řádně okomentován viz. přílohy a zdrojový kód v projektu. Vývojový diagram na obrázku 23 popisuje některé níže uvedené funkce a procedury obecněji.
3.3.1 Soubor Prolomeni Soubor Prolomeni obsahuje konstruktor: Prolomeni::Prolomeni(std::string oText, std::string sText, int dKlice) { this->otevrenyText = oText; this->delkaKlice = dKlice; this->sifrovyText = sText; } Parametry konstruktoru jsou otevřený text, šifrový text (otevřený text je zašifrovaný pomocí šifry RC4) a délka šifrovacího klíče, tyto parametry jsou známé dopředu před samotným záhájením prolamování šify RC4. Funkce, která postupně generuje potenciální klíče, zde: bool Prolomeni::najdiKlic(std::vector
&genKlic, int k, int n, int index) { if (index < k) //parametr k značí délku klíče { //ASCII_a má hodnotu a v ASCII tabulce, tudíž 97 for(int i = ASCII_a; i < ASCII_a + n; ++i) { //v každém cyklu vygeneruje jednu možnost variace a posune parametr i o 1 genKlic[index] = i; //funkce se zavolá rekurzivně a vygeneruje další možnost, která je založena na předchozí variaci if (najdiKlic(genKlic, k, n, index + 1)) return true; } } 73
else { if (zkusProlomit(genKlic)) //zjistí, zda je klíč ten správný { return true; //máme nalezený správný šifrový klíč } } return false; //klíč nebyl ten správný, pokračuje hledání }
Rekurzivní funkce generuje jednotlivé variace s opakováním, dokud nenarazí na tu správnou - tím pádem je nalezen šifrovací klíč. Prohledávání začíná u znaku a to znamená, že klíč obsahující znaky a bude nalezen ve výsledku rychleji, než klíč obsahující znaky z. Funkce zkusProlomit(genKlic) má za úkol otestovat, zda-li je vygenerovaný klíč správný, pokud není, je následně generována další variace. Funkce bool Prolomeni::zkusProlomit(std::vector klic)nejprve převede potenciální klíč z vektoru charů na pole bajtů. Poté zkusí originální zašifrovaný text dešifrovat pomocí získaného klíče. Dešifrování probíhá algoritmem RC4 pomocí C++ knihovny Crypto++. Následně porovná původní originální text a otevřený text získaný dešifrováním potenciálního klíče takto: if (desifrovanyText.compare(otevrenyText) == 0){ return true; } return false; Jestliže se oba otevřené texty shodují, byl nalezen správný šifrovací klíč a šifra RC4 byla prolomena hrubou silou, pokud se otevřené texty neshodují, funkce vrací false a funkce najdiKlic() pokračuje dále.
3.3.2 Soubor main Soubor main obsahuje for cyklus, který určuje, kolikrát bude šifra prolomena (POCET_POKUSU) a pro jakou délku klíče (MAX_DELKA_KLICE). Například z obrázku 25 uvedeném níže lze vyčíst, že se bude jednat o čtyři pokusy pro délku klíče až pět (délka 1-5), přičemž z obrázku 25 můžeme vidět, že druhý pokus u délky číslo pět, ještě není dokončen. Tím pádem zbývající dvě prolomení u šifrovacího klíče délky pět ještě nezačali.
74
Zmíněný for cyklus: for (int delkaKlice = 1; delkaKlice <= MAX_DELKA_KLICE; ++delkaKlice) { for (int pocetPokusu = 1; pocetPokusu <= POCET_POKUSU; ++pocetPokusu) { testujKlic(delkaKlice); } } MAX_DELKA_KLICE
a
POCET_POKUSU
jsou
konstanty
definované
v main.h.
testujKlic(delkaKlice) je hlavní metoda, která láme šifru RC4 hrubou silou (hledá správný šifrovací klíč) a měří čas (za jak dlouho k nalezení došlo). Vyváří otevřený text: string
otevrenyText
=
"Toto
je
otevreny
text,
ktery
bude
zasifrovan pomoci sifry RC4"; Následně je uvedený otevřený text zašifrován šifrovacím algoritmem RC4, který poskytuje C++ knihovna Crypto++: Soubor main.cpp obsahuje proceduru pro prvotní vygenerování šifrovacího klíče, klíč je generován náhodně funkcí rand(). Metoda vyžaduje číselnou hodnotu délky klíče (length), tato délka znamená, jak dlouhý bude vygenerovaný klíč. Klíč je uložen do pole bajtů (outKey[i]) a může nabývat 25 hodnot malé abecedy. Na pozici 97 se nachází a (viz. ASCII tabulka15). Z programového kódu uvedeného níže vyplývá, že šifrovací klíč může nabývat těchto hodnot: a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y Čím více hodnot může klíč nabývat, tím je těžší šifru prolomit hrubou silou (prolomení trvá déle). void generovaniKlice(int length, byte *outKey) { for (int i = 0; i < length; ++i){ outKey[i] = 97 + (byte)(rand() % 25); } } Soubor main dále obsahuje proceduru pro vypsání šifrovacího klíče viz. Příloha F. 15
výpis znaků ASCII tabulky lze najít například zde: http://cs.wikipedia.org/wiki/ASCII
75
3.4 Výstupy z programu Programový výstup musí evidovat šifrový klíč, jeho délku a čas, za který byl daný klíč nalezen. Příklad výstupu na obrazovce je zobrazen na následujícím obrázku.
Obrázek 25 - Příklad výstupu programu na obrazovce Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Z obrázku je patrné, jak velký má vliv délka klíče na prolomení šifry. U posledního údaje klíče na obrázku 25 si můžeme všimnout, že ještě nemá přiřazen čas, za který byl tento klíč nalezen, to protože útok hrubou silou stále ještě probíhá a uvedený klíč ještě nebyl nalezen, tzv ještě nebyla nalezena správná variace s opakováním. Pro jednodušší zpracovávání údajů nemusí být využíván výstup a na obrazovce (aby se údaje nemusely
přepisovat),
ale
data
mohou
být
uloženy
nazev_souboru.csv) a následně zpracovány v programu Excel.
76
do
souboru
(ve
formátu
4 Studie vypracovaná na základě výstupních hodnot programového kódu V programovém kódu je šifrovací klíč (v tabulkách označen jako klíč) generován zcela náhodně. Rozsah klíče je programem nastaven tak, že může nabývat 25 hodnot, jedná se o znaky malé abecedy a až y. V tabulkách uvedená veličina čas, charakterizuje čas potřebný pro nalezení správného šifrovacího klíče a tudíž prolomení šifry RC4 hrubou silou. Čas měří programový kód na desetiny vteřiny. Aby bylo možno vypracovat studii, musela být šifra RC4 lámána pro různé délky klíčů (viz. proměnná délka klíče).
4.1 Výstupní hodnoty z programového kódu na prolomení šifry RC4 hrubou silou Následující tabulky zobrazují šifrovací klíč, jeho délku a čas potřebný na prolomení šifry RC4 hrubou silou při znalosti otevřeného a šifrovacího textu. klíč délka klíče čas [s] i 1 0,00 w 1 0,00 q 1 0,00 w 1 0,01 c 1 0,00 p 1 0,00 b 1 0,00 v 1 0,01 y 1 0,00 g 1 0,00 průměr 1 0,005 Tabulka 10 - Čas potřebný pro nalezení klíče délky 1 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Z naměřených hodnot vyplývá, že prolomení šifry RC4 hrubou silou s délkou klíče jedna je uskutečněno téměř okamžitě. Hodnota času 0,00 znamená, že nalezení klíče se pohybovalo pod hodnotou 0,01 vteřin, protože čas je programovém kódu měřen přesně převážně do řádu desetin. Průměrná hodnota prolomení klíče o velikosti jeden znak je 0,005 vteřin.
77
Následující tabulka zobrazuje hodnoty prolomení šifry RC4 hrubou silou s délkou šifrovacího klíče dvě: klíč délka klíče čas [s] nu 2 0,04 ee 2 0,01 vd 2 0,04 mv 2 0,04 yh 2 0,08 eo 2 0,01 nc 2 0,04 ni 2 0,02 gd 2 0,01 fm 2 0,02 průměr 2 0,03 Tabulka 11 - Čas potřebný pro nalezení klíče délky 2 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Z naměřených hodnot vyplývá, že prolomení šifry RC4 hrubou silou s délkou šifrovacího klíče dvě je uskutečněno téměř okamžitě. Průměrná hodnota nalezení klíče o velikost dvou znaků trvá ve vytvořeném programovém kódu 0,03 vteřiny. Tabulka 12 uvedená níže, zobrazuje čas potřebný, pro prolomení šifry RC4 s délkou šifrovacího klíče tři metodou hrubou silou: klíč wwq vkf pjn yet fpl hwx cfc usk cuq gsg aqc cuh wfj epx rep syi uup
délka klíče čas [s] 3 1,35 3 1,28 3 0,82 3 1,43 3 0,37 3 0,51 3 0,16 3 1,34 3 0,19 3 0,35 3 0,04 3 0,16 3 1,40 3 0,26 3 1,19 3 1,23 3 1,30
78
aqc cuh wfj průměr
3 3 3 3
0,04 0,16 1,40 0,75
Tabulka 12 - Čas potřebný pro nalezení klíče délky 2 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Z naměřených hodnot vyplývá, že pro prolomení kryptografického algoritmu RC4 s délkou šifrovacího klíče tři hrubou silou, je možné do 1,5 vteřiny a průměrně trvá 0,75 vteřiny. Dobu nalezení správného šifrovacího klíče při délce čtyři, zobrazuje následující tabulka: klíč délka klíče vcft 4 opft 4 xdmq 4 nwgh 4 admi 4 cnhi 4 gifc 4 aboi 4 vrck 4 flcl 4 xcvc 4 jfjs 4 pgqm 4 jlpq 4 uwtf 4 yobo 4 egrp 4 sutw 4 xecn 4 nmii 4 průměr 4
čas [s] 52,43 22,28 36,31 21,58 0,170 3,594 9,99 0,12 34,25 8,46 55,32 22,9 24,7 15,67 32,35 38,26 6,530 29,28 36,27 21,40 23,59
Tabulka 13 - Čas potřebný pro nalezení klíče délky 4 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
79
Doba potřebná na prolomení šifry RC4 s délkou šifrovacího klíče pět: klíč délka klíče sqval 5 gdslm 5 rwgcg 5 jeavd 5 xpayf 5 rgrbs 5 ujqyi 5 scims 5 ioeoo 5 cmuvp 5 fvblg 5 axwpy 5 damoa 5 cccye 5 nmafy 5 ysogt 5 nmmxl 5 acpci 5 yscpg 5 heogr 5 průměr 5
čas [s] 731,09 240,49 711,08 360,56 925,78 675,64 799,33 704,62 334,31 96,82 226,93 37,07 119,43 79,66 528,67 969,50 526,97 1,49 968,60 284,39 466,12
Tabulka 14 - Čas potřebný pro nalezení klíče délky 5 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Můžeme si všimnout, že prolomit hrubou silou šifru RC4 s délkou šifrovacího klíče pět, trvá ve vytvořeném programovém kódu, který byl puštěn na běžném notebooku od několika vteřin, do patnácti minut. Průměrně trvá prolomení 466,12 vteřin v přepočtu pod osm minut. Pokud má šifra RC4 délku šifrovacího klíče šest, prolomení hrubou silou trvá v řádu hodin, viz. následující tabulka: klíč délka klíče ghmjcn 6 ehbphl 6 sjjtqt 6 muuehb 6 qsjerg 6 upimjb 6 srjemm 6 xubvuo 6 ibeowk 6
80
čas [s] 6282,07 4048,94 17065,76 11730,17 16789,16 20914,83 19145,46 23638,09 7985,31
fwhufk htqcwh jxafxb bpbfls tvllyg skxleg xeomhl fkjapy gttgcc ispvgu aowens průměr
6 6 6 6 6 6 6 6 6 6 6 6
15750,42 17126,04 22074,52 3263,12 19911,1 18967,47 23163,86 5813,42 4866,89 7490,98 522,68 13327,51
Tabulka 15 - Čas potřebný pro nalezení klíče délky 6 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Vytvořený programový kód lámal šifru RC4 s délkou klíče sedm i několik dní, viz. následující tabulka: klíč délka klíče urmyjnk 7 bpxqsgx 7 aeruecp 7 nqceopb 7 nkcnxew 7 průměr 7
čas [s] 565266,52 37676,60 7357,08 348574,60 339421,70 259659,30
Tabulka 16 - Čas potřebný pro nalezení klíče délky 7 Zdroj: výstup vytvořeného programu na lámání RC4 hrubou silou
Průměrné prolomení šifry RC4 s délkou klíče sedm hrubou silou trvá 259659,30 vteřin, což je v přepočtu tři dny. Protože prolomení šifry RC4 hrubou silou při délce klíče sedm tvá několik dní nepřetržitého běhu notebooku, nebylo možno v rámci včasného dokončení Diplomové práce zaznamenat hodnoty více náhodně vygenerovaných šifrovacích klíčů délky sedm. Autor diplomové práce potřeboval ještě čas na pokus o prolomení šifry o délce klíče osm a více. Lze se domnívat, že prolomení šifry RC4 hrubou silou s délkou šifrovacího klíče osm trvá několik týdnů, protože po jednom týdnu běhu programu nebyl šifrovací klíč stále nalezen a pokus byl kvůli včasnému odevzdání Diplomové práce přerušen, stejně tak byly přerušeny pokusy o prolomení šifry s délkou šifrovacího klíče devět.
81
4.2 Časová závislost prolomení šifry s ohledem na délku klíče Následující graf zobrazuje průměrné hodnoty vypočítané z naměřených hodnot (tabulky 10, 11, 12, 13, 14, 15, 16) časové doby prolomení šifry RC4 hrubou silou, pro jednotlivé délky šifrovacích klíčů. Vodorovná osa zobrazuje délku klíče. Svislá osa zobrazuje čas v sekundách, hodnoty na vodorovné ose jsou pro lepší představu v logaritmickém měřítku.
Průměrný čas (v sekundách) potřebný pro prolomení šifry RC4 hrubou silou v závislosti na délce šifrovacího klíče 1000000.00 100000.00 10000.00 1000.00 100.00 10.00 1.00 0.10 0.01 0.00 0.00
1.00
2.00
3.00
4.00
5.00
6.00
7.00
Obrázek 26 - Čas potřebný pro prolomení šifry RC4 v závislosti na délce šifrovacího klíče Zdroj: zpracované výstupní hodnoty z programového kódu
Obrázek 26 potvrzuje časovou závislost prolomení šifry s ohledem na délku klíče.
82
8.00
Závěr Teoretická rovina Diplomové práce nejdříve nastiňuje důležitou kryptologickou terminologii, kryptografická primitiva, cíle a některé kryptoanalytické útoky. Následně práce analyzuje symetrické a asymetrické šifry. Kryptografické šifrovací algoritmy byly nejdříve charakterizovány a následně byly rozebírány jejich klady a zápory, případně implementační omezení. Diplomová práce se konkrétně zaměřila na proudovou symetrickou šifru RC4, blokovou symetrickou šifru AES a asymetrickou šifru RSA. Z kapitoly 2.3.5.11 Studie kryptoanalytických útoků na symetrickou šifru AES vyplývá, že plné 128, 192 a 256 bitové verze AES ještě nemohou být v současnosti (rok 2014) prolomeny v praxi, protože i kdyby útočník využil nejmodernější současné technologie, tak mu momentálně chybí druh útoku, který by umožnil prolomení šifry AES ve využitelném čase. Kryptografie se zabývá především bezpečnostními opatřeními, pokud se podaří prolomit n rund šifry, může být navržena s 2n nebo 3n rundami. Ze současných typů útoků na AES je zřejmé, že bezpečnostní rezerva AES není tak velká, jak se dříve očekávalo. V současné době neexistuje důvod upustit od AES a favorizovat jiný kryptografický algoritmus. NSA by klidně mohla v budoucnosti zvýšit počet rund všech tří variant AES. V tomto momentě navrhuji pro 128 bitovou AES 16 rund, 192 bitovou AES 20 rund a 256 bitovou AES 28 rund. Počet rund algoritmu by mohl být navýšen ještě i více, pokud nechceme, aby se standard FIPS 197 v budoucnu znovu a znovu revidoval. Aneb jak říkají kryptografové: „Kryptoanalytické útoky se vždycky jen zlepšují, ale se nikdy nezhoršují.“ Jednoduché matematické pojmy (prvočísla, faktorizace celého čísla, umocňování) měly dramatický dopad na počítačovou bezpečnost a to zejména pro elektronický obchod. Teorie dobře funguje v praxi prostřednictvím asymetrické šifry RSA. Z hlediska asymetrické kryptografie matematici stále neznají nebo nezkusili rychlejší metodu faktorizace celého čísla, než tu která je v současnosti dostupná. Z hlediska výzkumu je zapotřebí, aby se pokusili nalézt rychlejší způsoby. Mnohem rychlejší metody faktorizace celého čísla již teoreticky existují, ale běžely by na super počítačích, které dosud nebyly postaveny. Pokud by byl vyvinut v plném rozsahu kvantový počítač, bude možné šifry prolamovat mnohem rychleji, než je tomu doposud. 83
V případě, že by jedna nebo více současně bezpečných asymetrických šifer byla v budoucnu prolomena, bylo by užitečné mít na výběr další alternativu. Toto je další důležitou oblastí výzkumu, jaké další těžké problémy v matematice jsou, z nichž by mohly být odvozeny kryptografické systémy s veřejným klíčem a schémata digitálního podpisu. V praktické rovině byl navržen a vytvořen programový kód v programovacím jazyce C++, který umožňuje prolomení rychlé proudové šifry RC4 hrubou silou. Vycházelo se ze zadání, že útočník (autor diplomové práce) zná otevřený i zašifrovaný text. Data získaná z výstupních hodnot programu umožnila realizovat statisticky vyhodnocenou studii potvrzující časovou závislost prolomení kryptografického algoritmu s ohledem na délku šifrovacího klíče. Před zahájením samotného programování kódu v C++ na prolomení šifry RC4 hrubou silou byla provedena důkladná analýza daného problému. Byl vytvořen Vývojový diagram (obrázek 23), který znázorňuje jednotlivé nejdůležitější kroky algoritmu. Do vývojového prostředí Visual studio 2008 byla includována kryptografická knihovna Crypto++, obsahující unifikovanou šifru RC4, kterou bylo poté možno prolomit hrubou silou. Během programování programového kódu v C++ byly využity standardní programátorské postupy, tj. trasování (využívání krokování při hledání chyb), testování a ladění programu. Je třeba si uvědomit, že šifrovací klíč je v programovém kódu náhodně generován tak, aby mohl nabývat pouze znaky o 25 hodnotách (znaky a až y). Tento postup byl takto zvolen, protože lámání šifry hrubou silou je velice časově náročná operace a při zvolení většího počtu znaků, který by mohl šifrovací klíč nabývat, by se nepodařilo tolikrát prolomit šifru RC4 hrubou silou a nepodařilo by se v omezeném čase, který je na vypracování Diplomové práce naměřit více hodnot pro vypracování studie (bylo třeba řádně dodržet termín odevzdání Diplomové práce). V reálném prostředí může šifrovací klíč nabývat mnohem více hodnot (znaky malé a velké abecedy, číslice, ostatní znaky, ...), tím pádem se mnohonásobně zvyšuje počet variací s opakováním, které je třeba prohledat k nalezení správného šifrovacího klíče a nalezení správného šifrovacího klíče by trvalo déle. Časovou závislost prolomení šifry RC4 hrubou silou s ohledem na délku klíče zobrazuje obrázek 26. Z naměřených hodnot (kapitola 4.1 Výstupní hodnoty z programového kódu na prolomení šifry RC4 hrubou silou) si můžeme všimnout, že prolomit hrubou silou šifru RC4 s délkou šifrovacího klíče pět trvá na běžném notebooku od několika vteřin, do patnácti minut (průměrně osm minut). Přičemž ta samá operace s délkou šifrovacího klíče sedm trvá průměrně tři dny. Délku šifrovacího klíče osm se nepodařilo autorovy diplomové práce během 84
zhruba dvou týdenního neustálého běhu programu vůbec prolomit. Z tohoto důvodu bych doporučoval používat délky šifrovacích klíčů (nebo hesel obecně) minimálně osm. Protože tím výrazně zvýšíme počet variací s opakováním, které je třeba prohledat pro nalezení správného šifrovacího klíče. Jakýkoli šifrovací kryptografický algoritmus může být prolomen hrubou silou. Tedy tak, že postupně vyzkoušíme všechny možné variace s opakováním, které může šifrovací klíč nabývat. Diplomová práce dokazuje, že časová závislost prolomení kryptografického algoritmu se zvětšuje s přibývající délkou šifrovacího klíče. Pokud bude šifrovací klíč dostatečně dlouhý (například 16 až 32 znaků), může zmíněná operace trvat při využití nejlepších součastných technologií desítky nebo stovky let. Kryptografický algoritmus se tak stává odolný na útok hrubou silou, protože šifru nelze prolomit ve využitelném čase.
85
Literatura (1) KLÍMA, Vlastimil. I. Moderní kryptografie. [Online] 2.1, 11. 4 2007. [Citace: 19. 1 2014.] http://crypto-world.info/klima/mffuk/Symetricka_kryptografie_I_2007.pdf. (2) MENEZES, Alfred J, OORSCHOT, Paul C a VANSTONE, Scott A. Handbook of applied cryptography. Vyd. 5. Boca Raton : CRC Press, 2001. str. 816. http://cacr.uwaterloo.ca/hac/. ISBN 08-493-8523-7. (3) PINKAVA, Jaroslav. Úvod do kryptologie. [Online] 5 1998. [Citace: 19. 1 2014.] http://crypto-world.info/pinkava/uvod/uvod98.pdf. (4) SHANNON, Claude E. Bell System Technical Journal: Communication Theory of Secrecy Systems. [Online] Bell System, 1949. [Citace: 19. 1 2014.] http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf. (5) BITTO, Ondřej. Šifrování a biometrika aneb tajemné bity a dotyky. Vyd. 1. Kralice na Hané : Computer Media, 2005. str. 168. ISBN 80-86686-48-5. (6) LEIBO, Li, KETING, Jia a Wang, XIAOYUN. Improved Meet-in-the-Middle Attacks on AES-192 and PRINCE. [Online] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, China, 6. 9 2013. [Citace: 23. 3 2014.] http://eprint.iacr.org/2013/573.pdf. (7) BOGDANOV, Andrey, KHOVRATOVICH, Dmitry a RECHBERGER, Christian. Biclique Cryptanalysis of the Full AES. [Online] K.U. Leuven, Belgium Microsoft Research Redmond, USA; ENS Paris and Chaire France Telecom, France, 16. 9 2011. [Citace: 23. 3 2014.] http://eprint.iacr.org/2011/449.pdf. (8) KLÍMA, Vlastimil. II. Symetrické šifrovací systémy. [Online] 2.1, Crypto-World, 11. 4 2007. [Citace: 19. 1 2014.] http://cryptoworld.info/klima/mffuk/Symetricka_kryptografie_II_2007.pdf. (9) PASEKA, Jan. Kryptografie. [Online] Masarykova univerzita, 26. 4 2012. [Citace: 19. 1 2014.] https://is.muni.cz/el/1431/jaro2012/M0170/um/um/Finalkrypto2012.pdf.
86
(10) MISTER, S a TAVARES, S E. Cryptanalysis of RC4-like Ciphers. [Online] Security Techlogogy Group, Ontario, Canada, 1999. [Citace: 27. 1 2014.] http://target0.be/madchat/crypto/codebreakers/Y_23_rc4_cryptana.pdf. (11) KLÍMA, Vlastimil. RC4 Šifra, která mícha karty. [Online] Chip, 17. 8 1999. [Citace: 27. 1 2014.] http://crypto-world.info/klima//1999/chip-1999-09-42-44.pdf. (12) CONNOR, Luke O. On the Entropy of Arcfour Keys. [Online] Cryptology ePrint Archive, 18. 7 2005. [Citace: 28. 1 2014.] http://eprint.iacr.org/2005/233.pdf. (13) STANEK, Martin. Kryptológia – blokové šifry. [Online] 22. 4 2002. [Citace: 29. 1 2014.] http://people.ksp.sk/~misof/browse.php?dirname=06c3e55085553ab64342c1bb28e0c941skol a/Teoria%20kodovania%20a%20kryptologia%20%283itm%204itm%29. (14) KLÍMA, Vlastimil. III. Mody činnosti blokových šifer a hašovací funkce. [Online] 2.1, Crypto-World, 11. 4 2007. [Citace: 19. 1 2014.] http://cryptoworld.info/klima/mffuk/Symetricka_kryptografie_III_2007.pdf. (15) Federal Information Processing Standards Publication 197. Advanced Encryption Standard (AES). [Online] National Institute of Standards, 11 2001. [Citace: 3. 2 2014.] http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf. (16) NECHVATAL, James, a další. Report on the Development of the Advanced Encryption Standard (AES). [Online] U.S. Department of Commerce, 2. 10 2000. [Citace: 4. 2 2014.] http://csrc.nist.gov/archive/aes/round2/r2report.pdf. (17) DAEMEN, Joan a RIJMEN, Vincent. AES Proposal: Rijndael. [Online] National Institute of Standards and Technology, 9. 4 2003. [Citace: 3. 2 2014.] http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf. (18) LÓRENCZ, Róbert. Bezpečnost 7. Proudové šifry, blokové šifry, DES, 3DES, AES, operační módy. [Online] ČVUT Fakulta informačních technologii Katedra počítačových systémů, 2011. [Citace: 4. 3 2014.] www.comtel.cz/files/download.php?id=4826. (19) LU, Jiqiang, a další. New impossible differential attacks on AES. Seoul : Indocrypt, 2008. stránky pp. 279-293. LNCS 5365 http://www.ma.huji.ac.il/~nkeller/Crypt-conf7.pdf.
87
(20) MALA, Hamid, a další. Improved Impossible Differential Cryptanalysis of 7-Round AES-128. Gong, G., Gupta, K.C. : INDOCRYPT, 2010. stránky 282–291. (21) DUNKELMAN, Orr, KELLER, Nathan a SHAMIR, Adi. Improved Single-Key Attacks on 8-round AES-192 and AES-256. [Online] Faculty of Mathematics and Computer Science, Weizmann Institute of Science, 2010. [Citace: 23. 3 2014.] http://www.ma.huji.ac.il/~nkeller/Crypt-conf1.pdf. (22) DERBEZ, Patrick, FOUQUE, Pierre Alain a JEAN, Jérémy. Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting. [Online] École Normale Supérieure, France, 19. 8 2012. [Citace: 23. 3 2014.] http://eprint.iacr.org/2012/477.pdf. (23) DERBEZ, Patrick a FOUQUE, Pierre Alain. Exhausting Demirci-Selçuk Meet-in-theMiddle Attacks against Reduced-Round AES. [Online] École Normale Supérieure, France, 13. 3 2013. [Citace: 23. 3 2014.] http://www.di.ens.fr/~fouque/pub/fse13b.pdf. (24) BIRYUKOV, Alex a KHOVRATOVICH, Dmitry. Related-key Cryptanalysis of the Full AES-192 and AES-256. [Online] University of Luxembourg, 28. 6 2009. [Citace: 27. 3 2014.] http://eprint.iacr.org/2009/317.pdf. (25) TUNSTALL, Michael. Improved "Partial Sums"-based Square Attack on AES. [Online] Department of Computer Science, University of Bristol, 27. 5 2012. [Citace: 29. 3 2014.] http://eprint.iacr.org/2012/280.pdf. (26) COURTOIS, Nicolas T. Is AES a Secure Cipher ? [Online] Independent AES security observatory, 24. 8 2007. [Citace: 9. 3 2014.] http://www.cryptosystem.net/aes/. (27) Jessica, J BENZ. PGP: A Hybrid Solution. [Online] 1.2e, SANS Institute, 28. 6 2001. [Citace: 19. 3 2014.] http://www.sans.org/reading-room/whitepapers/vpns/pgp-hybridsolution-717. (28) COUTINHO, S. C. The Mathematics of Ciphers: Number Theory and RSA Cryptography. Natick, Mass. : A K Peters, 1999. str. 196. ISBN 1-56881-082-2. (29) KALISKI, Burt. The Mathematics of the RSA Public-Key Cryptosystem. [Online] RSA Laboratories, 9. 4 2006. [Citace: 8. 3 2014.] http://www.mathaware.org/mam/06/Kaliski.pdf. (30) Národní bezpečnostní úřad. Právní předpisy. [Online] NBÚ. [Citace: 3. 3 2014.] http://www.nbu.cz/cs/pravni-predpisy/. 88
(31) PINKAVA, Jaroslav. Normy a mezinárodní doporučení v oblasti elektronického podpisu a kryptografie. [Online] Crypto-World, 1 2001. [Citace: 19. 1 2014.] http://cryptoworld.info/pinkava/clanky/normy_crypto.pdf. (32) ANONYMOUS. RC4 Source Code. [Online] CypherPunks mailing list, 9. 7 1994. [Citace: 28. 1 2014.] http://groups.google.com/group/sci.crypt/msg/10a300c9d21afca0.
89
Seznam zkratek AES
Advanced Encryption Standard
ASCII
American Standard Code for Information Interchange
DES
Data Encryption Standard
DSP
Digital Signal Processor
CACR
Centre for Applied Cryptographic Research
CBC
Cipher Block Chaining
CFB
Cipher FeedBack
CFR
Code of Federal Regulations
COSIC
Computer Security and Industrial Cryptography
CTR
CounTeR
CSOR
Computer Security Objects Register
DSA
Digital Signature Algorithm
ECB
Electronic CodeBook
ECC
Elliptic Curve Cryptography
FIPS
Federal Information Processing Standards
KSA
Key Scheduling Algorithm
MAC
Message Authentication Code
MIT
Massachusetts Institute of Technology
MITM
Meet In The Middle
NBÚ
Národní Bezpečnostní Úřad
NITS
National Institute of Standards and Technology
NSA
National Security Agency
OFB
Output FeedBack
PDF
Portable Document Format
PRN
PseudoRandom Number
PRGA
Pseudo Random Generation Algorithm
RC4
Riverst Cypher 4
RDP
Remote Desktop Protocol
RSA
Rivest Shamir Adleman
SSL
Secure Sockets Layer
TLS
Transport Layer Security
TMTO
Time Memory Trade Off 90
WEP
Wired Equivalent Privacy
WPA
Wifi Protected Access
WWW
World Wide Web
XOR
eXclusive OR
91
Seznam obrázků Obrázek 1 - Kryptografická primitiva ...................................................................................... 13 Obrázek 2 - Základní schéma kryptografického systému ........................................................ 14 Obrázek 3 - d-dimenzionální biclique ...................................................................................... 18 Obrázek 4 - Základní schéma symetrického šifrovacího systému ........................................... 20 Obrázek 5 - Procesy šifrování a dešifrování synchronní proudové šifry ................................. 23 Obrázek 6 - Procesy šifrování a dešifrování asynchronní proudové šifry................................ 24 Obrázek 7 - Princip RPGA ....................................................................................................... 27 Obrázek 8 - Náhodné permutace .............................................................................................. 30 Obrázek 9 - ECB mód n-bitových blokových šifer .................................................................. 31 Obrázek 10 - CBC mód n-bitových blokových šifer ................................................................ 32 Obrázek 11 - CFB mód n-bitových blokových šifer ................................................................ 34 Obrázek 12 - OFB mód n-bitových blokových šifer ................................................................ 35 Obrázek 13 - Vstup, výstup, pole Stav ..................................................................................... 38 Obrázek 14 - Nastínění procedury KeyExpansion() v 6 krocích.............................................. 43 Obrázek 15 - Procedura KeyExpansion() algoritmu AES ........................................................ 44 Obrázek 16 – Šifrovací a dešifrovací procesy AES ................................................................. 45 Obrázek 17 - Jedna runda šifrovacího procesu AES ................................................................ 46 Obrázek 18- ByteSub() působí na jednotlivé bajty pole Stav .................................................. 47 Obrázek 19 – ShiftRows() cyklicky posouvá poslední tři řádky pole Stav .............................. 48 Obrázek 20 - Procedura MixColumns() na dvourozměrném poli Stav .................................... 49 Obrázek 21 - Dešifrovací proces AES...................................................................................... 51 Obrázek 22- Základní princip asymetrického šifrování ........................................................... 63 Obrázek 23 - Vývojový diagram vytvořeného programu na prolomení RC4 hrubou silou formátu ..................................................................................................................................... 70 Obrázek 24 - Zatížení procesoru během běhu programů na prolomení šifry RC4................... 72 Obrázek 25 - Příklad výstupu programu na obrazovce ............................................................ 76 Obrázek 26 - Čas potřebný pro prolomení šifry RC4 v závislosti na délce šifrovacího klíče . 82
92
Seznam tabulek Tabulka 1 - Pravdivostní tabulka XOR .................................................................................... 22 Tabulka 2 - Specifikace AES, počet rund v závislost na délce klíče a velikosti bloku ............ 41 Tabulka 3 - Shrnutí nejúspěšnějších teoretických útoků na šifru AES-128 ............................. 56 Tabulka 4 - Shrnutí nejúspěšnějších teoretických útoků na šifru AES-192 ............................. 57 Tabulka 5- Shrnutí nejúspěšnějších teoretických útoků na šifru AES-256 .............................. 57 Tabulka 6 - Čtvercové kryptoanalytické útoky na AES ........................................................... 60 Tabulka 7 - Příklad šifrového textu zašifrovaného RC4 v hexadecimálním formátu .............. 69 Tabulka 8 - Použité softwarové technologie pro lámání RC4 hrubou silou............................. 71 Tabulka 9 - Použitý hardware pro lámání šifry RC4 hrubou silou........................................... 71 Tabulka 10 - Čas potřebný pro nalezení klíče délky 1 ............................................................. 77 Tabulka 11 - Čas potřebný pro nalezení klíče délky 2 ............................................................. 78 Tabulka 12 - Čas potřebný pro nalezení klíče délky 2 ............................................................. 79 Tabulka 13 - Čas potřebný pro nalezení klíče délky 4 ............................................................. 79 Tabulka 14 - Čas potřebný pro nalezení klíče délky 5 ............................................................. 80 Tabulka 15 - Čas potřebný pro nalezení klíče délky 6 ............................................................. 81 Tabulka 16 - Čas potřebný pro nalezení klíče délky 7 ............................................................. 81
93
Příloha A Zdrojový kód proudové šifry RC4 zdroj: (32) Zdrojový kód uveden v jazyce C tak, jak ho 9. 7. 1994 zaslal anonymní kryptoanalytik skupině Cyberpunks. Tímto krokem byla doté doby silně utajovaná proprietární šifra RC4 rozkryta. /* rc4.h */ typedef struct rc4_key { unsigned char state[256]; unsigned char x; unsigned char y; } rc4_key; void prepare_key(unsigned char *key_data_ptr,int key_data_len, rc4_key *key); void rc4(unsigned char *buffer_ptr,int buffer_len,rc4_key * key); /*rc4.c */ #include "rc4.h" static void swap_byte(unsigned char *a, unsigned char *b); void prepare_key(unsigned char *key_data_ptr, int key_data_len, rc4_key *key) { unsigned char swapByte; unsigned char index1; unsigned char index2; unsigned char* state; short counter; state = &key->state[0]; for(counter = 0; counter < 256; counter++) state[counter] = counter; key->x = 0; key->y = 0; index1 = 0; index2 = 0; for(counter = 0; counter < 256; counter++) { index2 = (key_data_ptr[index1] + state[counter] + index2) % 256; swap_byte(&state[counter], &state[index2]); index1 = (index1 + 1) % key_data_len; } }
1
void rc4(unsigned char *buffer_ptr, int buffer_len,rc4_key *key) { unsigned char x; unsigned char y; unsigned char* state; unsigned char xorIndex; short counter; x = key->x; y = key->y; state = &key->state[0]; for(counter = 0; counter < buffer_len; counter ++) { x = (x + 1) % 256; y = (state[x] + y) % 256; swap_byte(&state[x], &state[y]); xorIndex = (state[x] + state[y]) % 256; buffer_ptr[counter] ^= state[xorIndex]; } key->x = x; key->y = y; } static void swap_byte(unsigned char *a, unsigned char *b) { unsigned char swapByte; swapByte = *a; *a = *b; *b = swapByte; }
2
Příloha B S-box Substituční hodnoty pro bajt xy v hexadecimálním formátu. zdroj: (15) strana 20
1
Příloha C Čtyř rundový Imposible diffenciál útok na AES zdroj: (19) strana 21
SB- operace SubBytes(), SR- operace ShiftRows(), MC- operace MixColumns(), ARK- operace AddRoundKey(). Šedé dvourozměrné pole Stav představuje nenulovou diferenci v bajtech, zatímco bílé značí nulovou diferenci.
1
Příloha D main.h /* Program byl vytvořen ve Visual Studiu 2008. Pro správnou funkci programu je třeba nainstalovat a includovat freeware knihovnu Crypto++ 5.5.2, ke stazeni zde: http://www.cryptopp.com/#download */
#define CRYPTOPP_ENABLE_NAMESPACE_WEAK 1 #include #include #include <arc4.h> #include #include #include #include #include #include <math.h> #include #include "Prolomeni.h" //konstanta nastavení pro maximální délky klíče #define MAX_DELKA_KLICE 10 //konstanta určující, kolikrát algoritmus celkově proběhne #define POCET_POKUSU 10 //metoda pro výpis klíče void vypisKlic(byte *msg, int length); //metoda pro vygenerování náhodného klíče void generovaniKlice(int length, byte *outKey); //metoda, která prolamuje RC4 hrubou silou, princip je vysvětlen na obrázku 23 void testujKlic(int delkaKlice);
1
Příloha E Prolomeni.h #pragma once #define CRYPTOPP_ENABLE_NAMESPACE_WEAK 1 #include #include #include <arc4.h> #include <exception> #include //konstanta pro nastavení hodnoty, od jaké může nabývat klíč hodnoty, v ASCII 97 znamená malé a #define ASCII_a 97 class Prolomeni { public: //proměnné std::string otevrenyText; std::string sifrovyText; int delkaKlice; //konstruktor Prolomeni(std::string oText, std::string sText, int dKlice); //metoda, která získá klíč jako vektor charu, ale musí ho převést na pole bajtů bool zkusProlomit(std::vector klic); //funkce prolomeni, spusti generovani klicu a kdyz najde spravny klic tak prevede na string a vrati
std::string prolom(); // převede vektor na string std::string vektorNaString(const std::vector &vektor); //k prvková variace s opakováním z n prvku, prohledává celý klíčový prostor a hledá správný klíč //rekurzivní algoritmus, který postupně prochází cely klíčový prostor a generuje všechny klíče, dokud ho nenajde bool najdiKlic(std::vector &genKlic, int k, int n, int index); //destruktor ~Prolomeni(void); };
1
Příloha F main.cpp #include "main.h" using namespace std; using namespace CryptoPP; int main(int argc, char *argv[]) { srand (time(NULL)); //inicializace počítání času //záhlaví tabulky pro výpis printf("klic; delka klice;
cas;
\n");
//for cyklus do jaké délky klíče a kolik pokusu bude provádět for (int delkaKlice = 1; delkaKlice <= MAX_DELKA_KLICE; ++delkaKlice) { for (int pocetPokusu = 1; pocetPokusu <= POCET_POKUSU; ++pocetPokusu) { testujKlic(delkaKlice); } } return 0; } //metoda, ve které se děje vše podstatné, prolamuje RC4 hrubou silou void testujKlic(int delkaKlice) { byte *klic = (byte *)malloc(sizeof(byte) * delkaKlice); //alokuje klíč generovaniKlice(delkaKlice, klic); //vygeneruje náhodný klíč
vypisKlic(klic, delkaKlice); //vypsáni klice printf("; %d; ", delkaKlice); //vypsáni délky klíče //vytvoř zašifrování, pomoci knihovny crypto++ CryptoPP::Weak1::ARC4 zasifrovani; zasifrovani.SetKey((const byte *)klic, delkaKlice); //vytvořené otevřeného textu string otevrenyText = "Toto je otevreny text, ktery bude zasifrovan pomoci sifry RC4"; string sifrovyTextHexa, sifrovyText; //deklarace proměnných
1
//zašifruj pomoci RC4, nalezeno v dokumentaci crypto++, jak se používá šifrováni knihovny crypto++ StringSource ss1(otevrenyText, true, // zašifruje otevřený text na šifrový text new StreamTransformationFilter(zasifrovani, new StringSink(sifrovyText) ) ); //převedení do hexadecimálního formátu StringSource ss2(sifrovyText, true, new HexEncoder( new StringSink(sifrovyTextHexa) ) // HexEncoder ) //vypiš hexadecimálního formát cout << "sifrovy text: " << sifrovyTextHexa << endl; //třída, která umí prolomit šifru RC4 hrubou silou zná otevřený text, šifrový text a délku klíče, vyrobí objekt prolomení, co se používá k prolomení šifry Prolomeni prolomeni(otevrenyText, sifrovyText, delkaKlice); clock_t start = clock(); //začne měřit čas //realizace prolomeni a uložení nalezeného šifrového klíče string nalezenyKlic = prolomeni.prolom(); // konec měření času clock_t konec = clock(); double cas = double(konec - start) / CLOCKS_PER_SEC; printf("%f; \n", cas); //vypíše čas, jak dlouho trvalo prolomení //smazání dynamicky alokovaných proměnných free(klic); } //procedura vypsání klíče void vypisKlic(byte *msg, int length) { for (int i = 0; i < length; ++i) { printf("%c", msg[i]); } } //procedura generování klíče void generovaniKlice(int length, byte *outKey) { for (int i = 0; i < length; ++i){ //generování všech znaku ASCII tabulky od malého a (pozice 97 v ASCII) dalších 25 znaku outKey[i] = 97 + (byte)(rand() % 25); } }
2
Příloha G Prolomeni.cpp #include "Prolomeni.h" //konstruktor Prolomeni::Prolomeni(std::string oText, std::string sText, int dKlice) { this->otevrenyText = oText; this->delkaKlice = dKlice; this->sifrovyText = sText; } Prolomeni::~Prolomeni(void) //destruktor { } //funkce prolomeni, spustí generování variací s opakováním klíčů, a když najde správný klíč, tak ho převede na string a vratí std::string Prolomeni::prolom() { std::vector genKlic(delkaKlice, 0); //25 znamená počet znaků v abecede od a do z if(najdiKlic(genKlic, delkaKlice, 25, 0)) { //nalezeno, šifrový klíc je genKlic return vektorNaString(genKlic); } //nenalezeno, něco je špatně vyhoď výjimku(k tomu nedojde) throw std::exception(); } std::string Prolomeni::vektorNaString(const std::vector &vektor) // převede vektor na string { std::string vysledek; for (std::vector::const_iterator it = vektor.begin(); it < vektor.end(); ++it) // iteruje pres všechny písmena ve vektoru { vysledek.push_back(*it); } return vysledek; } bool Prolomeni::zkusProlomit(std::vector klic) //metoda ziska klíč jako vektor charu, ale musí ho převést na pole bajtů { //převede klíč na pole bajtů byte *hadanyKlic = (byte *)malloc(sizeof(byte) * klic.size()); int ind = 0; for(std::vector::iterator i = klic.begin(); i < klic.end(); ++i)
1
{ hadanyKlic[ind] = *i; ++ind; } //zašifrovaný text se zkusí dešifrovat pomocí klíče, k dešifrováni využívá knihovnu crypto++ std::string desifrovanyText; CryptoPP::Weak1::ARC4::Decryption dec; dec.SetKey((const byte *)hadanyKlic, klic.size()); CryptoPP::StringSource ss3(sifrovyText, true, new CryptoPP::StreamTransformationFilter(dec, new CryptoPP::StringSink(desifrovanyText) ) // StreamTransformationFilter ); free(hadanyKlic); //pokud se šifrový text shoduje s otevřeným textem, byl nalezen správný klíč a vrací true, jinak vrací false a pokračuje v hledání if (desifrovanyText.compare(otevrenyText) == 0){ return true; } return false; } //k-prvková variace s opakováním z n prvku, prohledává celý klíčový prostor a hledá správný klíč //rekurzivní algoritmus, který postupně prochází cely klíčový prostor a generuje všechny klíče, dokud ho nenajde bool Prolomeni::najdiKlic(std::vector &genKlic, int k, int n, int index) { if (index < k) //k značí délku klíče {
//ASCII_a má hodnotu a v ASCII tabulce, tudíž 97 //n je počet znaků, kterých může klíč nabývat, nastaveno na 25 for(int i = ASCII_a; i < ASCII_a + n; ++i) { //v každém cyklu vygeneruje jednu možnost a posune o 1 genKlic[index] = i; //zavolá se rekurzivně a vygeneruje další možnost založenou na předchozí if (najdiKlic(genKlic, k, n, index + 1)) return true; } } else { if (zkusProlomit(genKlic)) //zjisti zda je klíč ten správný { //máme nalezeny šifrový klíč, vrací true return true; } } return false; //klíč nebyl ten správný, pokračuje hledání }
2
