O HESLECH
TAJNÝCH ALGORITMECH
A ŠIFROVÁNÍ ZPAMĚTI
 
 

Článek představuje šifrování zpaměti především jako levný a snadno použitelný prostředek pro bezpečnější uložení, sdílení a předání hesel. V praxi může také zesílit ověření totožnosti či zkomplikovat tajný algoritmus.   

Jednou z možností ochrany objektů je použití hesel. Jeho výhody? Nepotřebujeme žádné speciální a drahé zařízení.

    Je-li seznam hesel v paměti počítače zašifrován jednosměrným šifrovacím algoritmem (algoritmus vybraný tak, aby pro něj neexistoval jednoduchý dešifrovací algoritmus), pak heslo může být uloženo na jediném a to nejbezpečnějším místě - v paměti člověka. A nevýhody? Uvedu jen některé:

  1. Určitě jste četli o kurýrech, kteří si zjistili jaká hesla doručují.
  2. Aby neoprávněná osoba nemohla heslo snadno uhodnout, mělo by být vybráno náhodně. Ale jak si najednou zapamatovat a nikam nezapsat velký počet takových hesel?
  3. V pohádce bratří Grimmů "Locika" zvolila čarodějnice heslo "Lociko, Lociko, své vlasy mi dolů shoď!". Málokdo by je uhodl, protože locika je rostlina (čarodějnice postupovala podle doporučení Puttera a Wagnera z článku [5]). Já bych je neuhodl určitě, protože jsem ani nevěděl, že taková rostlina existuje, ale princ je zaslechl a to stačilo. Co se právě píše na klávesnici (tedy i heslo) je možné odpozorovat nebo může být získáno infiltračními prostředky, případně úpravou klávesnice.
  4. Opravdu důležité heslo by mělo být "uzamčeno" pouze v paměti člověka. Ale co když je zapomene? Co když nebude přítomný v okamžiku, kdy je nutné toto heslo použít?

     Zkusili jste si někdy zvolit jako heslo náhodně sestavený řetězec znaků? Pokud ano, určitě jste si pro jeho vybavení v paměti našli nějaký algoritmus. V tomto směru není následující úryvek z jedné povídky Jamese Thurbera (Asociační metoda ...) zas až takovou nadsázkou: "Tak například jsem si kvůli zapamatování jednoho čísla představoval, že jsem důstojník ve válce s Mexikem (jistý poručík Chelsea), který poslal na pomoc Napoleonovi u Waterloo baseballovou devítku. Klíčové číslo bylo 4615, správně se mělo číst 3724. Prostě jsem odeslal 9 ze 46 k 15 chápete?".

     Výsledkem takového algoritmu je ovšem stále stejná hodnota. Už v knize [1] a také v [4], ale především v článcích J.A. Hasketta ([2] a [3]), jsou uvedeny příklady, ve kterých uživatel dokazuje svou totožnost znalostí tajného ověřovacího algoritmu (označme jej T), který zpaměti aplikuje na systémem předložené pseudonáhodně vybrané slovo (označme je x). Když se slovo x objeví jako výzva k zadání hesla na obrazovce, provede uživatel zpaměti jednoduchý algoritmus (v [1] a v [4] ještě aritmetickou transformaci), výsledek y = T(x) napíše na klávesnici a předá systému jako heslo platné právě v tomto okamžiku. Systém (pomocí ověřovacího programu) určí, jestli y je výstupní hodnotou algoritmu T při vstupní hodnotě x. Kromě/mimo x je možné využít i jiné smluvené údaje (například datum, hodinu, kdo má ten den svátek).

     Může být tajný algoritmus uložen jen na jediném místě - v paměti člověka? Obecně ne. Někdo ho mmusí vymyslet a někdo musí napsat a odladit odpovídající ověřovací program. To je dost příležitostí k prozrazení a není-li uživatel programátor, nemůže tuto činnost provádět jedna osoba. Ověřovací programy musí být uloženy v bezpečně chráněných souborech, ale k nim musí mít (už kvůli pojišťování) někdo přístup. Ověřovací program by ale mohl být před zápisem do souboru zašifrován heslem uživatele. V procesu ověření totožnosti by pak byl dešifrován pouze správně zadaným heslem uživatele a teprve potom proveden.

     Pokud tajný algoritmus použijeme jako obranu proti odpozorování, měl by být snadno proveditelný zpaměti a přitom téměř neodhalitelný z dvojic hodnot x , y. Z [1, s. 287] vyplývá, že by mělo být snadné takové algoritmy navrhnout. Putter a Wagner v kritice Haskettova článku [5] pochybují, že jich je dostatečný počet. A existuje vůbec nějaký? "Nevím" odpovídá Haskett sám sobě v [3].
     Když se dívám na nějaké sportovní utkání, vždycky se přistihnu, že fandím tomu, kdo právě prohrává (pak mě to má bavit). Od prvního přečtení Haskettova článku, ve kterém chybí odkazy na literaturu, přes jeho "já jsem autorem ověřovacích algoritmů" v odpovědi na první dvě kritiky (CACM 27 , 11/84, s. 1082) až po to dojímající "nevím" se ze mě postupně stal (jak se ukázalo špatný) hledač dobrých ověřovacích algoritmů. To, co v tomto článku nazývám šifrování hesel zpaměti, byl zpočátku jen další neúspěšný pokus o nalezení dobrého ověřovacího algoritmu. Protože jsem šifrování zpaměti několikrát použil ve své praxi (například pro bezpečnější uložení hesla), prozkoumal jsem je podrobněji. Zjistil jsem, že se mi nakonec přece jen podařilo "povýšit ponížené". Jenomže toto povýšení se netýká ani tak tajných algoritmů, jako spíš tolik zatracovaných hesel. Konec konců, z evolučního hlediska by mezi tajnými hesly a tajnými algoritmy měly stát algoritmy veřejně známé, parametrizované tajnými hesly. A právě jejich příkladem šifrování zpaměti je.

     V následujících kapitolách vysvětlím, co to je šifrování zpaměti, jak se provádí a k čemu nám může být dobré.

Šifrování hesel zpaměti

     Představme si, že neoprávněná osoba zjistí jen hodnotu y (jenom to, co se napsalo na klávesnici). Pak stačí najít "průměrný" algoritmus, který k heslu h a slovu x určí právě jedno slovo y a splňuje podmínku: pouze z hodnoty y nelze heslo h odvodit, ale při znalosti x je možné určit heslo h jednoznačně. Příkladem takového algoritmu je šifrování hesla h klíčem x na kryptogram y prováděné zpaměti. Nejjednodušší (a i tak dost složitý) postup šifrování zpaměti, který si umím představit, předpokládá: zapamatovat si náhodně vybrané heslo, vybavit si je znak po znaku, každý znak hesla zašifrovat odpovídajícím znakem klíče na znak kryptogramu a tento znak napsat (důležité je, že postupně vytvářený kryptogram si pamatovat nemusíme).

     Předpokládejme, že je dána konečná, minimálně dvouprvková množina M a na ní je definovaná komutativní operace sčítání, k níž existuje inverzní operace odčítání. To znamená, že pro libovolné prvky a z M , b z M (na jejich pořadí nezáleží) existuje v M právě jeden prvek c takový, že platí c = a + b; a pro libovolné prvky a z M, b z M existuje v M právě jeden prvek d takový, že platí b + d = a (tj. d = a - b).

Příklad: (Vernamova šifra) Operace sčítání i odčítání je logická operace nonekvivalence definovaná na dvouprvkové množině.

     Jestliže o h a x nelze předpokládat více, než že jsou prvky množiny M, pak pouze z hodnoty y = h + x nemůžeme h odvodit. Určíme-li totiž y - p postupně pro všechny prvky p z M, získáme tak, jako rovnocenné kandidáty na h, všechny prvky M. Jestliže však známe x, můžeme určit h jednoznačně výpočtem y - x.
     Podobné tvrzení ovšem bude platit i v případě, kdy místo množiny M budeme uvažovat množinu Mn všech slov délky n nad M (n je přirozené číslo a slovem délky n nad M nazýváme posloupnost n prvků vybraných z M), na níž je definována operace sčítání (a obdobně i k ní inverzní operace odčítání) takto:

     Pro libovolná slova a = a1a2 ... an z Mn, b = b1b2 ... bn z Mn nazveme součtem slov a, b (zřejmě právě jedno) slovo c = c1c2 ... cn z Mn takové, že platí ci = ai + bi, pro i = 1, 2, ..., n. Toto slovo označíme symbolem c = a + b.

     Volba vhodného algoritmu šifrování se tedy zjednodušuje na volbu vhodné množiny znaků a na ní definované vhodné komutativní operace, ke které existuje operace inverzní.

Proč šifrovat hesla zpaměti?

     Tato otázka je na místě a je nejvyšší čas na ni odpovědět. Předpoklad, že se neoprávněná osoba bude soustředit jenom na text napsaný na klávesnici, nikoho o užitečnosti šifrování zpaměti nepřesvědčí. Z předchozího výkladu, ale vyplývají některé zajímavé možnosti využití šifrování zpaměti v praxi (další informace uvedu v kapitole Příklady použití).

     Jestliže h je heslo uživatele a v paměti počítače je uložena hodnota h' = K(h), kde K označuje jednosměrný šifrovací algoritmus, pak odpovědí y = x + h na výzvu systému x prokáže uživatel znalost hesla h, pokud platí rovnost K(y - x) = h'. Jestliže operaci sčítání (odčítání) dvou slov nestejné délky definujeme tak, že délka součtu (rozdílu) se rovná délce kratšího slova, nemusí být v počítači uložen ani údaj o délce hesla. Stačí, aby se délka slova x rovnala maximální povolené délce hesla. Chce-li neoprávněná osoba odvodit heslo h nebo alespoň některé jeho znaky, musí získat dvojice odpovídajících si znaků ve slovech x a y. Jestliže jí v tom dokážeme zabránit, nemůže heslo odvodit (příklad Zesílené ověření totožnosti v kapitole Příklady použití).

     Šifrováním zpaměti můžeme ztížit odhalení jednoduchých tajných algoritmů (příklad Tajný algoritmus).

     Pokud uživatel zašifruje heslem h výstupní hodnotu T(x) tajného algoritmu (délka slova T(x) nesmí být menší než délka hesla h), pak odpovědí y = h + T(x) dokáže současně znalost hesla i tajného algoritmu, platí-li rovnost K(y - T(x)) = h'. Uživatel tak může znalostí tajného algoritmu prokázat oprávněnost přístupu k objektu chráněnému heslem.

     Určíme-li ke slovu h slova h1, h2 tak, že platí h = h1 + h2 (stručněji: rozdělíme-li heslo h na dílčí hesla h1 a h2, pak pouze z hodnoty h1 nebo pouze z hodnoty h2 nelze heslo h odvodit (příklady Předání hesla a Bezpečnější uložení hesla).

     Protože ve všech příkladech operaci sčítání provádí člověk, zatímco operaci odčítání počítač (pro rozdělení hesla si můžeme napsat program), popíšu v další kapitole podrobně jen provedení operace sčítání.

Jak šifrovat hesla zpaměti

     Konkrétní volbu množiny M ovlivňuje možnost neoprávněné osoby heslo hádat. Chceme-li, aby pravděpodobnost uhádnutí určitého slova délky n jediným pokusem byla přibližně rovna 10-6, musíme pro množinu s počtem prvků 2, 10, a 30 volit číslo n po řadě 20, 6 a 4. Například Vernamova šifra je vzhledem k potřebné délce hesla pro šifrování zpaměti téměř nepoužitelná, i když sčítání dvou prvků je velice jednoduché.
     Konkrétní volbu operace sčítání ovlivňuje rozumný předpoklad, aby šifrování zpaměti bylo nenápadné. Nemělo by být zřejmé zda se vůbec a nebo právě teď šifrování provádí (žádné tajné šifrovací tabulky, žádné pomocné výpočty na papíře).

     Nyní uvedu dva algoritmy šifrování zpaměti. První z nich je ověřovací algoritmus J.M.Carrolla a P.M.Lellanda z knihy [4, s. 49].

Algoritmus 1.

Prvky množiny M1 jsou celá čísla 0 až 9. Operace sčítání je sčítání modulo 10, operace odčítání je odčítání modulo 10. Máme-li určit zpaměti výsledek operace sčítání dvou čísel z M1 modulo 10, sečteme čísla obvyklým způsobem a je-li součet:

  • 0 až 9, pak se rovná výsledku;
  • 10, pak výsledek je 0;
  • 11 (jeden-áct ), pak výsledek je 1 (jedna);
  • 12 (dva-náct), pak výsledek je 2 (dvě);
  •   .
  •   .
  • 18 (osm-náct), pak výsledek je 8 (osm).

     Výsledek sčítání dvou prvků z M1 modulo 10 určíme tedy buď ze slovního vyjádření aritmetického součtu (počítáme-li v duchu devět plus čtyři je tři... už známe výsledek) nebo z jeho číselného vyjádření (poslední cifra).


Příklad:     0 4 2 7 6 9
           + 0 1 5 3 8 9 7
             0 5 7 0 4 8

     Operace sčítání je komutativní a asociativní. Operace odčítání není komutativní.

Algoritmus 2.

     Prvky množiny M2 jsou písmena latinské abecedy, středník, čárka, tečka a lomítko. Operace sčítání (odčítání) se odvozuje z tabulky:


  1 2 3 4 5 6 7 8 9 0
  Q W E R T Y U I O P
  A S D F G H J K L ;
  Z X C V B N M , . /

     V tabulce jsou prvky množiny M2 zapsány ve třech řádcích a deseti sloupcích. Sloupce jsou označeny čísly 1 až 9 a 0 v záhlaví tabulky. Součet dvou prvků z M2 najdeme v tabulce tímto postupem:

V záhlaví si přečteme čísla sloupců, ve kterých jsou zapsány sčítané prvky. Čísla sečteme modulo 10. Výsledek určuje sloupec, ve kterém je součet těchto prvků zapsán (součet D + F i O + K je v sedmém sloupci). Jsou-li sčítané prvky ve stejném řádku je v něm i jejich součet (D + F = J); jinak je součet ve zbývajícím řádku (O + K = M), tedy v tom řádku, ve kterém není žádný ze sčítaných prvků zapsán.


Příklad:     O K T I D
           + A L E N
             / J I F

     Nekomutativní operace odčítání se provádí podobně (číslo sloupce se určí operací odčítání modulo 10). Operace sčítání je komutativní, ale není asociativní. Pro a, b , c z M2 platí a + (b + c) = (a + b) + c tehdy a jen tehdy, když prvky a, c jsou zapsány ve stejném řádku tabulky.
     Při práci u počítače máme podobnou tabulku přímo před očima. Jistě jste sami poznali, že tabulka je "idealizovaným" zobrazením části anglické nebo americké klávesnice. V praxi by mohl údaj o typu použité klávesnice doprovázet uložený nebo předávaný kryptogram. V příkladech budu používat výhradně uvedenou tabulku.

Příklady použití

     Možnosti využití šifrování hesel zpaměti v praxi naznačuje následujících pět příkladů. Můžete si je porovnat s popisem záporů použití hesel v úvodu tohoto článku. Na to, že jejich výčet není úplný, jsem vás už upozornil. Příklady ukazují, že není ani náhodně sestavený.

Tajný algoritmus

     "... pochybuji, že lidský důmysl dokáže sestavit takový problém, který by zase lidský důmysl při vypjatém soustředění nevyřešil" čteme v povídce Zlatý brouk od E.A. Poa. Ale posuďte sami jak složité může být odhalení tajného algoritmu. Jste v roli neoprávněné osoby a máte k dispozici tyto údaje ze září roku 1992:

datum hodina minuta výzva systému odpověď uživatele
7.9 17 15 EFNSMGBU JMJL
8.9 14 13 CIHK.XED W/GV
10.9 16 10 GTC,CMVA KD//
11.9 14 22 LLCFGNPE PZUY
14.9 8 6 AWTXP/,Q HAJL
15.9 8 5 DALPNAIC ADWV
15.9 12 30 EAXEYNGA ?

Doplňte odpověď uživatele na výzvu EAXEYNGA (řešení je na konci článku).

Předání hesla

     Dvě osoby se předem domluví na pevném šifrovacím klíči "NATL". Chce-li předat jedna osoba druhé heslo "M/AE", předá jí nechráněným komunikačním kanálem rozdíl hesla a pevného klíče zřetězený s náhodně zvolenými znaky ("M/AE" - "NATL" = "ZONV", ale předá se například "ZONVTX/B"). Heslo je pak možné převzít výpočtem "ZONVTX/B" + "NATL".
     Pro předání hesla můžeme využít i kurýra (v tomto případě ne nutně důvěryhodného). Kurýr doručí dílčí heslo "ZONVTX/B". Druhé dílčí heslo "NATL" předáme v dopise nebo telefonem.

Použití velkého počtu hesel

     Chceme zvolit velký počet hesel tak, aby každé z nich vypadalo jako náhodně vybrané (některé systémy to kontrolují) a přitom nebylo nutné si je někam poznamenávat.
     Dříve než zvolíme určité heslo, najdeme nějaké slovo, které se nám před použitím tohoto hesla snadno vybaví. Například SQL/DS před použitím systému SQL/DS. K seznamu takových slov x1, x2 , ..., xn určíme jediné slovo k (nejlépe programem) tak, aby každé slovo xi + k vypadalo jako náhodně vybrané. Zapamatujeme si jen slovo k. Slova xi + k zvolíme za hesla. Správné heslo pak odvodíme šifrováním zpaměti až při jeho zadávání. Jestliže slovo k je "ILAG", pak správné heslo ke slovu "SQL/DS" bude "//;T". Když se musí hesla změnit (některé systémy tuto změnu vyžadují po uplynutí relativně krátké doby), stačí jen určit a zapamatovat si novou hodnotu k.

Zesílené ověření totožnosti

     Chceme utajit informaci, kterou vybraný uživatel vzdáleného počítače nebo terminálu dokazuje svou totožnost systému střediskového počítače nebo serveru, předpokládáme-li jako možný útok: odpozorování, infiltrační prostředky v počítači uživatele, úpravy klávesnice u počítače nebo terminálu uživatele.
     Využijeme šifrování hesel zpaměti jako ověřovací algoritmus a telefonické spojení uživatele s pověřenou osobou (operátorem). Slovo x se zobrazí na displeji operátora. Operátor je předá uživateli například při kontrole zpětným voláním. Uživatel šifrováním zpaměti určí x + h, výsledek napíše na klávesnici a předá ke kontrole systému.

Bezpečnější uložení hesla

     Správce systému rozdělí své heslo h na dílčí hesla h1 a h2. Heslo h1 předá určené osobě (vedoucímu), heslo h2 předá svému zástupci. Zapomene-li správce systému heslo, převezme od zástupce a vedoucího dílčí hesla a svoje heslo odvodí výpočtem h1 + h2. Předá-li vedoucí svoje dílčí heslo zástupci, provede tento výpo­ čet zástupce a získá tak heslo správce systému.
     Pokud správce systému použije šifrování hesel zpaměti (prvním algoritmem) jako ověřovací algoritmus, nemusí zástupce jeho heslo skutečně převzít. Rozhodne-li vedoucí, že je nutný zásah zástupce v roli správce systému, zahájí (o samotě) ověřovací proceduru, přijme hodnotu x od systému, určí w = x + h1, vymaže obrazovku a výsledek w předá zástupci. Zástupce (o samotě) dokončí ověřovací proceduru odesláním hodnoty w + h2 systému. Má-li platit

w + h2 = x + h1 + h2 = x + h1 + h2 = x + h

je zřejmé, že operace sčítání musí být asociativní.

Závěr

     V tomto článku jsem popsal dva algoritmy šifrování zpaměti. Operace sčítání v prvním z nich je jednodušší a je asociativní (příklad Bezpečnější uložení hesla). Výhodou druhého algoritmu je, že můžeme volit kratší a snadněji zapamatovatelné heslo, a pracovat se slovy jazyka nebo zkratkami (příklad Použití velkého počtu hesel). Příklady ukazují, že šifrování zpaměti je především levný a snadno použitelný prostředek pro bezpečnější uložení (sdílení) a předání hesel. "Obvyklé" řešení uvedených příkladů by vyžadovalo: šifrovací zařízení nebo důvěryhodného kurýra (příklad Předání hesla); závěsy na oknech, které by zabránily odpozorování hesla, nebo identifikační kartu vybavenou procesorem (příklad Zesílené ověření totožnosti a možná i příklad Tajný algoritmus); trezor s více zámky nebo identifikační karty umožňující sdílet tajemství (příklad Bezpečnější uložení hesla).

Řešení úlohy

     Správná odpověď je ".DLV". Z datumu (15), hodiny (12) a kalendáře na rok 1992 zjistíme, kdo má svátek 15. prosince. Podle mého kalendáře Radana. Tajné heslo je "GSHE". Heslo platné 15. září 1992 o půl jedné se určí šifrováním zpaměti: "RADANA" + "GSHE". Výzvu systému bychom mohli využít například pro určení hesla platného 30. září ve čvrt na tři.

Literatura

  1. C. J. DATE: An introduction to database systems. Addison-Wesley Publishing Co. 1975.
  2. J. A. HASKETT: Pass-algorithm: A user validation scheme based on knowledge of secret algorithms. CACM, r. 27, č. 8 1984, s. 777-781.
  3. J. A. HASKETT: Pass-algorithm: A user validation scheme based on knowledge of secret algorithms
    (technical correspondence). CACM r. 28 , č. 7 1985. s. 750-751.
  4. L. J. HOFFMAN: Modern methods for computer security and privacy (Sovremennyje metody zaščity informacii. Sovetskoje radio, Moskva 1980).
  5. P. PUTTER P. WAGNER: Pass-algorithms: A user validation scheme based on knowledge of secret algorithms (technical correspondence). CACM r. 28 , č. 7 1985. s. 750.

hlavní stránka identifikace a autentizace rexx akvašneci zrakové klamy mail

změněno 1. ledna 2001
Copyright © 1998-2001 Vladimír Zábrodský