Asi každého z nás niekedy zaujímalo uchovávanie a odkrývanie tajomstiev iných, či už to boli tajné správy počas detstva alebo tajomstvá a kódovanie na úrovni štátu. Zostavovanie a lúštenie šifier je nekonečný príbeh boja medzi tvorcami šifier a ich lúštiteľmi. Je to príbeh intelektuálneho zápasu, ktorého vplyv na svetovú históriu je častokrát fascinujúci. Kódy stoja v pozadí mnohých historických medzníkov. Niekedy rozhodovali o výsledkoch bitiek, inokedy zapríčinili smrť korunovaných hláv. Za tým všetkým stojí veda o šifrách, tj. kryptológia.
Keď prišiel pred pár rokmi do kín britsko-americký film Kód Enigmy (The Imitation Game), ktorý odhaľuje život matematického génia Alana Turinga a jeho rolu pri prelomení nacistickej šifry Enigma počas druhej svetovej vojny, opäť sme si mnohí mohli pripomenúť ako funguje kódovanie/šifrovanie a prelomenie nejakého kódu. Je toto iné v časoch Enigmy a dnes?
Tajné kódy a šifry
Šifry sa používajú od nepamäti, prvá zmienka o nich pochádza z Egypta asi z pred 4 000 rokov. V minulosti kryptológia slúžila výhradne k zatajeniu obsahu správ – zmenu obsahu textu správy z otvoreného textu do zašifrovaného textu a opačne v prípade zachytenia správy nepovolanou osobou alebo špiónom.
Podstatu šifrovania znázorňuje nasledujúci obrázok. Predstavme si, že Bob a Alice chcú tajne komunikovať, a Eve chce načúvať. „Obyčajný text“ reprezentuje pôvodnú správu a „šifrovaný text“ je kódovaná správa.
Existujú dva spôsoby ako môžu Bob a Alice šifrovať tajnú správu:
- Dohodnú si algoritmus (šifru), ktorú budú poznať len Bob a Alice, tzn. jeden aplikuje algoritmus a text zašifruje a druhý reverzným algoritmom správu dešifruje.
- Použijú dobre definovaný algoritmus, ale ešte navyše „niečo pridajú“; to „niečo“ bude pre Boba a Alice jednoduché, avšak pre Eve to bude zložité zistiť.
V prvom prípade, ak Eve chce prelomiť kód musí zistiť šifru, algoritmus ktorý Bob a Alice používajú. Príkladom sú klasické typy šifier, tj.:
- transpozičné šifry ktoré spočívajú v zamiešaní poradia písmen otvoreného textu (napr. slovo „pomôž mi“ sa zmodifikovalo na „opômž im“) a
- substitučné šifry, ktoré spočívajú v systematickom nahradzovaní jednotlivých symbolov obsahu textu za určené ďalšie symboly alebo skupinu symbolov (napr. substitučná šifra slova „wikipedia“ mohla vyzerať ako „xjljrfejb“ pričom v tomto spôsobe sa symboly šifrovanej abecedy posunuli o jeden symbol oproti abecede otvoreného textu).
Jednoduché verzie oboch šifier však poskytovali v prípade zachytenia správy nepovolanou osobou len malú ochranu a boli ľahko dešifrovateľné.
Medzi najstaršie substitučné šifry patrila Cézarova šifra, ktorá spočívala v tom, že každé písmeno n otvoreného textu bolo nahradené písmenom určitej hodnoty n+k. Táto šifra je pomenovaná po Juliusovi Cézarovi, ktorý ju používal s posunutím k o 3 miesta v abecede pri komunikácií s jeho generálmi počas vojenských operácií.
Inými slovami povedané Caesarova šifra je forma substitúcie, ktorá posúva písmená v abecede o niekoľko miest, napríklad posun o 13 znamená, že A sa stáva N, B sa stáva O, C sa stáva P a tak ďalej. Jedná sa o ľahký kód na prelomenie, pretože existuje len 25 jedinečných posunov a teda 25 odlišných šifier.
Oveľa ťažšia by bola zakódovaná abeceda, v ktorej akékoľvek písmeno abecedy môže byť priradené akémukoľvek inému písmenu bez rovnakého toho istého substitučného posunu ako to je pri Caesarovej šifre. V taktom prípade to vedie k obrovskému počtu permutácií – 403 miliónov miliárd miliárd a teda možných šifier. Aj kebyže použijeme superpočítač, s ktorým by sme vyskúšali miliardové mapovanie za sekundu, stále by nám to trvalo priemerne 6,3 miliárd rokov, kým by sme túto šifru prelomili.
Avšak, základnou slabinou týchto šifier je výskyt písmen: v angličtine písmeno s najväčším výskytom je pravdepodobne E, najčastejšie písmeno v anglickom jazyku. Pomocou frekvenčnej analýzy je možné túto prácu skrátiť na asi päť minút.
Na začiatku šifrovanie pomocou zakódovanej abecedy fungovalo dobre a šifrované texty si zachovali požadovanú tajnosť. Ale keď sa „Eve podarí prelomiť šifru“, ani Bob ani Alica nebudú o tom vedieť, rovnako ako nacisti nevedeli, že spojenci prelomili Enigmu. A preto moderná kryptografia využíva iný prístup: verejný kľúč na šifrovanie a súkromný (tajný) kľúč na dešifrovanie, ktorý „Eve len ťažko zistí“. To je šifrovanie verejným kľúčom.
Prelomenie kódu Enigma
V období ešte pred počítačmi boli šifry generované mechanicky. Dobrým príkladom je šifrovací rotorový stroj Enigma. Používal polyalfabetickú substitučnú šifru – s troma rotormi na generovanie troch abecedných posunov – a tajný kľúč. Úlohou bolo určiť používaný algoritmus aj kľúč.
Enigma bol automatický stroj na šifrovanie a dešifrovanie správ. Vyzeral ako písací stroj, tiež sa na ňom tak písalo. Avšak namiesto čitateľných viet z neho vychádzali skupiny nezrozumiteľných písmen a čísel. Vo vnútri totiž boli tri vzájomne prepojené valce nastavené podľa zvoleného kľúča, ktoré sa otáčali. Neskôr pridávali ďalšie, najzložitejšie aparatúra ich mala osem. Šifranti mohli stroj nastaviť zakaždým iným spôsobom, takže sa samotná šifra nikdy dvakrát nezopakovala. Každý znak mohol byť zapísaný v 150 triliónoch možných kombinácií, záležalo na postavení rotorov a ďalších drobnostiach. Zašifrovanú správu mohol na druhej strane prečítať len ten, kto poznal použitý kľúč. Preto považovali Nemci tento stroj za absolútne nerozlúštiteľný.
Podľa niektorých zdrojov „Enigmu“ vymyslel Holanďan Hugo Koch na šifrovanie správ, ktoré si medzi sebou vymieňali banky. Údajne nemal však peniaze na jeho postavenie, a preto predal plány inžinierovi Artur Scherbiusovi z Berlína. Nemec si ho nechal patentovať 23. februára 1918. Keď skonštruoval prototyp, pokrstil ho Enigma (podľa gréckeho slova Aenigma – záhada). Prístroj vážiaci okolo 50 kilogramov ponúkala jedna továreň od roku 1922 bankám, ale nie príliš úspešne.
Už v roku 1932 za pomoci francúzskej tajnej služby matematická šikovnosť poľského úradu Biuro Szyfrow utajene ako prvá prelomila kódy Enigmy. V predvečer vojny Poliaci odovzdali svoju prácu spojencom, ktorí boli prekvapení ich výsledkami. Ale teraz nemecká armáda už používala pokročilejšie verzie stroja Enigma s ďalšími rotormi a ďalšími funkciami, ktoré zvýšili zložitosť šifry. Dilly Knox, britský vedúci lúštiteľ kódov, mal určitý úspech, ale bolo potrebné lepšie vybavenie.
Alan Turing a Gordon Welchman rozvinutím práce Poliakov navrhli elektromechanické zariadenie Bomba, určené na napodobňovanie strojov Enigma. To s určitými informáciami zúžilo možné permutácie nastavení strojov Enigma z 150 miliónov na viac zvládnuteľné číslo.
Skutočným otcom prelomenia šifry je Colossus, prvý programovateľný elektronický digitálny počítač na svete, ktorý bol vytvorený inžinierom Tommym Flowersom, aby prelomil Lorenzovu šifru, sofistikovanejšieho nástupcu Enigmy.
Prelomenie šifier dnes
V dnešnej dobe sú počítače dnes oveľa výkonnejšie ako v čase Turinga a teda ich „hrubá sila“ môže prelomiť heslá alebo odhaliť šifrovacie metódy jednoducho spracovaním všetkých možných rôznych permutácií.
Väčšina hesiel je uložená s hash – fixný reťazec znakov generovaný matematickou funkciou z textu ľubovoľnej dĺžky. Jedná sa o jednosmerný proces, takže hash nie je možné reverzne použiť na získanie pôvodného textu.
Dnes je však možné zostaviť vyhľadávacie tabuľky pred-hash hodnôt, v podstate slovník hash-ov, ktorý sa porovná s heslami, ktoré reprezentujú.
Napríklad: heslo so 7-mi znakmi s malými písmenami by mohlo byť jednou z viac ako 8 miliárd možných permutácií. Grafický procesor na typickej počítačovej grafickej karte (ktorý je pre túto úlohu vynikajúci) môže skontrolovať viac ako 150 miliónov slov za sekundu, čo znamená, že maximálny čas na prelomenie akéhokoľvek hesla je iba 53 sekúnd.
Pridaním veľkých písmen dostaneme tisíc miliárd kombinácií a maximálny čas na prelomenie kódu 114 minút. Dokonca aj keď by sme pridali ďalších 20 číselných znakov a bežné interpunkčné znamienka, tak to bude viac ako desaťtisíc miliárd permutácií a maximálny čas na prelomenie šifry je len 18 hodín. Heslá s 8 znakmi už je o niečo zložitejšie s 722 miliardami permutácií, ale aj tak môžu byť prelomené za prijateľný rýchly čas 1 337 hodín alebo 55 dní.
Obava je, že distribuovaná výpočtová sila prostredníctvom cloud-u výrazne uľahčuje tento proces. Jedna z najbežnejších hash-ových funkcií, MD5, sa ukazuje ako príliš slabá, aby sa vyrovnala s výpočtovou silou, ktorá je teraz k dispozícii.
Každý MD5 hash je dlhý 128 bitov, takže uloženie všetkých možných 7 znakových hesiel by vyžadovalo 160 terabajtov úložného priestoru. A hoci sa to zdá dosť, už dnes si môžete kúpiť 4 TB za približne 100 libier, spoločnosť Microsoft neoznámila žiadne obmedzenia svojho úložiska a Dropbox ponúka niekoľko terabajtov za nízku cenu. Podobne, pomocou cloud-ových technológií, napríklad Amazon Cloud, bude možné si prenajať procesný čas na 1 000 takýchto grafických kariet len za pár drobných, rozdeliť úlohu medzi nich a prelomia 8 znakové heslo za hodinu a pol.
Viac informácií o hash funkciách nájdete aj v tomto článku.
Pridajte soľ podľa chuti
Pravým spôsobom, ako zvýšiť silu hesla, je pridať soľ, náhodný reťazec textu, ktorý sa používa na pridávanie zložitosti heslom.
Napríklad 7 znaková soľ „eFUqsfi“ sa pridá do hesla „heslo“ na vytvorenie reťazca „eFUqsfipassword“. Toto vytvára hash, ktorý je dostatočne náhodný, že sa nezobrazí v hash look-up tabuľke a má 15 znakov namiesto ôsmich, čo výrazne zvyšuje náročnosť snahy o prelomenia hesla pomocou útokov hrubou silou z 722 miliárd miliárd permutácií na viac ako 742 miliárd miliárd miliárd permutácií.
Preto sme prešli z miliónov dolárov investícií na vybudovanie a udržiavanie Colossus-u, do doby, kedy sa cracker-om podarilo vytvoriť rovnaký hash podpis pre iný obraz a trvalo to len 10 hodín a stálo len 65 centov plus daň na GPU inštanciu na Amazonskom cloude.
Takže určité čisto intelektuálne obdobie z Turingových čias je už prekonané a teraz je to o tom, kto má najrýchlejší počítač. Cloud sám o sebe je superpočítač, ktorý sa dennodenne rozširuje, a prostredníctvom webových stránok určených na analýzu a ukladanie čo najväčšieho množstva hesiel, sa asi začnú rozpadávať celé základy našej kryptografie, vrátane dôsledkov ktoré to má na bezpečnosť internetu.
