V oblasti poƒítaƒové bezpeƒnosti se velmi ƒasto setkáváme s náhodn∞mi ƒísly a τifrovacími klíƒi. Na kvalit╪ "náhodnosti" jejich generování p²itom záleºí úpln╪ stejn╪ jako na kvalit╪ pouºívan∞ch τifer. V tomto ƒlánku vás seznámíme s nedávn∞m objevem, kter∞ umoºσuje m╪²it kvalitu náhodnosti daného zdroje. Je to pom╪rn╪ p²esná metoda, jejíº v∞znam vτak sahá daleko za hranice poƒítaƒové bezpeƒnosti. Moºná vás uº n╪jak∞ program poºádal, abyste chvíli náhodn╪ £ukali do klávesnice nebo pohybovali myτí. To jsou okamºiky, kdy na náhodnosti záleºí natolik, ºe program odmítá za kvalitu svého zdroje p²evzít odpov╪dnost a obrací se p²ímo na uºivatele. Znát míru náhodnosti pouºívaného zdroje je nutné zejména u bezpeƒnostních aplikací. Kritické je to pak p²i generování τifrovacích klíƒà. Jestliºe generátor náhodn∞ch bità nemá dostateƒnou kvalitu, màºe se stát, ºe vygenerovan∞ch 128 bità τifrovacího klíƒe má pouze 40bitovou informaƒní hodnotu (neurƒitost, entropii). Generátor tak màºe snadno degradovat silnou τifru na slabou a dàsledky mohou b∞t znaƒné. Tyto p²ípady se uº staly - a bohuºel urƒit╪ nikoli naposledy.
Bezpeƒnost a náhoda
P²estoºe kvalitní zdroj entropie je p²i práci na poƒítaƒi pot²eba dost ƒasto, s poºadavkem vloºení náhodného ƒísla se v praxi setkáváme málokdy. P²ísluτné programy totiº necht╪jí obt╪ºovat uºivatele a generují náhodnost samy - jak um╪jí nejlépe. Ve v╪tτin╪ p²ípadà k tomu vyuºívají pouze "náhodnost" odvozenou od systémového ƒasu, coº je ale z hlediska bezpeƒnosti siln╪ nedostateƒné. Náhodné τifrovací klíƒe musí nap²íklad generovat internetov∞ prohlíºeƒ, pokud se se serverem spojuje zabezpeƒen∞m spojením prost²ednictvím protokolu SSL. Jak moºná víte, starτí verze prohlíºeƒe Netscape Navigator pouºívala slab∞ generátor náhodn∞ch ƒísel, a τifrovací klíƒe tak m╪ly entropii 47 namísto 128 bità. Tím se degradovala kvalita τifrování a byla z toho ostuda.Od té doby se na kvalitu náhodn∞ch generátorà dbá více.
Komprimace a náhodnost
Entropie vlastn╪ urƒuje skuteƒné mnoºství obsaºené informace a m╪²í se v bitech. Jednoduch∞m a znám∞m m╪²ítkem náhodnosti mohou proto b∞t nap². komprimaƒní metody. Pokud n╪jak∞ soubor dat zkomprimujeme dejme tomu na 40 % pàvodní délky, màºeme ²íci, ºe 60 % obsahu bylo nadbyteƒn∞ch a skuteƒn∞ informaƒní obsah byl 40 %. V jednom bajtu bylo tedy obsaºeno jen 40 %, tj. 8*0,4 = 3,2 bitu skuteƒné informaƒní hodnoty (entropie), neboli pràm╪rná entropie na jeden bit byla 0,40. A co komprimovan∞ soubor - bude náhodn∞? Tém╪² ano, i kdyº na jeho zaƒátku mohou b∞t prvopoƒáteƒní kusy pàvodního textu a v jeho t╪le n╪které markantní ²et╪zce. V mnoha p²ípadech ale komprimace skuteƒn╪ velmi p²iblíºí soubor dat jeho informaƒní hodnot╪. Jestliºe ale dáme zkomprimovat soubor náhodn∞ch dat, komprimaƒní metody zkolabují. A to i v p²ípadech, ºe zdrojová data nejsou zcela náhodná, ale mají entropii nap²íklad 0,90. Komprimace by m╪la dan∞ soubor zkrátit na 90 %, ale nestane se tak, protoºe p²ísluτná metoda prost╪ nezjistí, o jakou neurƒitost vlastn╪ jde. Neumí ji zjistit, zm╪²it ani odstranit. V p²ípadech náhodn∞ch nebo tém╪² náhodn∞ch souborà tedy b╪ºné komprimaƒní metody jako m╪²ítko neurƒitosti pouºít nelze.
Objev v m╪²ení entropie
Pràlom v m╪²ení entropie znamenal objev Ueliho Maurera z roku 1990, kter∞ jej prezentoval na kryptologické konferenci CRYPTO∩90 [1]. Nalezl velmi jednoduchou funkci, jíº dokázal m╪²it a pomocí statistického testu testovat entropii generátoru. Do té doby byla známa ²ada dàmysln∞ch testà, které zkoumaly partikulární parametry posloupnosti, jako nap²íklad statistické vlastnosti (autokorelaƒní test, test sérií, frekvenƒní test apod.) nebo sloºitostní charakteristiky, ale v∞sledky se nedaly kvantitativn╪ p²evést na hodnotu entropie. Jin∞mi slovy - v╪d╪li jsme, ºe posloupnost dejme tomu 200 pozic myτi (m╪²en∞ch v ƒasov∞ch mikrointervalech p²i jejím pohybu, viz obrázek 2) není náhodná a jaké má nedostatky (korelace sousedních pozic, nerovnom╪rn∞ v∞skyt jednotliv∞ch bajtà), ale nev╪d╪li jsme, jak dlouho máme myτí pohybovat, aby posloupnost jejích pozic uº reprezentovala nap²íklad 128bitovou entropii, tj. ekvivalent 128 náhodn∞ch bità. A Maureràv test práv╪ toto dokázal vypoƒítat.
Pouºitelnost Maurerova-Coronova testu
V roce 1999 zp²esnil odhady konstant Maurerova testu J. S. Coron [2] a poté navrhl i geniální zm╪nu testovací funkce [3]. Nov∞ test tak oproti d²ív╪jτímu m╪²í entropii p²ímo a p²esn╪ji. Pro vás, kte²í byste jej cht╪li p²ímo pouºít, jej dále popíτeme. Test se t∞ká stacionárních zdrojà s koneƒnou pam╪tí. P²esné definice a dàkazy tvrzení màºete nalézt v uvedené literatu²e. "Stacionární" znamená, ºe se v ƒase nem╪ní charakteristiky zdroje (nap²íklad na pohyb myτi nemá vliv to, zda je m╪²en v úter∞, nebo ve ƒtvrtek), a koneƒná pam╪£ (M) znamená, ºe n-t∞ v∞stup zdroje závisí maximáln╪ jen na koneƒném poƒtu (M) p²edchozích v∞stupà - nap²íklad poloha myτi v daném okamºiku závisí maximáln╪ na tom, kde byla p²ed sekundou, ale uº ne na tom, kde byla p²ed deseti sekundami.
V∞poƒet entropie
Poj╘me tedy k v∞poƒtu entropie S podle Maurerova-Coronova (dále jen M-C) testu. Nejprve si zvolíme t²i parametry - konstanty L, Q a K. Testovanou posloupnost N bità si dále rozd╪líme na Q + K nep²ekr∞vajících se L-tic bità b1, ..., bK+Q, kde bi je i-t∞ blok o L bitech a N = (Q + K)*L.
Parametr L by m╪l b∞t volen v rozmezí {6, ..., 16}, Q by m╪lo b∞t co nejv╪tτí, minimáln╪ ovτem 10*2L a K alespoσ 1000*2L. Jestliºe nap². zvolíme L = 8, zpracováváme posloupnost po bajtech.
Test má dv╪ fáze - inicializaƒní a v∞poƒetní. V inicializaƒní fázi nejprve naplníme tabulku T[0] ... T[2L -1] indexy prvních Q blokà tak, ºe pro i = 1, ..., Q postupn╪ definujeme T[bi] = i. Jin∞mi slovy: prvních Q blokà pouºijeme na to, abychom naplnili tabulku T. Hodnota T[blok] je místo, kde se naposledy objevil L-bitov∞ blok s hodnotou "blok". Q by m╪lo b∞t tak velké, aby se v inicializaƒní fázi korektn╪ naplnila tabulka T, tj. aby se v prvních Q blocích posloupnosti alespoσ jednou objevil kaºd∞ L-bitov∞ blok.
Hodnotu S urƒíme ve v∞poƒetní fázi podle vzorce na obrázku 3. Hodnota, kterou obdrºíme, je rovna entropii L-bitového bloku. Chceme-li zjistit entropii zdroje na jeden emitovan∞ bit, postaƒí obdrºenou hodnotu S vyd╪lit poƒtem bità bloku L - zdroj poskytuje neurƒitost H = S/L na jeden bit. Pokud se nad vzorcem zamyslíme, zjistíme, ºe je to vlastn╪ pràm╪rná hodnota jakési funkce g, aplikované na vzdálenost mezi totoºn∞mi L-bitov∞mi bloky v dané posloupnosti. P²itom pràm╪r se poƒítá p²es vτechny bloky v posloupnosti.
Genialita funkce g je v tom, ºe uvedenou vzdálenost blokà "p²em╪σuje" na entropii a navíc v∞poƒet hodnoty S je velmi jednoduch∞. Coron dokázal, ºe S z teoretického hlediska vyjad²uje hodnotu entropie p²esn╪ - navíc známe její statistické rozd╪lení. Umíme tedy entropii zdroje nejen vypoƒítat, ale urƒit i tzv. intervaly spolehlivosti, v nichº se nam╪²ené hodnoty S mohou pohybovat, má-li mít zdroj maximální entropii.
Hodnocení v∞sledkà
Kdyº pouºijeme M-C statistick∞ test na zkoumanou posloupnost, obdrºíme jednu jedinou hodnotu - tzv. statistiku S. Tato statistika je ve st²ední hodnot╪ rovna p²ímo entropii L-bitového bloku zkoumaného zdroje, ale zároveσ je to náhodná veliƒina, která má pravd╪podobnostní chování. A tak, i kdyº má zdroj dokonalou entropii (nap²íklad S = 8 na bajt), hodnoty S nam╪²ené na konkrétních posloupnostech se mohou pohybovat v urƒit∞ch intervalech kolem této dokonalé entropie. Tyto intervaly spolehlivosti (IS) umíme vypoƒítat, nebo£ S màºeme aproximovat normálním rozd╪lením, jehoº parametry naposledy zp²esnil práv╪ J. S. Coron [3].
K v∞poƒtu IS si nejprve stanovíme pravd╪podobnost r, ºe M-C testem vy²adíme n╪jakou posloupnost jako τpatnou (nemající maximální entropii), p²estoºe byla emitována skuteƒn╪ náhodn∞m zdrojem; b╪ºn╪ se volí r = 0,01 nebo r = 0,001. Pokud vypoƒtená hodnota S padne do uvedeného intervalu spolehlivosti, p²ijmeme hypotézu, ºe daná posloupnost má maximální entropii. Pokud S padne mimo n╪j, hypotézu zamítneme. V tom p²ípad╪ ji ale zamítneme správn╪, nebo£ tak ƒiníme s pravd╪podobností 1 - r, tj. tém╪² s jistotou. Pro ob╪ obvykle volené hodnoty r jsou p²ísluτné IS uvedeny v tabulce 1, stejn╪ jako obecn∞ vzorec.
Pokud tedy nap²íklad pro L = 8 obdrºíme S = 7,995, màºeme p²ijmout hypotézu, ºe se jedná o náhodn∞ zdroj s maximální entropií. Obdrºíme-li S = 4,002, hypotézu odmítneme, ale pokud bylo zdrojov∞ch dat velké mnoºství, màºeme uƒinit záv╪r, ºe kaºd∞ch 8 bità produkované posloupnosti obsahuje v pràm╪ru cca 4 bity neurƒitosti.
Pro ilustraci pouºitelnosti a schopností M-C testu jsme ud╪lali n╪kolik experimentà, jejichº v∞sledky uvádí tabulka 2. Samoz²ejm╪ je vºdy lepτí data testovat s v╪tτím rozliτením testu (p²i L = 16 je test mnohem p²esn╪jτí neº p²i L = 8), ale p²ipomeσme, ºe pro L = 16 test vyºaduje minimáln╪ 65 MB zdrojov∞ch dat, zatímco pro L = 8 staƒí jen 256 KB.
V prvních ƒty²ech experimentech jsme pouºili krátké texty, v pátém jeden dlouh∞ text. P²esto na nich test nefunguje ani zdaleka tak dob²e jako b╪ºn╪ dostupn∞ komprimaƒní program WinZip. Proƒ? Text totiº není pro M-C test vhodn∞. Text má hluboké závislosti, které zakladatel teorie informace C. E. Shannon ve sv∞ch ran∞ch pracích odhadoval (v angliƒtin╪) i p²i zjednoduτeném modelu minimáln╪ na p╪t znakà (jin∞mi slovy, v∞skyt písmene ƒitelného textu závisí aº na p╪ti p²edchozích písmenech). Museli bychom proto m╪²it entropii pro L = 5*8 = 40 bità, coº by vyºadovalo text o délce p²es 1000*240 znakà, tj. 1000 terabajtà. I tak bychom ale nezaregistrovali takové zákonitosti a opakování textu, jaké zachytí i b╪ºn∞ komprimaƒní program. Jeho "okno" totiº b∞vá nikoli p╪t, ale aº 8000 znakà.
Z experimentà 6 aº 8 je vid╪t, ºe L = 16 poskytuje p²esn╪jτí m╪²ení neº L = 8, a M-C test se blíºí v∞sledkàm WinZipu. Je to vícemén╪ náhodn∞ v∞sledek, protoºe uvedené formáty vlastní zdroj dat samy zásadn╪ upravují a p²etvá²ejí ve velmi velk∞ch blocích, takºe se jedná o zdroje dat znaƒn╪ um╪lé. Zjiτ£ovat u nich míru entropie by vyºadovalo studovat jejich systém kódování vstupních dat do v∞sledného formátu a odliτit skuteƒné vstupy od p²ídavn∞ch rámcà nebo formátovacích sekvencí. M╪²it u nich entropii M-C testem je proto nesmyslné.
V dalτích dvou experimentech jsme pro zajímavost zm╪²ili entropii pohybu myτi ze vzorku jejích poloh, po²ízen∞ch asi za 10 sekund (experiment 9), pokud jsme jí zám╪rn╪ pohybovali, a za jednu hodinu b╪ºné práce u PC (experiment 10), tj. vƒetn╪ doby, kdy se pouºívá více klávesnice a obƒas myτ, tj. kdy se v╪tτinu ƒasu nepohybuje. WinZip je zde lepτí, protoºe poloha myτi se zapisuje prost²ednictvím 32 bità, které M-C test s L = 8 a 16 nemàºe tak dob²e vyhodnotit.
Následující experimenty uº jdou M-C testu "k duhu". Abychom mohli vyhodnotit úƒinnost testu na velkém mnoºství dat, zvolili jsme zdroj dat s entropií 1,000000, tj. zcela náhodn∞ zdroj dat, poté binární zdroj s entropií 0,937500 na bit (15 bità ze 16 je náhodn∞ch, poslední bit je dopoƒítán jako paritní) a potom binární zdroj s entropií 0,875000 na bit (14 bità z 16 je náhodn∞ch, 15. bit je paritní bit za p²edchozí liché bity a 16. bit je paritní za p²edchozí sudé bity). Na t╪chto souborech WinZip zcela odmítl komprimovat, nebo£ je povaºoval za náhodné a nedosáhl ºádné komprimace. To by bylo v po²ádku u skuteƒn╪ náhodn∞ch souborà v experimentech 11 a 14, ale ne uº u ostatních, kde m╪l komprimovat na cca 93 % a 87 %. WinZip tam ale neodhalil ºádnou zákonitost, zatímco M-C test zapracoval fantasticky p²esn╪. T²eba v experimentech 14 aº 16 jím zjiτt╪né entropie 1,000000, 0,937511 a 0,875008 jsou aº neuv╪²iteln╪ blízko skuteƒn∞m entropiím m╪²en∞ch zdrojà. Tyto v∞sledky také ukazují, ºe na p²irozen∞ch náhodn∞ch zdrojích je M-C test velmi p²esn∞, a ƒím menτí pam╪£ zdroj má (nejlépe kdyº následné hodnoty jsou zcela nezávislé), tím je p²esn╪jτí.
Dále se zde ukazuje dalτí moºné pouºití M-C testu. Pokud data mají n╪jakou závislost v okn╪ délky N bità, M-C test to nezjistí pro parametr L < N, ale p²i L = N a v╪tτí ano (srv. testy 11 aº 16 pro L = 8 a L = 16). Jestliºe máme podez²ení, ºe p²edloºená data takovou zákonitost skr∞vají, lze ji odhalit provedením vτech testà pro L = 4, 5, 6, ..., N, N+1, ... Pokud obdrºené hodnoty S budou vykazovat v bod╪ L = N zásadní zlom, máme uº jistotu, ºe N-bitové vzorky n╪jakou neznámou zákonitost obsahují, a màºeme se pokusit ji odhalit. To je dalτí v∞sledek, kter∞ je hodnotn∞ sám o sob╪.
Trocha filozofie
Maureràv-Coronàv test je úƒinn∞ na testy fyzikálních a sv∞m charakterem p²írodních (originálních) zdrojà informace. Není vhodn∞ na m╪²ení entropie um╪l∞ch generátorà, nap²íklad kongruentních nebo kryptografick∞ch posloupností. Vysv╪tlíme si to na p²íkladu. M╪jme t²eba zdroj, kter∞ má entropii 0,5 na jeden bit v∞stupu. Dále uvaºujme, ºe máme tajnou substituƒní tabulku (8 bità na 8 bità), kterou aplikujeme na kaºd∞ bajt originální posloupnosti. Pokud pouºijeme M-C test s délkou bloku L = 8, pak entropie pàvodní i modifikované posloupnosti budou naprosto totoºné!
Sebetajn╪jτí substituce v∞sledek neovlivní, nebo£ test nezajímají konkrétní hodnoty znakà, ale jejich vztahy, ale ty se substitucí nem╪ní. Kdybychom pouºili 128bitovou substituci (nap². blokovou τifru), museli bychom u M-C testu volit také 128bitové bloky (tj. L = 128), abychom její vliv eliminovali. M-C test by v tomto p²ípad╪ vyºadoval zpracování 1000*2128 blokà, coº je ale v∞poƒetn╪ nezvládnutelné. Jin∞mi slovy, pokud v∞stupní posloupnost nemá dostateƒnou entropii, nemá cenu ji um╪le doupravovat a pak m╪²it entropii upravené posloupnosti M-C testem. Je ale moºné volit obrácen∞ postup. Ze zdroje, kter∞ má M-C testem zjiτt╪nou urƒitou entropii, nejprve generujeme posloupnost, aº dosáhneme poºadované entropie, a teprve poté tuto posloupnost màºeme upravovat, abychom získanou entropii vyuºili.
Záv╪r
Maureràv-Coronàv test je univerzální test náhodnosti, kter∞ je schopen detekovat τirokou τkálu statistick∞ch defektà. Na jejich odhalení není pak nutné pouºívat dalτí speciální statistické testy. Krom╪ toho test p²ímo poskytuje ƒíseln∞ odhad entropie daného zdroje. Màºe b∞t vyuºit k m╪²ení entropie p²irozen∞ch zdrojà, kde je nutná záruka kvality nebo znalost míry jejich náhodnosti, nehodí se ale k testování um╪l∞ch zdrojà ani tam, kde jsou tyto zdroje um╪le upravovány.
Vlastimil Klíma (v.klima@decros.cz)
Literatura
[1] Maurer, U., "An Universal Statistical Test for Random Bit Generators", Proceedings of CRYPTO∩90, Lecture Notes in Computer Science, pp. 409 - 420, Springer-Verlag, 1990.
[2] Coron, J. S., Naccache, D., "An Accurate Evaluation of Maurer's Universal Test", Proceedings of SAC'98, Lecture Notes in Computer Science, Springer-Verlag, 1998.
[3] Coron, J. S., "On the Security of Random Sources", Public Key Cryptography, Lecture Notes in Computer Science, vol. 1560, pp. 29 - 42, Springer-Verlag, 1999
[4] Klíma, V., "Aº nás podepíτe poƒítaƒ", Chip 5/99, str. 36 - 39.
