MASARYKOVA UNIVERZITA Fakulta informatiky
Diplomová práce
Moderní kryptoanalytické metody
Jan Lauš, květen 2007
Prohlášení Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
________________ Podpis
1
Poděkování Tímto bych rád poděkoval svému vedoucím diplomové práce Mgr. Janu Krhovjákovi za odbornou pomoc a připomínky. Také bych rád poděkoval své rodině za podporu a trpělivost při vypracovávání této práce. A také bych chtěl poděkovat své snoubence za nekonečnou trpělivost a velkou pomoc s korekturou textu.
2
Shrnutí Tato práce je souhrnem aktuálních informací o moderních kryptoanalytických metodách. První část se věnuje základním informacím o kryptologických algoritmech. Je zde definována symetrická kryptologie, proudové a blokové symetrické šifry. U blokových šifer jsou uvedeny základní módy šifrování. Dále jsou zde podány základní informace o asymetrické kryptografii, hašovacích funkcích a generátorech náhodných čísel. Druhá část se věnuje jednotlivým kryptoanalytickým metodám ve spojení s konkrétními útoky. Kapitoly jsou děleny podle toho zda se jedná o útok na symetrické šifry, asymetrické šifry, hašovací funkce nebo kryptografické protokoly. Třetí část je věnována implementaci útoku na hašovací funkce pomocí diamantové struktury. Tento útok využívá nedostatečné obrany hašovacích funkcí proti „Chosen Target Forced Prefix“.
Klíčová slova Symetrická kryptografie, asymetrická kryptografie, hašovací funkce, kolize v MD5, chybová analýza, Nostradámů útok
3
Obsah PROHLÁŠENÍ ............................................................................................................................ 1 PODĚKOVÁNÍ ........................................................................................................................... 2 SHRNUTÍ .................................................................................................................................... 3 KLÍČOVÁ SLOVA..................................................................................................................... 3 OBSAH......................................................................................................................................... 4 ÚVOD........................................................................................................................................... 6 1 SYMETRICKÁ KRYPTOGRAFIE....................................................................................... 8 1.1 PROUDOVÉ ŠIFRY ................................................................................................................. 8 1.1.1 Synchronní proudové šifry ............................................................................................ 8 1.1.2 Samočinně synchronní proudové šifry .......................................................................... 9 1.2 BLOKOVÉ ŠIFRY – SYMETRICKÉ......................................................................................... 10 1.2.1 Mód ECB..................................................................................................................... 12 1.2.2 Mód CBC .................................................................................................................... 13 1.2.3 Mód CFB..................................................................................................................... 14 1.2.4 Mód OFB .................................................................................................................... 15 2 ASYMETRICKÁ KRYPTOGRAFIE.................................................................................. 17 3 HAŠOVACÍ FUNKCE .......................................................................................................... 19 4 GENERÁTORY NÁHODNÝCH ČÍSEL ............................................................................ 20 5 ÚTOKY NA PROUDOVÉ SYMETRICKÉ ŠIFRY ........................................................... 21 5.1 DIFERENCIÁLNÍ KRYPTOANALÝZA PY, PYPY .................................................................... 21 5.1.1 Identické klíčové proudy ............................................................................................. 21 5.1.2 Útok na Py a Pypy pomocí kolizí ve vnitřním stavu.................................................... 22 6 ÚTOKY NA SYMETRICKÉ BLOKOVÉ ŠIFRY.............................................................. 25 6.1 ÚTOK POSTRANNÍM KANÁLEM NA BLOKOVOU ŠIFRU V CBC MÓDU PŘI POUŽITÍ PKCS#5 PADDING .................................................................................................................................. 25 6.1.1 Útok pomocí orákula O............................................................................................... 25 6.2 ÚTOK POSTRANNÍM KANÁLEM NA BLOKOVOU ŠIFRU V CBC MÓDU PŘI POUŽITÍ FORMÁTU ZPRÁV PKCS#7 ....................................................................................................................... 27 6.2.1 PKCS#7....................................................................................................................... 27 6.2.2 Útok pomocí orákula PKCS#7CONF ............................................................................. 28 6.2.3 Složitost dešifrování celého textu................................................................................ 30 6.3 ÚTOK NA AES POMOCÍ INDUKCE CHYB BĚHEM ŠIFROVÁNÍ. ............................................. 31 7 ÚTOKY NA ASYMETRICKÉ ŠIFRY ................................................................................ 32 7.1 ÚTOK NA RSAES-OAEP PODLE STANDARDU PKCS #1 V2.0 ........................................... 32 7.1.1 RSAES-OAEP.............................................................................................................. 32 7.1.2 Popis útoku ................................................................................................................. 33 7.2 ÚTOK NA RSAES-OAEP PKCS#1 V2.1 ............................................................................ 34 7.2.1 Popis útoku ................................................................................................................. 34 7.3 ÚTOK NA RSA-KEM ......................................................................................................... 36 7.3.1 Popis H-PKEYKEM, DEM ................................................................................................ 36
4
7.3.2 Popis útoku ................................................................................................................. 36 8.1 KOLIZE V MD5 .................................................................................................................. 38 8.1.1 Úvod............................................................................................................................ 38 8.1.2 Základní postup........................................................................................................... 38 8.1.3 Tunely v MD5.............................................................................................................. 40 8.1.4 Výsledky ...................................................................................................................... 41 8.2 PARALELNÍ HLEDÁNÍ KOLIZÍ V HAŠOVACÍCH FUNKCÍCH ................................................... 42 8.2.1 rho-metoda.................................................................................................................. 42 8.2.2 Dopady paralelního hledání kolizí.............................................................................. 43 8.2.3 Jak modifikovat zprávu beze změny obsahu................................................................ 44 8.3 ÚTOKY POMOCÍ KOLIZÍ ZPRÁV SE STEJNÝM PREFIXEM ..................................................... 45 8.3.1 Jak najít kolizi dvou vstupních zpráv, které mají společný prefix............................... 45 8.3.2 Diamantová struktura ................................................................................................. 45 8.3.3 Útoky s využitím diamantové struktury ....................................................................... 47 8.3.4 Smysluplnost dat ......................................................................................................... 47 9 ÚTOKY NA KRYPTOGRAFICKÉ PROTOKOLY.......................................................... 48 9.1 ČASOVÁ ANALÝZA SSH..................................................................................................... 48 10 PRAKTICKÝ ÚTOK.............................................................................................................. 50 10.1. POPIS IMPLEMENTACE .................................................................................................... 50 10.1.1 Fáze 1 – vybudování diamantové struktury .............................................................. 50 10.1.2 Fáze 2 – Nalezení spojovací zprávy.......................................................................... 50 10.2 MOŽNOSTI MODIFIKACE .................................................................................................. 51 10.3. POUŽITÝ JAZYK A NÁSTROJE .......................................................................................... 51 11 ZÁVĚR................................................................................................................................... 52 12 LITERATURA....................................................................................................................... 53 PŘÍLOHA 1. – POUŽITÉ ALGORITMY.............................................................................. 57 ALGORITMUS PY A PYPY ......................................................................................................... 57 ALGORITMUS AES................................................................................................................... 59 ALGORITMUS RSA .................................................................................................................. 62 ALGORITMUS MD5.................................................................................................................. 62 PŘÍLOHA 2. – TABULKY S PODMÍNKAMI PRO KOLIZE V MD5............................... 64
5
Úvod Kryptografie je v dnešní době velice důležitou součástí každodenního života. Možná si to většina z nás ani neuvědomuje, ale přichází s ní do styku téměř neustále. Kdo z Vás ještě nikdy nevybíral z bankomatu či neplatil platební kartou? Tyto jednoduché operace provázející nás každodenním životem využívají právě kryptografii. Kryptografie se nepoužívá jen u finančních operací, ale pro moderního člověka i u úplně běžných věcí, jako je přihlašování na počítač pod heslem (heslo je v počítači uloženo v zašifrované podobě), posílání emailu (email může být posílán v zašifrované podobě) nebo používání čipových karet v knihovnách, školách, městské dopravě, ... (informace uloženy na kartě jsou často chráněny proti zneužití právě kryptografií). Velké procento lidí má doma počítač, mnoho lidí s ním každý den pracuje na svém pracovišti, mají přístup k internetu a používají email, využívají internetové bankovnictví. Většina z těchto lidí bezmezně těmto službám důvěřuje a ani si neuvědomuje, že k tomu, aby mohli tyto operace provádět, potřebují kryptografii a že bez jejího přispění by si informace v jejich emailech mohl bez problému přečíst kdokoliv. Ovšem je tato důvěra zasloužená? Kryptografie je disciplína, která se zabývá převedením informace do podoby, v níž je tato informace skryta. Jejím úkolem je tedy učinit informaci nečitelnou hlavně v situacích kdy by k ní mohla mít přístup nepovolaná osoba. Obecně slouží k ochraně dat, informací a soukromí osob. Kryptoanalýza je jakýsi „opak“ kryptografie. Jejím hlavním cílem je analýza odolnosti kryptografických systému a hledání metody vedoucí k proniknutí do těchto systémů. [19] Hromadné použití kryptografie přišlo s masovým rozšíření počítačů a následně zpřístupněním Internetu široké veřejnosti. Ovšem historie kryptografie sahá až do 4. tisíciletí před našim letopočtem, kdy ji používali Egypťané. Největší rozvoj a rozmach kryptografie i kryptoanalýzy nastal za první a následně druhé světové války, kdy získání informací od nepřítele sehrálo důležitou roli. V dnešní době je díky počítačům nemyslitelné používat historické šifrovací metody. Díky obrovské výpočetní síle jsou všechny lehce překonatelné útokem hrubou silou, tj. vyzkoušením všech možných kombinací tzv. šifrovacích klíčů. Klíč je vlastní nastavení šifrovacího algoritmu, pomocí použití různých klíčů dostaneme pro stejnou vstupní informaci různý výsledek. Aktuálně se používají takové šifrovací metody, pro které by útok hrubou silou trval velmi dlouho. Právě proto se souběžně rozvíjí i kryptoanalýza, která se snaží najít efektivnější útok než hrubou silou. Každý se jistě zeptá, jestli neexistuje neprolomitelný algoritmus. V současnosti existuje algoritmus, o kterém bylo matematicky dokázáno, že není prolomitelný. Jedná se o takzvanou Vernamovu šifru. Ta ovšem předpokládá, že klíč je stejně dlouhý jako samotná zpráva, a že žádný klíč nebude použitý vícekrát. Toto samozřejmě velmi omezuje možnosti použití této šifry. Proto se momentálně používají tzv. výpočetně bezpečné kryptografické metody, což jsou metody, pro které nejlepší známý útok trvá tak dlouho, že není časově zvládnutelný, a to ať už z důvodu výpočetní náročnosti (provedení útoku trvá řádově desítky let), nebo z důvodu omezené časové platnosti utajované informace (například útok může trvat několik hodin, ale informaci je nutné utajovat jen hodinu). Kryptoanalytici se neustále snaží objevit slabiny používaných kryptografických metod, které by mohly vést k jejich prolomení. Tím se testuje bezpečnost těchto metod. Toto testování je založeno na tzv. Kerckhoffově principu – tj. že žádný algoritmus nesmí být tajný a jedinou
6
utajovanou věcí je šifrovací klíč. Díky tomuto principu je velmi malá šance, že se pro široké použití vybere nekvalitní algoritmus, který někdo brzo prolomí. Každým rokem se objevují nové algoritmy, ke kterým odborná veřejnost prezentuje odhalené slabiny nebo konkrétní útoky, které tento algoritmus prolomí. Cílem této práce je shromáždit a ucelit aktuální výsledky kryptoanalytiků týkající se nejčastěji používaných kryptografických metod, a to jak z oblasti symetrické nebo asymetrické kryptografie. Tato práce se zabývá odolností samotných algoritmů, ne jejich konkrétní implementací do různých hardwarových zařízení. Má se jednat o rozsáhlý (nikoli však vyčerpávající) přehled nejnovějších kryptoanalytických poznatků. Jelikož je kryptologie momentálně na vzestupu a velké množství odborníků prezentuje své výsledky o nejpoužívanějších algoritmech, není možné na takto omezeném prostoru popsat vše, co bylo publikováno. Proto je tato práce zaměřena především na útoky, které mají větší význam z hlediska bezpečnosti pro daný algoritmus.
7
1 Symetrická kryptografie Symetrické šifry jsou asi nejrozšířenější skupinou šifer a mají také velmi dlouho historii, na rozdíl od asymetrických šifer, které se podařilo sestrojit až koncem minulého století. Symetrické šifry používají dvojici klíčů d,e (d – na dešifrování, e – na šifrování), kde z d lze jednoduše odvodit e a naopak. Nejčastěji se d = e, tzn., že je používán stejný klíč pro šifrování i dešifrování. Symetrické šifry lze rozdělit na blokové a proudové symetrické šifry. Blokové symetrické šifry šifrují vstupní text po blocích pevně dané délky. Proudové symetrické šifry šifrují vstupní text bit po bitu, dá se říci, že proudové šifry jsou vlastně blokové šifry s velikostí bloku jeden bit.
1.1 Proudové šifry Proudové šifry jsou důležitou třídou šifrovacích algoritmů. Šifrují individuálně znaky (obvykle bity) vstupní zprávy jeden po druhém, přičemž používají šifrovací transformace, které se mění v čase. Na rozdíl od blokových šifer, které současně šifrují skupinu znaků vstupního textu a používají fixní šifrovací transformaci. Proudové šifry jsou obecně rychlejší než blokové šifry, pokud je použito hardwarové řešení, protože mají mnohem jednoduší hardwarové obvody. Jsou mnohem vhodnější, v některých speciálních případech (například v některých telekomunikačních aplikacích), když je vyrovnávací paměť příjemce limitována, nebo když znaky musí být zpracovávány individuálně, tak jak jsou přijímány. Protože mají omezenou nebo dokonce žádnou propagaci chyby, proudové šifry můžou také být výhodné v situacích, kdy jsou chyby v přenosu vysoce pravděpodobné. U blokových šifer je během celého šifrování použita neustále stejná funkce pro zašifrování všech bloků, takže (čisté) blokové šifry jsou bez paměti. Proudové šifry, na rozdíl od blokových, zpracovávají vstupní text v blocích tak malých, jako je jediný bit a šifrovací funkce se může měnit v průběhu zpracovávání vstupního textu, takže proudové šifry mají paměť. Někdy jsou nazývány stavové šifry protože šifrování závisí nejen na klíči a na vstupním textu, ale i na okamžitém stavu. Tento rozdíl mezi blokovými a proudovými šiframi není vymezující, přidáním trochy paměti do blokové šifry (jako se používá v CBC módu) vyústí do proudové šifry s velkými bloky. [17, 18]
1.1.1 Synchronní proudové šifry Synchronní proudové šifry jsou ty, jejichž klíč je generován nezávisle na vstupní zprávě nebo šifře. Šifrovací proces synchronních proudových šifer se dá zapsat následovně: σi+1 = f(σi, k) zi = g(σi, k) ci = h(zi, mi), kde σ0 je počáteční stav, který může být odvozen z klíče k, f je funkce určující další stav, g je funkce produkující klíčový proud zi a h je výstupní funkce (typicky exkluzivní součet), která kombinuje klíčový proud se vstupním textem mi a produkuje šifru ci, viz Obr.1. OFB mód blokové šifry se také dá považovat za příklad synchronní proudové šifry. [17]
8
Obr 1: Diagram šifrování a dešifrování synchronních proudových šifer
Vlastnosti synchronních proudových šifer: 1. Požadavek na synchronizaci – při použití synchronní šifry musejí být oba uživatelé, příjemce i odesilatel, synchronizovaní. Musejí používat stejný klíč a operace na stejných pozicích (ve stejných stavech), aby zajistili správné dešifrování. Jestliže je synchronizace ztracena, některé části zašifrované zprávy jsou ztraceny nebo nějaké jiné části jsou během přenosu přidány, tak dešifrování zhavaruje a do správného stavu je možné se dostat jen pomocí dodatečné techniky re-synchronizace. Technika re-synchronizace obsahuje proces re-inicializace, vkládání speciálních značek v pravidelných intervalech do šifrového textu, nebo pokud vstupní text obsahuje dostatečně redundance vyzkoušení všech možných offsetů klíčového proudu. 2. Žádná propagace chyby – pokud se změní (ne smaže) část šifrového textu během přenosu, tak tato chyba nemá žádný efekt na zbytek zprávy. tzn. až na chybnou část se zpráva dešifruje správně. [17]
1.1.2 Samočinně synchronní proudové šifry Samočinně synchronní nebo také asynchronní proudové šifry jsou ty, u kterých je klíčový proud generován jako funkce klíče a fixního počtu předchozích čísel šifrového textu. Šifrovací funkce samočinně synchronních proudových šifer lze zapsat následovně: σi = f(ci-t, ci-t+1, ci-t+2, ..., ci-1) zi = g(σi, k) ci = h(zi, mi), kde σ0 = (c-t, c-t+1, c-t+2, ..., ci-1) je (veřejný) iniciální stav, k je klíč, g je funkce která produkuje klíčový proud zi a h je výstupní funkce, která kombinuje klíčový proud zi a vstupní text mi a produkuje šifrový text ci, viz. Obr.2. [17]
Obr. 2: Diagram šifrování a dešifrování samočinně synchronních šifer
9
Vlastnosti samočinně synchronních proudových šifer: 1. Samočinná synchronizace – samočinná synchronizace je možná, i když jsou některé části šifrového textu smazány nebo nějaké nové vloženy, protože dešifrování závisí na fixním počtu předcházejících znaků šifrového textu. Takže šifra je schopná znovu zavést správné dešifrování automaticky po ztrátě synchronizace jenom s fixním počtem nedešifrovaných znaků zprávy. 2. Omezená propagace chyby – víme, že stav samočinně synchronní šifry závisí na t předchozích znacích šifrového textu. Jestliže je jeden znak šifrového textu změněn (smazán nebo vložen nový) během přenosu, pak dešifrování až t dalších znaků může být nesprávné, dále však následují správně dešifrované znaky zprávy. 3. Difůze statistik vstupního textu – jelikož každý znak šifrového textu ovlivní celý následující šifrový text (každý šifrový znak je použit pro generování následujícího klíčového proudu), tak statistické vlastnosti vstupního text jsou rozprostřeny do celého šifrového textu. Takže samočinně synchronní proudové šifry jsou odolnější proti útokům založeným na redundanci vstupního textu než synchronní proudové šifry. [17]
1.2 Blokové šifry – symetrické Symetrické blokové šifry jsou nejvýznamnějším a nejdůležitějším prvkem mnoha kryptografických systémů. Samy o sobě poskytují možnost utajení. Jako základní stavební kámen umožňují konstrukci pseudonáhodných generátorů čísel, proudových šifer, hašovacích funkcí a MAC (Message Authentication Code). Mohou také sloužit jako ústřední komponenta pro ověřování zpráv, zajištění integrity dat a ověřování entit. Žádná bloková šifra není dokonale vhodná pro všechna aplikační použití, a to i když nabízí vysoký stupeň zabezpečení. Je to dáno různými nároky, v různých aplikacích je třeba brát ohled na jiné vlastnosti jako jsou: rychlost šifrování, velikost využité paměti, použité módy šifrování nebo podmínky nutné pro implementaci na konkrétní hardware. Vždy je třeba zvolit vhodný kompromis mezi takovými požadavky a bezpečím proti útokům.[17,18]
Blokové šifry – definice Bloková šifra je funkce, která zobrazí b-bitové bloky vstupního textu do n-bitových bloků šifrového textu. Číslo n je nazýváno velikost bloku. Může být brána jako jednoduchá substituční šifra s velkou velikostí znaku. Funkce je parametrizována k-bitovým klíčem K z množiny Қ (klíčový prostor) všech možných k-bitových vektorů VK. Obecně je klíč z této množiny vybírán náhodně. Použití stejné velikosti bloků vstupního a výstupního textu zabraňuje expanzi dat. Aby byla umožněno unikátní šifrování, tak šifrovací funkce musí být invertovatelná. Pro n-bitové bloky vstupního a výstupního textu a fixní klíč musí být šifrovací funkce bijekcí, definující permutaci na n-bitovém vektoru. Každý klíč potenciálně definuje jinou bijekci. Počet klíčů je roven |Қ|, a efektivní velikost klíče je lg|Қ|, toto je délka klíče, jestliže všechny k-bitové vektory z Қ jsou platné klíče. Jestliže jsou všechny klíče stejně pravděpodobné a každý definuje rozdílnou bijekci, pak se entropie klíčového prostoru rovná taktéž lg|Қ|. [17, 18, 19]
10
Vlastnosti blokových šifer Velikost klíče – efektivní bitová délka klíče, nebo lépe entropie klíčového prostoru, definuje horní hranici bezpečnosti dané šifry(na tom závisí rychlost útoku hrubou silou). Delší klíče typicky znamenají nějakou nadbytečnou cenu, jako je složitější generování, přenos a uložení. Rychlost šifrování – rychlost šifrování závisí na složitosti kryptografického zobrazení a na tom, jak moc je toto zobrazení přizpůsobeno konkrétní implementaci nosiče nebo platformy. Velikost bloku – velikost bloku ovlivňuje jak bezpečnost (větší je lepší), tak složitost (větší je náročnější na implementaci). Složitost kryptografického zobrazení – složitost algoritmu ovlivňuje cenu implementace jak z hlediska vývoje a zdrojů, tak i z hlediska rychlosti a výkonnosti samotného šifrování v reálném čase. Expanze dat – obecně je vhodné, a v některých případech dokonce nutné, aby se při šifrování nezvětšovalo množství dat (aby neprobíhala expanze dat). Ovšem přesto některé techniky, jako jsou například homophonická substituce(každý znak je nahrazen jedním z množiny 100 znaků, tak aby výsledná pravděpodobnost výskytu každého znaku byla 1%) nebo technika náhodného šifrování (vstupní text je nedeterministicky zašifrován na jeden z možných šifrových textů, dešifrování již, ale probíhá deterministicky), mají za výsledek expanzi dat. Propagace chyby – dešifrování šifrového textu obsahující chybu v jediném bitu může vyústit v rozdílný efekt na výsledný text, podle toho jaký algoritmus byl použit. Propagaci chyby ovlivňuje například délka bloku a použitý mód.[17]
Výhody symetrické kryptografie 1. Symetrické šifry mohou být navrženy pro rychlejší šifrování dat, u některých hardwarových řešení se jedná i o stovky megabitů za sekundu. 2. Klíče pro symetrické šifry jsou relativně krátké. 3. Symetrické šifry mohou být použity jako základ pro další různé kryptografické mechanizmy jako jsou generátory pseudonáhodných čísel, hašovací funkce a podobně. 4. Symetrické šifry mohou být kombinovány a skládány do sebe, čímž zvyšují zabezpečení šifrového textu.
Nevýhody symetrické kryptografie 1. Při komunikaci dvou entit musí zůstat klíč tajemstvím na obou stranách. 2. Ve velké síti je třeba mít uloženo velké množství párů klíčů. 3. Při komunikaci mezi dvěmi entitami je konvencí měnit často klíče, optimální je mít nový klíč pro každou komunikační relaci, což může být poněkud komplikované, jelikož přenos klíče vyžaduje zabezpečený kanál.
Módy šifrování pomocí blokových šifrovacích algoritmů Blokové šifry šifrují vstupní text do bloků s pevnou bitovou délkou n. Zprávy, které mají více jak n bitů, se jednoduše rozdělí na n-bitové bloky a ty se pak postupně šifrují. Podle
11
způsobů šifrování se rozlišuje několik módů. Základní módy jsou ECB(electronic-codebook), CBC(cipher-block chaining), CFB(cipher feedback) a OFB(output feedback). V následujícím textu EK označuje šifrovací funkcí blokové šifry E parametrizovanou klíčem K, EK-1 označuje dešifrování. Vstupní text x = x1, x2, x3, ... xt se skládá z n-bitových bloků pro módy ECB a CBC nebo r-bitových bloků pro módy CFB a OFB pro pevně dané r ≤ n. [17]
1.2.1 Mód ECB ECB mód je nejjednodušším a také nejpřirozenějším způsobem šifrování pomocí blokové šifry. Při tomto módu je každý blok šifrován zcela nezávisle na ostatní blocích zprávy. To znamená, že pokud jsou ve vstupním textu dva stejné bloky, pak i jejich odpovídající bloky v šifrovém text budou stejné. [17] Pro vstupní text x = x1, x2, x3, ... xt s n-bitovými bloky, šifrový text c = c1, c2, c3, ... ct s n-bitovými bloky a k-bitový klíč K je šifrování a dešifrování ukázáno na Obr.3.
Obr. 3: Diagram ECB
Šifrování bloku j, kde 1≤ j ≤ t probíhá: cj = EK(xj). Dešifrování bloku j, kde 1≤ j ≤ t probíhá: xj = EK-1(cj).
Vlastnosti módu ECB: 1. Identické bloky vstupního textu (při použití stejného klíče) vyústí ve stejné bloky šifrového textu. 2. Bloky jsou šifrovány a dešifrovány zcela nezávisle na ostatních blocích. Změna pořadí bloků ve vstupním textu se odrazí ve změně pořadí bloků v šifrovém textu. 3. Propagace chyby – jedno nebo více bitová chyba v jednom bloku šifrového textu ovlivní dešifrování právě jen tohoto bloku. [17, 18]
12
Použití ECB módu: Jelikož bloky šifrového textu jsou nezávislé, tak náhodné či podloudné nahrazení jednoho bloku šifrového textu neovlivní dešifrování ostatních bloků. Kromě toho, blokové šifry v ECB módu neskrývají modely dat – identické bloky šifrového textu znamenají identické bloky v šifrovém textu. Z tohoto důvodu se ECB mód nedoporučuje pro zprávy delší jak jeden blok. Bezpečnost tohoto módu může být částečně zvýšena přidáním náhodných bitů ke každému bloku. [17]
1.2.2 Mód CBC Bloková šifra v CBC módu již nešifruje bloky nezávisle na sobě, ale před zašifrováním každého bloku provede XOR tohoto bloku s předchozím blokem šifrového textu. Z toho důvodu závisí zašifrovaná podoba každého bloku na všech předcházejících blocích. [17, 18] Pro vstupní text x = x1, x2, x3, ... xt s n-bitovými bloky, šifrový text c = c1, c2, c3, ... ct s n-bitovými bloky, n-bitovou inicializační hodnotu IV (ta nemusí být tajná) a k-bitový klíč K je šifrování a dešifrování ukázáno na Obr.4.
Obr. 4: Diagram CBC
Šifrování bloku j, kde 1≤ j ≤ t probíhá: cj = EK(cj-1⊕xj), c0 je IV(inicializační hodnota). Dešifrování bloku j, kde 1≤ j ≤ t probíhá: xj = cj-1⊕EK-1(cj), c0 je IV(inicializační hodnota)
Vlastnosti CBC módu: 1. Stejné bloky vstupního textu vyústí v stejné bloky šifrového textu(za předpokladu, že používáme stejný klíč) pouze pokud bude shodná i IV použitá pro tyto bloky. Obecně díky řetězení IV, klíče a šifrovaného bloku stejné bloky ve vstupním textu mají různé bloky
13
v šifrovém textu, tzn. dvou blokům vstupního textu, které jsou zcela identické a jsou zašifrovány stejným klíčem, odpovídají různé bloky šifrového textu. 2. Řetězící mechanizmus způsobuje, že blok cj šifrového textu nezávisí jen na bloku xj vstupního textu, ale i na všech předešlých blocích vstupního textu. Z tohoto důvodu znamená přeskládání bloků vstupního textu rozdílný šifrový text. Správné dešifrování nějakého bloku závisí na správném dešifrování bloku předchozího. 3. Propagace chyby – jednobitová chyba v bloku cj šifrového textu ovlivní dešifrování cj a cj+1. Blok x'j dešifrovaný z cj je s největší pravděpodobností zcela náhodný, ovšem blok x'j+1 má jednobitovou chybu přesně na tom stejném místě jako měl blok cj. Pokud je tato chyba v bloku x'j+1 rozpoznána, je možné podle ní opravit i chybu v bloku cj a tím umožnit správné dešifrování všech bloků. 4. Oprava chyb – CBC mód je samočinně synchronní ve smyslu toho, že pokud se objeví chyba v bloku cj, ale ne v blocích cj+1 a cj+2, pak je blok xj+2 dešifrován správně. [17, 18]
1.2.3 Mód CFB CBC mód pracuje s bloky vstupního textu n-bitů, ale některé aplikace vyžadují r-bitové jednotky vstupního textu, které musí být zašifrovány a odeslány bez zdržení, pro nějaké pevně dané r ≤ n (často r = 1 nebo r = 8). V tomto případě může být použit mód CFB. [17] Pro vstupní text x = x1, x2..., xt s r-bitovými bloky, šifrový text c = c1, c2..., ct s r-bitovými bloky, n-bitovou inicializační hodnotu IV a k-bitový klíč K se dá šifrování a dešifrování zapsat takto: Šifrování bloku j, kde 1≤ j ≤ t probíhá v několika krocích: a) Oj = EK(Ij) – spočítání výstupu blokové šifry, Ij je vstupní hodnota v posuvném registru b) tj = r levých krajních bitů Oj c) cj = xj ⊕ tj – odeslání r-bitového bloku cj d) Ij+1 = 2r * Ij + cj mod 2n – posun cj na pravý konec posuvného registru Ij+1 Počáteční inicializace I je: I1 = IV Dešifrování bloku j, kde 1≤ j ≤ t probíhá také v několika krocích: Výpočet tj, Oj a Ij jsou stejné jako při šifrování, tzn.: a) viz výše. b) viz výše. c) xj = cj ⊕ tj d) viz výše.
Vlastnosti módu CFB: 1. Stejně jako u CBC módu i u módu CFB se díky řetězení zašifrují stejné bloky vstupní zprávy do různých bloků šifrové zprávy, přičemž stejně jako u CBC není potřeba tajit inicializační hodnotu IV. 2. Stejně jako u módu CBC řetězící mechanizmus zajišťuje, že blok cj šifrového textu závisí jak na bloku xj vstupního textu, tak i na všech blocích předcházejících. Pro správné dešifrování
14
daného bloku je třeba, aby předcházejících [n/r] bloků šifrového textu bylo bez chyby. To totiž znamená, že posuvný registr obsahuje správnou hodnotu. 3. Propagace chyby – jedno nebo více bitová chyba v jednom r-bitovém bloku šifrového textu ovlivní dešifrování tohoto bloku i dalších [n/r] bloků šifrového textu (po dešifrování těchto bloků je konečně chybový blok vyřazen z posuvného registru). Obnova chyby je možná stejně jako u CBC módu. 4. Oprava chyb – CFB mód je samočinně synchronní a na obnovení potřebuje [n/r] bloků. 5. Výkon – pro bloky r < n výkon klesá, jelikož každým zavoláním funkce E je zašifrován nebo dešifrován jen blok délky r. [17]
1.2.4 Mód OFB OFB mód je používaný v aplikacích, ve kterých musí být zachycena každá chyba(způsobená přenosem) v šifrovém textu. Tento mód se podobá módu CFB, jelikož umožňuje šifrovat různě dlouhé bloky, ale liší se v blokovém výstupu šifrovací funkce E, který slouží jako zpětná vazba. Jsou obvyklé dvě verze OFB módu. OFB mód s úplnou zpětnou vazbou a OFB mód s r-bitovou zpětnou vazbou. [17] Pro vstupní text x = x1, x2..., xt s r-bitovými bloky, šifrový text c = c1, c2..., ct s r-bitovými bloky, n-bitovou inicializační hodnotu IV a k-bitový klíč K K se dá šifrování a dešifrování zapsat takto: Šifrování bloku j, kde 1≤ j ≤ t probíhá v několika krocích: a) Oj = EK(Ij) – spočítání výstupu blokové šifry, Ij je vstupní hodnota v posuvném registru b) tj = r levých krajních bitů Oj c) cj = xj ⊕ tj – odeslání r-bitového bloku cj d) Ij+1 = Oj – obnovení vstupu pro další blok Počáteční inicializace I je následující: I1 = IV Dešifrování bloku j, kde 1≤ j ≤ t probíhá také v několika krocích: Výpočty tj, Oj a Ij jsou stejné jako při šifrování., tzn.: a) viz výše. b) viz výše. c) xj = cj + tj d) viz výše. Pro vstupní text x = x1, x2..., xt s r-bitovými bloky, šifrový text c = c1, c2, ... ct s r-bitovými bloky, n-bitovou inicializační hodnotu IV a k-bitový klíč K probíhá šifrování a dešifrování bloku j, kde 1≤ j ≤ t skoro stejně jak jako u OFB módu s plnou zpětnou vazbou až na rozdíl v kroku, kde se počítá následující hodnota posuvného registru: d) Ij+1 = 2r * Ij + tj mod 2n – posun výstupu tj na pravý konec posuvného registru Ij+1
15
Vlastnosti Módu OFB: 1. Stejně jako CBC a CFB módy, dva stejné bloky vstupního textu nejsou šifrovány do dvou stejných bloků šifrového textu pokud nejsou použity stejné IV. 2. Klíčový proud je zcela nezávislý na vstupním textu. 3. Propagace chyby – jedno nebo více bitová chyba v kterémkoliv bloku cj šifrového textu ovlivní jen tento blok. Navíc se tato chyba objeví jen na odpovídacích místech ve výsledném textu, takže je možno tyto chyby zpětně opravit. 4. Oprava chyb – OFB mód umožňuje obnovit bitové chyby v šifrovém textu, ale nemůže se sám sesynchronizovat po úplné ztrátě některého bloku. V tomto případě je nutná explicitní obnova synchronizace. 5. Výkon – výkon stejně jako u CFB módu klesá. Ovšem díky tomu, že klíčový proud nezávisí ani na vstupním text ani na šifrovém textu, tak může být přepočítán, což umožní určité zrychlení. [17]
16
2 Asymetrická kryptografie V systémech využívajících asymetrickou kryptografii má každá entita A svůj veřejný klíč e a odpovídající soukromý klíč d. Pokud by měl být systém dokonale bezpečný, pak by problém odvození odpovídajícího soukromého klíče d ze známého veřejného klíče e měl být nemožný. V realitě se ale používají systémy založené na nějakém výpočetně velice složitém problému, takže odvození d ze známého e není nemožné, ale jen výpočetně velice složité a náročné. Veřejný klíč definuje šifrovací transformaci Ee a soukromý klíč definuje odpovídající dešifrovací transformaci Dd. Jakákoliv entita B, která chce poslat zprávu m entitě A, obdrží ověřenou kopii veřejného klíče e, použije šifrovací transformaci a obdrží šifrový text c = Ee(m), a pošle c entitě A. Aby entita A dešifrovala šifrový text c použije dešifrovací transformaci a obdrží tak otevřený text zprávy m = Dd(c). Veřejný klíč není třeba uchovávat v tajnosti a z toho důvodu může být veřejně dostupný, jenom je třeba zaručit jeho ověření k entitě A, která má příslušný odpovídající soukromý klíč. Hlavní výhodou asymetrické kryptografie je, že zaručit ověření veřejného klíče je mnohem jednoduší než distribuce tajných klíčů, která je potřebná v případě symetrické kryptografie. Navíc při vzájemné komunikaci n stran není potřeba n*(n-1)/2 klíčů jako u symetrické kryptografie, ale jen 2n klíčů. Hlavním cílem systémů používajících asymetrickou kryptografii je zajištění utajení a důvěrnosti. Jelikož jsou šifrovací transformace i veřejný klíč veřejně známé, pak šifrování pomocí veřejného klíče nezaručuje ověření zdroje dat nebo jejich integritu. Tyto vlastnosti musí být zabezpečeny použitím dalších technik jako jsou ověřovací kódy a digitální podpis. Asymetrická kryptografie je bohužel o dost pomalejší než symetrická kryptografie. Z tohoto důvodu se asymetrická kryptografie nejčastěji používá na přenosy klíčů pro symetrickou kryptografii, která bude následně použita pro přenos dat a zaručení ostatních bezpečnostních opatření jako je právě ověření dat a jejich integrita, nebo například při challenge-response protokolů využívaných ke vzdálenému přihlašování a přístupu k internetovému bankovnictví. [17, 18]
Výhody asymetrické kryptografie 1.V tajnosti musí být udržován pouze privátní klíč, u veřejného stačí, pokud je garantována jeho autenticita. 2. Podle způsobu použití mohou být dvojice soukromý/veřejný klíč používány po delší dobu (například několik relací, nebo i několik let). 3. Většina asymetrických šifer umožňuje relativně účinný mechanizmus digitálního podpisu. 4. I ve velké síti je počet uložených klíčů mnohem menší než u symetrické kryptografie.
Nevýhody asymetrické kryptografie 1. Rychlost šifrování nejčastěji používaných algoritmů je mnohem menší než v případě symetrické kryptografie. 2. Velikosti klíčů jsou většinou mnohem větší než jaké vyžadují algoritmy symetrické kryptografie.
17
3. U žádné asymetrické šifry nebylo dokázáno, že je bezpečná (to stejné se dá ovšem říct i o symetrických šifrách). Nejlepší asymetrické šifry mají bezpečnost založenou na nějakém problému teorie čísel.
18
3 Hašovací funkce Hašovací funkce jsou jedním ze základních prvků moderní kryptografie, často jsou nazývány jednosměrné hašovací funkce. Hašovací funkce je účinně navržená funkce zobrazení binárních řetězců neomezené délky na binární řetězce nějaké fixní délky, nazývané haš hodnota. Pro ideální hašovací funkci, která má n-bitovou haš hodnotu, je šance ,že náhodně vybraný řetězec bude zobrazen na konkrétní haš hodnotu 2-n. Základní idea hašovacích funkcí je, že haš hodnota by měla sloužit jako kompaktní reprezentant vstupního řetězce. Hašovací funkce vhodná k použití v kryptografii je většinou zvolena tak, že je výpočetně velmi složité najít dva různé vstupní řetězce, které mají stejnou haš hodnotu. Pokud se podaří takové dva řetězce najít říkáme, že jsme našli kolizi. Stejně tak by mělo být výpočetně velmi složité najít pro nějakou haš hodnotu odpovídající vstupní řetězec. Použití hašovacích funkcí slouží nejčastěji ke kontrole integrity dat a při digitálním podepisování dat. [17, 18]
19
4 Generátory náhodných čísel V mnoha aplikacích je třeba bezpečně vygenerovat nepředvídatelné údaje. V kryptografii je nejčastější použití při generování hesel (v případě symetrických šifer) nebo jejich částí (v případě RSA se generují prvočísla p,q). K tomuto účelu se právě používají generátory (pseudo)náhodných čísel. Generátory (pseudo)náhodných čísel jsou také důležitou součástí kryptografických protokolů (nejčastěji challenge-responce). Mnoho protokolů využívá během svého průběhu náhodně generované sekvence nebo čísla. Náhodnost je vyžadována z bezpečnostních důvodů, aby potencionální útočník neměl možnost jakkoliv předpovědět využitou sekvenci nebo číslo. Generátor náhodný bitů je algoritmus nebo zařízení, jehož výstupem jsou statisticky nezávislá a neodvoditelná binární čísla. Generátor pseudonáhodný bitů je deterministický algoritmus, jehož výstupem je sekvence bitů, která se jeví náhodně, ovšem je založena na vstupu do generátoru, který se nazývá seed. Ovšem výstup z takového generátoru však není náhodný a pokud útočník je schopen zjistit nebo odvodit seed, pak je schopen zjistit tuto pseudonáhodnou sekvenci. Proto se jako seed používá krátká opravdu náhodná sekvence, která se použitím pseudonáhodného generátoru rozšíří na sekvenci dostatečně dlouhou. Pro bezpečnost generátoru je velice důležité, aby z předchozích čísel sekvence nešla odvodit čísla, která mají následovat.
20
5 Útoky na proudové symetrické šifry 5.1 Diferenciální kryptoanalýza Py, Pypy Biham a Seberry představili proudovou šifru Py [44], která vychází z návrhu RC4. Py je jedna z nejrychlejších proudových šifer pro 32-bitové procesory. Proudová šifra Pypy [44] je úprava šifry Py odolná proti Distinguishing attack. Od Py se liší tím, že je zahozena polovina výstupů, tzn. první výstup z každých dvou výstupů v každém kroku je zahozen. Py a Pypy byly vybrány jako kandidátní šifry do fáze 2 ECRYPT eSTREAM project. Inicializace Py a Pypy jsou shodné a právě fáze inicializace má několik bezpečnostních nedostatků, které znamenají, že obě tyto šifry jsou překonatelné pomocí diferenciální kryptoanalýzy. Tyto nedostatky vedou k tomu, že dva klíčové proudy mohou být stejné jestliže je klíč použit s některou z 216 IV, které mají speciální rozdíly. Je to velice reálná hrozba, protože množina IV potřebných pro útok se může objevit v aplikacích používajících Py a Pypy s velkou pravděpodobností. [43]
5.1.1 Identické klíčové proudy IV je použita pouze ve fázi nastavení IV. Na začátku fáze nastavení IV je použito pouze 15 bitů z IV (iv[0] a iv[1], nejméně význačný bit iv[1] není použit) k inicializaci pole P a proměnné s. Pro dvojice IV, které mají těchto 15 bitů shodných je i výsledné pole P shodné. Označme si následující kód jako algoritmus A: for(i=0; i
21
IV rozdílné ve dvou bytech Přepokládejme dvě IV iv1 a iv2 rozdílné ve dvou po sobě jdoucích bytech s iv1[i] ⊕iv2[i]=1, nejméně význačný bit iv1[i] je 1, iv1[i+1] ≠ iv2[i+1] (1 ≤ i ≤ ivsizeb - 1) a iv1[j] = iv2[j] pro 0 ≤ j < i a i+1 < j ≤ ivsizeb-1. Projdeme algoritmus A a ukážeme jak rozdíly v iv ovlivní s a EIV. Na konci i-tého kroku algoritmu A EIV1[i] ≠ EIV2[i]. Nechť β1 = EIV1[i] a β2 = EIV2[i]. Dostaneme, že s1 – s2 = 0x100 + δ1, kde δ1 = (β1 ⊕ x) – (β2 ⊕ x), a x je s otočené o 8 bitů. V dalším kroku platí iv1[i+1] ≠ iv2[i+1], jestliže iv2[i+1] – iv1[i+1] = δ1, a s1, s2 se stanou shodnými s vysokou pravděpodobností. Z pozorování provedeného v [43] je tato pravděpodobnost pi = 2-10.6. Jestliže, s1 = s2, pak EIV1[i+1] = EIV2[i+1], a v následujících krocích i+2, i+3, ..., i+ivsizeb-1 v algoritmu A zůstanou s1 a s2 stejné a EIV1[j] = EIV2[j] pro j ≠ i. Po algoritmu A jsou iv[i] a iv[i+1] znovu použity k aktualizaci s a EIV v algoritmu B. Na konci i-tého kroku algoritmu B platí EIV1[i] = EIV2[i] s pravděpodobností 1/255. Nechť γ1 = s01 a γ2 = s02. Jestliže EIV1[i] = EIV2[i], tak platí γ2 - γ1 = β1 – β2. Na konci tohoto kroku s1 – s2 = 0x100 + δ2 , kde δ2 = (γ1 ⊕ y) - (γ2 ⊕ y) a y je ROTL32(s,8). Na konci dalšího kroku, jestliže iv2[i+1] – iv1[i+1] = δ2, se stanou s1 a s2 shodnými s vysokou pravděpodobností. Poznamenejme, že iv2[i+1] – iv1[i+1] = δ1 a δ1, δ2 korelují, takže iv2[i+1] – iv1[i+1] = δ2 s pravděpodobností větší než 2-8. Pravděpodobnost p1’, že s1 = s2 je podle provedeného pozorování 2-5,6. Jakmile jsou dvě hodnoty s stejné, EIV1[i+1] = EIV2[i+1], tak ve všech následujících krocích i+2, i+3, ..., i+ivsize-1 algoritmu B platí s1 = s2 a EIV1[i+2] = EIV2[i+2], EIV1[i+3] = EIV2[i+3], ..., EIV1[i+ ivsize-1] = EIV2[i+ ivsize-1]. To znamená, že po použití IV na aktualizaci s a EIV, nastane situace s1 = s2 a EIV1 = EIV2 s pravděpodobností p1 * 1/255 * p1’ = 2-24,2. Jelikož je IV je použita jen v algoritmech A a B, takže jakmile po skončení algoritmu B platí s1 = s2 a EIV1 = EIV2, tak je jisté, že tyto dva klíčové proudy budou stejné. [43]
IV rozdílné ve třech bytech Stejně jako byla v předchozí části popsána možnost použít byte i a i+1 z IV, tak lze podobně použít ještě třetího bytu a to i+4. Při použití třech bytů IV je pravděpodobnost vytvoření stejného klíčového proudu přibližně 2-23. [43]
5.1.2 Útok na Py a Pypy pomocí kolizí ve vnitřním stavu Prezentované bezpečnostní nedostatky vedou k tomu, že na Py a Pypy je možné provést útok na odhalení klíče. Důležitou roli zde právě hrají kolize ve vnitřním stavu. Tento útok má dvě fáze:
Fáze 1: Obnovení časti pole Y Předpokládejme IV rozdílné ve dvou bytech, tzn. kolize se objeví s pravděpodobností 2-23,2. Napřed použijeme algoritmus A ze kterého se pokusíme získat část pole Y a poté se pokusíme získat další části z algoritmu B. P JE ZNÁMÉ PROČ? Pro ivm si označme s na konci j-tého kroku jako sjm, nejméně význačný bit označme jako sj,0m a nejvýznačnější bit jako sj,3m.
22
Označme ε jako možný binární přenos, který má hodnotu 0 s pravděpodobností 0,5 a B(x) je funkce, která vrátí nejméně význačný bit x. Jestliže jsou klíčové proudy shodné, pak víme: si1 + iv1[i+1] = si2 + iv2[i+1] (1) Z algoritmu A víme: si = ROTL32(si-1 + iv[i] + Y(-3 + i),8) ⊕ P(B(si-1 + iv[i] + Y(-3 + i))) (2) Z těchto rovností dostaneme: si,0 = P((B(si-1 + iv[i] + Y(-3 + i))) ⊕ B(si-1,3 + Y(-3 + i) + εi) (3) a (si1 – si,02) – (si2 –si,02) = (iv1[i] – iv2[i]) << 8 = 256, (4) -15 kde (4) platí s pravděpodobností 1- 2 . Z (1), (3) a (4) odvodíme: (P(B(si-1,01 + iv1[i] + Y-3 + i,0)) ⊕ B(si-1,31 + Y-3 + i,3 + εi,1)) + 25 + iv1[i+1] = = (P(B(si-1,02 + iv2[i] + Y-3 + i,0)) ⊕ B(si-1,32 + Y-3 + i,3 + εi,2)) + iv2[i+1], (5) kde εi,1 = εi,2 s pravděpodobností 1-2-15, takže v následujícím textu budeme εi,1, εi,2 označovat εi. Označme si ivθ jako pevnou IV s prvními i byty shodnými se všemi IV lišícími se pouze v iv[i] a iv[i+1]. Takže si-1,02 = si-1,01 = si-1,0θ a si-1,32 = si-1,31 = si-1,3θ. Podle tohoto se rovnost (5) přepsat následovně: (P(B(si-1,0θ + iv1[i] + Y-3 + i,0)) ⊕ B(si-1,3θ + Y-3 + i,3 + εi)) + 25 + iv1[i+1] = (6) = (P(B(si-1,0θ + iv2[i] + Y-3 + i,0)) ⊕ B(si-1,3θ + Y-3 + i,3 + εi)) + iv2[i+1] Použitím jiné dvojice IV lišícími se v iv[i] a iv[i+1] s prvními i byty shodnými s ivθ, které mají kolizi ve vnitřních stavech, dostaneme další rovnost (6). Předpokládejme tedy, že je k dispozici několik rovností (6). Z množiny těchto rovností lze odvodit hodnoty B(si-1,0θ + Yθ 3+i,0) a B(si-1,3 + Y-3+i,3 + εi). V [43] je ukázáno, že pokud budeme mít k dispozici více jak 5 těchto rovností, tak je velmi malá šance, že odvozené hodnoty budou špatně. Po odvození několika po sobě jdoucích hodnot B(si-1,0θ + Y-3+i,0) a B(si-1,3θ + Y-3+i,3 + εi) jsme schopni zjistit část informací o poli Y. Z hodnot B(si-1,0θ + Y-3+i,0) a B(si-1,3θ + Y-3+i,3 + εi) a rovnosti (3) jsme schopni určit hodnotu si,0θ a následně jsme také schopni z hodnot B(si-1,0θ + Y-3+i,0) a B(si-1,3θ + Yθ 3+i,3 + εi) a si,0 určit Y-3+i+1,0. [43] Postup jak vygenerovat dostatečné množství rovností (6) je uveden v [43].
Fáze 2: Získání klíče Ve fázi 1 odhalíme hodnoty Y-3+1,0 a Y256-i,0 pro 2 < i < ivsize-2. Nyní odvodíme 15ti bitovou tajnou informaci v P využitím eliminace rozdílů i EIV. Označme siθ v algoritmu A jako siA,θ a siθ v algoritmu B jako siB,θ. Pro dvě IV lišící se jen v iv[i] a iv[i+1] a generující shodný klíčový proud, spočítáme EIV1A[i], EIV2A[i], EIV1B[i] a EIV2B[i] následujícím způsobem: (7) EIV1A[i] = (P(B(si-1,0A, θ + iv1[i] + Y-3+i,0)) EIV2A[i] = (P(B(si-1,0A, θ + iv2[i] + Y-3+i,0)) (8) B A B, θ EIV1 [i] = EIV1 [i] + (P(B(si-1,0 + iv1[i] + Y-3 + i,0)) (9) (10) EIV2B[i] = EIV2A[i] + (P(B(si-1,0B, θ + iv2[i] + Y-3 + i,0)) Jelikož jsou dva klíčové proudy shodné, pak platí: EIV2B[i] = EIV1B[i] (11) B(si-1,0A, θ + iv1[i] + Y-3 + i,0) a B(si-1,0B, θ + iv1[i] + Y256-i,0) jsou určeny při zjišťování částí Y z algoritmů A a B. Z rovností (7), (8), (9), (10) a (11) je odhaleno 8 bytů z P. Existuje asi 7
23
dvojic IV, které generují shodné klíčové proudy pro každou hodnotu i, takže můžeme zjistit všechny byty z P. Pro odhalení klíče použijeme následující část algoritmu z fáze nastavení klíče: for(i=YMININD, j=0; i<=YMAXIND; i++) { s = s + key[j]; s0 = internal_permutation[s&0xFF]; Y(i) = s = ROTL32(s, 8) ⊕ (u32)s0; j = (j+1) mod keysizeb; } Pojmenujme uvedenou část jako algoritmus C. Z algoritmu C dostáváme následující rovnost: B(Y-3+i,0 + key[i+1 mod keysizeb] + εi’) ⊕ P’(B(Y-3+i+3,0 + key[i+4 mod keysizab])) = Y-3+i+4,0, (12) kde P’ znázorňuje „internal_permutation“ a εi’ znázorňuje možný bitový přenos. εi’, který má s pravděpodobností 0,5 hodnotu 0. Jakmile je známa hodnota Y-3+i,0 (pro 2 < i < ivsize-2), máme rovnost (12), která dává do souvislosti key[i+4 mod keysizab] a key[i+1 mod keysizab] pro 2 < i < ivsize-6. Každá taková rovnost nám dává alespoň 7 bitů informace o key[i+4 mod keysizab] a key[i+1 mod keysizab]. Hodnota Y256-i,0 (pro 2 < i < ivsize-2) je také známá a můžeme díky ní získat další informace z rovnosti (12). Celkově máme 2 * (ivsize - 9) rovností (12) dávající informace o bytech klíče. Pro 16ti bytový klíč a 16ti bytovou IV získáme 14 rovností (12). V těchto 14ti rovnostech je použito 13 bytů, které můžeme odvodit, což znamená že efektivnost klíče je snížena na 3 byty. Podobně pro 32 bytový klíč a 32 bytovou IV máme 46 rovností (12), ze kterých můžeme odvodit 29 bytů klíče, takže efektivnost klíče je snížena na 3 byty. [43]
24
6 Útoky na symetrické blokové šifry 6.1 Útok postranním kanálem na blokovou šifru v CBC módu při použití PKCS#5 padding Tento útok představený Sergem Vaudenayem [20, 21] je klasickým útokem postranním kanálem využívajícím chybového výstupu dešifrovací fce. Pokud má útočník přístup k chybovému hlášení o tom, že doplnění (padding) nebylo v pořádku, může podle tohoto útoku postupně odkrýt celý vstupní text.
PKCS#5 padding Při šifrování pomocí blokové šifry v CBC módu je třeba vyřešit problém jak šifrovat poslední blok vstupního textu pokud velikost vstupního textu, není dělitelná velikostí bloku. Řešením je doplnění (padding) posledního bloku nějakými “náhodnými“ slovy, která půjdou po dešifrování lehce rozpoznat a od výsledného textu následně odstranit. PKCS#5 definuje jednu možnost jak zprávu doplnit. Podle PKCS#5 se doplní n slov o hodnotě n, tak aby výsledná zpráva byla dělitelná velikostí bloku, tzn. pokud je potřeba doplnit tři slova, aby byla vstupní zpráva dělitelná velikostí bloku, pak je doplněno 333. [22]
6.1.1 Útok pomocí orákula O Pro úspěšný útok musíme sestrojit čtyři orákula. První orákulum (orákulum O) nám bude říkat, jestli má dešifrovaná zpráva správné doplnění. Další orákulum je orákulum posledního slova, toto orákulum nám pomocí opakovaného volání předchozího orákula O dokáže spočítat poslední slovo posledního bloku. Třetí orákulum je orákulum dešifrující daný blok zprávy pomocí opakovaného volání orákula posledního slova. Poslední orákulum je dešifrovací orákulum, to nám pomocí volání předchozího orákula pro každý, blok umožní dešifrovat celou zprávu. [20,21]
Orákulum O Sestrojit toto orákulum není těžké, již podle předpokladů tohoto útoku má útočník přístup k chybovému hlášení o správnosti doplnění. Takže pokud je doplnění správné, tzn. nevznikne žádné chybové hlášení, tak nám orákulum O vrátí 1. Pokud doplnění není správné a vznikne nějaké chybové hlášení, tak orákulum vrátí 0. Jelikož správné dešifrování, a tedy to jestli vznikne nějaké chybové hlášení nebo ne, je závislé na šifrovací funkci C a iniciační hodnotě IV, tak je i orákulum O závislé na funkci C a hodnotě IV. [20,21]
Orákulum posledního slova (Last Word Oracle) Toto orákulum má za úkol spočítat poslední slovo C-1(y), kde y je poslední blok šifrového textu. Útočník, který má přístup k orákulu O sestrojí velice jednoduše toto orákulum pomocí v průměru W/2 volání orákula O na dvoublokové zprávě, kde W je počet všech možných slov.
25
Nechť r1, r2, ...., rb jsou náhodná slova a b je počet slov v jednom bloku, pak nechť r = r1, r2, ...., rb. Vytvoříme falešný šifrový text r|y tím, že za sebou spojíme náhodný blok r a blok y. Tento šifrový text necháme dešifrovat a orákulum O nám řekne, zda má dešifrovaný text správné doplnění nebo ne. Pokud O(r|y) = 0, tak C-1(y) ⊕ r nekončí správným doplněním a je třeba upravit blok r. Jelikož se snažíme nalézt poslední slovo, tak upravíme rb a znovu otestujeme r|y pomocí orákula O. Toto provádíme tak dlouho, dokud O(r|y) = 1. Pokud O(r|y) = 1, tak potom C-1(y) ⊕ r končí správným doplněním. V tomto případě musíme zjistit jaké je to doplnění, zda je to 1, 22, 333, ... . Toto (pro případ kdy testujeme doplnění 1) zjistíme tak že orákulu O pošleme r’|y, kde r‘ = r’1, r‘2, ...., r’b, kde r’b = rb. Pokud nám orákulum O vrátí 1, pak bylo doplnění 1. Pokud nám vrátí 0, bylo použito delší doplnění (které jsme výše uvedeným postupem narušili. Jaké, to otestujeme stejně, jen nezměněných slov v r’ bude postupně přibývat, dokud orákulum O nevrátí 1. V tu chvíli víme jak dlouhé doplnění bylo použito. Řekněme, že by doplnění bylo jen 1, pak poslední slovo C-1(y) je rb⊕1. [20,21]
Orákulum dešifrující daný blok Toto orákulum má za úkol, pomocí předchozího orákula posledního slova a orákula O, získat text vstupní zprávy nějakého bloku y, tzn. spočítat C-1(y). Nechť je a1, a2, ..., ab posloupnost slov dešifrovaného textu C-1(y). Můžeme jednoduše určit poslední slovo ab pomocí orákula posledního slova. Teď stačí ukázat že dokážeme zjistit aj, pokud již známe aj+1, ..., ab. Pokud se to podaří, tak následně můžeme opakovaným postupem získat celý blok. Nechť r1, r2, ...., rj-1 jsou náhodná slova a rk = ak ⊕ (b-j+2) pro k = j,...,b. Nechť r = r1, r2, ...., rb. Vytvořme falešný šifrový text r|y tím, že spojíme bloky r a y. Jestliže orákulum O vrátí pro náš falešný text 1, tak rj-1 ⊕ aj-1 = b-j+2 a z tohoto vztahu dokážeme odvodit aj-1. Jestliže rj-1 je náhodné, pak je pravděpodobnost W-1, že orákulum O vrátí právě 1. Z toho vyplývá, že průměrně potřebujeme W/2 volání aby tato situace nastala. Takže pokud každý blok má b slov, pak potřebujeme v průměru bW/2 volání orákula O pro implementaci orákula dešifrujícího daný blok. [20,21]
Dešifrující orákulum Pomocí orákula dešifrujícího daný blok můžeme dešifrovat jakoukoliv zprávu y1, y2, ...., yN s pomocí orákula O. V průměru je třeba NbW/2 volání orákula O. Stačí pouze zavolat pro každý blok yi orákulum dešifrující daný blok a provést CBC dešifrování. Jediný problém by mohl nastat tehdy bude-li IV tajná, pokud by to nastalo tak bychom nemohli dešifrovat první blok zprávy. Nicméně můžeme dostat první blok vstupního textu až po neznámou. Zejména pokud jsou dvě zprávy zašifrované se stejnou IV, tak můžeme spočítat XOR dvou prvních bloků vstupních zpráv. Útok má složitost O(NbW). Například pro b = 8 a W = 256 dokážeme dešifrovat jakoukoliv vstupní zprávu pomocí 1024N volání orákula O. To znamená, že je tento útok velice efektivní.
26
6.2 Útok postranním kanálem na blokovou šifru v CBC módu při použití formátu zpráv PKCS#7 Po zveřejnění Vaudenayova útoku[20,21] na šifry v CBC módu používající PKCS#5 doplňování [22] byly provedeny studie a byly navrženy možné rozšíření a protiopatření [23], které by zabránily tomuto útoku. Jediné efektivní doplnění, které zde bylo uvedeno pod názvem ABYT-PAD (arbitrary-tail padding) pro bytově orientované zprávy a ABIT-PAD pro bitově orientované zprávy. ABYT-PAD je definován následujícím způsobem: nechť poslední byte zprávy je X, vezmeme nějaký rozdílný byte Y a přidáme jeden nebo více bytů Y tak, aby velikost zprávy byla dělitelná velikostí bloku. Příjemce si přečte poslední byte dešifrované zprávy a odstraní všechny stejné byty z konce zprávy. Hlavní výhodou tohoto doplňování je, že neexistuje žádné špatné doplnění, to znamená, že nelze použít útok popsaný Vaudenayem. Ovšem ani toto doplnění samo o sobě není dostačující, V. Klíma a T. Rosa publikovali útok na symetrickou blokovou šifru v CBC módu využívající známou standardní syntaxi PKCS#7 a ABYT-PAD doplnění [24]. Jejich útok není postaven na orákulu, které říká, zda daná zpráva má správné doplnění, ale na orákulu PKCS#7CONF, které pro daný šifrový text říká, zda dešifrovaný text odpovídá PKCS#7 syntaxi. K určení, zda to tak je, postačuje jakákoliv informace, například zpráva pro uživatele, chybové hlášení API, zápis do logovacího souboru, rozdílná časová náročnost mezi dešifrování správného a nesprávného textu, a podobně. Ve svém článku ukázali, že pokud má útočník přístup k takovému orákulu, je schopen dešifrovat celý vstupní text. [24]
6.2.1 PKCS#7 Formát PKCS#7 [25] popisuje obecnou syntax pro kryptograficky chráněná data. PKCS#7 definuje těchto šest obsahových typů: data, podepsaná data, zabalená data, podepsaná a zabalená data, shrnutá data a zašifrovaná data. Tyto obsahové typy jsou definovány použitím ASN.1 [26] notace a jsou použity v mnoha aplikacích a programech. Podle ANS.1 je struktura kódování vstupní zprávy (0x04, L, data), kde 0x04 je daná konstanta a L je délka zprávy. Při tomto útoku budeme bez ztráty obecnosti předpokládat, že data jsou uvedena jako oktetové stringy. Dále budeme předpokládat, že zašifrovaná data mají datový typ „zabalená data“, bloková šifra pracuje v CBC módu a je použito ABYT-PAD doplňování. Šifrový text je umístěn ve vysoce strukturovaném datovém bloku „zabalená data“. Symetrický klíč použitý k zašifrování je zašifrován pomocí asymetrické kryptografie a je také uložen na specifickém místě v „zabalených datech“. Inicializační hodnota IV je také uložena v této struktuře, mimo šifrový text, takže je možno ji změnit bez ovlivnění samotného šifrového textu. Dále předpokládáme, že pokud změníme zprávu, tak jsme schopni upravit všechny oktety v struktuře „zabalená data“ určující délku zprávy, takže nebude porušena korektnost struktury „zabalená data“. V následujícím textu budeme manipulovat jen s IV a šifrovým textem. [24]
PKCS#7 potvrzovací orákulum PKCS#7CONF Nechť CT je šifrový text neobsahující IV, který je uložen ve struktuře „zabalená data“, pak označme C = (IV, CT).
27
Sestrojíme orákulum PKCS#7CONF, které bude vracet odpověď OK, BAD. Bude obsahovat následující proceduru [24]: 1. P = DEC-CBCK(C)
/*Vstupní text P je získán dešifrováním šifrového textu C v CBC módu pomocí symetrického klíče K.*/ 2.Odstraníme doplnění a výslednou zprávu označíme jako M. 3. Rozdělíme a zkontrolujeme zda M odpovídá PKCS#7. - zkontrolujeme typové oktety M, předpokládáme, že zde objevíme hodnotu 0x04, jestliže zde není, tak je to chyba. - zkontrolujeme oktety délky zprávy M, předpokládáme, že je zde jeden oktet označující délku(L), dále L musí být stejný jako je délka M. Jestliže tomu tak není, tak je to opět chyba. 4. Jestliže jsou obě kontroly kroku 3 úspěšné tak PKCS#7CONF vrací OK, jinak vrací BAD.
6.2.2 Útok pomocí orákula PKCS#7CONF Máme validní šifrový text C = (IV, CT1, CT2, ..., CTs), kde s ≥ 1, pak označme (P1, P2, ... Ps) odpovídající vstupní text. Ukážeme si, že dokážeme vypočítat X = Dk(Y) pro zvolené Y z čehož dokážeme dešifrovat celý šifrový text.
Přípravná fáze Jestliže je C validní šifrový text a M odpovídající vstupní zpráva (vstupní text bez doplnění) ve formátu PKCS#7, tak víme, že P1,1 = 0x04 a P1,2 = L (první index značí pořadí bloku ve správě a druhý index je pořadí oktetu v bloku), kde L je délka M. Ukážeme si jak zjistit hodnotu L pomocí PKCS#7CONF orákula. Nechť s ≥ 3. Touto podmínkou zajistíme, že změny provedené v posledním bloku neovlivní první blok vstupní zprávy obsahující oktet s L. Označme LDATA délku dat LPAD délku doplnění, LDATA + LPAD = n. V následujícím kódu [24] budeme testovat každý byte od konce zprávy, zda je to byte doplnění nebo byte zprávy. Jakmile narazíme na první byte zprávy máme hodnotu LDATA. Pro přehlednost označme orákulum PKCS#7CONF v kódu pouze písmenem O. CTemp = CTs-1 /* od předposledního bitu začínáme, jelikož minimálně jeden bit je doplnění */ LDATA = 0 For j = (n -1) downto 1 { CTs-1,j = CTempj ⊕ 1 If O(C') = "OK" then LDATA = j, break /* změna znamená porušení celého bloku Ps-1. Jestliže orákulum O vrátí „OK“, tak to znamená, že změna originálního vstupního textu Ps,j na hodnotu Ps,j ⊕ 1 neovlivnila délku L. To jest, Ps,j je datový byte a my máme LDATA = j. Jestliže orákulum O vrátí „BAD“, tak to znamená, že délka zprávy neodpovídá hodnotě uložené v L. Toto může mít dva důvody - Ps,j byl poslední datový byte a my jsme jej náhodně změnili na doplňkový byte
28
- Ps,j je doplňkový byte a my jsme jej změnili na datový. Zjistit která z těchto dvou možností je ta správná můžeme tak, že změníme hodnotu posledního bytu na jinou a znovu zavoláme orákulum O */ CTs-1,j = CTempj ⊕ 2 and call O(C') If O(C') = "OK" then LDATA = j, break /* Jestliže tentokrát vrátilo orákulum O „OK“ tak Ps,j je datový byte, jinak je to doplňkový byte a my pokračujeme s testováním na dalším bytu. */ } L = (n - 2) + (s - 2)*n + LDATA /* (n-2) bytů je započítáno z prvního bloku, LDATA je délka zprávy v posledním bloku a zbývajících (s-2) bloků má plnou délku */
Spočítání X = DK(Y) s jedním neznámým bytem V této fázi použijeme první dva bloky (IV, CT1) šifrového textu C a vytvoříme falešný šifrový text C’ = (IV, CT1, S, T, Y), kde S a T jsou libovolné a Y je blok který chceme dešifrovat. Označme si P = (P1, P2, P3, P4) vstupní text odpovídající šifrovému textu C’. Máme P1,1 = 0x04 a P1,2 = L, kterou známe z předchozího kroku. Použitím následující procedury [24] určíme X = DK(Y) s tím, že jeden byte ponecháme neurčený. ITemp =IV , TTemp = T, A = Xn . Tn For i = (n - 1) downto 1 { /* V tomto cyklu odvozujeme i-tý byte P4,i, kde P4,i+1 = ... = P4,n jsou doplňkové byty všechny rovny A. */ N = (n - 2) + n + n + (i - 1) IV2 = ITemp2 ⊕ P1,2 ⊕ N /* Po dešifrování C', dostane orákulum O číslo N na pozici P1,2. Tudíž předpokládáme i -1 datových bytů a n - (i - 1) doplňkových bytů v posledním bloku vstupního textu P4 . */ (*) For j = 0 to 255 do { Ti = TTempi ⊕ j If O(C') = "OK" go to (**) /*
29
Jestliže orákulum O vrátí pro C' hodnotu „OK“, tak vstupní text je vyhovující PKCS#7 a Xi ⊕ Ti je doplňkový byte A. Tudíž máme Xi ⊕ Ti = Xi+1 ⊕ Ti+1 = ... = Xn ⊕ Tn = A můžeme pokračovat v odvozování dalšího bytu. */ } If (i >1) then Ti-1 = TTempi-1 . 1 else Sn = Sn . 1 Go to (*) /* Jestliže orákulum O v předešlém cyklu vrátí vždy „BAD“, tak to znamená, že pokud se objevila správná hodnota (A) na i-tém bytu, tak se naneštěstí také objevila na pozici jeho levého souseda. Takže změníme byte nalevo a vrátíme se k (*), teď již musí orákulum v nějakém místě vrátit „OK“ */ (**) /* Pokračujeme v dalším cyklu */ Na konci této procedury máme: X1 ⊕ T1 = X2 ⊕ T2 = ... = Xn ⊕ Tn = A
Určení zbývajícího neznámého bytu Teď je třeba určit poslední neznámý byte a na to použijeme bloky T a Y, které jsme vytvořili v předchozím kroku. Šifrový text C = (T, Y) nám dá jeden blok obsahující n bytů se stejnou hodnotou A. Teď změníme T1, T2 a Tn tak abychom dostali zprávu splňující PKCS#7. Zkonstruujeme zprávu tak, o délce n-3 oktetů plus jeden doplňkový byte. Dále určíme hodnotu A následujícím způsobem [24]: TTemp = T For j = 0 to 255 do { T1 = TTemp1 ⊕ 0x04 ⊕ j, T2 = TTemp2 ⊕ (n - 3) ⊕ j, Tn = TTempn ⊕ 1 C' = (T, Y) /* C' odpovídá vstupnímu text (A ⊕ 0x04 ⊕ j, A ⊕ (n-3) ⊕ j, A,..., A, A ⊕ 1). */ If O(C') = "OK" then A = j, break /* Jestliže orákulum O vrátí pro C' hodnotu „OK“, tak vstupní zpráva splňuje PKCS#7. Máme A ⊕ 0x04 ⊕ j = 0x04. Dále pak jednoduše zjistíme neznámou A jako A = j. */ }
6.2.3 Složitost dešifrování celého textu Nyní jsme už schopni opakovaným voláním dvou výše popsaných procedur pro každý blok šifrového textu dešifrovat celý šifrový text. Celkově je tento útok velmi efektivní, jelikož
30
nalezení délky L vyžaduje maximálně 2*(n-1) volání orákula, spočítání X = DK(Y) s jedním neznámým bytem vyžaduje průměrně 128*(n-1) volání orákula a maximálně 512*(n-1) volání orákula a určení neznámého bytu vyžaduje průměrně 128 volání orákula a maximálně 256 volání orákula. Celkově je tedy potřeba průměrně s*(2*(n-1)+128*n) volání orákula a maximálně je potřeba s*(2*(n-1)+512*(n-1)+256) pro dešifrování zprávy o s blocích s délkou bloku n.
6.3 Útok na AES pomocí indukce chyb během šifrování. Tento útok předpokládá, že máme přístup k zařízení, které používá k šifrování vstupních dat AES, ale neznáme klíč, který používá. To je informace, kterou se právě snažíme zjistit. Předpokládejme, že State klíče i bloku je vyjádřen jako tabulka o čtyřech řádcích, obsahující bytová slova. Označme kij bytové slovo klíče z tabulky na pozici i,j a podobně aij označme byte bloku na pozici i,j. Dále si označme kijl l-tý bit bytu kij a aijl l-tý bit bytu aij. Dalším důležitým předpokladem je, že jsme schopni během dešifrování vyvolat jednobitovou chybu v zařízení, a to tím, že se určitý vybraný bit pokusíme nastavit na 0. Způsoby k dosažení takovéto jednobitové chyby jsou shrnuty v [39] ve třetí kapitole, konkrétní postup se dá nalézt například v [40] nebo v [41]. Postup útoku záleží na velikosti bloku Nb a velikosti klíče Nk použitého při šifrování. Napřed si ukážeme postup útoku při Nk ≤ Nb, v tomto případě je celý klíč použit v iniciálním AddRoudKey. Základní krok je, že šifrovacímu zařízení dáme zašifrovat vstupní text o délce jednoho bloku, který se skládá ze samých nul, označme si ho O. Během průběhu iniciální operace AddRoundKey probíhá: aij = 08 ⊕ kij Z toho vyplývá, že po této operaci aij = kij. nyní provedeme náš zásah a pokusíme se změnit aijl na 0. Po tom, co způsobíme tuto chybu, necháme proces bez dalšího zasahování a bez dalších chyb doběhnout. Pokud dostaneme korektně zašifrovaný náš vstupní text O, pak změna aijl na 0 neměla na šifrování žádný vliv a kijl je 0, ovšem pokud není vstupní text O zašifrován korektně pak změna aijl na 0 měla na šifrování vliv a to znamená, že kijl je 1. Pokud je Nk > Nb, pak je postup trošku odlišný. Vyplývá to z toho, že při prvním kole není použit celý klíč, ale jen prvních Nb jeho bitů. Předcházejícím postupem dokážeme těchto Nb prvních bitů klíče zjistit. Jakmile známe prvních Nb bitů klíče, tak můžeme nasimulovat první kolo AES a proto dokážeme najít takový vstupní text P, který po prvním kole bude mít State bloku opět samé nuly. Takže můžeme v dalším kole, kde je použit zbytek klíče, použít stejný postup jako v předchozím případě. [39] Pokud jsme tedy schopní vyvolat jednobitovou chybu v šifrovacím zařízení, jsme také schopni odhalit tajný klíč, který toto zařízení využívá na šifrování. Tento útok je možno aplikovat nejen na AES, ale na jakoukoliv symetrickou blokovou šifru, která používá při šifrování textu operaci AddRoudKey. [39]
31
7 Útoky na asymetrické šifry 7.1 Útok na RSAES-OAEP podle standardu PKCS #1 v2.0 D. Bleichenbacher představil na CRYPTO 98 chosen cipher-text útok na RSA [31] podle standardu PKCS #1 v1.5 s blokovým doplňování typu 2. Z tohoto útoku vyplývá, že šifrování pomocí RSA by mělo obsahovat kontrolu integrity, a že kritická fáze je mezi dešifrováním a kontrolou integrity. Verze 2.0 PKCS #1 RSAES-OAEP [32], která k obraně proti tomuto útoku využívá Optimal Asymmetric Encryption Padding (OAEP), by měla být odolná proti podobným útokům. Přesto definice RSAES-OAEP naznačuje, že z implementací je útočník schopen získat nějaké informace právě z kritické fáze mezi dešifrováním a kontrolou integrity. [30]
7.1.1 RSAES-OAEP Šifrování RSAES-OAEP začíná zakódováním seed, haš hodnoty, doplňkových oktetů a tajného klíče (typicky klíče pro dané spojení) do oktetového string. Před tím než se na tyto oktety použije pro zašifrování RSA jsou znáhodněny pomocí maskovacích operací. Číslo pro doplnění oktetů je vybráno tak, že kódování spotřebuje o jeden oktet méně než je potřeba na binární reprezentaci modula. Toto zajistí, že celé číslo reprezentující zašifrovanou zprávu je menší než modulus, což je pro RSA nutné. Další možnost doplnění je, že zakódovaná zpráva je stejně dlouhá jako modulus, ale její nejvýznačnější oktet je ‘00’h. [32] Na obrázku je ukázáno dešifrování dekódování RSAES-OAEP. Šifrový text je převeden vstupní modulární exponencializací následovanou převodem výsledného čísla na oktety. Maskovací funkce MGF(mask generation function) použije nejméně význačnou část vstupního textu na odmaskování seed. Pomocí maskování použitého na seed je odmaskována následně i haš hodnota, doplnění a tajná zpráva (přenášený klíč). Integrita zprávy je zkontrolována pomocí odmaskované haš hodnoty, jejím porovnáním se spočítanou haš hodnotou parametrů. [32]
Obr. 5: Dešifrování podle RSAES-OAEP
32
Chybou může skončit převod čísla na oktety (číslo je příliš velký, nebo je počet oktetů menší než modulus) nebo při OAEP dekódování (zpráva neprošla kontrolou integrity). V obou těchto případech vypíše PKCS#1 v2.0 na chybový výstup „decryption error“. [32]
7.1.2 Popis útoku Nechť n je modulus, e veřejný klíč a d privátní klíč. Nechť k = [log256 n] je bytová délka n a nechť B = 28(k-1). Předpokládejme, že známe veřejný klíč a máme přístup k orákulu, které pro jakýkoliv šifrový text x zjistí, zda je nebo není odpovídající vstupní text y≡xd(mod n) menší než B. Toto orákulum můžeme získat pomocí chybového hlášení „decryption error“. Samozřejmě se snažíme zjistit vstupní text m≡cd(mod n) odpovídající zachycenému šifrovému textu c. Základním krokem útoku je vybrat násobek f a poslat fe(mod n) orákulu. Tento šifrový text odpovídá f ⋅ m (mod n). Orákulum nám řekne, jestli je to v rozsahu [0, B) nebo (B, n) modulo n, což nám poskytne matematickou souvislost mezi zprávou m a rozsahem, ve kterém m leží. Pomocí úspěšných volání orákula zmenšujeme rozsah, ve kterém se může zpráva nacházet, až nám zbude jedna jediná hodnota - m. Na počátku víme, že m leží v intervalu [0, B) stejně jako každá jiná platná zpráva. Jelikož m < B, tak vždy existuje f takové, že f ⋅ m leží v nějakém intervalu délky B. Například, pro každé číslo i existuje číslo f takový, že f ⋅ m ∈ [in, in + B). [30] Následující popis předpokládá, že n > 2B. Tento předpoklad je většinou splněn a neubírá útoku na obecnosti.[30]
Fáze 1 Zkoušíme násobky dvou, čtyř, osmi,... 2i,... dokud nám orákulum nevrátí „ ≥ B“. Pro každý násobek f1, posouvají možné hodnoty f1 ⋅ m jednu hranici intervalu. [30] 1.1 Víme, že m ∈ [0, B). Nechť f1 = 2. 1.2 f1 ⋅ m ∈ [0, 2B). Pošleme orákulum f1e * c(mod n). 1.3a Jestliže orákulum vrátí ≤ B, tak to znamená, že f1 * m ∈ [0, B) a 2f1 * m ∈ [0, 2B). Nastavíme f1 = 2*f1 a vrátíme se ke kroku 1.2 1.3b Jestliže orákulum vrátí ≥ B, tak to znamená, že f1 * m ∈ [B, 2B), a z toho plyne, že f1 / 2 * m ∈ [B/2, B). Přesuneme se do další fáze.
Fáze 2 Začneme s násobkem f2 takovým, že f2 * m je menší než n + B pro maximální možné m. Zvyšujeme tento násobek dokud orákulum nevrátí < B.[30] 2.1 Máme f1/2 * m ∈ [B/2, B). Nechť f2 = (n+B)/B * f1/2. 2.2 Takže f2 * m ∈ [n/2, n+B). Vyzkoušíme f2 pomocí orákula. 2.3a Jestliže orákulum vrátí ≥ B, tak to znamená, že f2 * m ∈ [n/2, n) a že (f2 + f1/2) * m ∈ [n/2, n+B). Nastavíme f2 = f2 + f1/2 a vrátíme se ke kroku 2.2
33
2.3b Jestliže orákulum vrátí < B, tak to znamená, že f2 * m ∈ [n, n+B). Přesuneme se do další fáze.
Fáze 3 3.1 Máme f2 * m ∈ [n, n+B), což se dá zapsat, tak že máme násobek f2 a rozsah [mmin, mmax) možných hodnot m. 3.2 Vybereme násobek ftmp takový, že velikost ftmp * m je přibližně 2B. Tato hodnota je přibližně dvakrát větší než předchozí násobek. Vybereme hraniční bod in + B blízko rozsahu ftmp * m. i = ftmp * mmin / n. 3.4 Vybereme násobek f3 = in/mmin, což nám dává, že f3 * m ∈ [in, in + 2B). Vyzkoušíme f3 pomocí orákula. 3.5a Jestliže orákulum vrátí ≥ B tak to znamená, že f3 * m ∈ [in + B, in + 2B). Nastavíme mmin = (in + B) / f3. Vrátíme se na krok 3.2. 3.5b Jestliže orákulum vrátí < B tak to znamená, že f3 * m ∈ [in, in + B). Nastavíme mmax = (in + B) / f3. Vrátíme se na krok 3.2. Každá odpověď orákula ve třetí fázi posune buď spodní nebo horní hranici intervalu, ve kterém leží f3 * m a tím zmenší jeho velikost na polovinu. Rozsah, ve kterém leží m se časem zmenší na jedno číslo. Což je hledaný vstupní text. [30]
7.2 Útok na RSAES-OAEP PKCS#1 v2.1 Tento útok na RSAES-OAEP PKCS#1 v2.1[34] předpokládá, že je možné zjistit pomocí nějakého skrytého kanálu Hammingovu váhu w(x) (tzn. počet bitů 1) slova x ve chvíli, kdy je vstupní text m zpracováván pomocí operace MGF. Získání takové informace je realizovatelné, jak je ukázáno v [35], pomocí výkonové analýzy. [33]
7.2.1 Popis útoku Útok počítá s RSA s modulem n, které má délku L(n) bitů, kde L(n) je násobek 512, tj. L(n) = 512*k, kde k je přirozené číslo. Útok se zaměřuje na část, ve které je vstupní text zpracováván ihned po dešifrování pomocí RSA. [33] SeedMask je spočítána podle [34] jako: Seedmask = MGF(maskedDB, 20) = SHA-1 (maskedDB// 00 00 00 00). Pomocí MFG jsou ke zprávě připojeny čtyři nulové oktety. Dále z definice OAEP kódování vyplývá, že maskedDB vždy obsahuje 64*k-1-20 oktetů, takže 64*k-17 (jsou přidány 4 nulové oktety) oktetů vstupuje do SHA-1. Podle definice SHA-1 [36] je zpráva rozdělena na bloky, obsahující 64 oktetů, které jsou sekvenčně zpracovávány. Poznamenejme, že nejméně význačný bit originální zprávy je zpracováván v posledním bloku a je následován 4 nulovými oktety a doplněním SHA-1. Pro různé L(n) je hodnota doplnění různá, ale pro konkrétní délku je to známá konstanta, kterou je možné použít pro potřeby útoku použít. SHA-1 rozdělí poslední blok na 32-bitová slova W0, ..., W15, kde W0, ..., W10 jsou slova obsahující část zprávy a W11, ..., W15 jsou slova obsahující známé hodnoty, ať už 4 nulové oktety doplněné funkcí MGF nebo známé doplnění SHA-1. Dále tato slova expanduje na slova W16, ..., W79 podle následujícího vzorce:
34
W16 = S1(W13 ⊕ W8 ⊕ W2 ⊕ W0) W17 = S1(W14 ⊕ W9 ⊕ W3 ⊕ W1) W18 = S1(W15 ⊕ W10 ⊕ W4 ⊕ W2) atd. Když počítáme W16, tak je první operací W13 ⊕ W8, kde W13 je známá konstanta. V tomto momentě je to klasická situace, kdy do N-ární operace vstupuje D-1 známých parametrů a jeden neznámý. Předpokládáme, že známe Hammingovu váhu slova W8 při zpracování operace W13 ⊕ W8, kde jedinou neznámou je právě W8. Stejná situace nastává i při dalších dvou operacích. Očíslujeme si bity slova Wi (od nejvýznačnějšího bitu k nejméně význačného bitu) jako Wi,31 , Wi,30 , Wi,29 , ... , Wi,0. V následujícím textu si ukážeme, že jsme schopni odhadnout hodnotu bitu W10,8 s nezanedbatelnou pravděpodobností blížící se ½. Z teorému individuálních bitů RSA [37] můžeme znalost tohoto bitu použít k útoku, který bude vést k dešifrování celého textu. [33]
Získání nejméně význačného bitu vstupního textu Známe šifrový text c, odpovídající modulus n a veřejný klíč e. Dále jsme při dešifrování c změřili Hammingovu váhu slov W8, W9, W10, tj. známe w(W8), w(W9) a w(W10). Dále dešifrovacímu zařízení podstrčíme šifrový text c’ = c*2-e (mod n). Při tomto dešifrování jsme změřili váhu slov W‘8, W‘9, W’10, tj. známe w(W‘8), w(W‘9) a w(W‘10), a výsledek tohoto dešifrování označíme m‘.[33] Jestliže bit W10,8 je nula tak dešifrování c‘ vrátí m‘ = m >>1, kde >>1 značí bitový posun o jeden bit doprava. Pokud je bit W10,8 jedna, tak m‘ = (m+n) >>1. Pokud přepokládáme, že bit W10,8 je nula, tak (W‘8, W‘9, W‘10) vznikne z (W8, W9, W10) posunem jednoho bitu doprava (s výjimkou W10, kde posun ovlivní pouze bity nalevo, které jsou nezávisle doplněny nulovými bity). Rozdíl mezi (w(W8), w(W9), w(W10)) a (w(W‘8), w(W‘9), w(W‘10)) je buď 0 nebo 1. Podle kombinace hodnot nultých bitů slov W8, W9, W10 platí jedna z osmi situací v tabulce 1. [33] Bity Možné vztahy
W9,0 W8,0 W7,0 0
0
0
w(W’10,0) = w(W10,0)
w(W’9,0) = w(W9,0)
w(W’8,0) = w(W8,0)
0
0
1
w(W’10,0) = w(W10,0)
w(W’9,0) = w(W9,0)
w(W’8,0) = w(W8,0) + 1
0
1
0
w(W’10,0) = w(W10,0)
w(W’9,0) = w(W9,0) + 1
w(W’8,0) = w(W8,0) - 1
0
1
1
w(W’10,0) = w(W10,0)
w(W’9,0) = w(W9,0) + 1
w(W’8,0) = w(W8,0)
1
0
0
w(W’10,0) = w(W10,0) + 1 w(W’9,0) = w(W9,0) - 1
w(W’8,0) = w(W8,0)
1
0
1
w(W’10,0) = w(W10,0) + 1
w(W’8,0) = w(W8,0) + 1
1
1
0
w(W’10,0) = w(W10,0) + 1 w(W’9,0) = w(W9,0)
w(W’8,0) = w(W8,0) - 1
1
1
1
w(W’10,0) = w(W10,0) + 1 w(W’9,0) = w(W9,0)
w(W’8,0) = w(W8,0)
Tabulka 1. Možné vztahy mezi W’ a W
Jestliže W10,8 = 1, tak m‘ není vytvořena jednoduchým posunem na m, ale jako (m+n) >>1, toto z největší pravděpodobností poruší lineární vztahy z předchozí tabulky. Zkontrolujeme jestli přesto nejsou splněny vztahy z tabulky 1, pokud ano pak se vrátíme k předpokladu, že W10,8 = 0, pokud ne tak jsme ověřili, že W10,8 = 1. Pravděpodobnost, že přijmeme hypotézu W10,8 = 0 a přitom W10,8 = 1 je přibližně 0,008. [33]
35
Tento postup nám umožňuje určit nejméně význačný bit vstupního textu m s velmi vysokou pravděpodobností a jak bylo řečeno v [37], pokud jsme schopni určit jeden bit vstupního textu jsme schopni dalším postupem určit celý vstupní text.
7.3 Útok na RSA-KEM Účelem RSA-KEM je přenos symetrického klíče, tzn. používá se jako součást hybridního šifrovacího schématu H-PKEKEM, DEM[38], které obsahuje Data Encapsulation Mechanism (DEM) a Key Encapsulation Mechanism (KEM). Tento útok je založen na chování celého hybridního systému. [33]
7.3.1 Popis H-PKEYKEM, DEM Popis základních funkcí a mechanizmů KEM je obsažen v následujícím abstraktním rozhraní [38]: KEM.Encrypt(PubKey) -> (K, C0) – generuje klíč pro symetrickou šifru a používá RSA pro vytvoření odpovídajícího šifrového textu C0. KEM.Decrypt(PrivKey, C0) -> (K) – dešifruje šifrový text pomocí RSA a pomocí KDF odvodí symetrický klíč K Popis základních funkcí a mechanizmů DEM je obsažen v následujícím abstraktním rozhraní[38]: DEM.Encrypt(K, M) -> (C1) – zašifruje zprávu m pomocí symetrického klíče K do šifrového textu C1 DEM.Decrypt(K, C1) -> (M) – dešifruje šifrový text pomocí symetrického klíče K a vrátí zprávu m. Postup celého H-PKEYKEM, DEM schématu se dá shrnout následovně: Šifrování: 1. (K,C0) = KEM.Encrypt(PubKey) 2. C1 = DEM.Encyrypt(K,M) 3. šifrový text C = C0 || C1 Dešifrování: 1. Nechť C = C0 || C1 2. K = KEM.Decrypt(C0) 3. M = DEM.Decrypt(K, C1)
7.3.2 Popis útoku Poznamenejme, že v tomto schématu neexistuje žádná kontrola integrity klíče K, ale ve třetím kroku dešifrování je prováděna kontrola integrity zprávy M. Předpokládáme, že útočník může zjistit zda proběhla nebo neproběhla kontrola v pořádku. Pomocí tohoto hlášení můžeme sestrojit orákulum RSA-COd,n(r,y) (RSA conformation oracle), které pro dané proměnné vrátí ano pokud kontrola integrity zprávy proběhla v pořádku, v ostatních případech vrátí ne. Z toho vyplývá, že orákulum vrátí ano, pokud r = (yd mod n), kde r je výsledek dešifrování pomocí RSA, ze kterého se odvozuje symetrický klíč, y je r zašifrované pomocí
36
RSA, d je soukromý klíč a n je veřejný exponent. Orákulum vrátí ne v kterémkoliv jiném případě. Pravděpodobnost správnosti odpovědi RSA-COd,n(r,y) se blíží 1 a závisí na kolizích ve funkci KDF a na síle kontroly integrity. Klíčové je, že můžeme provést kontrolu kongruence r ≡ yd (mod n) bez znalosti privátního klíče.[33] Jelikož neexistuje kontrola integrity přenášeného symetrického klíče, lze tento klíč pozměnit a pomocí orákula zjistit, zda výsledná zpráva prošla nebo neprošla kontrolou integrity. Ovšem mnohem zajímavějším postupem je neměnit přenášený klíč, ale vytvořit chybu v privátním exponentu. Předpokládejme, že jsme schopni změnit i-tý bit exponentu d(i) na opačnou hodnotu a tato změna projde nezjištěna až k příjemci (tato situace může nastat například u čipových karet). Pak pomocí RSA-COd,n(r,y) jsme schopni zjistit opakovaným vyvoláním této chyby celý exponent. [33] Nechť d(i) je i-tý bit exponentu, kterému jsme změnili hodnotu. Označme d‘ změněný exponent, pak d‘ = d + 2i nebo d‘ = d - 2i. Nechť I = 2i, α ≡ yI (mod n) a α*α-1 ≡ 1 (mod n). Pro hodnotu r = (yd mod n) máme: r = (yd * α mod n), jestliže d(i) = 0 r = (yd * α-1 mod n), jestliže d(i) = 1 Použitím RSA-COd,n(r,y) jsme schopni zjistit hodnotu d(i) následujícím způsobem: 1. náhodně vybereme x, 0 < x < n 2. nechť r = (xe mod n), kde e je odpovídající veřejný exponent 3. nechť r = (x * α mod n) 4. jestliže RSA-COd,n(r,y) vrátí ano, tak d(i) = 0 jinak d(i) = 1 Opakováním toho postupu pro různé bitové pozice (a jejich kombinace) můžeme postupně získat celý soukromý klíč, nebo alespoň jeho část a zbytek dopočítat jiným postupem.
37
8 Útoky na Hašovací funkce 8.1 Kolize v MD5 8.1.1 Úvod Na rump session konference CRYPTO 2004 Wangová a kol. předložili kolidující zprávy o délce 1024 bitů, ale neukázali metodu, pomocí které zprávy získali. Získat první 512ti bitovou část kolidující zprávy pomocí jejich útoku trvalo superpočítači IBM P690 přibližně jednu hodinu a získat druhou 512ti bitovou část trvalo maximálně 5 minut [1]. V říjnu 2004 Hawkes a kol. Analyzovali publikovaná data a dvojice kolizních zpráv a popsali jejich vlastnosti. Zjistili, že kolize používá rozdíly rozložené v dvou blocích vstupní zprávy. Ve svém článku popsali tyto rozdíly a z nich určili složitost nalezení kolize 242,2 (nalezení kolize hrubou silou má složitost 264) [2]. V březnu 2005 Klíma prezentoval metodu generování kolizí [3], [8]. Později prezentovali svoji metodu původní autoři [4]. Metody Klímy a Wangové jsou v některých ohledech rozdílné. Metoda Klímy je rychlejší v nalezení kolize v prvním bloku a metoda Wangové je rychlejší v druhé části. Ve [4] byly publikovány tzv. postačující podmínky, jejichž splnění zaručuje kolizi pro danou diferenční cestu. Později se ukázalo, že tyto postačující podmínky nejsou úplné a úplně správně. Ve článku Yajima a Shimoyama [5] jsou prezentovány nové podmínky a opraveny některé podmínky, které prezentovala Wangová. Další opravené podmínky jsou uvedeny ve článku z listopadu 2005 od Sasaki a kol. [6]. Sasaki zde uvedl nové způsoby mnohonásobné modifikace zpráv v druhém kole. Pro zlepšené hledání multikolizí zavádí nové extra podmínky. Později v listopadu 2005 Liang a Lai [7] ukázali protipříklady na postačující podmínky Wangové, tím dokázali jejich neúplnost a částečnou nesprávnost. Následně předložili úplnou sadu nových podmínek, která je pravděpodobně správná a konečná. Dále navrhli další cesty mnohonásobné modifikace zpráv a tím opět zmenšili časovou náročnost. Prozatím poslední postup navrhl Klima [9]. Tyto tzv. tunely radikálně zrychlí průběh hledání kolize. Reálně lze pomocí tunelů v MD5 nalézt kolizi do několika minut i na normálním stolním počítači.
8.1.2 Základní postup Základní postup hledání kolizí z [4] je následující. Kolidující zprávy se skládají ze dvou 512 bitových bloků (M,N) a (M’, Ni’), přičemž MD5(M, N) = MD5(M’, Ni’). První bloky zpráv (M, M’) se liší o předem definovaný konstantní vektor C1, M’ = M + C1 (kde C1 = (0, 0, 0, 0, 231, ...,215 ,...,231 ,0), nenulové hodnoty jsou na pozicích 4, 11 a 14), a druhé bloky (N, Ni’) se liší o předem definovaný konstantní vektor C2, Ni’ = N + C2 (kde C2 = (0, 0, 0, 0, 231 ,... ,-215 ,...,231 ,0), nenulové hodnoty jsou na pozicích 4, 11 a 14). Jestliže jsou splněny postačující podmínky při zpracování bloku M, výsledek po hašování bloku M a výsledek po hašování bloku M’ se také liší o předem definovanou konstantu C3. Při pokračování hašování druhých bloků se (jsou-li splněny postačující podmínky pro druhý blok N) rozdíl C3 postupem času zruší a obdržíme kolizi zpráv (M, N) a (M’, Ni’), pak MD5(M, Ni) = MD5(M’, Ni’). Postup zpracování bloků je podobný u obou bloků, popíšeme postup u prvního bloku (M). Blok M má 512 bitů, které jsou podle algoritmu MD5 zpracovávány po 32bitových slovech M = (x[0], ..., x[15]) v 64 krocích. V prvním kroku vzniká meziproměnná Q[1], v druhém kroku Q[2] atd. až Q[64]. Proměnné Q[-3] (= IV[0] = 0x67452301), Q[-2] (= IV[3] =
38
0x10325476), Q[-1] (= IV[2] = 0x98badcfe) a Q[0] (= IV[1] = 0xefcdab89) jsou inicializační hodnotou, buď standardní nebo zvolenou. Po 64 krocích je k výsledku Q[61...64] (poslední čtyři proměnné) přičtena vstupní hodnota (IV[0..3]) a dostáváme výsledek zpracování prvního bloku IHV[0...3] (intermediate hash value). IHV pak vstupuje do druhého bloku stejně jako IV do prvního bloku a postup se opakuje.
Postačující podmínky Postačující podmínky v prvním bloku jsou podmínky na jednotlivé bity proměnných IHV[0...3] a Q[1...64], které vznikají při zpracování slov zprávy x[0...15] nelineárními funkcemi F, G, H, I. Postačující podmínky říkají, že některé bity zmíněných proměnných musí být stejné, některé různé, některé nuly a některé jedničky, zbývající bity mohou být libovolné, viz tabulka 1. v příloze 2. Postačující podmínky se liší v prvním a druhém bloku. V prvním bloku je jich více, neboť se týkají jak Q, tak IHV. V druhém bloku je podmínek méně. Budeme se věnovat prvnímu bloku, neboť je složitější. Postup u druhého bloku je podobný. Máme blok M = (x[0],..., x[15]) a blok M’ = (Hx[0],...,Hx[15]), který se od M liší o konstantní vektor C1 = (0,...0, 0x80000000, 0,...,0, 0x00008000, 0,...,0), tj. při hašování Hx vznikají proměnné Q’ a IHV’. Jsou-li splněny postačující podmínky u bloku M na proměnné Q[1...64] a IHV[0...3], pak automaticky při zpracování proměnných Hx[0...15] vznikající proměnné Q’[1...64] a IHV’[0...3] splňují diferenční cestu podle obrázku 2. Nevýhoda postačujících podmínek je v tom, že je jich je velmi mnoho a že zasahují příliš daleko do proměnných Q. Postačujících podmínek je zhruba 250.
Jednoduchá modifikace zprávy Jednoduchá modifikace zprávy spočívá v postupném nastavení jednotlivých bitů zprávy, tak aby byla co největší šance, že výsledná zpráva bude splňovat všechny postačující podmínky. Staticky bez ovlivňování ostatních bitů lze nastavit bity ovlivňující podmínky Q[1] až Q[16]. Pokud ovšem naplníme podmínky Q[1] až Q[16] tím, že tyto hodnoty zvolíme, nemáme již žádnou volnost ve volbě zprávy x[0...15], a tudíž hodnoty Q[17..64] a IHV[0..3] jsou plně určeny. Podmínky na ně jsou splněny pouze náhodně. Pokud hodnoty Q[1] až Q[16] nestanovíme zcela, budou se nám špatně počítat hodnoty Q[17..64] a IHV[0..3], které na nich nelineárně a složitě závisí.
Mnohonásobná modifikace zpráv Metoda mnohonásobné modifikace zpráv [3] [4] [5] [6] [7] spočívá v tom, že se zvolí náhodně zpráva x[] a její modifikací se krok za krokem naplňují podmínky na Q[1, 2,...64]. Tento proces v různých pracích zprvu končil u Q[18], potom u Q[19] atd. V současné době je možné se nejdále dostat ke splnění podmínky na Q[24] ([6], poznamenejme však, že metoda nebyla ověřena experimentálně). Další podmínky jsou příliš daleko - až na Q[35]. V uvedených pracích se navrhovaly různé způsoby modifikace zpráv.
Extra podmínky Aby tento proces byl efektivnější, byly zavedeny další podmínky, které se nazývají „extra podmínky“. Tyto podmínky jsou podobné jako postačující podmínky, ale nejsou nezbytné pro naplnění dané diferenční cesty. Umožňují však rychleji realizovat některou
39
konkrétní metodu mnohonásobné modifikace zpráv. V praxi jde zhruba o deset až dvacet podmínek na jednotlivé bity proměnných Q[1...24].
Bod POV Úspěšnost metod mnohonásobné modifikace zpráv v každém případě končila splněním podmínky na Q[24]. Proměnné x[] byly plně určeny a zbývalo už jen ověřit, zda zbývající podmínky na Q[25...64] a IHV[0...3] jsou splněny náhodně. V případě, že nebyly splněny, metoda pokračovala dalším generováním zprávy x a její modifikací krok za krokem až do splnění podmínek Q[24]. Tento bod nazýváme bodem verifikace POV (point of verification), neboť v tomto bodě nic jiného nezbývalo než pouze verifikovat, zda i ostatní podmínky na Q[25...64] a IHV[0...3] jsou splněny. Protože konkrétně u MD5 je těchto zbývajících podmínek 29, složitost metody mnohonásobné modifikace zpráv spočívala v nalezení 229 bodů POV [9].
8.1.3 Tunely v MD5 V. Klima ve svém článku [9] prezentoval metodu nalezení kolizí pomocí tunelů. Využívá v nich všech již prezentovaných výsledků. Jeho metoda umožňuje nalézt další body POV rychleji než postupným aplikováním mnohonásobné modifikace velkého množství zpráv. Metoda tunelování spočívá v nalezení jednoho bodu POV a pomocí tunelů se pak tento bod rozmnoží na větší počet bodů POV. Jeho myšlenka spočívá v tom, že změní některé bity zprávy, u které se již dosáhlo k bodu POV. Ovšem tato změna neovlivní testované podmínky Q[1...24], zato tato změna ovlivní náhodným a dosti složitým způsobem téměř všechny proměnné v podmínkách Q[25...64] a následně i proměnné v podmínkách IHV[0...3]. Tzn. pokud najdeme jeden takovýto bit, tak z jednoho bodu POV získáme další bod POV a tyto dva body POV mají podmínky Q[25...64] a IHV[0...3] na sobě zcela nezávislé. Pokud nalezneme dva takovéto bity, získáme již další tři body POV. Počet bitů, které můžeme za daných okolností měnit, Klima nazývá síla tunelu. Je zřejmé, že pokud nalezneme tunel o síle n, získáme 2n bodů POV.
Typy tunelů V [9] je prezentováno několik konkrétních tunelů, které jsou rozděleny do několika typů. Jde o deterministické tunely, kde změnou daného bitu(ů) vždy získáme další bod(y) POV. Dále prezentoval pravděpodobnostní tunely, kde změnou bitu se může díky nechtěnému přenosu porušit některá další podmínka a tak nezískáme bod POV. Ovšem pravděpodobnost tohoto přenosu je velmi malá a jednoduchým testováním lze zjistit, zda množina ohrožených podmínek je nebo není splněna. Posledním prezentovaným typem tunelů jsou dynamické tunely. U tohoto typu se možnost změnit nějaký bit mění podle toho, jaké podmínky jsou splněny pro jiné bity (např.: jestliže je bit n = 1 tak bit m může být libovolný, jestliže je bit n = 0 tak bit m měnit nesmíme).
Extra podmínky pro tunely Tunely se ve všech zprávách nevyskytují se 100% pravděpodobností. Aby bylo zajištěno, že se daný tunel bude v zprávě vyskytovat, je třeba k postačujícím podmínkám přidat extra podmínky. Tyto podmínky zajistí, že se daný tunel bude ve zprávě vyskytovat a budeme ho moci použít k získání dalších bodů POV. Tyto podmínky se pro každý tunel liší [9].
40
Deterministický tunel Q9 Ukázku hledání tunelu provedeme na tunelu Q9. Hledání tunelu vždy začíná u postačujících podmínek. Podíváme-li se na rovnice pro Q[11] a Q[12] v tabulce 2., vidíme, že případná změna Q[9] na i-tém bitu by se nemusela vůbec projevit v těchto rovnicích, pokud bude i-tý bit Q[10] nula a i-tý bit Q[11] jednička, tj. Q[10]i = 0, Q[11]i = 1. Funkce F v tom případě nezávisí na hodnotě i-tého bitu Q[9], viz definice F(x, y, z) = (x AND y) XOR ((NON(x) AND z). Q[ 7]=Q[ 6]+RL(F(Q[ 6],Q[ 5],Q[ 4])+Q[ 3]+x[ 6] Q[ 8]=Q[ 7]+RL(F(Q[ 7],Q[ 6],Q[ 5])+Q[ 4]+x[ 7] Q[ 9]=Q[ 8]+RL(F(Q[ 8],Q[ 7],Q[ 6])+Q[ 5]+x[ 8] Q[10]=Q[ 9]+RL(F(Q[ 9],Q[ 8],Q[ 7])+Q[ 6]+x[ 9] Q[11]=Q[10]+RL(F(Q[10],Q[ 9],Q[ 8])+Q[ 7]+x[10] Q[12]=Q[11]+RL(F(Q[11],Q[10],Q[ 9])+Q[ 8]+x[11] Q[13]=Q[12]+RL(F(Q[12],Q[11],Q[10])+Q[ 9]+x[12] Q[14]=Q[13]+RL(F(Q[13],Q[12],Q[11])+Q[10]+x[13] Q[15]=Q[14]+RL(F(Q[14],Q[13],Q[12])+Q[11]+x[14]
+0xa8304613,17); +0xfd469501,22); +0x698098d8, 7); +0x8b44f7af,12); +0xffff5bb1,17); +0x895cd7be,22); +0x6b901122, 7); +0xfd987193,12); +0xa679438e,17);
32 p. 29 p. 28 p. 18 p. 19 p. 15 p. 14 p. 15 p. 9 p.
Tabulka 2.: Rovnice pro tunel Q9
Na všech těchto bitech i můžeme změnit hodnotu Q[9]i, přičemž tato změna se neprojeví v rovnicích pro Q[11] a Q[12]. Projeví se v rovnicích pro Q[9], Q[10] a Q[13]. Tyto změny však kompenzujeme změnou hodnot zprávy, tj. x[8], x[9] a x[12], zatímco Q[10], Q[11], Q[12] a Q[13] zůstávají nezměněny. Na dalším obrázku vidíme, co znamenají změny hodnot x[8], x[9] a x[12] pro následující proměnné Q[14] až Q[64]. Pokud se podíváme do tabulky 2. v příloze 2. vidíme, že změny se projeví až za bodem verifikace, takže všechny podmínky před ním zůstávají splněny. A jak je z této tabulky dále vidět, změní se všechny proměnné Q[25] až Q[64], a to dosti složitým a náhodným způsobem. Abychom získali co nejsilnější tunel, máme zájem na nastavení co nejvíce dvojic bitů Q[10]i=0 a současně Q[11]i=1. Tyto podmínky nejsou součástí postačujících podmínek, jsou to extra podmínky pro zajištění přítomnosti tunelů. Bohužel počáteční podmínky v současném diferenčním schématu umožňují jen volbu třech těchto pozic (i = 22, 23, 24), ostatní nejsou volné. Tím získáváme tunel o síle 3.
8.1.4 Výsledky Metoda tunelování spočívá v ideálním případě v nalezení pouze jednoho bodu POV. Pomocí tunelů se pak tento bod rozmnoží na potřebný počet, zde 229. Jeden bod POV je v tomto případě možné udělat jakkoli i zcela náhodně s minimální složitostí. V ideálním případě tak zcela odpadá fáze přípravy bodů POV a dále v diferenčním schématu (diferenční cesta plus postačující podmínky) je možné ponechat pouze postačující podmínky a podmínky pro zajištění přítomnosti tunelů. Pro nalezení takového množství bodů POV není třeba nalézt jeden tunel o síle 29, ale stačí najít několik menších tunelů o sílách n1, n2 .. nm, tak aby n1 + n2 + ... + nm = 29.
41
Rychlost hledání kolizí pomocí tunelů byla ověřena experimentálně a průměrná doba nalezení kolize na normálním notebooku byla asi 31s [9].
8.2 Paralelní hledání kolizí v hašovacích funkcích Paul C. van Oorschot a Michael J Wiener v [10] publikovali metodu paralelního hledání kolizí, a to nejen v hašovacích funkcích. Jejich nová metoda je založena na Pollardově rhometodě, která byla v původní verzi aplikována na faktorizaci [11] a diskrétní logaritmy [12]. Pollardova rho metoda pro diskrétní logaritmy je vylepšením známého „baby-step giant-step“ algoritmu připisovaného Shanksovi [13]. Shanksova metoda umožňovala spočítat diskrétní logaritmy v cyklické grupě o velikosti n v deterministickém čase O(√n) a při potřebném místě pro √n grupu prvků. Polladova rho-metoda má také časovou složitost O(√n), ale s potřebou pouze velmi malé spotřeby místa.
8.2.1 rho-metoda Pokud se obecná rho-metoda používá na hledání kolizí mezi výstupy funkce f, pak se jedná jen o vylepšení jednoduché techniky vybrání různých vstupů xj, pro j = 1,2,3,.. a hledání kolizí mezi hodnotami f(xj). Vylepšení spočívá hlavně v menší náročnosti na místo pro uložení dat. Předpokládejme funkci f, která má stejný definiční obor i obor hodnot f :S -> S. Předpokládejme, že S je konečná množina. Pak rho-metoda bude provádět pseudo-náhodnou procházku po této konečné množině, a to následovně: pro vytvoření vstupního souboru dat xi, pro i = 0,1,2, ... vybereme počáteční hodnotu x0, na ni aplikujeme funkci f, následně budeme aplikovat funkci f vždy na výsledek předchozího kroku, tzn.: xi = f(xi-1), pro i = 1,2,3 ... . Jelikož je S konečná, tak se tato sekvence musí začít cyklit. Tato sekvence bude obsahovat vedoucí subsekvenci následovanou nekonečným cyklem. Pokud je xk poslední prvek vedoucí subsekvence, než začne cyklus, pak xk+1 je již na tomto cyklu. Nechť xc je bezprostřední předchůdce xk+1 pak dostáváme kolizi, protože f(xk) = f(xc), ale xk ≠ xc [10].
Přímá paralelizace rho-metody Pollardova rho-metoda je přirozeně sériová. Vždy se musí počkat na dokončení daného volání funkce f, než začne další krok. O paralelizaci se pokusil Brent při použití rho-metody pro faktorizaci [14]. Spustil paralelně velké množství procesorů, kde každý produkoval nezávislou sekvenci, naneštěstí tato paralelní implementace rho-metody nedala lineární zrychlení. Podobně by dopadly i pokusy o podobnou paralelizaci při hledání kolizí. Je jasné, že každý paralelně pracující procesor produkuje vlastní sekvenci zcela nezávislou na ostatních procesorech, a to znamená, že se tím nezvyšuje šance nalezení kolize u ostatních procesorů [10].
Vylepšená paralelizace rho-metody Při paralelním hledání kolizí pomocí rho-metody bude každý procesor mít podobnou sekvenci, jak byla popsána výše, tzn.: zvolí si svůj počáteční bod x0 (nezávisle na ostatních procesorech) a začne produkovat sekvenci bodů xi, kde xi = f(xi-1). Ovšem nečeká na vytvoření nějaké kružnice, ale skončí, jakmile dosáhne charakteristického bodu. Charakteristický bod má nějakou lehce testovatelnou vlastnost, například předem daný počet nulových bitů. Jakmile
42
dosáhne tohoto bodu, skončí a tento charakteristický bod přidá do seznamu charakteristických bodů společného pro všechny procesory. Následně si vybere další počáteční bod a proces začne od začátku. Kolizi nalezneme tehdy, pokud do seznamu pro ukládání charakteristických bodů uložíme charakteristický bod, který v něm již je. Pak je jasné, že dvě sekvence vedly z různých počátečních bodů do stejného charakteristického bodu. Konkrétní kolizi nalezneme v místě, kde se tyto dvě sekvence potkaly viz.obr.6.
x5 = x4’ x4 = x3’ x3 = x2’ x2 Sekvence 2.
x1 x0
Sekvence 1.
x1’ x0’ Sekvence 4.
Sekvence 3. Charakteristický bod:
Obrázek 6. : Sekvence a charakteristické body
V případě znázorněném na tomto obrázku je kolizní dvojce x2 a x1’. Pokud jsme hledali jen jedinou kolizi, pak hledání končí, pokud kolizí potřebujeme více, proces pokračuje, dokud stejným způsobem nenalezneme daný počet kolizí. Můžou nastat některé speciální případy. První je, pokud nějaký procesor vstoupí do cyklu, v němž neexistuje žádný charakteristický bod, v tomto případě by procesor nebyl již dále využit. Nechť je Ө podíl bodů, jež splňují vlastnost charakteristického bodu, pak je průměrná délka sekvence vedoucí do charakteristického dobu 1/Ө. Problém s nekonečnými cykly můžeme vyřešit nastavením maximální délky sekvence bodů na 20/Ө. Pokud se v tomto počtu kroků nenajde charakteristický bod, je tato sekvence opuštěna a je pro daný procesor zvolen další počáteční bod. Druhý speciální případ který může nastat je, že jedna sekvence bude kolidovat s počátečním bodem jiné sekvence. V tomto případě máme tzv.: „Robina Hooda“ a tento případ nevede ke kolizi. Ovšem v reálném případě je Ө velmi malé číslo a průměrná velikost sekvence je velmi velká, takže pravděpodobnost “Robina Hooda” je tak malá, že se tento speciální případ nevyplatí ošetřovat [10].
8.2.2 Dopady paralelního hledání kolizí Pomocí této paralelní metody můžeme hledat nejenom kolize v hašovacích funkcích obecně (tzn. dvě náhodné zprávy, které mají stejnou haš hodnotu), ale i smysluplné kolize (tzn. vstupem nejsou zcela náhodné zprávy, ale útočník může z velké části nebo úplně ovlivnit obsah zpráv). Ukážeme si, jak se dá vylepšit starší útok prezentovaný Yuvalem [15]. Tento útok
43
využívá toho, že pro digitální podpisy se častěji než celá zpráva používá jen haš hodnota této zprávy. Předpokládejme, že máme zprávu m, kterou chceme aby náš cíl podepsal, ale on to nechce udělat. V tuto chvíli využijeme toho, že nám stačí, aby náš cíl digitálním podpisem podepsal jen haš teto zprávy. Proto vybereme nějakou jinou zprávu m´, kterou náš cíl bude ochoten podepsat. Teď najdeme způsoby jak modifikovat obě zprávy m a m´ tak aby to nezměnilo jejich obsahový smysl. Tímto získáme velké množství modifikovaných zpráv m a m´ a jejich různých haš hodnot. Zprávy budeme modifikovat tak dlouho, dokud nenajdeme takovou verzi zprávy m a takovou verzi zprávy m’, jejichž hodnoty se budou rovnat. Náš cíl poté podepíše takovouto haš hodnotu zprávy m’ a my následně můžeme tento podpis připojit ke zprávě m. Tento útok má časovou a prostorovou složitost O(√n), kde n=|R|. Právě paměťové požadavky pro tento útok můžou být eliminovány použitím paralelní techniky hledání kolizí. Nechť m∈M, pak si zavedeme injektivní funkci gm:R->M, která má na vstupu haš hodnotu (a fixní zprávu m) a jejímž výstupem je modifikovaná zpráva m se stejným obsahovým smyslem jako původní zpráva m. Rozdělíme si množinu R na dvě přibližně stejné podmnožiny S1 a S2 založené na nějaké jednoduše testovatelné vlastnosti haš hodnot. Dále si definujeme funkci f:R->R pro konstantní zprávy m a m´ následovně: f(r)
{
H(gm (r)), jestliže (r∈S1) H(gm’(r)), jestliže (r∈S2)
Použitím metody paralelního hledání kolizí popsané výše najdeme dvojice haš hodnot a,b takové, že f(a)=f(b), ale a≠b. Takto nalezená kolize je použitelná pouze pokud a a b jsou v rozdílných množinách, toto nastane s pravděpodobností ½. Předpokládejme takto nalezenou dvojici a∈S1 a b∈S2, pak H(gm(a))=H(gm´(b)), kde H je námi zvolená hašovací funkce. To znamená, že máme verzi zprávy m a verzi zprávy m´, které mají stejnou haš hodnotu [10].
8.2.3 Jak modifikovat zprávu beze změny obsahu Jednou z možných modifikací zprávy bez změny obsahu je přidávání přebytečných mezer mezi slova v textu (pro účely funkce gm například určité bity ve vstupní haš hodnotě odpovídají určitým pozicím, na které lze vložit do zprávy m mezeru, podle toho zda má daný bit hodnotu 1 nebo 0 bude mezera vložena nebo ne) [10]. Další z možností je použití textového procesoru a v něm na pozadí naší zprávy m vložit obrázek (například logo firmy). Modifikovat v tomto případě nebudeme samotnou zprávu m, ale právě obrázek na pozadí, což nám umožní téměř neomezené možnosti modifikace [10].
44
8.3 Útoky pomocí kolizí zpráv se stejným prefixem Pokud je možno nalézt kolizi v dané hašovací funkci, pak je v [16] popsán způsob získání kolizních zpráv v této hašovací funkci, které mají stejný prefix. Je zde ukázáno, jak lze těchto kolizních zpráv zneužít. Vlastnost odolat tomuto typu útoku autoři nazvali Choosen target forced prefix (CTFP) preimage resistance. Jde o to, že útočník si vybere cílový haš (choosen target) a snaží se nalézt zprávu m, která má daný prefix P (forced prefix), takovou aby měla haš H. Autoři ve svém článku přepokládají hledání kolizí především hrubou silou, ale dala by se na hledání těchto kolizí použít i metoda paralelního hledání kolizí popsaná v kapitole 8.2.
8.3.1 Jak najít kolizi dvou vstupních zpráv, které mají společný prefix Předpokládáme-li, že útočník si může vybrat zadaný haš. Dále se zadaný prefix zprávy, kterou bude hledat, se dozví později, pak je stručný postup nalezení takovéto zprávy následující. 1. Útočník si vybuduje tzv. diamantovou strukturu podobnou binárnímu stromu, jejímž kořenem je vybraný haš H. Tuto strukturu tvoří kolizní zprávy a obsahuje na své nejnižší úrovni 252 (pro 160ti bitou hašovací funkce) a více uzlů. Počet zpráv v diamantové struktuře závisí na zvolené hašovací funkci, velikosti přidaného sufixu a celkové práci kterou na budování diamantové struktury můžeme nebo jsme ochotni vynaložit. 2. Poté co, se dozví zadaný prefix P, začne hledat nějaký jednoblokový sufix S, takový že hash(P|S) = nějaký prvek diamantové struktury. S je tzv. spojovací zpráva. 3. Poté co nalezne takovýto sufix S, pomocí kterého vytvoří kolizi s nějakým prvkem diamantové struktury, získá z diamantové struktury sufix X, takový že hash(P|S|X) = H. Každá úroveň diamantové struktury, kterou dělí nalezenou kolizi od kořene, zvětší přidaný sufix X o jeden blok. Pokud bychom chtěli, aby finální zpráva měla nějakou fixní délku, pak v kroku 2 nehledáme kolizí s jakýmkoliv prvkem diamantové struktury, ale jen s prvky na nejnižší úrovni. 4. Po nalezení spojovací zprávy S a sufixu X může útočník sestavit hledanou vstupní zprávu se zadaným prefixem P, tato zpráva bude mít tvar: (P|S|X) a její haš se bude rovnat vybranému haši H.
8.3.2 Diamantová struktura Diamantová struktura je binární strom, jehož uzly jsou hodnoty IHV (intermediate hash value) a jehož hrany jsou zprávy (viz obr.7).
45
Obrázek 7.: Ukázka diamantové struktury
Vždy ze dvou IHV (uzlů) a k nim přidaných dvou zpráv (hran) vznikne kolize, která je ve stromu o úroveň výš. Na obrázku č.7 jsou to například IHV h[0,0], IHV h[0,1] a k nim odpovídající zprávy znázorněné hranami vedoucími do kolizní IHV h[1,0].
Budování diamantové struktury Prvním krokem je vybrání 2k vstupních zpráv, pro které spočítáme jejich haše. Tím nám vznikne nejnižší úroveň IHV naši diamantové struktury. Poté začneme hledat takové jednoblokové zprávy, které po přidání k námi spočítaným IHV vytvoří kolizní páry. Hledání těchto kolizí není tak těžké, jak se na první pohled zdá. Místo abychom fixovali pozice každého uzlu, tak dynamicky utváříme diamantovou strukturu podle toho, mezi kterými uzly vznikne kolize. Postupně se všechny počáteční IHV sloučí pomocí odpovídajících zpráv do jediného kolizního haše H. Na obrázku č. 7 je to IHV h[3,0]. Při použití útoku hrubou silou je pro nalezení všech zpráv potřebných pro přechod od úrovně s 2k IHV k úrovni s 2k-1 IHV, potřeba vygenerovat asi 2n/2+1/2-k/2 kandidátských jednoblokových zpráv. Celkově je třeba vygenerovat asi 2n/2+1/2+k/2 kandidátských jednoblokových zpráv, pokud v nejnižší úrovni bylo 2k IHV. Samozřejmě můžeme použít i nějaký sofistikovaný algoritmus pro hledání kolizi, který ovšem musí splňovat některé podmínky popsané v [16].
Předpočítání diamantové struktury Pokud je množina možných prefixů omezena, můžeme místo náhodných zpráv, pro počítání první úrovně IHV použít právě tuto množinu všech možných prefixů. Tím si zajistíme, že ať bude v budoucnu požadován jakýkoliv prefix, budeme moci bez dalších výpočtů ihned vyprodukovat zprávu s daným prefixem, která má haš H.
46
8.3.3 Útoky s využitím diamantové struktury Nostradámův útok Útočník (Nostradámus) používá hašovací funkci k prokázání znalosti nějaké budoucí události. Tvrdí, že zná nějakou budoucí událost nebo informaci, která dosud není známá (například ceny na burze, na konci posledního dne v roce). Svoje tvrzení podpoří hašem, o kterém tvrdí, že je to haš zprávy obsahující tuto informaci, plus nějaké další nepodstatné věci. Samotnou zprávu ukáže až po tom, co nastane tato událost. Pokud útočník použije výše uvedený postup, tak znalost této události opravdu prokáže. Navíc některé takovéto předpovědi mají omezenou množinu možností a tak se dá s úspěchem použít předpočítání diamantové struktury.
Změna podepsaného dokumentu Útočník může vydat dokument, jenž podepíše hašem H, pro který si vytvořil diamantovou strukturu. Později může tvrdit, že nepodepsal tento dokument, ale dokument s úplně jiným prefixem, který si sám zvolí. Podobných útoků využívajících této metody se dá vymyslet velké množství [16].
8.3.4 Smysluplnost dat Na první pohled patrný problém tkví v náhodnosti sufixu, který připojujeme k zvolenému prefixu. Je jasné, že pro použití v reálné situaci by náhodný soubor znaků na konci zveřejněné zprávy vypadal přinejmenším podezřele. Je třeba tedy produkovat smysluplný sufix. Jedna z možností je použití Yuvalova triku [15]. Místo generování náhodných zpráv si připravíme dostatečně dlouhý dokument zabývající se tématem vhodným k našemu podvrhu a z něj můžeme vybírat mnoho nezávislých částí, které můžeme modifikovat. Například každá zpráva na i-té úrovni diamantové struktury bude variace na to samé téma. Pro vytvoření dostatečného počtu variací pro zprávy na dané úrovni bude potřeba asi n/2 změnových bodů (bodů, kde se dá zpráva modifikovat bez toho, aby se změnil obsahový smysl). Toto sice daný sufix prodlouží, protože tolik změnových bodů do jednoho bloku asi vložit nepůjde, ale to na celkový výsledek nemá vliv. Tento způsob nám umožní vytvořit smysluplný sufix, který navíc bude mít ve všech větvích diamantové struktury stejný smysl.
47
9 Útoky na kryptografické protokoly 9.1 Časová analýza SSH SSH je navržen tak, aby poskytoval bezpečný kanál mezi dvěma účastníky. Poskytuje nástroje pro ověření a šifrování dat na zabezpečení kanálu. Přes všechny svoje zabezpečení Song, Wagner a Tian prezentovali dvě slabosti SSH vzhledem k časové analýze [42]. 1. Přenášené packety jsou doplněny na osm bytů (pokud je použita bloková šifra). Což útočníkovi umožňuje zjistit přibližnou délku originálních dat. 2. V interaktivním módu je každá klávesa, kterou uživatel stiskne, odeslána samostatně v IP packetu okamžitě po jejím stisknutí (samozřejmě s výjimkami jako jsou CTRL nebo SHIFT). Jelikož čas, který potřebuje operační systém na odeslání packetu po stisknutí klávesy je zanedbatelný vzhledem k času mezi stisknutím jednotlivých kláves, tak tato vlastnost umožňuje útočníkovi, podle času příchodu packetů, měřit právě tyto časy mezi stisknutí jednotlivých kláves. Ve své práci se zaměřili hlavně na druhou prezentovanou slabost. Při přihlášení pomocí SSH ke vzdálenému počítači se zadávané heslo odesílá v jednom packetu (nebo více, pokud je delší jak osm znaků). Důležité však je, že pokud se pomocí již navázaného spojení pokoušíme přihlásit k dalšímu vzdálenému počítači, tak heslo již neodchází jako celek, ale jednotlivé znaky odcházejí postupně, ihned jakmile je stisknutá odpovídající klávesa, v izolovaných IP packetech. Jelikož je odesláno každé stisknutí klávesy i při zadávání příkazů na příkazovou řádku, tak je možné identifikovat sekvenci která předchází zadání hesla pro přihlášení, jak ukazuje obr. X. [42]
Obrázek 8.: Provoz na síti spojený s příkazem su. Čísla v obrázku jsou velikosti odpovídajících packetům.
Potencionální útočník tak nejenom může získat počet znaků v hesle, ale i časy mezi stisknutím jednotlivých kláves. Dále ukázali jak moc informace lze z takto získaných časů zjistit o dvojici kláves, které byly stisknuty. Z posbíraných dat se zjistili, že z časů mezi stisknutím jednotlivých kláves hesla lze získat v průměru 1,2 bitu informace. Což je nezanedbatelné množství (v angličtině nese každý znak 0,6 – 1,3 bitu informace). Pokud jsou k dispozici naměřená data, tak je možné nad nimi vytvořit statistický model, který může určovat možné kombinace kláves, jaké mohly být stisknuty vzhledem k naměřenému času mezi stisknutím kláves. Tato dodatečná informace může vést k odhalení hesla, nebo alespoň může snížit prostor pro útok hrubou silou. [42]
48
Experimentální výsledky autorů ukázaly, že pokud jsou nasbírané vzorky (nad kterými je postaven statistický model) od uživatele, kterému je heslo zjišťováno, je zmenšení prostoru pro útok hrubou silou opravdu radikální (z množiny možných hesel, která vyšla ze statistického modelu, se reálné heslo vyskytovalo v prvních několika málo procentech). Při použití statistického modelu postaveného nad vzorky od jiného uživatele byly naměřené výsledky horší (reálné heslo se vyskytovalo většinou v prvních 20%), ale přesto velice urychlily hledání hesla hrubou silou. Obecně tento útok urychlil vyhledávání hesla hrubou silou až 50krát. [42]
49
10 Praktický útok Pro praktickou ukázku jsem si zvolil hledání útok pomocí diamantové struktury popsaná v kapitole 8.3. K této volbě mě vedlo hned několik důvodů. Tento útok má velice jednoduchou myšlenku a přitom je velice efektivní. Je velice použitelný i v praxi, hlavně z důvodu, že není závislý na konkrétní implementaci konkrétní hašovací funkce, ale lze ho dokonce použít pro útok na jakoukoliv hašovací funkci. Další výhodou pro použití v praxi je, že výstup tohoto útoku se bude, při použití metod prezentovaných v 8.3.4, jevit velice věrohodně. Navíc jasně ukazuje jak je pro každou hašovací funkci důležitá odolnost proti kolizím. Jakmile totiž lze efektivně nalézt kolize v jakékoliv hašovací funkci, tak je tato funkce tímto útokem jednoduše napadnutelná. Protože tento útok popisuje univerzální postup napadnutí hašovací funkce bude jednoduše použitelný i v budoucnu narozdíl od útoku vymyšleného na konkrétní implementaci nějaké hašovací funkce.
10.1. Popis implementace Tento útok má dvě fáze. První fází je vybudování diamantové struktury a druhou fází, po té co již máme vybudovanou diamantovou strukturu je nalezení spojovací zprávy a vytvoření výsledné zprávy, která bude mít odpovídající haš hodnotu.
10.1.1 Fáze 1 – vybudování diamantové struktury V této fázi se ze vstupních dat vytvoří diamantová struktura. Vstupní hodnoty jsou typu string a jejich počet musí být 2i, kde i je přirozené číslo. Vstupní data budou použita na vytvoření nejnižší úrovně diamantové struktury a následně se spustí cyklický proces, který najde pro nějakou dvojici prvků na stejné úrovni kolizní haš. Teto haš bude prvkem další úrovně diamantové struktury. Jakmile se najde pro všechny prvky dané úrovně kolizní haš, tak proces pokračuje ve zpracovávání další úrovně. Celý proces vytvoření diamantové struktury končí, jakmile na nové úrovni existuje jen jeden prvek (jedna haš hodnota H), kořen diamantové struktury. Tato fáze je časově nejnáročnější, je v ní třeba nalézt velké množství kolizí, proto velice záleží na použité hašovací funkci a počtu vstupních hodnot. Výhoda této fáze je, že se neprovádí v časové tísni, máme většinou čas si diamantovou strukturu přepočítat, zveřejnit výsledný haš H a čekat na prefix, pro který budeme hledat zprávu s haš hodnotou H.
10.1.2 Fáze 2 – Nalezení spojovací zprávy Do této fáze vstupuje přepočítaná diamantová struktura a prefix pro který hledáme výslednou zprávu s haš hodnotou H. Teď jsme pomocí diamantové struktury schopni najít zprávu s jakýmkoliv prefixem která bude mít haš hodnotu H. Tato fáze je, oproti fázi 1, mnohem méně časově náročná, je totiž třeba najít jen jednu kolizi a to ještě množství možných kolizních zpráv se rovná počtu prvků diamantové struktury, pokud nepotřebujeme sufix s přesně stanovenou délkou i+1 (i bloků je přidáno z diamantové struktury a jeden blok je spojovací zpráva), pokud potřebujeme tuto konstantní délku, tak je počet možných kolizních zpráv roven počtu prvků na nejnižší úrovni diamantové struktury. Tato fáze naopak probíhá v časové tísni.
50
Po obdržení prefixu musím dokázat vytvořit odpovídající zprávu co nerychleji, abychom například mohli prokázat znalost tohoto prefixu ještě před jeho zveřejněním.
10.2 Možnosti modifikace Z důvodů omezených výpočetních kapacit je v dodaném kódu použita velice jednoduchá hašovací funkce. Pro útok na jinou hašovací funkci je třeba implementovat funkci diamantHash(string input) podle požadavků definovaných v kódu a přiložené dokumentaci.
10.3. Použitý jazyk a nástroje Pro naprogramování tohoto útoku jsem použil C++. Kód byl napsán a zkompilován v DEV C++ verze 4.9.9.2
51
11 Závěr Cílem této práce bylo vytvořit přehled moderních kryptoanalytických metod, nezávislých na konkrétní hardwarové implementaci, pro aktuálně používané kryptologické algoritmy a mechanizmy. Na nich jsem se snažil ukázat rizika, z toho vyplývající, pro praktické využití těchto algoritmů. V první části uvádím stručný popis základních kryptografických mechanizmů. Více se v ní zabývám postupy, které následně využiji při popisu útoků v druhé části. V druhé části jsem se snažil pro prezentované metody uvést ucelený popis, který, pro čtenáře dostatečně vybaveného teoretickými znalostmi o základních principech a mechanizmech kryptografických postupů a metod, nebude pro pochopení vyžadovat podrobné studium dalších materiálů. Jelikož existuje celá řada různých kryptoanalytických metod a konkrétních útoků, nebylo možno na omezeném prostoru uvést zcela vyčerpávající přehled. Proto jsem musel vybrat jen určité reprezentanty pro daný typ útoků na konkrétní algoritmy. Vybral jsem proto z každé oblasti nejpoužívanější algoritmus a na něm prezentoval vybrané útoky. Ovšem i pro tyto vybrané algoritmy existuje celá řada útoků. Snažil jsem se zde uvést ty, jenž ve svém důsledku mají větší dopad na bezpečnost těchto algoritmů a jsou i prakticky využitelné, to znamená že představují reálnou hrozbu pro aktuálně používané implementace, nebo jsou nějakým způsobem zajímavé. Velká pasáž je zde věnována metodě hledání kolizí v MD5 pomocí diferenciálních schémat a následně tunelů. Další větší pasáž je věnována chybovým analýzám blokových šifer v módu CBC a chybovým analýzám RSA. Dle mého názoru jsou tyto metody důležité, jelikož odhalují slabiny ve velmi rozšířených kryptografických algoritmech a je proto nutné se jim více věnovat. Podle zadání jsem se měl ve větší míře věnovat diferenciální kryptoanalýze symetrických šifer. Ovšem největší rozmach diferenciální kryptoanalýzy byl při prolomení šifry DES a podle mě již šifra DES nepatří do skupiny moderních kryptologických algoritmů, po té co bylo ukázáno její prolomení ve velmi krátké době a její nahrazení šifrou AES. Další šifry navrhované po prezentování diferenciální kryptoanalýzy DES byly již implementovány tak, aby byly proti takovému útoku odolné. Proto neexistuje mnoho aktuálně používaných a široce rozšířených algoritmů, na které by šla diferenciální kryptoanalýza efektivně použít. Naopak útoky jimž jsem věnoval větší část práce (útoky pomocí chybové analýzy) jsou momentálně velice časté a budoucí implementace stávajících, ale i nových algoritmů budou muset počítat s tím, že jakákoliv i sebe méně podstatná informace unikající při šifrování či dešifrování je velikým potencionálním rizikem a může vést až k úplnému prolomený kryptografického systému. Pro implementaci konkrétního útoku popsaného v třetí části jsem si vybral útok pomocí diamantové struktury. Důvodem vybrání je jednoduchost a elegantnost základní myšlenky. Také proto, že je tento útok zcela nezávislý na konkrétní hardwarové implementaci a dokonce i nezávislý na konkrétním použitém algoritmu, z čehož vyplívá možnost jeho jednoduchého rozšíření pro jakoukoliv hašovací funkci. V neposlední řadě to byl i důvod výpočetních kapacit, které jsem měl pro implementaci k dispozici. Navíc tento útok podle mě jasně ukazuje jak nebezpečné jsou kolize v používaných hašovacích funkcích a jak velké riziko představují. Tato práce je vypracována k datu květen 2007 a zohledňuje jen metody a útoky prezentované k tomuto datu. Je zřejmé že jak se budou vyvíjet nové postupy a metody kryptografie, budou se vyvíjet i kryptoanalytické metody a budou publikovány nové útoky. Proto pro budoucí použití této práce ji bude třeba aktualizovat.
52
12 Literatura [1]
Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, CRYPTO 2004, Cryptology ePrint Archive: Článek 2004/199. Dokument dostupný na URL: http://eprint.iacr.org/2004/199.pdf (březen 2007)
[2]
Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision, Cryptology ePrint Archive: Článek 2004/264, 13. řijna 2004. Dokument dostupný na URL: http://eprint.iacr.org/2004/264.pdf (březen 2007)
[3]
Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, Cryptology ePrint Archive: Článek 2005/102, 5. května 2005. Dokument dostupný na URL: http://eprint.iacr.org/2005/102.pdf (Březen 2007)
[4]
X. Wang and H. Yu: How to Break MD5 and Other Hash Functions., Eurocrypt’05, Springer-Verlag, LNCS, Vol. 3494, pp. 19–35. Springer, 2005.
[5]
Jun Yajima and Takeshi Shimoyama: Wang’s sufficient conditions of MD5 are not sufficient, Cryptology ePrint Archive: Článek 2005/263, 10. srpna 2005. Dokument dostupný na URL: http://eprint.iacr.org/2005/263.pdf (Březen 2007)
[6]
Yu Sasaki and Yusuke Naito and Noboru Kunihiro and Kazuo Ohta: Improved Collision Attack on MD5, Cryptology ePrint Archive: Článek 2005/400, 7. listopadu 2005. Dokument dostupný na URL: http://eprint.iacr.org/2005/400.pdf (Březen 2007)
[7]
Liang J. and Lai X.: Improved Collision Attack on Hash Function MD5, Cryptology ePrint Archive: Článek 2005/425: Článek 425/2005, 23. listopadu 2005. Dokument dostupný na URL: http://eprint.iacr.org/2005/425.pdf. (Březen 2007)
[8]
Vlastimil Klima: Finding MD5 Collisions – a Toy for Notebook, Cryptology ePrint Archive, 5. března 2005. Dokument dostupný na URL: http://eprint.iacr.org/2005/075.pdf (Březen 2007)
[9]
Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute IACR ePrint archive: Článek 2006/105. Dokument dostupný na URL: http://eprint.iacr.org/2006/105.pdf, 18. března, 2006, v češtině na http://cryptography.hyperlink.cz/2006/tunely.pdf. (Březen 2007)
[10] P.C. van Oorschot and M.J. Wiener: Parallel Collision Search with Cryptanalytic Applications, 1995. [11] J.M. Pollard: A Monte Carlo method for factorization, BIT, díl 15 , s. 331-334, 1975. [12] J.M. Pollard: Monte Carlo Methods for Index Computation (mod p), Math.Comp. díl. 32, s. 918-924, 1978. [13] D.E. Knuth: The Art of Computer Programming, díl. 3: Sorting and Searching, AddisonWesley, 1973.
53
[14] R.P. Brent: Parallel algorithms for integer factorization, London Mathematical Society Lecture Note Series díl. 154, Number Theory and Cryptography, J.H. Loxton (ed.), s. 2637, Cambridge University Press, 1990. [15] G. Yuval: How to Swindle Rabin, Cryptologia, díl. 3, s. 187-189, 1979. [16] T. Kohno, J. Kelsey: Herding Hash Functions and the Nostradamus Attack, Advances in Cryptology -- Eurocrypt'2006, LNCS 4004, s. 183--200, Springer (2006). Dokument dostupný na URL: src.nist.gov/pki/HashWorkshop/2005/Oct31_Presentations/Kelsey_HerdingHash.pdf (květen 2007) [17] A. Menezes, P. van, Oorschot, S. Vanstone: Handbook of Applied Cryptography, CRC Press, 1996. Dokument dostupný na URL: http://www.cacr.math.uwaterloo.ca/hac. (duben 2007) [18] Fred Piper, Sean Murphy: Kryptografie, s. 74 – 83, Dokořán s.r.o., 2006. [19] Pavel Vondruška, Kryptologie, šifrování a tajná písma, s. 8 – 11, Albatros, Praha, 2006. [20] Vaudenay, S.: Security Flaws Induced By CBC Padding - Application to SSL, IPSEC, WTLS..., EUROCRYPT '02, s. 534-545, Springer-Verlag, 2002 . [21] Vaudenay, S.: CBC Padding: Security Flaws in SSL, IPSEC, WTLS..., Rupm session of CRYPTO 01, 2001 [22] PKCS#5 v. 2.0: Password-Based Cryptography Standard, RSA Laboratories, March 25, 1999. [23] Black, J., and Urtubia, H.: Side-Channel Attacks on Symmetric Encryption Schemes: The Case for Authenticated Encryption, In Proc. of 11th USENIX Security Symposium, s. 327-338, San Francisco 2002. . [24] V. Klíma,T. Rosa:. Side Channel Attacks on CBC Encrypted Messages in the PKCS#7 Format. Dokument dostupný na URL: http://eprint.iacr.org/2003/098.pdf. (leden 2007) [25] PKCS #7 v1.5: Cryptographic Message Syntax Standard, RSA Laboratories, November 1, 1993. [26] ITU-T Recommendation X.680 (1997), ISO/IEC 8824-1:1998, Information Technology – Abstract Syntax Notation One (ASN.1): Specification of Basic Notation. [27] Daemen, and Rijmen, V.: AES proposal: Rijndael. Dokument dostupný na URL: http://carc.nist.gov/encryption/aes/rijndael/Rijndael.pdf (leden 2007) [28] Rivest, R.; Shamir, A.; and Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." MIT Memo MIT/LCS/TM-82, 1977. Dokument dostupný na URL: http://theory.lcs.mit.edu/~rivest/rsapaper.pdf (leden 2007)
54
[29] D. Boneh and Hovav Shacham: Fast variants of RSA,. CryptoBytes, díl. 5, s. 1-9. Dokument dostupný na URL: http://crypto.stanford.edu/~dabo/pubs.html (Březen 2007) [30] Manger, J.: Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS#1 v2.0, Crypto’2001, s. 230 – 238, Springer Verlag, 2001. [31] D. Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In Hugo Krawczyk (ed.), Advances in Cryptology CRYPTO '98, s. 1 - 12, Berlin, Springer, 1998. [32] PKCS #1 v2.0: RSA Cryptography Standard, 1. řijna 1998. Dokument dostupný na URL: http://www.rsasecurity.com/rsalabs/pkcs/ (Leden 2007) [33] V. Klíma,T. Rosa.Further results and considerations on side channel attacks on RSA. CHES 2002, LNCS 2523, s.244-259, 2002. [34] PKCS#1 v2.1: RSA Cryptography Standard, RSA Laboratories, DRAFT2, 5. ledna 2001. [35] Messegers, T.-S., Dabbish, E. A. and Sloan, R. H.: Investigations of Power Analysis Attacks on Smartcards, in Proc. of USENIX Workshop on Smartcard Technology, s. 151161, 1999. [36] Secure Hash Standard, Federal Information Processing Standards Publication 180-1, 17.dubna 1995. [37] Håstad, J. and Näslund M.: The Security of Individual RSA Bits, in Proc. of FOCS ’98, s.510-521, 1998. [38] Shoup, V.: A Proposal for an ISO Standard for Public Key Encryption (version 2.0), 17. září, 2001. [39] J. Blömer, J.P. Seifert. Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). FC 2003,LNCS 2742, s.162-181, 2003. [40] R. Anderson, M. Kuhn, “Tamper Resistance – a cautionary note”, Proc. of 2nd USENIX Workshop on Electronic Commerce, s. 1–11, 1996. [41] R. Anderson, M. Kuhn, “Low cost attacks attacks on tamper resistant devices”, Proc. of 1997 Security Protocols Workshop, Springer LNCS díl. 1361, s. 125–136, 1997. [42] Dawn Xiaodong Song, David Wagner and Xuqing Tian, Timing Analysis of Keystrokes and Timing Attacks on SSH, 10th USENIX Security Symposium, 2001 [43] H. Wu and B. Preneel, Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy, Eurocrypt 2007, LNCS, Springer-Verlag, 2007. [44] E. Biham, J. Seberry, Py (Roo): A Fast and Secure Stream Cipher Using Rolling Arrays. The ECRYPT eSTREAM project Phase 2 focus ciphers. Dokument dostupný na URL: http://www.ecrypt.eu.org/stream/ciphers/py/py.ps .(květen 2007)
55
[45] E. Biham, J. Seberry, Pypy (Roopy): Another Version of Py. The ECRYPT eSTREAM project Phase 2 focus ciphers. Dokument dostupný na URL: http://www.ecrypt.eu.org/stream/p2ciphers/py/pypy p2.ps (květen 2007)
56
Příloha 1. – Použité algoritmy Algoritmus Py a Pypy Py a Pypy jsou synchronní proudové šifry umožňující velikost klíče až 256 bytů a velikost IV až 64 bytů. Inicializace Py a Pypy jsou shodné. Inicializace se sestává ze dvou fází: nastavení klíče a nastavení IV. V následujícím popisu je P pole z 256-ti osmibitovými prvky. Y je pole z 260-ti 32bitovými prvky a S je 32-bitový integer. YMININD = -3 a YMAXIND = 256. Tabulka „internal_permutation“ je konstantní permutační tabulka s 256-ti prvky, „u8“ a „u32“ znamenají „osmibitový integer bez znaménka“ a „32-bitový integer bez znaménka“. „RTL32(a,n)“ znamená, že 32-bitové a je pootočeno doleva o n bitů.
Fáze nastavení klíče Ve fázi nastavení klíče je klíč použit pro inicializaci pole Y podle následujícího kódu: keysizeb = velikost klíče v bytech; ivsizeb = velikost IV v bytech; YMININD = -3; YMAXIND = 256; s = internal_permutation[keysizeb-1]; s = (s<<8) | internal_permutation[(s ⊕ (ivsizeb-1))&0xFF]; s = (s<<8) | internal_permutation[(s ⊕ key[0])&0xFF]; s = (s<<8) | internal_permutation[(s ⊕ key[keysizeb-1])&0xFF]; for(j=0; j
57
Fáze nastavení IV Během fáze nastavení IV, je IV použitá k ovlivnění každého bitu vnitřního stavu. EIV je dočasné bytové pole se stejnou velikostí jako IV. Fáze nastavení IV má následující kód: /* Vytvoření počáteční permutace */ u8 v= iv[0] ⊕ ((Y(0)>>16)&0xFF); u8 d=(iv[1 mod ivsizeb] ⊕ ((Y(1)>>16)&0xFF))|1; for(i=0; i<256; i++) { P(i)=internal_permutation[v]; v+=d; } /* Inicializace s */ s = ((u32)v<<24) ⊕ ((u32)d<<16) ⊕ ((u32)P(254)<<8) ⊕ ((u32)P(255)); s ⊕= Y(YMININD)+Y(YMAXIND); for(i=0; i
58
s=(keysizeb*8)+((ivsizeb*8)<<16)+0x87654321;
Generování klíčového proudu Po fázi nastavení klíče a fázi nastavení IV se generuje samotný klíčový proud. Následující kód ukazuje jeden krok generování klíčového proudu. U šifry Py jsou použity všechny výstupy, u šifry Pypy je vždy první výstup tohoto kroku zahozen. /* prohození a rotace P */ swap(P(0), P(Y(185)&0xFF)); rotate(P); /* aktualizace s */ s+=Y(P(72)) - Y(P(239)); s=ROTL32(s, ((P(116) + 18)&31)); /* výstup 8 bytů (nejméně význačný byte první) */ output ((ROTL32(s, 25) ⊕ Y(256)) + Y(P(26))); output (( s ⊕ Y(-1)) + Y(P(208))); /* aktualizace a rotace Y */ Y(-3)=(ROTL32(s, 14) ⊕ Y(-3)) + Y(P(153)); rotate(Y);
Algoritmus AES Za AES (Advanced Ecryption Standard) byla zvolena bloková šifra Rjindael. Rjindael je iterativní bloková šifra s variabilní délkou klíče i bloku. Délka bloku i klíče může být nezávisle 128, 196 nebo 256 bitů. [27] Algoritmus AES se pomocí pseudokódu dá zapsat takto: Rjindael(State, CipherKey) { KeyExpansion(CipherKey, ExpandedKey); AddRoundKey(State, ExpandedKey); For ( i = 1; i < Nr; i++ ) { Round(State, ExpandedKey + Nb*i); } FinalRound(State, ExpandedKey + Nb*Nr); } Teď postupně vysvětlíme jednotlivé funkce a proměnné použité v tomto algoritmu.
State
59
State je stav šifrovaného bloku a klíče v průběhu šifrování. Stav bloku lze vyjádřit pomocí pole o čtyřech řádcích a Nb sloupcích, kde Nb = velikost bloku/32 a stav klíče lze také vyjádřit pomocí pole o čtyřech řádcích a Nr sloupcích, kde Nk = velikost klíče/32. Další možnost vyjádření je pomocí jednořádkového pole obsahujícího 4bytová slova, kde jednotlivá slova jsou odpovídající sloupce předchozího čtyřřádkového pole. [27] Počet kol algoritmu Rjindael Počet kol algoritmu se určuje z Nk a Nb a to podle tabulky: Nr Nb = 4 Nb = 6 Nb = 8 Nk = 4 10 12 14 Nk = 6 12 14 14 Nk = 8 14 14 14
Key expansion Tato funkce rozšíří šifrový klíč na dostatečnou délku pro zašifrování celého vstupního textu. Zde použijeme vyjádření pomocí jednořádkového pole 4bytových slov. Key expansion je různá pro Nk ≤ 6 a pro Nk > 6. Pro Nk ≤ 6: KeyExpansion { for( i = 0; i < Nk; i++) { W[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3] ); } for( i = Nk; i< N*(Nr+1); i++) { temp = W[i-1]; if (i%Nk == 0) {temp = SubByte(RotByte(temp)) ^bRcon[i /Nk];} W[i]= W[i-Nk]^temp; } } Pro Nk > 6: KeyExpansion { for( i = 0; i < Nk; i++) { W[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3] ); } for( i = Nk; i< N*(Nr+1); i++) { temp = W[i-1]; if (i%Nk == 0) {temp = SubByte(RotByte(temp)) ^ Rcon[i /Nk];}
60
else if (i%Nk == 4) {temp=SubByte(temp)} W[i]= W[i-Nk]^temp; } } SubByte je funkce, která vrací 4bytové slovo, ve které je na každý byte aplikován Rjindael S-Box. RotByte je funkce vracející slovo, které je permutací bytů vstupu a to: RotByte(word[a,b,c,d]) vrátí word[b,c,d,a]. Je vidět, že prvních Nk slov je naplněno šifrovacím klíčem a každé další slovo W[i] je rovno XOR předchozího slova W[i-1] a slova W[i-Nk]. [27] Výběr klíče pro dané kolo: Pro dané kolo i jsou z expandovaného klíče vybrána slova W[Nb*i] až W[Nb*(i+1)]. Tato vybraná slova jsou klíčem pro dané kolo šifrování. [27]
AddRoundKey Tato funkce aplikuje na klíč pro dané kolo a State jednoduchý bitový XOR. Round/FinalRound Tato funkce je složena ze čtyř různých transformací: Round(State, RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey); } Pro poslední kolo je tato funkce lehce pozměněna: FinalRound(State, RoundKey) { ByteSub(State); ShiftRow(State); AddRoundKey(State, RoundKey); } Funkce ByteSub je nelineární bytová substituce pomocí S-boxu (substituční tabulky), která je invertibilní. Funkce ShiftRow je funkce, během které jsou sloupce cyklicky posouvány . Ve funkci MixColumn jsou sloupce State považovány za polynomy na GF(28). Tyto sloupce modulo x4 + 1 jsou vynásobeny fixním polynomem c(x). Funkce AddRoundKey byla popsána výše. [27]
61
Algoritmus RSA RSA (Rivest, Shamir, Adleman) je šifrovací algoritmus spadající do asymetrické kryptografie. Každý uživatel má svůj soukromý a veřejný klíč. Vše, co je zašifrováno pomocí veřejného klíče lze rozšifrovat jen pomocí klíče soukromého a naopak, co je zašifrováno pomoci klíče soukromého, lze rozšifrovat pomocí klíče veřejného (toho se využívá u elektronického podpisu, zašifrování pomocí soukromého klíče je podpis a dešifrování pomocí veřejného klíče je jeho ověření). [28]
Vytvoření klíčů Zvolíme dvě dostatečně velká náhodná prvočísla p a q a spočítáme n = p*q. Dále zvolíme dostatečně velké číslo d takové, že splňuje tuto podmínku: gcd(d,(p-1)*(q-1)) = 1 (gcd – největší společný dělitel). Teď spočítáme poslední část klíčů e: e*d ≡ 1 (mod (p-1)*(q-1)). Veřejný klíč je potom dvojice čísel (e,n) a soukromý klíč je dvojce čísel (d,n). Přestože je číslo n veřejné, jeho složky p a q jsou díky složité faktorizaci velkých čísel efektivně skryty, a z toho důvodu nelze jednoduše zjistit d z veřejného klíče (e,n). [28]
Algoritmus šifrování Zprávu M si převedeme na číslo mezi 0 a n-1, pokud je zpráva dlouhá, rozložíme ji na bloky, které na toto číslo převést jdou. Toto neděláme z důvodu ukrytí obsahu zprávy, jen zprávu převádíme na tvar, na který lze algoritmus aplikovat. Samotný algoritmus je: Enctryption(M) ≡ Me (mod n), pro zprávu M Decryption(C) ≡ Cd (mod n), pro šifrový text C. [28] V reálné používaných algoritmech je ovšem postup šifrování a dešifrování doplněn o další bezpečnostní prvky jako je např. kontrola integrity. Ve většině implementací se používají techniky popsané PKCS #1.
Algoritmus MD5 MD5 je hašovací funkce. Tato funkce vrací pro jakýkoliv vstup 128bitový výstup. Algoritmus se dá rozdělit na několik kroků. [29]
Připojení doplňovacích bitů Zpráva je doplněna tak, že její délka v bitech modulo 512 se rovná 448. Doplnění se provede vždy, a to i když originální délka zprávy splňuje tuto podmínku (v tomto případě se doplní celý blok). Doplnění se provádí přidáním jednoho bitu 1 a podle potřeby několika bity 0. [29]
Připojení délky V tomto kroku se ke zprávě připojí 64bitová reprezentace její délky v bitech. Pokud je delší než 264 bitů, tak se použije jen nižších 64bitů. Po tomto doplnění máme délku vstupu dělitelnou 512. [29]
62
Inicializace MD Bufferu Pro počítání haše je použit čtyřslovový buffer (A, B, C, D). Každé z A, B, C, D je 32bitový registr. V tomto kroku je tento buffer naplněn iniciálními hodnotami nezávislými na zprávě. [29]
Zpracovávání bloků o 16ti slovech V tomto kroku se cyklicky zpracovává blok 16ti 32bitových slov ze vstupní zprávy. Slova jsou načítána postupně od počátku zprávy. Pro každý blok jsou provedeny čtyři série operaci, v každé sérii je provedeno 16 operací, jejich základem je MD buffer, vstupní blok, tabulka T (tabulka T obsahuje 64 hodnot T[i] odvozených od násobku abs(sin(i))) a funkce(pro každou sérii 16 operaci je použita jiná funkce). Výstupní hodnoty jsou zapisovány do bufferu a jsou použity pro další blok. Funkce použité v jednotlivých sériích jsou postupně: F(X, Y, Z) = (X∧Y) ∨ (not(X) ∧Z) G(X, Y, Z) = (X∧Z) ∨ (not(Z) ∧Y) H(X, Y, Z) = X xor Y xor Z I(X, Y, Z) = Y xor (X ∨ not(Z)) Operace prováděné v dané sérii mají tvar: a = b + ((a + fce(b, c, d) + X[k] + T[i]) <<< s), kde a,b,c,d jsou 32bitová slova obsahující slova z MD bufferu, X[k] je k-slovo vstupního bloku, T[i] je i-tá hodnota z tabulky T a s je parametr cyklického posunu vlevo. [29] X, Y, Z jsou 32bitová slova a výsledkem těchto funkcí je vždy zase 32bitové slovo.
Konečný výstup Konečným výstupem je posloupnost slov A, B, C, D uložených v bufferu. [29]
63
Příloha 2. – Tabulky s podmínkami pro kolize v MD5 Q[ 1]=Q[ 0]+RL(F(Q[ 0],Q[ 1],Q[-2])+Q[-3] +x[ 0] +0xd76aa478, 7); Q[ 2]=Q[ 1]+RL(F(Q[ 1],Q[ 0],Q[-1])+Q[-2] +x[ 1] +0xe8c7b756,12); Q[ 3]=Q[ 2]+RL(F(Q[ 2],Q[ 1],Q[ 0])+Q[-1] +x[ 2] +0x242070db,17); Q[ 4]=Q[ 3]+RL(F(Q[ 3],Q[ 2],Q[ 1])+Q[ 0]+x[ 3] +0xc1bdceee,22); Q[ 5]=Q[ 4]+RL(F(Q[ 4],Q[ 3],Q[ 2])+Q[ 1]+x[ 4] +0xf57c0faf, 7); Q[ 6]=Q[ 5]+RL(F(Q[ 5],Q[ 4],Q[ 3])+Q[ 2]+x[ 5] +0x4787c62a,12); Q[ 7]=Q[ 6]+RL(F(Q[ 6],Q[ 5],Q[ 4])+Q[ 3]+x[ 6] +0xa8304613,17); Q[ 8]=Q[ 7]+RL(F(Q[ 7],Q[ 6],Q[ 5])+Q[ 4]+x[ 7] +0xfd469501,22); Q[ 9]=Q[ 8]+RL(F(Q[ 8],Q[ 7],Q[ 6])+Q[ 5]+x[ 8] +0x698098d8, 7); Q[10]=Q[ 9]+RL(F(Q[ 9],Q[ 8],Q[ 7])+Q[ 6]+x[ 9] +0x8b44f7af,12); Q[11]=Q[10]+RL(F(Q[10],Q[ 9],Q[ 8])+Q[ 7]+x[10] +0xffff5bb1,17); Q[12]=Q[11]+RL(F(Q[11],Q[10],Q[ 9])+Q[ 8]+x[11] +0x895cd7be,22); Q[13]=Q[12]+RL(F(Q[12],Q[11],Q[10])+Q[ 9]+x[12] +0x6b901122, 7); Q[14]=Q[13]+RL(F(Q[13],Q[12],Q[11])+Q[10]+x[13] +0xfd987193,12); Q[15]=Q[14]+RL(F(Q[14],Q[13],Q[12])+Q[11]+x[14] +0xa679438e,17); Q[16]=Q[15]+RL(F(Q[15],Q[14],Q[13])+Q[12]+x[15] +0x49b40821,22); Q[17]=Q[16]+RL(G(Q[16],Q[15],Q[14])+Q[13]+x[ 1] +0xf61e2562, 5); Q[18]=Q[17]+RL(G(Q[17],Q[16],Q[15])+Q[14]+x[ 6] +0xc040b340, 9); Q[19]=Q[18]+RL(G(Q[18],Q[17],Q[16])+Q[15]+x[11] +0x265e5a51,14); Q[20]=Q[19]+RL(G(Q[19],Q[18],Q[17])+Q[16]+x[ 0] +0xe9b6c7aa,20); Q[21]=Q[20]+RL(G(Q[20],Q[19],Q[18])+Q[17]+x[ 5] +0xd62f105d, 5); Q[22]=Q[21]+RL(G(Q[21],Q[20],Q[19])+Q[18]+x[10] +0x02441453, 9); Q[23]=Q[22]+RL(G(Q[22],Q[21],Q[20])+Q[19]+x[15] +0xd8a1e681,14); Q[24]=Q[23]+RL(G(Q[23],Q[22],Q[21])+Q[20]+x[ 4] +0xe7d3fbc8,20); Q[25]=Q[24]+RL(G(Q[24],Q[23],Q[22])+Q[21]+x[ 9] +0x21e1cde6, 5); Q[26]=Q[25]+RL(G(Q[25],Q[24],Q[23])+Q[22]+x[14] +0xc33707d6, 9); Q[27]=Q[26]+RL(G(Q[26],Q[25],Q[24])+Q[23]+x[ 3] +0xf4d50d87,14); Q[28]=Q[27]+RL(G(Q[27],Q[26],Q[25])+Q[24]+x[ 8] +0x455a14ed,20); Q[29]=Q[28]+RL(G(Q[28],Q[27],Q[26])+Q[25]+x[13] +0xa9e3e905, 5); Q[30]=Q[29]+RL(G(Q[29],Q[28],Q[27])+Q[26]+x[ 2] +0xfcefa3f8, 9); Q[31]=Q[30]+RL(G(Q[30],Q[29],Q[28])+Q[27]+x[ 7] +0x676f02d9,14); Q[32]=Q[31]+RL(G(Q[31],Q[30],Q[29])+Q[28]+x[12] +0x8d2a4c8a,20); Q[33]=Q[32]+RL(H(Q[32],Q[31],Q[30])+Q[29]+x[ 5] +0xfffa3942, 4); Q[34]=Q[33]+RL(H(Q[33],Q[32],Q[31])+Q[30]+x[ 8] +0x8771f681,11); Q[35]=Q[34]+RL(H(Q[34],Q[33],Q[32])+Q[31]+x[11] +0x6d9d6122,16); Q[36]=Q[35]+RL(H(Q[35],Q[34],Q[33])+Q[32]+x[14] +0xfde5380c,23); Q[37]=Q[36]+RL(H(Q[36],Q[35],Q[34])+Q[33]+x[ 1] +0xa4beea44, 4); Q[38]=Q[37]+RL(H(Q[37],Q[36],Q[35])+Q[34]+x[ 4] +0x4bdecfa9,11); Q[39]=Q[38]+RL(H(Q[38],Q[37],Q[36])+Q[35]+x[ 7] +0xf6bb4b60,16); Q[40]=Q[39]+RL(H(Q[39],Q[38],Q[37])+Q[36]+x[10] +0xbebfbc70,23); Q[41]=Q[40]+RL(H(Q[40],Q[39],Q[38])+Q[37]+x[13] +0x289b7ec6, 4); Q[42]=Q[41]+RL(H(Q[41],Q[40],Q[39])+Q[38]+x[ 0] +0xeaa127fa,11);
64
0 p. 0 p. 17 p. 21 p. 32 p. 32 p. 32 p. 29 p. 28 p. 18 p. 19 p. 15 p. 14 p. 15 p. 9 p. 6 p. 5 p. 3 p. 2 p.(+1m.) 1 p.(+1m.) 1 p. 1 p. 2 p. 1 p.
1 p.
Q[43]=Q[42]+RL(H(Q[42],Q[41],Q[40])+Q[39]+x[ 3] +0xd4ef3085,16); Q[44]=Q[43]+RL(H(Q[43],Q[42],Q[41])+Q[40]+x[ 6] +0x04881d05,23); Q[45]=Q[44]+RL(H(Q[44],Q[43],Q[42])+Q[41]+x[ 9] +0xd9d4d039, 4); Q[46]=Q[45]+RL(H(Q[45],Q[44],Q[43])+Q[42]+x[12] +0xe6db99e5,11); Q[47]=Q[46]+RL(H(Q[46],Q[45],Q[44])+Q[43]+x[15] +0x1fa27cf8,16); Q[48]=Q[47]+RL(H(Q[47],Q[46],Q[45])+Q[44]+x[ 2] +0xc4ac5665,23); Q[49]=Q[48]+RL(I(Q[48],Q[47],Q[46])+Q[45]+x[ 0] +0xf4292244, 6); Q[50]=Q[49]+RL(I(Q[49],Q[48],Q[47])+Q[46]+x[ 7] +0x432aff97,10); Q[51]=Q[50]+RL(I(Q[50],Q[49],Q[48])+Q[47]+x[14] +0xab9423a7,15); Q[52]=Q[51]+RL(I(Q[51],Q[50],Q[49])+Q[48]+x[ 5] +0xfc93a039,21); Q[53]=Q[52]+RL(I(Q[52],Q[51],Q[50])+Q[49]+x[12] +0x655b59c3, 6); Q[54]=Q[53]+RL(I(Q[53],Q[52],Q[51])+Q[50]+x[ 3] +0x8f0ccc92,10); Q[55]=Q[54]+RL(I(Q[54],Q[53],Q[52])+Q[51]+x[10] +0xffeff47d,15); Q[56]=Q[55]+RL(I(Q[55],Q[54],Q[53])+Q[52]+x[ 1] +0x85845dd1,21); Q[57]=Q[56]+RL(I(Q[56],Q[55],Q[54])+Q[53]+x[ 8] +0x6fa87e4f, 6); Q[58]=Q[57]+RL(I(Q[57],Q[56],Q[55])+Q[54]+x[15] +0xfe2ce6e0,10); Q[59]=Q[58]+RL(I(Q[58],Q[57],Q[56])+Q[55]+x[ 6] +0xa3014314,15); Q[60]=Q[59]+RL(I(Q[59],Q[58],Q[57])+Q[56]+x[13] +0x4e0811a1,21); Q[61]=Q[60]+RL(I(Q[60],Q[59],Q[58])+Q[57]+x[ 4] +0xf7537e82, 6); Q[62]=Q[61]+RL(I(Q[61],Q[60],Q[59])+Q[58]+x[11] +0xbd3af235,10); Q[63]=Q[62]+RL(I(Q[62],Q[61],Q[60])+Q[59]+x[ 2] +0x2ad7d2bb,15); Q[64]=Q[63]+RL(I(Q[63],Q[62],Q[61])+Q[60]+x[ 9] +0xeb86d391,21);
1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 2 p. 2 p. 2 p.(+1m.) 2 p.
IHV[0] = IV[0]+Q[61]; IHV[3] = IV[3]+Q[62]; 1 p. IHV[2] = IV[2]+Q[63]; 3 p. IHV[1] = IV[1]+Q[64]; 4 p. Tabulka 1.: Postačující podmínky pro kolize v MD5
Q[14]=Q[13]+RL(F(Q[13],Q[12],Q[11])+Q[10]+x[13] +0xfd987193,12); 15 p. Q[15]=Q[14]+RL(F(Q[14],Q[13],Q[12])+Q[11]+x[14] +0xa679438e,17); 9 p. Q[16]=Q[15]+RL(F(Q[15],Q[14],Q[13])+Q[12]+x[15] +0x49b40821,22); 6 p. Q[17]=Q[16]+RL(G(Q[16],Q[15],Q[14])+Q[13]+x[ 1] +0xf61e2562, 5); 5 p. Q[18]=Q[17]+RL(G(Q[17],Q[16],Q[15])+Q[14]+x[ 6] +0xc040b340, 9); 3 p. Q[19]=Q[18]+RL(G(Q[18],Q[17],Q[16])+Q[15]+x[11] +0x265e5a51,14); 2 p.(+1m.) Q[20]=Q[19]+RL(G(Q[19],Q[18],Q[17])+Q[16]+x[ 0] +0xe9b6c7aa,20); 1 p.(+1m.) Q[21]=Q[20]+RL(G(Q[20],Q[19],Q[18])+Q[17]+x[ 5] +0xd62f105d, 5); 1 p. Q[22]=Q[21]+RL(G(Q[21],Q[20],Q[19])+Q[18]+x[10] +0x02441453, 9); 1 p. Q[23]=Q[22]+RL(G(Q[22],Q[21],Q[20])+Q[19]+x[15] +0xd8a1e681,14); 2 p. Q[24]=Q[23]+RL(G(Q[23],Q[22],Q[21])+Q[20]+x[ 4] +0xe7d3fbc8,20); 1 p. ........................................ zde je bod verifikace (POV) ........................................ Q[25]=Q[24]+RL(G(Q[24],Q[23],Q[22])+Q[21]+x[ 9] +0x21e1cde6, 5); Q[26]=Q[25]+RL(G(Q[25],Q[24],Q[23])+Q[22]+x[14] +0xc33707d6, 9);
65
Q[27]=Q[26]+RL(G(Q[26],Q[25],Q[24])+Q[23]+x[ 3] +0xf4d50d87,14); Q[28]=Q[27]+RL(G(Q[27],Q[26],Q[25])+Q[24]+x[ 8] +0x455a14ed,20); Q[29]=Q[28]+RL(G(Q[28],Q[27],Q[26])+Q[25]+x[13] +0xa9e3e905, 5); Q[30]=Q[29]+RL(G(Q[29],Q[28],Q[27])+Q[26]+x[ 2] +0xfcefa3f8, 9); Q[31]=Q[30]+RL(G(Q[30],Q[29],Q[28])+Q[27]+x[ 7] +0x676f02d9,14); Q[32]=Q[31]+RL(G(Q[31],Q[30],Q[29])+Q[28]+x[12] +0x8d2a4c8a,20); Q[33]=Q[32]+RL(H(Q[32],Q[31],Q[30])+Q[29]+x[ 5] +0xfffa3942, 4); Q[34]=Q[33]+RL(H(Q[33],Q[32],Q[31])+Q[30]+x[ 8] +0x8771f681,11); Q[35]=Q[34]+RL(H(Q[34],Q[33],Q[32])+Q[31]+x[11] +0x6d9d6122,16); Q[36]=Q[35]+RL(H(Q[35],Q[34],Q[33])+Q[32]+x[14] +0xfde5380c,23); Q[37]=Q[36]+RL(H(Q[36],Q[35],Q[34])+Q[33]+x[ 1] +0xa4beea44, 4); Q[38]=Q[37]+RL(H(Q[37],Q[36],Q[35])+Q[34]+x[ 4] +0x4bdecfa9,11); Q[39]=Q[38]+RL(H(Q[38],Q[37],Q[36])+Q[35]+x[ 7] +0xf6bb4b60,16); Q[40]=Q[39]+RL(H(Q[39],Q[38],Q[37])+Q[36]+x[10] +0xbebfbc70,23); Q[41]=Q[40]+RL(H(Q[40],Q[39],Q[38])+Q[37]+x[13] +0x289b7ec6, 4); Q[42]=Q[41]+RL(H(Q[41],Q[40],Q[39])+Q[38]+x[ 0] +0xeaa127fa,11); Q[43]=Q[42]+RL(H(Q[42],Q[41],Q[40])+Q[39]+x[ 3] +0xd4ef3085,16); Q[44]=Q[43]+RL(H(Q[43],Q[42],Q[41])+Q[40]+x[ 6] +0x04881d05,23); Q[45]=Q[44]+RL(H(Q[44],Q[43],Q[42])+Q[41]+x[ 9] +0xd9d4d039, 4); Q[46]=Q[45]+RL(H(Q[45],Q[44],Q[43])+Q[42]+x[12] +0xe6db99e5,11); Q[47]=Q[46]+RL(H(Q[46],Q[45],Q[44])+Q[43]+x[15] +0x1fa27cf8,16); Q[48]=Q[47]+RL(H(Q[47],Q[46],Q[45])+Q[44]+x[ 2] +0xc4ac5665,23); Q[49]=Q[48]+RL(I(Q[48],Q[47],Q[46])+Q[45]+x[ 0] +0xf4292244, 6); Q[50]=Q[49]+RL(I(Q[49],Q[48],Q[47])+Q[46]+x[ 7] +0x432aff97,10); Q[51]=Q[50]+RL(I(Q[50],Q[49],Q[48])+Q[47]+x[14] +0xab9423a7,15); Q[52]=Q[51]+RL(I(Q[51],Q[50],Q[49])+Q[48]+x[ 5] +0xfc93a039,21); Q[53]=Q[52]+RL(I(Q[52],Q[51],Q[50])+Q[49]+x[12] +0x655b59c3, 6); Q[54]=Q[53]+RL(I(Q[53],Q[52],Q[51])+Q[50]+x[ 3] +0x8f0ccc92,10); Q[55]=Q[54]+RL(I(Q[54],Q[53],Q[52])+Q[51]+x[10] +0xffeff47d,15); Q[56]=Q[55]+RL(I(Q[55],Q[54],Q[53])+Q[52]+x[ 1] +0x85845dd1,21); Q[57]=Q[56]+RL(I(Q[56],Q[55],Q[54])+Q[53]+x[ 8] +0x6fa87e4f, 6); Q[58]=Q[57]+RL(I(Q[57],Q[56],Q[55])+Q[54]+x[15] +0xfe2ce6e0,10); Q[59]=Q[58]+RL(I(Q[58],Q[57],Q[56])+Q[55]+x[ 6] +0xa3014314,15); Q[60]=Q[59]+RL(I(Q[59],Q[58],Q[57])+Q[56]+x[13] +0x4e0811a1,21); Q[61]=Q[60]+RL(I(Q[60],Q[59],Q[58])+Q[57]+x[ 4] +0xf7537e82, 6); Q[62]=Q[61]+RL(I(Q[61],Q[60],Q[59])+Q[58]+x[11] +0xbd3af235,10); Q[63]=Q[62]+RL(I(Q[62],Q[61],Q[60])+Q[59]+x[ 2] +0x2ad7d2bb,15); Q[64]=Q[63]+RL(I(Q[63],Q[62],Q[61])+Q[60]+x[ 9] +0xeb86d391,21); Tabulka 2.: Tunel Q9 a bod verifikace
66
1 p.
1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 2 p. 2 p. 2 p. 2 p.
