Důležité upozornění!

Policie České republiky se zajímá o IP-adresy osob, které komentují tento blog. Ve vlastním zájmu zde proto nic nepopírejte, nezpochybňujte, neschvalujte, neospravedlňujte, nikoho a nic nehanobte, nepodporujte a nepropagujte, a pokud se přesto rozhodnete komentář přidat, pak se, prosím, ničemu nedivte.

Náhoda a pseudonáhoda

K diskusi na Jiném právu bych si dovolil přičinit stručnou vysvětlující poznámku.

V informatice je zvykem rozlišovat dva druhy náhodných funkcí (generátorů):

Skutečný generátor náhodných čísel (true RNG) vytváří výstupní sekvenci náhodných veličin, jež splňují statistické podmínky nahodilosti, avšak neumíme ji rekonstruovat, což znamená, že ani ze znalosti libovolně dlouhé sekvence ni až ni+k, kde k ≥ 0, nejsme schopni zjistit žádné jiné nj pro j < i ani pro j > i + k.

Toto chování je žádoucí zejména v kryptografických aplikacích, a moderní procesory, např. Intel řady Ivy Bridge a vyšší, mají hardwarovou podporu takového generátoru vestavěnu přímo na chipu.

Fysikální provedení RNG může být různé, tradiční řešení je vzít vzorek radioaktivního materiálu s dlouhým poločasem rozpadu a sledovat jeho radiaci, nověji se, pokud mne neplete paměť, používá měření tepelného šumu na přechodu Zenerovy nebo tunelové diody.

Proč takový generátor potřebují kryptologové, je nasnadě: útočník nemá žádnou možnost, jak reprodukovat proces vytvoření pomocí RNG vygenerovaného privátního klíče.

Naproti tomu u generátoru pseudonáhodných čísel (PRNG) vyžadujeme, aby jeho výstup splňoval pokud možno stejné statistické předpoklady jako RNG, avšak zároveň aby výstupní sekvence byla dokonale reprodukovatelná, tj. aby určitý vnitřní stav generátoru Pi (jenž není zaměnitelný s výstupem ni) určoval všechny následující stavy Pi+1, Pi+2, …

Generátory pseudonáhodných čísel se neřeší fysikálně, ale jako mathematická funkce, která ze stavu Pi vytvoří jednoznačně výstup ni a následující stav Pi+1. Jednou z nejjednodušších možností je lineární kongruentní generátor (LCG), dnes se ale spíše dává přednost jiným algorithmům s lepšími statistickými vlastnostmi výstupu (např. Mersenne twister).

Použití PRNG v kryptografii je, minimálně pro generování privátních klíčů, nebezpečné, protože není vyloučeno, že útočník z dostatečně dlouhé výstupní sekvence ni až ni+k, kde k > 0, rekonstruuje stav generátoru Pi+k a tím i všechny budoucí stavy Pi+k+1, Pi+k+2, …

Existují však aplikace, kdy nám toto risiko nevadí a kdy naopak chceme, aby byla sekvence dokonale reprodukovatelná, abychom předešli obvinění, že jsme při jejím vytváření fixlovali.

Mezi takové případy patří i výběr podpisových archů ke kontrole registrujících se kandidátů. Algorithmus by měl být publikován předem, a aby se zabránilo možnosti účelového uspořádání souboru kandidátem, který by si sám spočítal, které z jeho archů se budou ověřovat, měl by mít jako další vstup dodatečnou informaci, která je ministerstvem neovlivnitelná a bude známa až poté, co kandidáti své archy odevzdají.

Není třeba nic komplikovaného, k zamezení takového risika stačí několik málo bitů entropie. Typickým příkladem je ciferný součet denního bursovního indexu, ale myslitelné jsou i jiné varianty, ještě méně ovlivnitelné: třeba počet v tento den narozených dětí nebo počet branek padlých v posledním fotbalovém kole (paranoici mohou místo fotbalu zvolit koše v basketbalu).

Ministerstvo vnitra udělalo to nejhorší, co udělat mohlo: sice algorithmus PRNG nezveřejnilo předem, ale žádný prvek náhody do něj nezařadilo, takže kdokoli se o něm včas dozvěděl, mohl své podpisové archy očíslovat tak, aby se do kontrolních vzorků dostaly jen ty nejlepší kusy, a navíc se jím při výběru patrně ani neřídilo.

Celkově to začíná působit dojmem, že Česká pošta, Lidové noviny a MF Dnes nejsou jediným, kdo dává v této kampani Janu Fischerovi slevu a kdo se naopak snaží některé další adepty osolit.
Kategorie: Volby
Počet zobrazení: 4592

Komentáře   

0 # Anonymní 2012-11-28 15:09
My starší si pamatujeme na večerníčky se Špěpánkou Haničincovou a jejím papouškem Lórinkou. Taková Lórinka by vytahovala určitě sčítací archy nepodjatě, pouze za oříšek, což by vyšlo MV levněji než si držet IT oddělení :-)
T. Moláček
0 # Tomáš Pecina 2012-11-28 15:17
Příliš velká spotřeba oříšků a v důsledku přejedení se jimi i Lórinek: stačilo by, kdyby vytáhla seed. I když, na druhou stranu, tradice "karlovarských losovaček" varuje…
0 # Mormegil 2012-11-28 15:21
Dovolil bych si drobně poopravit: V kryptografii samozřejmě PRNG používáme a používat chceme, jen ne ke generování klíčů, soli atp., k tomu je opravdu vhodné použít skutečné RNG (ovšem o konkrétním účelu nepíšete). PRNG je totiž v principu jen jiný název pro proudovou šifru (resp. její základní součást) – prvek, do kterého na začátku vložím trochu entropie (tajný klíč) a ona generuje (prakticky) libovolně dlouhý proud bitů, který mohu použít jako klíč pro one-time pad. Tento proud pochopitelně musí být přesně reprodukovatelný se znalostí původního klíče (seedu). Pochopitelně vyžadujeme, aby útočník nebyl prakticky schopen z předchozího výstupu odhadnut výstup následující (s nezanedbatelnou pravděpodobností), to ale není v žádném rozporu s reprodukovatelností (ta předpokládá znalost klíče/seedu).
0 # Tomáš Pecina 2012-11-28 15:27
Opravil jsem, díky, nicméně proudová šifra není PRNG, protože na rozdíl od něj nemusí splňovat téměř žádné statistické předpoklady. Jestliže je pravděpodobnost, že po dvou nulách v bitstreamu následuje jednička, dvakrát nižší, než že následuje nula, vůbec to nevadí, kdežto PRNG s takovými vlastnostmi bychom mohli rovnou zahodit.
0 # Mormegil 2012-11-28 16:22
To určitě vadí, šifru s takovými vlastnostmi bychom mohli rovnou zahodit. Proudová šifra (resp. „kryptograficky bezpečný PRNG“) je silnější konstrukce než PRNG – každá proudová šifra musí být PRNG, zatímco ne každý PRNG je použitelný jako proudová šifra (příkladem je třeba ten LCG). Abychom proudovou šifru považovali za bezpečnou, musí se jednat o nepředvídatelný PRNG, což znamená, že nesmí existovat praktický algoritmus A a nějaké i, pro který by pravděpodobnost (vůči náhodně vybranému klíči/seedu), že by se výstup algoritmu A, který jako vstup dostane prvních i bitů výstupu PRNG, rovnal i+1. bitu výstupu PRNG, byla větší než 1/2 + nějaké nezanedbatelné ε. V případě, že by o PRNG platila taková jednoduchá poučka, bylo by ta pravděpodobnost rozhodně vyšší. (PRNG bude předvídatelný dokonce i v případě, že jediné, co víme, je, že XOR všech bitů celého výstupu (celé periody) je roven nule – jsme totiž schopni předvídat poslední bit na základě všech předchozích a už to se nám nelíbí.)
0 # Tomáš Pecina 2012-11-28 16:27
Nemáte pravdu, protože zaměňujete dvě různá kriteria. Na PRNG se kladou statistické požadavky, na šifru kryptografické, které jsou sice daleko silnější, ale nejsou nadmnožinou těch statistických.
0 # Tomáš Pecina 2012-11-28 16:31
K tomu příkladu: hovořím o vztahu výstupních bitů k sobě navzájem v posloupnosti, nikoli jejich vztahu ke vstupu/stavu.
0 # Mormegil 2012-11-28 16:46
Já vám snad rozumím, vy mně patrně ne. :-) O žádném vstupu/stavu nehovořím, bavíme se výhradně o black-box testování té proudové šifry/toho PRNG.

Ve vašem konkrétním případě: pokud platí, že po dvou nulách ve výstupu je dvakrát pravděpodobnější jednička než nula, pak algoritmus A vypadá takto: pokud dva poslední dodané bity výstupu PRNG jsou nula, tipni jedničku, jinak tipni náhodně. Takový algoritmus bude mít pravděpodobnost úspěchu uhádnutí bitu následujícího po dvou nulách ve výstupu PRNG 2/3 = 1/2 + 1/6, přičemž 1/6 rozhodně není zanedbatelná výhoda.

Pokud zkonstruujete jakýkoli statistický test, kterým budete schopen rozlišit výstup toho PRNG od doopravdy náhodného proudu bitů, není ten PRNG kryptograficky bezpečný.
0 # Tomáš Pecina 2012-11-28 17:02
Nějak si nerozumíme. Příklad: Sestrojme proudovou šifru C' tak, že vezmeme kvalitní šifru C (klidně one-time pad) a nahraďme každou nulu sekvencí 00 a každou jedničku sekvencí 11. Taková proudová šifra je kryptograficky bezpečná, ale jako PRNG nepoužitelná.
0 # Mormegil 2012-11-28 18:14
Tak teď už si asi opravdu nerozumíme. One-time pad není proudová šifra a vaší konstrukci nerozumím. Mějme keystream generovaný nějakým PRNG z proudové šifry, dejme tomu RC4. Tento generátor upravíme popsaným způsobem. Vy z nějakého důvodu tvrdíte, že výsledek je bezpečná proudová šifra. Inu, není; resp. nesplňuje běžné požadavky, které jsou na bezpečnost proudových šifer (potažmo PRNG) kladeny (což nutně neznamená, že existuje nějaký triviální útok, jak z šifrového textu odvodit text otevřený). Vaše konstrukce není sémanticky bezpečná neboli není IND-CPA: útočník si nechá zašifrovat zprávy 00 a 01; u první zprávy dostane jako šifrový text vždy dva shodné bity, u druhé zprávy vždy dva různé bity, tím dokáže vždy (s výhodou = 1) rozpoznat, která z obou zpráv byla zašifrována.
0 # Tomáš Pecina 2012-11-28 18:19
Nekonečný one-time pad je použitelný jako proudová šifra.

Podstatu mé konstrukce jste nicméně nepochopil, útočník nic takového, co píšete, nedostane.
0 # Tomáš Pecina 2012-11-28 23:03
Myslím, že nedorozumění je v chápání pojmu proudová šifra. Pokud byste postuloval požadavek, že proudová šifra musí být symetrická (theoretická p.š. nemusí, praktická/technická samozřejmě symetrická je), pak byste musel odmítnout i mou počáteční konstrukci, protože p.š., která má mnou popsané vlastnosti, nemůže fungovat: nebyla by schopna pojmout plaintext. A ostatně by byla nemožná i vaše šifra s posledním bitem nenesoucím informaci.
0 # v6ak 2012-11-28 23:11
Mormegil: Takže Franta vezme text a zašifruje to kvalitní blokovou šifrou. To bude splňovat základní požadavky na bezpečnost proudových šiifer. Já, aniž bych znal bližší podrobnosti o plaintextu, vezmu jeho ciphertext a aplikuju na binární podobu zmíněnou funkci (_:String).flatMap(x => ""+x+x). (Samozřejmě String zde není v reálném světě praktický, ale to teď nevadí.) A teď to najednou přestává splňovat požadavky na bezpečnost? (Předpokládejme, že jsem nechtěl šifrovathttp://paragraphos.pecina.cz/2012/11/nahoda-pseudonahoda.html.)

Nebo analogicky: zašifruju text bezpečnou proudovou šifrou. Pustím to po drátě, kde se použije nějaké kódování bitů, třeba zmíněné (_:String).flatMap(x => ""+x+x). Dostává tímto kódováním útočník nějakou výhodu?

Z principu ne. Pokud by dostal nějakou výhodu (tzn. šifra by potom nebyla bezpečná), určitě to útočník může provést i sám bez jakýchkoli dalších znalostí. To by ale znamenalo, že už původní šifra nebyla bezpečná. Což je ale spor s předpokladem.
0 # Mormegil 2012-11-29 10:35
Nejprve jsem se chystal v6ak odbýt tím, že nepochopil, že se bavíme o zdvojování keystreamu, nikoli šifrového textu. Pak mě ovšem napadlo, že i vy možná mluvíte o zdvojování výsledného šifrového textu. To ale mluvíte o něčem úplně jiném než já v původním příspěvku. Proudová šifra je PRNG+XOR. Ano, pokud si na výstup takové proudové šifry ještě přidáte nějaké zdvojování, nebude to vypadat náhodně, ano, nevznikne tím žádná díra, ale 1. nechápu, proč byste to dělal, 2. je to proudová šifra + váš bazmek navrch, takže nevím, proč to označovat termínem „proudová šifra“, ale to je pochopitelně „jen“ otázka terminologie. Každopádně je to irelevantní, tou podstatnou informací z mého příspěvku bylo, že _pseudonáhodná_ čísla jsou v kryptografii používána naprosto běžně jako generátor keystreamu v proudové šifře, přičemž musí splňovat _všechny_ statistické testy náhodnosti a ještě víc (tedy ne každý PRNG takto lze použít – třeba ten zmiňovaný Mersenne twister bez úprav použít nemůžete).

A tím bych to ze své strany asi tak uzavřel. :-)
0 # Tomáš Pecina 2012-11-29 12:50
A já naopak souhlasím, že u symetrické p. š. se statistická slabost použitého PRNG vždy projeví oslabením kryptografické bezpečnosti šifry. I když jen theoreticky.
0 # David Schmidt 2012-11-28 15:27
Z toho co píšete, vyplývá, že je to na stejno, jako kdyby ministersvo kontrolovalo náhodně např. "každý desátý sčítací list", přičemž tato informace mohla být známa některým kandidátům ještě před registrací, nebo desítka byla zvolena, protože nejlépe sedí opět preferovanému kandidátovi. Za těchto okolností, pokud ministerstvo nedoloží, jak dospělo ke "svému" vstupnímu klíči, je otázka, zda jednoduše nezaregistrovat všechny , kdo si za takového stavu věcí budou stěžovat a u nichž přitom dosažení hranice není zjevně vyloučeno tím, že dodali méně podpisů. Právním důvodem by byla zmatečnost postupu ministerstva, které nepostupovalo náhodně (důkazní břemeno je na ministerstvu) a argument, že není jiný právní prostředek, jak zjednat nápravu (lze jen zavázat k registraci, zamítnout, tedy pokud nebudeme uvažovat o nepřezkoumatelnosti :)) Tím spíše, pokud přiznané oprávnění je nemá povahu finálního benefitu, nýbrž toliko vstupu do svobodné soutěže politických sil.
0 # Tomáš Pecina 2012-11-28 15:28
Zatím se situace jeví tak, že přidanou entropií je předem nepředvídatelná idiocie implementujícího programátora :-)
0 # David Schmidt 2012-11-28 15:39
Ne vážně. Já bych dokonce zaujal názor, že pokud ministerstvo nevtělilo prokázání náhodného postupu do odůvodnění, rozhodnutí je tím zmatečné a nelze jej dovysvětlovávat u soudu, což v tomto typu řízení znamená registraci kandidáta, neboť nelze vrátit k dalšímu řízení, ani zamítnout (element nezvratnosti + pouhé registrace, ne finálního výsledku).
0 # Anonymní 2012-11-28 19:51
Pro nastartování algorithmu použilo ministerstvo počet petičních archů dané petice. Ano, pokud tato informace unikla, mohl ji někdo zneužít. To je jistě nevýhoda. Dokazovat, že nastartování přes true RNG (třeba přes termický šum) není zmanipulováno ovšem také není jednoduché. (Absence verifikace podpisů dává daleko jednodušší možnost zneužití.)
Napsal jste to pěkně, ale nic neschvaluji, nepopírám a nehanobím-:)
0 # Michal z Michle 2012-11-29 14:04
Pro výběr počátečního seedu by šla v tomto případě využít libovolná informace, která je veřejně dostupná a nelze ji jednoduše ovlivnit - průměrná teplota v Klementinu den po uzávěrce, konečná cena burzovního indexu PX, viz geohashing - wiki.xkcd.com/geohashing/Main_Page
0 # Tomáš Pecina 2012-11-29 14:09
Přesně tak. Podle mě by mělo bohatě stačit nějakých dvanáct až šestnáct bitů, a mechanismus by měl být navržen tak, aby neumožňoval fixlování s duplicitami: např. pokud by se nikdy nemohlo stát, že by byl při daném N zkontrolován zároveň arch 548 a 3984, kandidát by tam mohl vložit dva archy s identickými záznamy.

To se všechno udělat dá, mathematické methody na to existují; jen je škoda, že v právu, jak víme, primitivní pavědy jako mathematika nejsou použitelné :-)

Komentovat články mohou pouze registrovaní uživatelé; prosím, zaregistrujte se (v pravém sloupci dole)