Hardware generátor náhodných čísel - Hardware random number generator

Tato počítačová karta akcelerátoru TLS používá hardwarový generátor náhodných čísel ke generování kryptografických klíčů k šifrování dat odesílaných přes počítačové sítě.

Ve výpočtu , je hardwarový generátor náhodných čísel ( HRNG ), nebo platí generátor náhodných čísel ( trénink ) je zařízení, které generuje náhodná čísla z fyzikálního procesu , spíše než pomocí algoritmu . Taková zařízení jsou často založena na mikroskopických jevech, které generují nízkoúrovňové, statisticky náhodnéšumové “ signály, jako je tepelný šum , fotoelektrický efekt zahrnující rozdělovač paprsků a další kvantové jevy. Tyto stochastické procesy jsou teoreticky zcela nepředvídatelné, pokud je rovnice řídící tyto jevy neznámá nebo nevypočitatelná a tvrzení teorie o nepředvídatelnosti jsou předmětem experimentálního testu . To je v kontrastu s paradigmatem generování pseudonáhodných čísel běžně implementovaným v počítačových programech .

Hardwarový generátor náhodných čísel se obvykle skládá z převodníku převádějícího některý aspekt fyzických jevů na elektrický signál, zesilovače a dalších elektronických obvodů za účelem zvýšení amplitudy náhodných výkyvů na měřitelnou úroveň a určitého typu analogově-analogových digitální převodník pro převod výstupu na digitální číslo, často jednoduchá binární číslice 0 nebo 1. Opakovaným vzorkováním náhodně se měnícího signálu se získá řada náhodných čísel.

Hlavní aplikace pro elektronické hardwarové generátory náhodných čísel je v kryptografii , kde se používají ke generování náhodných kryptografických klíčů pro bezpečný přenos dat. Jsou široce používány v protokolech internetového šifrování, jako je TLS ( Transport Layer Security ).

Generátory náhodných čísel lze také sestavit z „náhodných“ makroskopických procesů pomocí zařízení, jako je překládání mincí , kostky , ruleta a loterijní automaty . Přítomnost nepředvídatelnosti v těchto jevech lze odůvodnit teorií nestabilních dynamických systémů a teorií chaosu . Přestože jsou makroskopické procesy v newtonovské mechanice deterministické , výstup dobře navrženého zařízení, jako je ruleta, nelze v praxi předvídat, protože závisí na citlivých mikro detailech počátečních podmínek každého použití.

Ačkoli kostky byly většinou používány v hazardních hrách a jako „randomizující“ prvky ve hrách (např. Hry na hraní rolí ), viktoriánský vědec Francis Galton popsal v roce 1890 způsob, jak pomocí kostek explicitně generovat náhodná čísla pro vědecké účely.

Hardwarové generátory náhodných čísel obecně produkují pouze omezený počet náhodných bitů za sekundu. Aby se zvýšila dostupná výstupní datová rychlost, často se používají ke generování „ osiva “ pro rychlejší kryptograficky bezpečný generátor pseudonáhodných čísel , který pak generuje pseudonáhodnou výstupní sekvenci při mnohem vyšší datové rychlosti.

Využití

V souvislosti s hazardními hrami byla nejprve zkoumána nepředvídatelná náhodná čísla a pro takové použití bylo nejprve vyvinuto mnoho randomizačních zařízení, jako jsou kostky , míchání hracích karet a ruleta . Správně vytvořená náhodná čísla jsou pro elektronické hazardní hry životně důležitá a způsoby jejich vytváření jsou někdy regulovány vládními herními komisemi.

Náhodná čísla se také používají pro účely nehazardních her, a to jak tam, kde je jejich použití matematicky důležité, jako je výběr vzorků pro průzkumy veřejného mínění , tak v situacích, kde je spravedlnost aproximována randomizací , jako jsou vojenské loterie a výběr porotců .

Kryptografie

Hlavní využití hardwarových generátorů náhodných čísel je v oblasti šifrování dat , například k vytváření náhodných kryptografických klíčů a nonces potřebných k šifrování a podepisování dat. Jsou bezpečnější alternativou k generátorům pseudonáhodných čísel (PRNG), softwarovým programům běžně používaným v počítačích ke generování „náhodných“ čísel. PRNG používají k produkci numerických sekvencí deterministický algoritmus . Ačkoli tyto pseudonáhodné sekvence procházejí náhodnými statistickými testy , díky znalosti algoritmu a podmínek použitých k jeho inicializaci, nazývaných „semeno“, lze výstup předpovědět. Protože posloupnost čísel vytvářených PRNG je v zásadě předvídatelná, data šifrovaná pseudonáhodnými čísly jsou potenciálně náchylná ke kryptoanalýze . Hardwarové generátory náhodných čísel vytvářejí sekvence čísel, u nichž se předpokládá, že nejsou předvídatelné, a proto při šifrování dat poskytují největší zabezpečení.

Brzká práce

Jedním z prvních způsobů, jak vytvářet náhodná čísla, byla variace stejných strojů, které se používaly ke hře keno nebo výběru čísel v loterii . Jednalo se o smíšené, očíslované ping-pongové míčky s vháněným vzduchem, možná kombinované s mechanickým mícháním, a používaly nějaký způsob pro odebírání míčků ze směšovací komory ( US patent 4 786 056 ). Tato metoda poskytuje v některých smyslech rozumné výsledky, ale náhodná čísla generovaná tímto způsobem jsou drahá. Tato metoda je ze své podstaty pomalá a pro většinu výpočetních aplikací je nepoužitelná.

Dne 29. dubna 1947 začala společnost RAND Corporation generovat náhodné číslice s „elektronickým ruletovým kolem“, skládajícím se ze zdroje pulzů s náhodnou frekvencí přibližně 100 000 pulzů za sekundu, bránou jednou za sekundu s pulsem konstantní frekvence a přiváděným do pětibitového binárního čítače . Douglas Aircraft sestrojil zařízení, které implementovalo návrh Cecila Hastinga (RAND P-113) na zdroj hluku (pravděpodobně dobře známé chování miniaturní plynové tyratronové trubice 6D4 , když je umístěno v magnetickém poli). Dvacet z 32 možných hodnot čítačů bylo mapováno na 10 desetinných míst a dalších 12 hodnot čítačů bylo vyřazeno.

Výsledky dlouhého běhu ze stroje RAND, filtrované a testované, byly převedeny do tabulky, která byla publikována v roce 1955 v knize A Million Random Digits with 100,000 Normal Deviates . Tabulka RAND byla významným průlomem v poskytování náhodných čísel, protože tak velká a pečlivě připravená tabulka nikdy předtím nebyla k dispozici. Byl to užitečný zdroj pro simulace, modelování a pro odvozování libovolných konstant v kryptografických algoritmech k prokázání, že konstanty nebyly vybrány zlomyslně. Blokové šifry Khufu a Khafre patří mezi aplikace, které používají tabulku RAND. Viz: Nic v mých číslech v rukávu .

Fyzikální jevy s náhodnými vlastnostmi

Kvantové náhodné vlastnosti

Existují dva základní zdroje praktické kvantově mechanické fyzikální nahodilosti: kvantová mechanika na atomové nebo subatomární úrovni a tepelný šum (z nichž některé jsou kvantově mechanického původu). Kvantová mechanika předpovídá, že určité fyzikální jevy, jako je jaderný rozpad atomů, jsou zásadně náhodné a nelze je v zásadě předvídat (diskuse o empirickém ověření kvantové nepředvídatelnosti viz Bell testovací experimenty ). A protože svět existuje při teplotě nad absolutní nulou , každý systém má ve svém stavu nějaké náhodné variace; například molekuly plynů tvořících vzduch se od sebe neustále náhodně odrážejí ( viz statistická mechanika .) Tato náhodnost je také kvantový jev ( viz fonon ).

Protože výsledek kvantově mechanických událostí nelze předpovědět ani v zásadě, jsou „ zlatým standardem “ generování náhodných čísel. Některé kvantové jevy používané pro generování náhodných čísel zahrnují:

Klasické náhodné vlastnosti

Tepelné jevy lze snadněji detekovat. Jsou poněkud náchylné k útoku snížením teploty systému, ačkoli většina systémů přestane fungovat při teplotách dostatečně nízkých, aby se hluk snížil dvakrát (např. ~ 150 K). Některé z použitých tepelných jevů zahrnují:

Při absenci kvantových efektů nebo tepelného šumu lze použít i jiné jevy, které bývají náhodné, i když způsoby, které nejsou snadno charakterizovány fyzikálními zákony. Když je pečlivě zkombinováno několik takových zdrojů (jako například v Yarrowově algoritmu nebo Fortuna CSPRNGs ), lze shromáždit dostatek entropie pro vytvoření kryptografických klíčů a nonces , i když obecně s omezenými sazbami. Výhodou je, že tento přístup v zásadě nepotřebuje žádný speciální hardware. Nevýhodou je, že dostatečně informovaný útočník může tajně upravovat software nebo jeho vstupy, čímž se možná podstatně sníží náhodnost výstupu. Primárním zdrojem náhodnosti, který se v takových přístupech obvykle používá, je přesné načasování přerušení způsobených mechanickými vstupními/výstupními zařízeními, jako jsou klávesnice a diskové jednotky , různé čítače systémových informací atd.

Tento poslední přístup musí být implementován opatrně a v opačném případě může být napaden. Například zabezpečení generátoru vpřed v jádře Linux 2.6.10 by mohlo být narušeno časovou složitostí 2 64 nebo 2 96 .

Drift hodin

Další proměnlivý fyzikální jev, který lze snadno měřit, je posun hodin. Existuje několik způsobů, jak měřit a používat drift hodin jako zdroj náhodnosti.

Intel 82802 Firmware Hub (FWH) čip obsahoval hardwarovou RNG pomocí dvou free running oscilátory, jeden rychlý a jeden pomalu. K modulaci frekvence pomalého oscilátoru se používá zdroj tepelného šumu (neobvyklý režimový šum ze dvou diod), který pak spouští měření rychlého oscilátoru. Tento výstup je poté odstraněn pomocí kroku dekorelace typu von Neumann (viz níže). Výstupní rychlost tohoto zařízení je o něco menší než 100 000 bitů/s. Tento čip byl volitelnou součástí rodiny čipových sad 840, které podporovaly dřívější sběrnici Intel. Není součástí moderních počítačů.

Všechny mikroprocesory VIA C3 obsahují hardwarový RNG na procesorovém čipu od roku 2003. Namísto použití tepelného šumu jsou surové bity generovány pomocí čtyř volně běžících oscilátorů, které jsou navrženy tak, aby běžely s různými rychlostmi. Výstup dvou je XORed pro řízení zkreslení na třetím oscilátoru, jehož výstup taktuje výstup čtvrtého oscilátoru, aby vytvořil surový bit. Menší výkyvy teploty, křemíkové charakteristiky a místní elektrické podmínky způsobují pokračující kolísání rychlosti oscilátoru a vytvářejí tak entropii surových bitů. Aby se dále zajistila náhodnost, ve skutečnosti jsou na každém čipu dvě takové RNG, každá umístěná v jiném prostředí a rotovaná na křemíku. Konečný výstup je kombinací těchto dvou generátorů. Rychlost surového výstupu je desítky až stovky megabitů za sekundu a bělená rychlost je několik megabitů za sekundu. Uživatelský software má přístup k generovanému náhodnému bitovému proudu pomocí nových neprivilegovaných instrukcí strojového jazyka.

Softwarová implementace související myšlenky na běžném hardwaru je součástí CryptoLib, knihovny kryptografických rutin. Algoritmus se nazývá truerand . Většina moderních počítačů má dva krystalové oscilátory, jeden pro hodiny reálného času a jeden pro primární hodiny CPU; truerand této skutečnosti využívá. Využívá službu operačního systému, která nastavuje alarm, běžící mimo hodiny reálného času. Jeden podprogram nastaví, aby se alarm spustil jedním tiknutím hodin (obvykle 1/60 sekundy). Další pak vstoupí na chvíli do smyčky čekající na spuštění alarmu. Protože se alarm nebude vždy spouštět přesně v jednom zatržítku, nejméně významné bity z počtu iterací smyčky, mezi nastavením alarmu a jeho spouštěním, se budou lišit náhodně, možná dost pro některá použití. Truerand nevyžaduje další hardware, ale ve víceúlohovém systému je třeba věnovat velkou pozornost tomu, aby nedocházelo k náhodnému rušení jinými procesy (např. Při pozastavení procesu sčítací smyčky, protože plánovač operačního systému spouští a zastavuje různé procesy ).

RDRANDOpcode vrátí hodnoty z palubní hardwarový generátor náhodných čísel. V procesorech Intel Ivy Bridge a AMD64 je přítomen od roku 2015.

Řešení podjatosti

Bitový tok z takových systémů je náchylný k předpětí, přičemž převažují buď 1 s, nebo 0 s. Existují dva přístupy k řešení zkreslení a dalších artefaktů. První je navrhnout RNG, aby se minimalizovalo zkreslení vlastní provozu generátoru. Jedna metoda, jak to napravit, přivádí zpět generovaný bitový proud filtrovaný filtrem s nízkým průchodem, aby se upravilo předpětí generátoru. Podle věty o centrálním limitu bude smyčka zpětné vazby obvykle dobře upravena „ téměř pořád “. Ultrarychlé generátory náhodných čísel tuto metodu často používají. I poté jsou generovaná čísla obvykle poněkud zkreslená.

Bělení softwaru

Druhým přístupem ke zvládání předpojatosti je snížit ji po generování (v softwaru nebo hardwaru). Existuje několik technik pro snížení zkreslení a korelace, často nazývaných „ bělící “ algoritmy, analogicky se souvisejícím problémem vytváření bílého šumu z korelovaného signálu.

John von Neumann vynalezl jednoduchý algoritmus pro opravu jednoduchých zkreslení a snížení korelace. Uvažuje dva bity najednou (nepřekrývající se), přičemž provede jednu ze tří akcí: když jsou dva po sobě jdoucí bity stejné, jsou vyřazeny; sekvence 1,0 se stane 1; a sekvence 0,1 se stane nulou. Představuje tedy sestupnou hranu s 1 a stoupající hranu s 0. To eliminuje jednoduché zkreslení a je snadno implementovatelné jako počítačový program nebo v digitální logice. Tato technika funguje bez ohledu na to, jak byly bity generovány. Nemůže však zajistit náhodnost ve svém výstupu. To, co může udělat (s významným počtem vyřazených bitů), je transformovat zkreslený náhodný bitový proud na nezaujatý.

Další technikou pro zlepšení téměř náhodného bitového toku je exkluzivní-nebo bitový tok s výstupem vysoce kvalitního kryptograficky zabezpečeného generátoru pseudonáhodných čísel, jako je Blum Blum Shub nebo šifra silného proudu . To může zlepšit dekorelaci a zkreslení číslic za nízké náklady; lze to provést hardwarem, například FPGA, což je rychlejší než softwarové.

Související metoda, která snižuje zkreslení v téměř náhodném bitovém toku, je vzít dva nebo více nekorelovaných blízkých náhodných bitových toků a vyloučit je nebo dohromady. Nechť pravděpodobnost bitového proudu produkujícího 0 je 1/2 +  e , kde −1/2 ≤  e  ≤ 1/2. Pak e je zkreslení bitového proudu. Pokud jsou dva nekorelované bitové toky se zkreslením e exkluzivní nebo společně, pak zkreslení výsledku bude 2 e 2 . To se může opakovat s více bitovými proudy (viz také lemující hromadné lemma ).

Některá provedení používají kryptografické hashovací funkce jako MD5 , SHA-1 nebo RIPEMD-160 nebo dokonce funkci CRC na celý bitový proud nebo jeho část a poté používají výstup jako náhodný bitový tok. To je atraktivní, částečně proto, že je to relativně rychlé.

Mnoho fyzických jevů lze použít ke generování bitů, které jsou velmi zkreslené, ale každý bit je nezávislý na ostatních. Geigerův čítač (s dobou vzorkování delší než doba regenerace elektronky) nebo poloprůhledný zrcadlový fotonový detektor generují bitové toky, které jsou většinou „0“ (tiché nebo přenosové) s občasným „1“ (kliknutí nebo odraz). Pokud je každý bit nezávislý na ostatních, strategie Von Neumanna generuje jeden náhodný, nezaujatý výstupní bit pro každý ze vzácných bitů „1“ v takto vysoce předpojatém bitovém toku. Bělicí techniky, jako je Advanced Multi-Level Strategy (AMLS), mohou extrahovat více výstupních bitů-výstupních bitů, které jsou stejně náhodné a nezaujaté-z takto vysoce předpojatého bitového proudu.

PRNG s periodicky obnovovaným náhodným klíčem

Jiné konstrukce používají to, co je považováno za pravdivé náhodné bity, jako klíč pro vysoce kvalitní algoritmus blokové šifry , přičemž šifrovaný výstup bere jako náhodný bitový tok. V těchto případech je však třeba dbát na výběr vhodného blokového režimu . V některých implementacích je PRNG spuštěno na omezený počet číslic, zatímco zařízení generující hardware produkuje nové osivo.

Pomocí pozorovaných událostí

Softwaroví inženýři bez skutečných generátorů náhodných čísel se je často pokoušejí vyvinout měřením fyzických událostí, které má software k dispozici. Příkladem je měření času mezi uživatelskými stisky kláves a poté brát nejméně významný bit (nebo dva nebo tři) z počtu jako náhodnou číslici. Podobný přístup měří plánování úkolů, zásahy do sítě, časy hledání na hlavě disku a další interní události. Jeden návrh společnosti Microsoft obsahuje velmi dlouhý seznam těchto interních hodnot, což je forma kryptograficky zabezpečeného generátoru pseudonáhodných čísel . Lávové lampy byly také použity jako fyzická zařízení, která mají být monitorována, jako v systému Lavarand .

Tato metoda je riskantní, když používá počítačem řízené události, protože chytrý, zlomyslný útočník může být schopen předvídat kryptografický klíč ovládáním vnějších událostí. Je to také riskantní, protože domnělou uživatelem generovanou událost (např. Stisknutí klávesy) může zfalšovat dostatečně důmyslný útočník, což umožňuje kontrolu nad „náhodnými hodnotami“ používanými kryptografií.

S dostatečnou péčí však lze navrhnout systém, který produkuje kryptograficky zabezpečená náhodná čísla ze zdrojů náhodnosti dostupných v moderním počítači. Základním návrhem je udržovat „entropický fond“ náhodných bitů, o nichž se předpokládá, že jsou útočníkovi neznámé. Nová náhodnost se přidá, kdykoli je k dispozici (například když uživatel stiskne klíč), a zachová se odhad počtu bitů ve fondu, které útočník nemůže znát. Některé z používaných strategií zahrnují:

  • Když jsou požadovány náhodné bity, vraťte tolik bitů odvozených z fondu entropie (řekněme funkcí kryptografické hash) a snižte odhad počtu náhodných bitů zbývajících ve fondu. Pokud není k dispozici dostatek neznámých bitů, počkejte, až jich bude k dispozici dostatek. Toto je návrh nejvyšší úrovně zařízení „ /dev /random “ v Linuxu, který napsal Theodore Ts'o a používá se v mnoha dalších operačních systémech podobných Unixu. Poskytuje vysoce kvalitní náhodná čísla, pokud jsou odhady náhodnosti vstupu dostatečně opatrné. Zařízení Linux „/dev/urandom“ je jednoduchá modifikace, která nebere v úvahu odhady náhodnosti vstupu, a je proto spíše méně pravděpodobné, že by ve výsledku měla vysokou entropii.
  • Udržujte proudovou šifru pomocí klíče a inicializačního vektoru (IV) získaného z fondu entropií. Když bylo shromážděno dostatek bitů entropie, nahraďte klíč i IV novými náhodnými hodnotami a snižte odhadovanou entropii zbývající ve fondu. To je přístup, který používá knihovna řebříčku . Poskytuje odolnost proti některým útokům a zachovává těžko dosažitelnou entropii.

(De) centralizované systémy

Skutečným generátorem náhodných čísel může být (de) centrální služba. Jedním příkladem centralizovaného systému, kde lze získat náhodné číslo, je služba majáku náhodnosti od Národního institutu pro standardy a technologie ; dalším příkladem je Random.org , služba, která využívá atmosférický šum ke generování náhodných binárních číslic (bitů).

Jako příklad decentralizovaného systému využívá platforma Cardano účastníky jejich decentralizovaného protokolu proof-of-stake ke generování náhodných čísel.

Problémy

Je velmi snadné nesprávně konstruovat hardwarová nebo softwarová zařízení, která se pokoušejí generovat náhodná čísla. Většina se také potichu „zlomila“ a při degradaci často produkuje klesající náhodná čísla. Fyzickým příkladem může být rychle se snižující radioaktivita dříve zmíněných detektorů kouře, pokud by byl tento zdroj použit přímo. Režimy selhání v takových zařízeních jsou hojné a jsou komplikované, pomalé a těžko zjistitelné. Metody, které kombinují více zdrojů entropie, jsou robustnější.

Protože mnoho zdrojů entropie je často velmi křehkých a tiše selhává, měly by být statistické testy na jejich výstupu prováděny nepřetržitě. Mnoho, ale ne všechna, taková zařízení obsahují nějaké takové testy do softwaru, který čte zařízení.

Útoky

Stejně jako u ostatních součástí kryptografického systému by měl být softwarový generátor náhodných čísel navržen tak, aby odolal určitým útokům . Bránit se proti těmto útokům je obtížné bez zdroje entropie hardwaru.

Odhad entropie

Existují matematické techniky pro odhad entropie sekvence symbolů. Žádný není tak spolehlivý, aby se na jejich odhady dalo plně spolehnout; vždy existují předpoklady, které může být velmi obtížné potvrdit. Ty jsou užitečné například při určování, zda je ve fondu semen dostatek entropie, ale obecně nemohou rozlišovat mezi skutečným náhodným zdrojem a pseudonáhodným generátorem. Tomuto problému se vyhneme konzervativním využíváním zdrojů hardwarové entropie.

Zkouška výkonu

Hardwarové generátory náhodných čísel by měly být neustále monitorovány kvůli správné funkci. RFC 4086, FIPS Pub 140-2 a NIST Special Publication 800-90b obsahují testy, které k tomu lze použít. Viz také dokumentace k novozélandské knihovně kryptografického softwaru cryptlib .

Protože mnoho praktických návrhů spoléhá na hardwarový zdroj jako vstup, bude užitečné alespoň zkontrolovat, zda zdroj stále funguje. Statistické testy mohou často detekovat selhání zdroje hluku, například rozhlasové stanice vysílající na kanálu, o kterém se domníváme, že je prázdný. Z výstupu generátoru šumu by měly být odebrány vzorky k testování a poté prošly „bělidlem“. Některé návrhy bělidel mohou projít statistickými testy bez náhodného zadávání. Zatímco detekce velké odchylky od dokonalosti by byla známkou toho, že skutečný náhodný zdroj hluku byl degradován, malé odchylky jsou normální a mohou být známkou správné funkce. Korelace zkreslení vstupů na konstrukci generátoru s jinými parametry (např. Vnitřní teplota, napětí sběrnice) může být navíc užitečná jako další kontrola. U aktuálně dostupných (a předvídaných) testů bohužel absolvování takových testů nestačí k zajištění, že výstupní sekvence jsou náhodné. Kromě testování na vysoce hodnotná použití může být zapotřebí pečlivě zvolený design, ověření, že vyrobené zařízení implementuje tento design, a nepřetržité fyzické zabezpečení k zajištění proti neoprávněné manipulaci.

Viz také

Reference

Obecné reference

externí odkazy