Hardwarový generátor náhodných čísel

Hardwarový generátor náhodných čísel (TRNG, anglicky true random number generator) je v informatice zařízení, které je připojeno k počítači (nebo je obsaženo přímo v procesoru)^[1] a které generuje náhodná čísla z fyzikálního procesu. Taková zařízení jsou často založena na mikroskopických jevech, které generují nízkoúrovňové, statisticky náhodné "šumové" signály, například z tepelného šumu či fotoelektrického jevu nebo jiných kvantových jevů. Tyto procesy jsou, teoreticky, zcela nepředvídatelné a teoretická potvrzení nepředvídatelnosti jsou předmětem zkušebního testu. Kvantově založený hardwarový generátor náhodných čísel se typicky skládá z převodníku převádějící některé aspekty fyzikálních jevů na elektrický signál, zesilovače a dalších elektronických obvodů, aby byl výstup snímače přenesen do makroskopické oblasti a nějaký A/D převodník pro konverzi analogového výstupu do digitálního formy (řada binárních čísel 0 a 1). Tím, že opakujeme vzorky náhodně různého signálu, se získá řada náhodných čísel.

Hardwarové generátory náhodných čísel se liší od generátorů pseudonáhodných čísel, které se běžné používají ve většině počítačů. Tyto pseudogenerátory náhodných čísel používají deterministický algoritmus pro výrobu číselné posloupnosti. Proto nejsou vhodné pro kryptografické aplikace, jsou totiž náchylné k dešifrovacímu útoku. Takže ve vysokých bezpečnostních aplikací, jako jsou produkce náhodných klíčů pro vojenské a obchodní šifrovací systémy, se používají generátory hardwarově náhodné.

Hardwarové generátory náhodných čísel jsou často relativně pomalé a mohou produkovat (do jisté míry vždy produkují) zkreslené sekvence (tj. některé hodnoty jsou častější než ostatní), což vyžaduje použití debiasingu. Zdrojem nenáhodnosti generátoru (tedy i jeho slabosti) může být například pravidelné elektromagnetické záření (zdroj může být zabudován v zařízení, ale může pocházet i z elektromagnetického rušení) ovlivňující stavy.

Fyzikální jevy s kvantově-náhodnými vlastnostmi

Existují dva základní zdroje praktické kvantově mechanické fyzikální náhodnosti: kvantová mechanika na atomární nebo sub-atomární úrovni a tepelný šum (z nichž některé jsou kvantově mechanického původu). Kvantová mechanika předpovídá, že jsou některé fyzikální jevy, jako je například radioaktivní rozpad atomů, v zásadě náhodné, a proto je nemůžeme předvídat. (Pro diskuzi o empirickém ověření kvantové nepředvídatelnosti viz Bellovy testovací experimenty). A protože žijeme v konečné, nenulové teplotě, každý systém má nějaké náhodné změny svého stavu, například molekuly vzduchu jsou neustále od sebe náhodně odstrkovány. (Viz statistická mechanika) Tato náhodnost je také kvantový jev. (Viz fonon)

Protože výsledky kvantově-mechanické události nemohou být v zásadě předpovězeny, jsou jakýmsi "zlatým standardem" pro generování náhodných čísel. Mezi některé kvantové jevy používané pro generování náhodných čísel patří:

• výstřelový šum – kvantově mechanický zdroj šumu v elektronických obvodech
• radioaktivní rozpad zdroje záření, detekovaný Geigerovým počítačem připojeným k PC.
• fotony procházející polopropustným zrcadlem

Fyzikální jevy bez kvantově-náhodných vlastností

Tepelné jevy jsou jednodušeji detekovatelné.

• Tepelný šum z rezistoru, zesílený tak, aby se z něj stal zdroj náhodného napětí.
• Šum generovaný z lavinové diody nebo šum Zenerova průrazu z opačně zapojené Zenerovy diody (jedná se v podstatě o stejné jevy).
• Atmosférický šum, detekovaný rádiovým přijímačem, který je připojený k osobnímu počítači (i když hodně veliká část, jako třeba světelný šum, není správně termální šum, ale nejpravděpodobněji chaotický jev).

Další fyzikální jev, který je jednoduše měřitelný je zpoždění hodin.

V případě absence kvantových efektů nebo termálního šumu, mohou být použity jiné jevy, které mají tendenci být náhodné, ačkoli způsoby, které nejsou jednoduše charakterizovatelné zákony fyziky. Pokud několik takovýchto zdrojů pečlivě zkombinujeme (například Yarrow algoritmus nebo Fortuna CSPRNGs), můžeme získat dostatek entropie pro vytvoření kvalitního kryptografického klíče. Výhoda tohoto postupu je v principu hlavně v tom, že není zapotřebí speciálního hardwaru. Nevýhoda spočívá v tom, že dostatečně znalý útočník může tajně modifikovat software nebo jeho vstupy tak, že se podstatně sníží náhodnost výstupu.

Typicky používaný primární zdroj náhodnosti je přesné časování přerušení způsobené vstupem nebo výstupem mechanických zařízení, jako například klávesnice a disková jednotka nebo různé systémové čítače. Poslední přístup musí být implementován velmi pečlivě, protože může být předmětem útoku, pokud by nebyl. Například pokroková bezpečnost generátoru v jádru Linuxu 2.6.10 může být prolomena s časovou komplexností 2⁶⁴ nebo 2⁹⁶. Generátor náhodných čísel používaný pro kryptografické účely v prvních verzích internetového prohlížeče Netscape byl jistě zranitelný (a proto byl okamžitě vyměněn).

Jeden z přístupů v používání náhodnosti fyzikálních jevů je konvertování zdroje šumu do náhodné sekvence bitů v oddělených zařízeních, které jsou propojené s osobním počítačem pomocí vstupně/výstupních portů. Získaný šum je zesílen, filtrován a poté poslán přes vysokorychlostní napěťový komparátor, kde produkuje logický signál v náhodných intervalech. Částečně je takto generovaná náhodnost závislá na specifických detailech odděleného zařízení. Obzvláště je potřeba dávat pozor při zesilování slabého šumu, abychom nezískali zkreslený signál od šumu elektrické linky a nebo nechtěných broadcastů. Proto některé systémy používají konverzi do typu signálu RS-232, který je posílán přímo do sériového portu počítače. Software tedy vidí série logických hodnot. Více sofistikované systémy mohou formátovat hodnoty bitů ještě předtím, než je pošlou do počítače.

Další možností je posílat signál analogového šumu do A/D převodníku, jako je například audio vstup, který se nachází na většině moderních osobních počítačů. Takto vzniklý signál pak může být přímo zpracován softwarem. Často se stává, že digitalizace je zdrojem dalšího zkreslení, proto je důležité dávat na ní pozor a péči.

Další možností je použití vstupu digitální kamery, jako třeba webové kamery a zpracovávat makroskopické náhodné jevy. Skupina v Silicon Graphics snímala Lava lampy a z obrazu získávala náhodná čísla. Jeden z problémů je stanovit, jestli chaotické tvary, které lampa generuje, jsou skutečně náhodné. Dalšími náhodnými scénami by mohly být proudy vzduchu z ventilátorů nebo pravděpodobně snímaní bublinek z akvária s rybičkami (závislý na rybách). Digitalizovaný obraz sám o sobě obsahuje přidaný šum, daný digitální konverzí, avšak tento šum není považován za velmi náhodný.

Posun času

Existuje několik způsobů jak měřit a použít zpoždění (nebo zrychlení) hodin (anglicky clock drift) jako zdroj náhodnosti.

Firmware procesoru Intel 82802 (FWH) obsahuje hardware RNG, který používá dva volně běžící oscilátory, jeden rychlý a druhý pomalý. Zdroj termálního šumu je použit k modulování frekvence pomalého oscilátoru, který spouští měření rychlého oscilátoru.

Výstup je poté zpracován použitím Von Neumannova typu dekorelace. Výstupní frekvence tohoto generátoru je o něco menší než 100 000 bit/s. Tento čip byl jako příplatková komponenta rodiny chipsetů 840, které podporovala dřívější Intel sběrnice. V moderních počítačích se tento způsob generování náhodných čísel již nevyskytuje.

Všechny VIA C3 mikroprocesory již obsahují RNG hardware přímo na čipu procesoru od roku 2003. Místo používání tepelného šumu, se čistě náhodné bity generují pomocí použití čtyř různých volně běžících oscilátorů, které jsou designované tak, aby běžely na různých frekvencích.

Výstup dvou je zpracován přes XOR kontrol a ovládá nastavení třetího oscilátoru, jehož výstup časuje výstup čistých bitů čtvrtého oscilátoru. Miniaturní variace v teplotě, charakteristice silikonu a aktuálních elektrické kondice způsobuje průběžné změny rychlosti oscilátoru a to produkuje dostatečnou entropii pro výstupní bity. Abychom ještě více zajistili náhodnost, tak se na každém čipu nacházejí minimálně dva RNG generátory, každý je v rozdílném prostředí a jinak vyrotován v silikonu. Finální výstup je mix těchto dvou generátorů. Čistá výstupní rychlost je na úrovni desítek až stovek megabitů za sekundu. Uživatelův software může přistupovat k takto generovaným náhodným bitům pomocí nových neprivilegovaných instrukcí. 

Softwarová implementace, která využívá standardní hardware je v CryptoLib, což je kryptografická knihovna. Algoritmus se nazývá truerand. Většina moderních počítačů obsahuje dva oscilační krystaly, jeden pro hodiny reálného času a jeden primární jako hodiny pro CPU. Využívá se služba operačního systému, která nastaví alarm, který se vypne pomocí hodin reálného času. Jedna podrutina nastaví vypnutí alarmu po jednom tiku hodin (obvykle je to interval 1/60 sekundy). Další podrutina vstoupí do while smyčky a čeká na spuštění alarmu.

Jelikož se alarm pokaždé nespustí přesně stejně po uplynutí jednoho tiku, tak pak nejméně důležitý bit je vygenerován přibližně náhodně. Výhodou Truerand funkce je v tom, že není potřeba dalšího hardwaru, ale v multitaskingových systémech se musíme postarat o to, aby nenáhodné rozhraní mezi procesy nenarušilo náhodnost této funkce.

Vyrovnávání se se zkreslením

Proud bitů z těchto systémů je náchylný být zkreslený, s dominancí jedniček a nebo nul. Existují dvě cesty jak se vyrovnat se zkreslením. První způsob je designovaní RNG takových způsobem, aby se minimalizovalo zkreslení při samotné práci generátoru.

Druhá metoda, jak ladit generovaný bit stream, je použití low pass filteru pro doladění odchylky generátoru. Podle centrálního limitního teorému bude mít tendenci zpětnovazební smyčka být vyvážená po celý čas. Ultra vysoce rychlostní generátory náhodných čísel velmi často využívají tuto metodu. I přesto jsou náhodně vygenerovaná čísla nějakým způsobem zkreslená.

Software whitening

Druhý způsob jak se vypořádat se zkreslením je redukovat ho po až po vygenerování náhodných čísel (buď softwarem nebo hardwarem). I když použijeme hardware pro filtrování odchylek tak proud bitů bude pravděpodobně stále obsahovat zkreslení a korelace. Existuje několik metod jak redukovat zkreslení a korelaci, často nazýváme tyto metody jako „whitening“ algoritmus. Je to dáno analogii s problematikou produkování bílého šumu z korelovaného signálu.

Existuje způsob, dynamicko statický test, který kontroluje statistickou náhodnost v každém náhodném bloku dynamicky. Toto může být použitelný v krátkém čase, touto metodou lze zkontrolovat řádově 1 gigabyte za sekundu a více.

Pokud daný blok obsahuje pochybnou náhodnost, je automaticky z bitového proudu vyřazen. Tato metoda je požadována v návrhu ANSI (X9F1). John von Neumann vynalezl jednoduchý algoritmus jak zafixovat jednoduché zkreslení a snížit zkreslení. Vyžaduje to dva bity v jeden moment a na základě zpracování provede jednu ze tří možných operací: pokud dva bity jsou stejné, tak jsou smazány; ze sekvence 1, 0 se stává 1; ze sekvence 0, 1 se stává 0. Reprezentuje to padající hranu s 1 a vzestupnou hranu s 0.

Toto eliminuje jednoduché zkreslení a je to velice jednoduché na implementaci jak pro počítačového programátora, tak i pro digitální logiku. Tato metoda funguje nezávisle na tom, jak byly bity generovány. Ale i přesto to nemůže zaručit náhodnost svého výstupu.

Ale může to s vysokým počtem diskartovaných bitů transformovat zkreslený bitový proud na nezkreslený.

Další používanou technikou pro přiblížení se ideálnímu náhodnému proudu bitů je použít exkluzivní or s vysoce kvalitním kryptograficky bezpečným pseudonáhodným generátorem čísel jako je třeba Blum Blum Shrub nebo velmi silný stream cipher. Toto může velmi pomoci s dekorelací a digitálním zkreslením při zachování velmi nízké ceny; toto můžeme provést například pomocí hardwaru jako je třeba FPGA, který je mnohem rychlejší než kdybychom se to snažili dělat pomocí softwaru.

Podobná metoda, která redukuje zkreslení a vytváří téměř ideálně náhodný bitový proud je když vezmeme dva a více nekorelovaných velmi blízko náhodných bitových proudů a provedeme s nimi operaci XOR. 

Když pravděpodobnost výskytu nuly v bitovém proudu je 1/2 + e, kde e se nachází v rozmezí -1/2 <= e <= 1/2. Poté e je zkreslení bitového proudu. Pokud vememe dva nekorelované bitové proudy se zkreslením e a použijeme na ně operaci exkluzivní or, potom zkreslení výsledku je 2e². Toto může být opakováno s více bitovými streamy (souvisí Pilling-up lemma).

Některé návrhy aplikují kryptografický hash funkce jako třeba MD5, SHA-1 nebo RIPEMD-160 a nebo dokonce CRC funkci na celý bitový proud a nebo jeho část. Toto řešení je velmi atraktivní, částečně proto, že je o hodně rychlejší v porovnání s některými jinými metodami, ale velmi zde záleží na celkové kvalitě hash výstupu.

Mnoho fyzikálních jevů může generovat bity, které jsou velmi zkreslené, ale každý bit je nezávislý na ostatních. Geigerův čítač nebo polopropustné zrcadlo s detektorem fotonů mohou generovat bitový proud, který obsahuje většinou 0 (ticho nebo propuštění fotonu) s občasnou 1 (klik nebo odraz fotonu). Pokud každý bit je nezávislý na ostatních, tak Von Neumannova strategie generuje jedno náhodný, nezkreslený bit na výstup.

Whitening technika jako třeba Advanced Multi Level Strategy (AMLS) může extrahovat více výstupních bitů.

Použití vnitřních událostí počítače

Softwaroví inženýři bez skutečně reálného generátoru náhodných čísel se je pokoušejí vyvinout měřením fyzických událostí, které jsou k dispozici v softwaru. Například měřením doby mezi stiskem dvou tlačítek a poté se vezme nejméně důležitý bit, dva nebo tři. Podobné metody jsou dále měření plánování úloh, přerušení na síťové kartě, doba vystavení hlavičky harddisku na stopu a nebo nějaké další vnitřní události. Jeden z designů od Microsoftu obsahuje velmi dlouhý seznam takovýchto událostí (viz CSPRNG)).

Tato metoda je docela riskantní, protože když bude program využívat data z počítačově kontrolovaných událostí, tak chytrý útočník může být schopen predikovat kryptografický klíč. Další riziko je v tom, že uživatelsky generované události (jako například stisky kláves) mohou být sledovány útočníkem a nebo dokonce podvrženy, tak aby měl kontrolu nad náhodnými hodnotami a tím i nad celou kryptografií.

Avšak s dostatečnou mírou péče, může takto navržený systém být pro náhodné generování čísel v kryptografii bezpečný. Základem správného návrhu je udržovat si zásobník entropie náhodných čísel tak, aby se k nim nedostal útočník. Nové náhodně generované bity jsou neustále přidávány do zásobníku tak, aby útočník nemohl odhadnout jejich pozici.

Některé strategie obsahují:

• Pokud je požádáno o další náhodné číslo, tak všechny požadované bity je potřeba uvolnit ze zásobníku, pokud tam není dostatek bitů, tak je třeba počkat, než se doplní. Takto je navrženo zařízení /dev/random v Linuxu, které napsal Theodore Ts'o a které je používáno v mnoha unixových operačních systémech. Nabízí vysokou kvalitu náhodných čísel po takovou dobu dokud jsou k dispozici odhady z náhodného vstupu.

• Udržovat proud šifer s klíčem a inicializačním vektorem získaným ze zásobníku entropie. Jakmile je dostatečný počet bitů shromážděn, je potřeba změnit jak klíč tak inicializační vektor novými náhodnými hodnotami a snížit počet zbývajících hodnot v zásobníku.

Takto je to například uděláno v yarrow knihovně. Toto řešení umožňuje odolat některým útokům.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Hardware random number generator na anglické Wikipedii.

Související články

• Generátor náhodných čísel

Externí odkazy

• Obrázky, zvuky či videa k tématu hardwarový generátor náhodných čísel na Wikimedia Commons