Úvod do klasických a moderních metod šifrování
Jaro 2012, 7. přednáška
Historické poznámky
• Německo napadlo Dánsko a Norsko 9.4.1940
• Ten samý den požádalo Švédsko o pronájem telefonních kabelů
• Dohoda byla uzavřena 14.4.1940
• Ve stejnou dobu začaly pokusy o odposlechy pronajatých linek
• Od 20.4. byly dálnopisné hovory nahrávány
• Na počátku šlo pouze o testovací provoz, nešifrovaný
• Dálnopisné spojení je duplexní, zpočátku nebylo možné dvojice linek párovat, záznamy byly z každé linky zvlášť
• Němečtí operátoři si psali o brzkém zapojení Geheimschreiber
• Brzy poté začaly být zprávy nečitelné
• Mezi nešifrovaným klábosením operátorů se objevovaly šifrované části vždy uváděné textem UMUM
• Tato čtyři písmena pravděpodobně označovala přepnutí do šifrovaného
• módu Od 21.5.1940 běželo veškeré odposlouchávací zařízení v plném provozu,
párování linek už bylo zvládnuté
Dálnopisné spojení
• Každý znak je kódován pomocí pětice impulsů stejné délky
• Označovat je budeme 0 a 1
• Znamená to, že v daném okamžiku proud prochází nebo neprochází
• Zprávy se buď psaly přímo na klávesnici nebo je stroj četl z děrné pásky
• Děrná páska obsahovala pětice otvorů/neotvorů ve sloupcích
• Umožňovalo to kódovat 32 znaků
• To bylo málo, takže dálnopisy obsahovaly přepínače LS (letter shift) a FS (forward shift)
• Tím se počet možností zvýšil na 64
Kódovací tabulka CCITT2
LS pořadí pulsů FS LS pořadí pulsů FS Švédské značení 12345 12345
A 11000 - Q 11101 1 B 10011 ? R 01010 4 C 01110 : S 10100 ´ D 10010 Kdo je tam? T 00001 5 E 10000 3 U 11100 7 F 10110 CS V 01110 = G 01011 CS W 11001 2 H 00101 CS X 10111 / I 11010 8 Y 10101 6 J 11010 zvonek Z 10001 +
K 11110 ( posun válce 00010 posun válce 1 L 01001 ) nový řádek 01000 nový řádek 2 M 00111 . LS 11111 LS 3 N 00110 , FS 11011 FS 4 O 00011 9 space 00100 space 5 P 01101 0 prázdné místo 00000 prázdné místob 6 CS – (country specific) speciální znaky
Šifrování pomocí Vernamovy šifry
• K otevřenému textu byl přičítán klíč modulo 2
• Každá pětice bitů kódující nějaký znak byla měněna pomocí pětice bitů přečtené z děrné pásky nebo jiného zařízení
• Například písmeno A: 11000
• bylo pomocí klíče 01010
• změněno na 10010
• Protože nevíme, byl-li klíč pro tuto šifru generován náhodně, budeme ji
nazývat pseudoVernamova šifra
Příklad komunikace
• Odposlechnuté zprávy mohly vypadat takto
• HIER35MBZ35QRV54B35KK35QEP45QW55QI55RU55TW
335555353535UMUM35VEVE35ZRDDLH5FNY13QUKD4GEHNSWO
• Připomeňme si, že 3,4,5 znamená LS, FS, Space
• Tučné znaky znamenají, že byly vysílány přijímající stranou. Obyčejně znaky byly vysílány vysílající stranou
• 25.5. a 27.5. byly první dny, kdy se podařilo správně spárovat oba kanály, na kterých probíhala komunikace mezi dvěma stanicemi a podařilo se správně odposlechnout větší množství zpráv.
• Obsluha dálnopisů to ale viděla na papíře následovně
• HIER MBZ QRV? KK QEP 12 25 18 47 52 UMUM VEVE ...
• MBZ je identifikátor stanice
• QRV? je žádost o potvrzení, že příjemce rozumí
• KK je potvrzení přijímající strany, že rozumí
• QEP uvádí indikátor zprávy
• UMUM oznamuje přechod do šifrovacího módu
• VEVE přijímající strana potvrzuje přechod do šifrovacího módu
Použití stejného klíče
• To, že dvě zprávy byly šifrované ze stejného počátečního nastavení, se dalo usoudit ze stejných QEP čísel.
• Příslušné otevřené texty nebyly identické kvůli pohodlnosti operátorů a vkládaných krátkých sekvencí typu 35
1: ALZGJMGU66H4HJPLHN 2: NP3UMWFZ31NMYKMJHB 3: GRQUMAA4JTQFLQMHJI 4: LYZGJMORYYDRQKNHJN 5: LEZGKVRVANBWE6MJUT 6: BOTA3WFUSGODA2JIUN 7: YEYZL42DYD5LMHLOIM 8: RKZGBWFLIX6AZEMKEY 9: CCNRWWGKOTV5LLUMCD 10: ITXUMSMU4VVNTZJNFI
Opakované bigramy na počátku
• Hledáme stejné bigramy na stejných místech na počátcích textů
• Předpoklad je, že jsou to šifrové podoby otevřeného textu 35 (tj. LS SP)
123456789
1: ALZGJMGU66H4HJPLHN 3535
2: NP3UMWFZ31NMYKMJHB 3535
3: GRQUMAA4JTQFLQMHJI 35
4: LYZGJMORYYDRQKNHJN 3535
5: LEZGKVRVANBWE6MJUT 35
6: BOTA3WFUSGODA2JIUN 35
7: YEYZL42DYD5LMHLOIM 8: RKZGBWFLIX6AZEMKEY 35 35
9: CCNRWWGKOTV5LLUMCD 10: ITXUMSMU4VVNTZJNFI 35
Kódy pro LS a SP
•
Arne Beurling si všimnul, že kódy pro LS a SP se liší pouze v prostředním bitu
3(LS): 11111 5(SP): 00100
•
Stejnou vlastnost by měly mít i po zašifrování pseudoVernamovou šifrou sloupec 4 5 6
U: 11100 J: 11010 W: 11001 G: 01011 M: 00111 1: 00010
•
Kromě Vernamovy šifry se tedy muselo dít ještě něco dalšího
•
Arne Beurling si řekl, že s pěti bity se mnoho dělat nedá
•
Kromě přičtení klíče se dají ještě bity přeházet
•
Tedy ve 4.sloupci se třetí bit poslal na druhý, v 5. se poslal na čtvrtý a v
šestém sloupci třetí bit zůstal na místě
Kódy pro Q, R, V
• Další často používanou kombinací písmen bylo QRV?
• To obvykle následovalo po 35
• Další šťastnou shodou okolností byly rozdíly mezi kódy následujících dvojic znaků
3: 11111 Q: 11101 3: 11111 Q: 11101 R: 01010 V: 01111
• Tyto rovnosti se zachovávají po přičtení klíče pro pseudoVernamovu šifru
• Je pouze třeba odhadnout, které části šifrových textů odpovídají otevřenému textu QRV?
• Správnost odhadu lze ověřit porovnáním, liší-li se šifrové podoby ve
správném počtu znaků
Odhady pro Q,R,V
123456789
1: ALZGJMGU66H4HJPLHN 35353535
2: NP3UMWFZ31NMYKMJHB 3535
3: GRQUMAA4JTQFLQMHJI 35QRV
4: LYZGJMORYYDRQKNHJN 3535QRV
5: LEZGKVRVANBWE6MJUT 35QRV35
6: BOTA3WFUSGODA2JIUN 35
7: YEYZL42DYD5LMHLOIM 8: RKZGBWFLIX6AZEMKEY 35 35
9: CCNRWWGKOTV5LLUMCD 10: ITXUMSMU4VVNTZJNFI 35
• Porovnáme v telegramech 4 a 5 písmena v pátém sloupci
• Jsou to písmena
J: 11010 3: 11111 K: 11110 Q: 11101
• Šifrové znaky se shodují na čtyřech místech, což je v souladu s tím, že se odhadované znaky v otevřeném textu rovněž shodují na čtyřech místech
• Permutace v pátém sloupci tedy musí přesouvat čtvrtý bit na třetí místo
• Podobnými úvahami doplníme i modré znaky 35
Permutace v sedmém sloupci
123456789
1: ALZGJMGU66H4HJPLHN 35353535
2: NP3UMWFZ31NMYKMJHB 3535
3: GRQUMAA4JTQFLQMHJI 35QRV
4: LYZGJMORYYDRQKNHJN 3535QRV
5: LEZGKVRVANBWE6MJUT 35QRV35
6: BOTA3WFUSGODA2JIUN 35
7: YEYZL42DYD5LMHLOIM 8: RKZGBWFLIX6AZEMKEY 35 35
9: CCNRWWGKOTV5LLUMCD 10: ITXUMSMU4VVNTZJNFI 35
• V sedmém sloupci se nyní již vyskytují
všechny naše speciální znaky 3,5,Q,R,V
• Můžeme tedy udělat všechna porovnání 3-5, 3-Q, Q-R, 3-V
OT 3: 11111 3: 11111 ŠT G: 01011 G: 01011 OT 5: 00100 Q: 11101 ŠT F: 10110 O: 00011 OT Q: 11101 3: 11111 ŠT O: 00011 G: 01011 OT R: 01010 V: 01111 ŠT A: 11000 R: 01010
• Permutace bitů po přičtení klíče tedy
přesouvá bity takto: 3. na 4., 4. na 2., 2. na 3., 1. na 5. a tedy 5. na 1.
• Použitá permutace je tedy 54231 .
Nalezení bitů klíče pro Vigenéra
• Připomeňme si, že v sedmém sloupci máme tuto dvojici
• OT 3: 11111 ŠT G: 01011
• Odhalili jsme, že po zašifrování Vigenérovo šifrou následovalo přeházení bitů 3. na 4., 4. na 2., 2. na 3., 1. na 5., a tedy 5. na 1.
• Odstraníme-li toto přeházení bitů ze šifrového znaku G: 01011 ,
• dostaneme 10110 .
• To je výsledek Vigenérovy šifry použité znak otevřeného textu 3: 11111
• Klíč pro sedmý znak Vigenérovy šifry je tedy 01001 .
Tam a zpátky, tam a zpátky
• Tímto způsobem postupně odhadujeme další znaky otevřených textů a z nich pak dostaneme klíč pro pesudoVernamovu šifru a permutace pro jednotlivé znaky
Sloupce 1 2 3 4 5 6 7 8 9 10 1 A L Z G J M G U H 4 3 5 3 5 3 5 3 5 2 N P 3 U M W F Z 3 1 2 3 5 3 5 Q R V 3 G R Q U M A A 4 J T P 3 5 Q R V 4 ? 4 L Y Z G J M O R Y Y 3 5 3 5 Q R V 4 5 L E Z G K V R V A N 3 5 Q R V 3 5 G Permutace 21435 13254 12435 52314 54231 31245 15234 52314 Klíč 10110 00011 00011 10100 01001 11000 10101 11111
• Celkem takto Beurling odhalil kolem stovky znaků klíče a příslušných permutací
Posloupnosti bitů klíče
•
Beurling si všimnul, že posloupnost prvních bitů jednotlivých slov klíče pro pseudoVernamovu šifru je periodická
•
Podobně periodické byly posloupnosti druhých bitů slov klíče, třetích bitů, čtvrtých bitů a pátých bitů
•
Tyto posloupnosti byly různé a měly různé periody
•
V různých dnech se některé z těchto posloupností opakovaly, i když se měnil číslo bitu, kterému odpovídaly
•
Objevovaly se také ale nové posloupnosti s periodou odlišnou od těch již odhalených
•
Na základě znalosti konstrukce jiných dálnopisných šifrátorů Beurling
správně předpokládal, že tyto posloupnosti jsou generované pomocí rotorů
•
Jak jsou ale generovány permutace přehazující pětice bitů po použití
pseudoVernamovy šifry?
Přepínače
• Beurling předpokládal, že permutace bitů je zařízena pomocí přepínačů mezi jednotlivými linkami
• Zapojení nebo nezapojení přepínače je pak kontrolováno pomocí bitu
1 0
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
• Z permutace pro čtvrtý znak usoudil, že existuje přepínač mezi 1. a 2. bitem a další mexi 3. a 4. bitem
• Z permutace pro čtvrtý znak usoudil, že také existuje také přepínač mezi 2. a 3.
bitem a mezi 4. a 5. bitem
• Permutaci pro pátý znak lze získat pomocí jednoho přepínače mezi 3. a 4. bitem
Další přepínače a jejich pořadí
• Permutaci pro sedmý bit lze získat pomocí tří přepínačů. Jeden je pro 1. a 5. bit
• Další je pro 2. a 3. bit a poslední přehazuje 3. a 4. bit
• Tyto dvě transpozice ale nekomutují, žádoucí permutace lze dosáhnout pouze pokud napřed přehodíme 3. a 4. bit a poté přehodíme 2. a 3. bit
• Podobně permutaci pro šestý znak získáme tak, že napřed přehodíme 1. a 5. bit a poté přehodíme 4. a 5. bit
• Jiným způsobem ji pomocí dvou přepínačů nelze získat.
• Dalším experimentováním Beurling zjistil, že přepínače jsou na jednotlivých linkách v následujícím pořadí
• Prvním zleva je přepínač, který prohazuje 1. a 5. bit, poté přepínač prohazující 4.
a 5. bit, uprostřed je přepínač prohazující 3. a 4. bit, druhý zprava je přepínač prohazující 2. a 3. bit a nejvíce vpravo je přepínač prohazující 1. a 2. bit
• Zapojení přepínačů pro šestý znak je pak 00111, pro sedmý 01001, atd.
Další rotory a denní klíče
• Získal tak posloupnosti bitů kontrolujících zapojení jednotlivých přepínačů
• Ty byly odlišné od posloupností generujících jednotlivé bity klíče pro pseudoVernamovu šifru
• Získal tak celkem 10 posloupností bitů, které se opakovaly i v jiných dnech, pouze v jiných rolích a v jiném pořadí
• To už stačilo k dešifrování všech zpráv v daném dni
• Délky těchto posloupností, tedy délky obvodu jednotlivých rotorů byly od nejmenšího k největšímu 47, 53, 59, 61, 64, 65, 67, 69, 71, 73.
• Každý den vždy pět posloupností začínalo u každé zprávy stejně, zbývajících pět posloupností mohlo mít v daný den různé počátky
• Tyto počátky odpovídaly pěti číslům, které byly vždy uvedené znaky QEP
• Beurling z toho usoudil, že denní klíče fixovaly nastavení pěti rotorů, obsluha si pak volila sama nastavení zbývajících pěti rotorů pro každou konkrétní zprávu – to sdělovala přijímající straně jako indikátor
• Dále musel denní klíč určit, který rotor generuje posloupnost prvním bitů klíče pro pseudoVernamovu šifru, který geberuje druhé bity, atd.
• A dále který rotor generuje zapojování přepínače mezi 1. a 5. bitem, který mezi 5. a 4. bitem, atd.