Nepředpokládám, že by většina čtenářů Rootu patřila do generace, která přišla do styku s dálnopisem. Nepatřím do ní vlastně ani já – i když jsem dálnopisné přístroje, neboli Telexy, několikrát v životě viděl nejen v muzeu, ale i v provozu, sám jsem s nimi už nepracoval. Dálnopis ale hraje v našem příběhu poměrně zásadní roli – neuškodí tedy krátký úvod do historie.
Co je vlastně dálnopis…
Dálnopis (obch. Telex, angl. Teleprinter) se zrodil pod označením „tisknoucí telegraf“ již v roce 1846, kdy první prototyp s 28 klávesami z piana představil v USA Royal Earl House. O devět let později jej výrazně vylepšil David Edward Hughes – jeho řešení posléze převzala řada malých telegrafních společností v USA, které se posléze sloučily do Western Union Telegraph. Evropskou verzi využívající při přenosu pětibitové kódování navrhl Francouz Emile Baudot v roce 1874 a ve Francii byla zavedena v roce 1877 – odtud se pak rozšířila do velké části Evropy. Systém byl na přelomu 19. a 20. století ještě lehce inovován a koncem 20. let na něm byl vytvořen standard pro globální dálnopisnou síť „Telex“, kterou využívaly ke komunikaci zejména firmy až do 80. či 90. let (v podstatě do nástupu síťové komunikace a e-mailu).
Dnes dálnopisy fungují (spíše z nostalgie) v některých redakcích velkých novin v USA a v některých zemích třetího světa (osobně jsem se setkal s aktivním využíváním dálnopisu ještě v roce 2006 v Barmě – vzhledem k tehdejšímu celostátnímu zákazu internetu se v tu dobu jednalo o nejlevnější legální formu spojení například se sousedním Thajskem). Pro náš příběh je podstatné, že díky globální síti Telex používaly dálnopisy standardní způsob přenosu znaků.
První zpráva z přenosů „Tuňák“ (toto označení bylo ovšem přiděleno až v létě 1942), kterou dostali do ruky kryptoanalytici, byla odeslána krátce po invazi Němců do Ruska. Jednalo se o spojení mezi Aténami a Vídní. Ze způsobu přenosu jsme usoudili, že se jedná o stejný typ spojení jako v pokusných přenosech z května. Ty byly odesílány jako pětimístný kód, z čehož jsme usoudili, že se jednalo o dálnopisné spojení. To bylo potvrzeno i při předběžném zkoumání dalších zpráv, z něhož vyplynulo, že se jedná o abecedu obsahující 32 znaků – 26 znaků klasické abecedy se šesti dodatečnými symboly 3, 4, 8, 9, +, a /.
Úryvek ze zprávy „General Report on Tunny“. Jack Good, Donald Michie, Geoffrey Timms, Bletchley Park 1945. Odtajněno roku 2000.
Tuňák připlouvá
Lorenz SZ40, SZ42A a SZ42B (SZ značí Schuesselzusatz – tedy „s připojenou šifrou“) byla šifrovací zařízení, která si pro komunikaci štábu a hlavního velení objednala na počátku války německá armáda. Jejich výrobou byla pověřena stejnojmenná společnost C. Lorenz A.G. v Berlíně. Britové označovali obecně veškerou šifrovanou dálnopisnou komunikaci Němců jako „Ryby“, což vysvětluje, proč právě zprávy šifrované Lorenzovými dálnopisy získaly označení „Tuňák“ (Tunny).
Pohled na odkrytý Lorenz SZ42
Na základě předpokladu, že se jedná o dálnopisné zařízení, jsme čelili dvěma základním otázkám. Za prvé, zda vztah mezi 26 písmeny běžné abecedy a znaků dálnopisu odpovídá mezinárodnímu standardu a za druhé, jaké znaky odpovídají symbolům 3, 4, 8, 9, +, a /. Obě tyto otázky se nám podařilo vyřešit studováním série vadných zpráv odeslaných 22. července. Tyto zprávy měly jen 16 různých písmen a patrně díky závadě zařízení začínaly impulzy všech těchto písmen tečkou i v případě, kdy měly začínat křížkem. Tím se nám podařilo jednoznačně určit, že základem zařízení je dálnopis odpovídající mezinárodním standardům. […]Dalším pokrokem bylo, když se nám podařilo prokázat, že „Tuňák“ funguje na principu záměny písmen.
Úryvek ze zprávy „General Report on Tunny“. Jack Good, Donald Michie, Geoffrey Timms, Bletchley Park 1945. Odtajněno roku 2000.
Šifrovací stroje Lorenz SZ byly, jak jsme již uvedli, klasické dálnopisné stroje doplněné o sofistikovaný šifrovací systém s dvanácti válci, využívající princip proudové šifry – tedy symetrické šifry, jejíž „[…] vstupní datový tok je kombinován (typicky pomocí funkce XOR) s pseudonáhodným proudem bitů (angl. Keystream) vytvořeným ze šifrovacího klíče a šifrovacího algoritmu. Výsledkem je zašifrovaný datový tok (proud, který je kódován neustále se měnící transformací – na rozdíl od blokové šifry, kde je transformace konstantní). Proudové šifry jsou typicky rychlejší než blokové šifry a pro implementace potřebují jednodušší hardware. Naopak jsou na rozdíl od blokových šifer náchylnější ke kryptoanalytickým útokům, pokud jsou nevhodně implementovány (počáteční stav nesmí být použit dvakrát).“ (Wikipedie).
Citátu z české Wikipedie odpustíme ty opakované implementace (koneckonců, já zas dělám překlepy a zapomínám čárky v souvětích – a nezbývá mi než doufat ve vaši shovívavost) a zdůrazníme závěrečnou závorku. Ta je totiž v celém příběhu rozluštění Lorenzovy šifry naprosto zásadní.
Nikoliv Lorenzova, ale Vernamova šifra
Kryptoanalytici v Bletchley Park byli na rozdíl od Enigmy v případě Tuňáka v mnohem složitější situaci. Komerční přístroje Enigma bylo možné před válkou koupit a základní princip jejich fungování tak byl znám. První rozluštění vojenských verzí enigmy provedli Poláci a i během války byla Enigma sice vzácnou ale přeci jen občasnou kořistí. V případě Tuňáka ale lidé z Bletchley park viděli první exemplář původního německého stroje až několik týdnů po skončení války v roce 1945. Kryptoanalytici naštěstí nemuseli pátrat tak docela ve tmě. Vedle poznatku, že základem zařízení je dálnopis byla známá i samotná šifrovací metoda, kterou Lorenzova šifra využívala. Jak jsme již uvedli, jednalo se o proudovou šifru využívající logickou operací Exkluzivní disjunkce (vylučovací, exkluzívní OR nebo zkráceně XOR), kterou vyvinul v roce 1917 v laboratořích AT&T Bell matematik Gilbert Vernam. Jedná se o šifru z oblasti symetrické kryptografie, která používá k šifrování i dešifrování jediný klíč (na rozdíl od dnes často používaných nesymetrických algoritmů s veřejným a tajným klíčem). Vernam původně předpokládal, že by se takové šifrování dalo využít při přenosu telegrafních zpráv, nicméně jeho původní nápad přenášet fyzicky klíče ve formě telegrafní pásky se ukázal jako nepraktický. Navíc o deset let později byly nezávisle na čtyřech místech vyvinuty šifrovací přístroje s válci, které otázku generování a přenosu klíče elegantně vyřešily.
Přestože proudové symetrické šifry jsou z dnešního hlediska považovány za snáze rozluštitelné, počet kombinací, který Lorenzova šifra nabízela, byl úctyhodný – celkový počet variant nastavení všech válců činí 2501 (tedy 10151). I když v praxi byly skutečné počty kombinací menší (například počet počátečních pozic činil 1,6 × 1019), bylo to stále příliš mnoho variant, než aby mělo smysl zkoušet útok hrubou silou. Podobně jako v případě Enigmy, i u Lorenze tak první úspěšné pokusy v luštění (a co je podstatnější pochopení vnitřního zapojení a fungování stroje) závisely na chybách, které Němci při posílání zpráv udělali z nedbalosti nebo lenosti – například dvě zprávy, které byly odeslány se stejným počátečním nastavením stroje. Ty analytici v Bletchley Park označovali kódem „Hloubka“ (Depth).
Při prvních pokusech dešifrování „Hloubek“ se nedařilo získat souvislejší bloky textu ani jasnou souvztažnost mezi krátkými úryvky. Není proto divu, že zpočátku byly pokrok v luštění šifry „Tuňák“ minimální. Sestavit delší části klíče bylo velmi obtížné a i když se nám to podařilo, výsledky nebyly jednoznačné. Zachránila nás až neopatrnost německých operátorů ze 30. srpna 1941. Toho dne byly odeslány dvě velmi dlouhé zprávy s identickými indikátory HQIBPEXEZMUG ze stejného místa. Při hlubším dešifrování jsme zjistili, že zprávy byly praktické stejné až na odlišnosti v mezerách, překlepy a opravy. Zjevně byla stejná zpráva zadána ručně dvakrát. Měli jsme tak k dispozici k dispozici pár zpráv s identickým začátkem a jen malými rozdíly ve vlastním textu. Tyto rozdíly mírně rostly v průběhu zpráv – u znaku 3796, kde kratší ze zpráv končila, činil rozdíl o něco více než sto písmen.
Dešifrování této dvojice zpráv se ukázalo mnohem snazší – mimo jiné i proto že text jedné šlo snáze luštit podle dešifrovaných částí druhé. […] Díky tomu že se podařilo rozluštit kratší ze zpráv v celé délce jsme mohli určit i samotnou délku klíče (u několika znaků jsme neměli jistotu). Po zbytek roku 1941 se na základě těchto informací výzkumná sekce pokoušela analyzovat tento klíč a odhalit tak povahu šifrovacího zařízení. Němci si patrně sami uvědomili, k že došlo k porušení bezpečnosti, protože přenos zpráv na několik dní ustal a až do roku 1941 se nepodařilo získat žádnou další zprávu vhodnou k hloubkovému luštění.
Úryvek ze zprávy „General Report on Tunny“. Jack Good, Donald Michie, Geoffrey Timms, Bletchley Park 1945. Odtajněno roku 2000.
Turingovina a Britský Tuňák
Při luštění zprávy z konce srpna 1941 byla použita opět metoda „Cribs“, kterou jsme zmiňovali v předchozích dílech – tedy hledání často se vyskytujících slovíček. V tomto případě se jednalo o slovo „SPRUCHNUMMER“ (číslo zprávy), které bylo ve druhé zprávě zkráceno na „SPRUCHNR“. Takovou technikou se ale dalo luštit jen málo zpráv typu „hloubka“ – na způsob, jak luštit řadu dalších, nepřišel nikdo jiný než náš starý známý Alan Turing (věnovali jsme mu minulý díl). V červenci 1942 se krátce přidal k týmu, který řešil „Tuňáka“ a vyvinul metodu, kterou v Bletchley Park označovali jako „Turingery“. Jeho metoda byla založená na manipulaci se šifrovaným textem či klíčem, s jejíž pomocí bylo možné zjistit frekvenční výskyt znaků, které takřka „čouhaly“ z průměru. Turing totiž přišel na to, že XOR kombinace dvou po sobě jdoucích znaků v šifrovaném textu nebo klíči mohla pomoci odhalit odchylky od průměrné (jednotné) distribuce znaků ve zprávě. I když to byl postup, který umožňoval luštit kratší opakované zprávy, skutečný průlom přišel odjinud.
Přestože se „Výzkumné stanici“ která mela na starosti agendu Tuňák podařilo rozluštit dvojici dlouhých zpráv, nedařilo se jim na jejich základě odhalit konstrukci a fungování vlastního Lorenzova šifrovacího mechanismu. Úkol proto převzal matematik Bill Tutte, který ručním rozborem šifry v pětibitovém Baudotově kódu, dešifrovaného klíče a hledáním opakování odhalil vzor opakování 41 znaků ve zprávě a po několika dalších měsících společně s kolegy vytvořit kompletní logickou strukturu Lorenzovy šifry – s ní bylo konečně možné zprávy skutečně luštit. Britové sice postavili své vlastní „Tuňáky“, tedy funkční repliky Lorenzovy šifry (byly ovšem nesrovnatelně větší), nicméně mohli je využít jen pro rutinní dešifrování německých zpráv až poté, co byla kryptoanalytiky odhalena počáteční nastavení. Takzvané BTM (British Tunny Machines) spadaly pod sekci Testery, která měla na starosti kompletní dešifrování zpráv Tuňák. Zpočátku pracovali matematici v Testery takřka výhradně ručně, dokud Max Newman nepřišel koncem roku 1942 se svou „Newmanovinou“ (Newmanry), která umožnila dešifrování značně urychlit a částečně automatizovat pomocí tzv. „Robinsonů“ – strojů, které používaly děrnou pásku a logické obvody pro hledání některých počátečních nastavení Lorenze.
Němci pochopitelně měnili postupy a pravidla používání Lorenzovy šifry, čímž Brity často na několik týdnů až měsíců „odstavili“ od aktuálních informací. Zatímco zpočátku se některá nastavení šifry měnila čtvrtletně, jiná měsíčně a denně, ke konci války (od srpna 1944) se všechna nastavení měnila denně.
1943: Kolos
Luštění zpráv vrchního velení mělo samozřejmě obrovský význam a situace, kdy Britové nemohli německou komunikaci několik týdnů či měsíců sledovat, byla krajně nepříjemná. Byla to právě Lorenzova šifra, pro jejíž luštění byl poprvé použit stroj, který je označován jako vůbec první počítač – přestože neměl programovou paměť, byl Kolos (Colossus) programován pomocí kabelových propojek a přepínačů a jako výstup sloužil panel se žárovkami. Kolos Mk. 1 byl uveden do provozu v prosinci 1943 – byl osazen 1500 elektronkami a tyratrony. Výkon Kolosu byl omezen především možnostmi čtecího zařízení děrné pásky, které bylo spolehlivé při maximální rychlosti čtení 5000 znaků za sekundu.
Původní Colossus Mk. 2 v akci
Kolos nebyl univerzálním počítačem (například dle Turingovy definice), jednalo se o počítač navržený pro sčítací operace a funkce typu boolean. Dokonce ani druhá generace se 2400 elektronkami to nezměnila. V obou případech se ale podařilo významně urychlit proces luštění Lorenzovy šifry. Přesto mu ale prvenství patřilo, byť velmi krátké, neboť první univerzální počítač ENIAC s neuvěřitelnými 17 500 elektronkami spatřil světlo světa již v roce 1946. Bylo to navíc prvenství neveřejné – Kolos, stejně jako drtivá většina ostatních vynálezů v Bletchley Park, zůstala až do počátku 70. let tajná.
Jak fungoval britský Tuňák? Podívejte se na vyprávění jeho operátorky na YouTube.
Chcete si vyzkoušet Lorenzovu šifru? Zkuste zjednodušenou verzi v prohlížeči nebo verzi naprogramovanou v Pythonu.
Popis fungování Lorenz SZ [PDF].
Jak přesně fungoval Colossus (anglicky).
Jak těžké bylo v roce 2007 rozluštit Lorenzovu šifru?
Zdroje
- General Report on Tunny z roku 1945 na Alanturing.net.
- Wikipedie: Colossus
- Wikipedie: luštění Lorenzovy šifry
- Wikipedie: Lorenzova šifra
- Practical Cryptography
- Codes and ciphers
ČLÁNKY DO MAILU