Kryptograficky bezpečný generátor pseudonáhodných čísel - Cryptographically-secure pseudorandom number generator

Kryptograficky zabezpečené pseudonáhodné číslo generátor ( CSPRNG ) nebo šifrovací generátor pseudonáhodných čísel ( CPRNG ) je číslo pseudonáhodný generátor (PRNG) s vlastností, která je vhodná pro použití v kryptografii . Je také volně známý jako kryptografický generátor náhodných čísel ( CRNG ) (viz Generování náhodných čísel § „Pravda“ vs. pseudonáhodná čísla ).

Většina kryptografických aplikací vyžaduje náhodná čísla, například:

• generování klíčů
• nonces
• soli v některých systémech, včetně podpisových ECDSA , RSASSA-PSS

„Kvalita“ náhodnosti požadovaná pro tyto aplikace se liší. Například vytvoření nonce v některých protokolech vyžaduje pouze jedinečnost. Na druhou stranu generování hlavního klíče vyžaduje vyšší kvalitu, například větší entropii . A v případě jednorázových bloků platí informačně teoretická záruka dokonalého utajení pouze v případě, že klíčový materiál pochází ze skutečného náhodného zdroje s vysokou entropií, a tedy jakýkoli druh generátoru pseudonáhodných čísel je nedostatečný.

V ideálním případě generování náhodných čísel v CSPRNG využívá entropii získanou z vysoce kvalitního zdroje, obecně API náhodnosti operačního systému. V několika zdánlivě nezávislých procesech však byly nalezeny neočekávané korelace. Z informačně-teoretického hlediska je množství nahodilosti, entropie, kterou lze generovat, stejné jako entropie poskytovaná systémem. Ale někdy je v praktických situacích zapotřebí více náhodných čísel, než je k dispozici entropie. Také procesy extrahování náhodnosti z běžícího systému jsou ve skutečné praxi pomalé. V takových případech lze někdy použít CSPRNG. CSPRNG může „natáhnout“ dostupnou entropii na více bitů.

Požadavky

Požadavky běžného PRNG splňuje také kryptograficky zabezpečený PRNG, ale opak není pravdou. Požadavky CSPRNG spadají do dvou skupin: za prvé, že procházejí statistickými testy náhodnosti ; a za druhé, že se dobře drží při vážném útoku, i když část jejich počátečního nebo běžícího stavu bude k dispozici útočníkovi.

• Každý CSPRNG by měl splňovat další bitový test . To znamená, že vzhledem k prvním k bitům náhodné sekvence neexistuje žádný algoritmus polynomiálního času , který by dokázal předpovědět ( k +1) th bit s pravděpodobností úspěchu nezanedbatelně lepší než 50%. Andrew Yao v roce 1982 dokázal, že generátor, který projde dalším bitovým testem, projde všemi ostatními statistickými testy polynomiálního času pro náhodnost.
• Každý CSPRNG by měl vydržet „rozšíření kompromisu stavu“. V případě, že část nebo celý její stav byl odhalen (nebo uhádnut správně), mělo by být nemožné před odhalením zrekonstruovat proud náhodných čísel. Navíc pokud existuje entropický vstup za běhu, mělo by být nemožné použít znalosti o stavu vstupu k předpovědi budoucích podmínek stavu CSPRNG.

Příklad: Pokud uvažovaná CSPRNG produkuje výstup počítáním bitů π v sekvenci, počínaje od nějakého neznámého bodu v binární expanzi, může dobře splnit další bitový test a být tedy statisticky náhodný, protože π se zdá být náhodná sekvence . (To by bylo zaručeno, pokud je například π normální číslo .) Tento algoritmus však není kryptograficky bezpečný; útočník, který určí, který bit pi (tj. stav algoritmu) se aktuálně používá, bude schopen vypočítat také všechny předchozí bity.

Většina PRNG není vhodná pro použití jako CSPRNG a selže v obou bodech. Za prvé, zatímco většina výstupů PRNG se jeví jako náhodná pro různé statistické testy, nebrání se určenému reverznímu inženýrství. Specializované statistické testy lze nalézt speciálně vyladěné na takový PRNG, který ukazuje, že náhodná čísla nejsou skutečně náhodná. Za druhé, u většiny PRNG, když byl odhalen jejich stav, lze všechna minulá náhodná čísla retrodikovat, což útočníkovi umožní přečíst si všechny zprávy minulé i budoucí.

CSPRNG jsou navrženy výslovně tak, aby odolávaly tomuto typu kryptoanalýzy .

Definice

V asymptotickém nastavení je rodina deterministických polynomiálních časově vypočítatelných funkcí pro nějaký polynom p , generátor pseudonáhodných čísel ( PRNG nebo v některých referencích PRG ), pokud natahuje délku jeho vstupu ( pro jakékoli k ) a pokud jeho výstup je výpočetně nerozeznatelný od skutečné náhodnosti, tj. pro jakýkoli pravděpodobnostní polynomiální časový algoritmus A , který vydává 1 nebo 0 jako rozlišovací ${\ displaystyle G_ {k} \ colon \ {0,1 \}^{k} \ to \ {0,1 \}^{p (k)}}$${\ Displaystyle p (k)> k}$

${\ Displaystyle \ left | \ Pr _ {x \ gets \ {0,1 \}^{k}} [A (G (x)) = 1]-\ Pr _ {r \ gets \ {0,1 \ }^{p (k)}} [A (r) = 1] \ vpravo | <\ mu (k)}$

pro nějakou zanedbatelnou funkci . (Zápis znamená, že x je vybráno náhodně rovnoměrně z množiny X. ) ${\ Displaystyle \ mu}$${\ displaystyle x \ gets X}$

Tam je ekvivalentní charakteristika: Pro všechny funkce rodiny , G je PRNG tehdy a jen tehdy, pokud je další výstup trochu G nelze předpovědět pomocí polynomu časového algoritmu. ${\ displaystyle G_ {k} \ colon \ {0,1 \}^{k} \ to \ {0,1 \}^{p (k)}}$

Dopředu bezpečné PRNG s délkou bloku je PRNG , kde je vstupní řetězec s délkou k je současný stav v době i , a výstup ( , ) se skládá z dalšího stavu a pseudonáhodné výstupního bloku období i , který odolává stav kompromitovat rozšíření v následujícím smyslu. Pokud je počáteční stav vybrán rovnoměrně náhodně z , pak pro libovolné i musí být posloupnost výpočetně nerozeznatelná od , ve které jsou vybrány rovnoměrně náhodně z . ${\ Displaystyle t (k)}$${\ Displaystyle G_ {k} \ colon \ {0,1 \}^{k} \ to \ {0,1 \}^{k} \ times \ {0,1 \}^{t (k)}}$${\ displaystyle s_ {i}}$${\ displaystyle s_ {i+1}}$${\ displaystyle y_ {i}}$${\ displaystyle s_ {i+1}}$${\ displaystyle y_ {i}}$${\ displaystyle s_ {1}}$${\ displaystyle \ {0,1 \}^{k}}$${\ Displaystyle (y_ {1}, y_ {2}, \ dots, y_ {i}, s_ {i+1})}$${\ displaystyle (r_ {1}, r_ {2}, \ dots, r_ {i}, s_ {i+1})}$${\ displaystyle r_ {i}}$${\ displaystyle \ {0,1 \}^{t (k)}}$

Libovolný PRNG lze přeměnit na dopředu zabezpečený PRNG s délkou bloku rozdělením jeho výstupu do dalšího stavu a skutečného výstupu. To se provádí nastavením , ve kterém a ; pak G je dopředně bezpečný PRNG s jako dalším stavem a jako pseudonáhodný výstupní blok aktuálního období. ${\ Displaystyle G \ colon \ {0,1 \}^{k} \ to \ {0,1 \}^{p (k)}}$${\ Displaystyle p (k) -k}$${\ Displaystyle G (s) = G_ {0} (s) \ Vert G_ {1} (s)}$${\ Displaystyle | G_ {0} (s) | = | s | = k}$${\ Displaystyle | G_ {1} (s) | = p (k) -k}$${\ displaystyle G_ {0}}$${\ displaystyle G_ {1}}$

Extrakce entropie

Santha a Vazirani dokázali, že lze kombinovat několik bitových toků se slabou nahodilostí a vytvořit tak kvazi-náhodný bitový tok vyšší kvality. Ještě dříve John von Neumann dokázal, že jednoduchý algoritmus dokáže odstranit značné množství zkreslení v jakémkoli bitovém proudu, který by měl být aplikován na každý bitový tok před použitím jakékoli variace designu Santha – Vazirani.

Návrhy

V níže uvedené diskusi jsou návrhy CSPRNG rozděleny do tří tříd:

1. ty založené na kryptografických primitivách, jako jsou šifry a kryptografické hashe ,
2. ty založené na matematických problémech považovaných za těžké, a
3. účelové designy.

Poslední často zavádí další entropii, pokud je k dispozici, a, přísně vzato, nejsou „čistými“ generátory pseudonáhodných čísel, protože jejich výstup není zcela určen jejich počátečním stavem. Toto přidání může zabránit útokům, i když je počáteční stav narušen.

Návrhy založené na kryptografických primitivách

• Zabezpečenou blokovou šifru lze převést na CSPRNG spuštěním v režimu čítače . To se provádí výběrem náhodného klíče a zašifrováním 0, pak zašifrováním 1, zašifrováním 2 atd. Počitadlo lze také spustit na libovolném čísle jiném než nula. Za předpokladu, že n -bitovou blokovou šifru bude možné výstup odlišit od náhodných dat po přibližně 2 ^{n /2} blocích, protože po problému s narozeninami by se srážkové bloky v tomto bodě mohly stát pravděpodobnými, zatímco bloková šifra v režimu CTR nikdy nevydá identické bloky . U 64bitových blokových šifer to omezuje bezpečnou velikost výstupu na několik gigabajtů, u 128bitových bloků je omezení dostatečně velké, aby neovlivnilo typické aplikace. Pokud je však používán samostatně, nesplňuje všechna kritéria CSPRNG (jak je uvedeno výše), protože není silný proti „rozšíření kompromisu stavu“: se znalostí stavu (v tomto případě čítače a klíče) můžete předpovídat všechny minulé výstupy.
• Kryptograficky bezpečný hash čítače může v některých případech fungovat také jako dobrý CSPRNG. V tomto případě je také nutné, aby počáteční hodnota tohoto čítače byla náhodná a tajná. Existuje však málo studií o těchto algoritmech pro použití tímto způsobem a alespoň někteří autoři před tímto používáním varují.

• Většina šifrovacích proudů pracuje generováním pseudonáhodného proudu bitů, které jsou kombinovány (téměř vždy XORed ) s prostým textem ; spuštění šifry na čítači vrátí nový pseudonáhodný proud, případně s delší periodou. Šifra může být bezpečná pouze tehdy, je -li původní datový tok dobrým CSPRNG, i když tomu tak nemusí být (viz šifra RC4 ). Počáteční stav musí být opět utajen.

Číslově teoretické návrhy

• Blum Blum Shub algoritmus má důkaz zabezpečení založenou na obtížnosti kvadratické residuosity problému . Protože jediným známým způsobem řešení tohoto problému je faktor modulu, obecně se má za to, že obtížnost celočíselné faktorizace poskytuje podmíněný bezpečnostní důkaz pro algoritmus Blum Blum Shub. Algoritmus je však velmi neefektivní, a proto nepraktický, pokud není zapotřebí extrémního zabezpečení.
• Algoritmus Blum-Micali má důkaz zabezpečení založenou na obtížnosti problému diskrétního logaritmu , ale je také velmi neefektivní.
• Daniel Brown Certicom napsal Security 2006 důkaz pro Dual_EC_DRBG , založený na předpokládaném tvrdosti předpokladu Rozhodovací Diffie-Hellman , o problému x-logaritmu , a zkrácený problému bodu . Důkaz z roku 2006 výslovně předpokládá nižší výdrž než ve standardu Dual_EC_DRBG a že P a Q ve standardu Dual_EC_DRBG (které byly odhaleny v roce 2013 jako pravděpodobně backdoorované NSA) jsou nahrazeny hodnotami bez backdoorů.

Speciální provedení

Existuje řada praktických PRNG, které byly navrženy tak, aby byly kryptograficky bezpečné, včetně

• Yarrow algoritmus , který se snaží, aby zhodnotila entropickou kvalitu svých vstupů. Yarrow se v macOS a dalších Apple OS používá zhruba do prosince 2019. Od té doby Apple přešel na Fortunu. (Viz /dev /random ).
• ChaCha20 algoritmus nahradí RC4 v OpenBSD (verze 5.4), NetBSD (verze 7.0), a FreeBSD (verze 12.0).
• ChaCha20 také nahradil SHA-1 v Linuxu ve verzi 4.8.
• algoritmus Fortuna , následník Yarrow, který si neklade za cíl hodnotit entropickou kvalitu svých vstupů. Fortuna se používá ve FreeBSD. Apple se změnil na Fortunu pro většinu nebo všechny Apple OS počínaje kolem prosince 2019.
• Funkce CryptGenRandom uvedené v Microsoft ‚s Cryptographic Application Programming Interface
• ISAAC na základě varianty šifry RC4
• Posuvný registr s lineární zpětnou vazbou vyladěný evolučním algoritmem na základě sady NIST Statistical Test Suite.
• arc4random
• AES - CTR DRBG se často používá jako generátor náhodných čísel v systémech, které používají šifrování AES.
• Standard ANSI X9.17 ( Key Institution Key Management (velkoobchod) ), který byl také přijat jako standard FIPS . Trvá jako vstup balíček klíčů TDEA ( možnost klíčování 2 ) k a (počáteční hodnota) 64bitové náhodné semeno s . Pokaždé, když je požadováno náhodné číslo:
  • Získá aktuální datum/čas D na maximální možné rozlišení.
  • Vypočítá dočasnou hodnotu t = TDEA _k ( D )
  • Vypočítá náhodnou hodnotu x = TDEA _k ( s ⊕ t ) , kde ⊕ označuje bitově exkluzivní nebo .
  • Aktualizuje osivo s = TDEA _k ( x ⊕ t )

Je zřejmé, že tuto techniku ​​lze snadno zobecnit na jakoukoli blokovou šifru; Bylo navrženo AES .

Standardy

Několik CSPRNG bylo standardizováno. Například,

• FIPS 186-4
• NIST SP 800-90A :

Tento stažený standard má čtyři PRNG. Dva z nich jsou nekontroverzní a osvědčené: CSPRNG s názvem Hash_DRBG a HMAC_DRBG.

Třetí PRNG v tomto standardu, CTR DRBG , je založen na blokové šifře běžící v režimu čítače . Má nekontroverzní design, ale bylo prokázáno, že je slabší, pokud jde o rozlišování útoku, než je úroveň zabezpečení základní blokové šifry, když je počet bitů vycházejících z této PRNG větší než dva na sílu velikosti bloku základního bloku šifry v bitech.

Když je maximální počet výstupů bitů z tohoto PRNG roven 2 ^blockize , výsledný výstup přináší matematicky očekávanou úroveň zabezpečení, kterou by měla generovat velikost klíče, ale výstup je ukázán jako nerozeznatelný od skutečného náhodného čísla generátor. Když je maximální počet výstupů bitů z tohoto PRNG menší než tento, je doručena očekávaná úroveň zabezpečení a výstup se zdá být nerozeznatelný od skutečného generátoru náhodných čísel.

V další revizi je uvedeno, že nárokovaná síla zabezpečení pro CTR_DRBG závisí na omezení celkového počtu generovaných požadavků a poskytovaných bitů na generovaný požadavek.

Čtvrtý a poslední PRNG v tomto standardu se jmenuje Dual_EC_DRBG . Ukázalo se, že není kryptograficky bezpečný, a předpokládá se, že má kleptografické zadní vrátko NSA.

• NIST SP 800-90A Rev.1: Toto je v podstatě NIST SP 800-90A s odstraněným Dual_EC_DRBG a je nahrazením staženého standardu.
• ANSI X9.17-1985, dodatek C
• ANSI X9.31-1998, dodatek A.2.4
• ANSI X9.62-1998 příloha A.4, zastaralá ANSI X9.62-2005, příloha D (HMAC_DRBG)

NIST udržuje dobrou referenci .

Existují také standardy pro statistické testování nových návrhů CSPRNG:

• Sada statistických testů pro generátory náhodných a pseudonáhodných čísel , speciální publikace NIST 800-22 .

Klepttografické zadní vrátka NSA v Dual_EC_DRBG PRNG

The Guardian a The New York Times v roce 2013 uvedly, že Národní bezpečnostní agentura (NSA) vložila zadní vrátka do generátoru pseudonáhodných čísel (PRNG) NIST SP 800-90A, který umožňuje NSA snadno dešifrovat materiál, který byl pomocí této pomoci šifrován z Dual_EC_DRBG . Oba dokumenty uvádějí, že, jak nezávislí bezpečnostní experti dlouho tušili, NSA zavádí slabiny do standardu CSPRNG 800-90; toto je poprvé potvrzeno jedním z přísně tajných dokumentů, které do Guardianu unikl Edward Snowden . NSA tajně pracovala na tom, aby v roce 2006 schválila vlastní verzi návrhu bezpečnostního standardu NIST pro celosvětové použití. Uniklý dokument uvádí, že „nakonec se NSA stal jediným editorem“. Navzdory známému potenciálu pro kleptografické zadní vrátka a dalším známým významným nedostatkům s Dual_EC_DRBG, několik společností, jako je RSA Security, pokračovalo v používání Dual_EC_DRBG, dokud nebylo zadní vrátko potvrzeno v roce 2013. RSA Security za to obdržel od NSA platbu 10 milionů dolarů.

Chyby zabezpečení

Útok DUHK

23. října 2017 Shaanan Cohney , Matthew Green a Nadia Heninger , kryptografové z University of Pennsylvania and Johns Hopkins University, zveřejnili podrobnosti o útoku DUHK (Don't Use Hard-coded Keys) na WPA2, kde prodejci hardwaru používají hardcoded seed klíč pro algoritmus ANSI X9.31 RNG, který uvádí „útočník může hrubou silou zašifrovat zašifrovaná data, aby zjistil zbývající parametry šifrování a odvodil hlavní šifrovací klíč používaný k šifrování webových relací nebo připojení virtuální soukromé sítě (VPN)“.

Japonský šifrovací stroj PURPLE

Během druhé světové války Japonsko používalo šifrovací stroj pro diplomatickou komunikaci; Spojené státy to dokázaly rozluštit a přečíst si zprávy , většinou proto, že použité „klíčové hodnoty“ nebyly dostatečně náhodné.

Reference

externí odkazy

• RFC  4086 , náhodné požadavky na zabezpečení
• Java „entropický fond“ pro kryptograficky zabezpečená nepředvídatelná náhodná čísla.
• Standardní třída Java poskytující kryptograficky silný generátor pseudonáhodných čísel (PRNG).
• Kryptograficky zabezpečené náhodné číslo ve Windows bez použití CryptoAPI
• Předpokládané zabezpečení eliptické křivky ANSI-NIST RNG , Daniel RL Brown, IACR ePrint 2006/117.
• Bezpečnostní analýza generátoru náhodných čísel eliptické křivky NIST SP 800-90 , Daniel RL Brown a Kristian Gjosteen, IACR ePrint 2007/048. Objeví se v CRYPTO 2007.
• Kryptanalýza generátoru pseudonáhodných duálních eliptických křivek , Berry Schoenmakers a Andrey Sidorenko, IACR ePrint 2006/190.
• Efektivní generátory pseudonáhodných na základě předpokladu DDH , Reza Rezaeian Farashahi a Berry Schoenmakers a Andrey Sidorenko, IACR ePrint 2006/321.
• Analýza generátoru náhodných čísel Linuxu , Zvi Gutterman a Benny Pinkas a Tzachy Reinman.
• Stažení dokumentace a softwaru NIST Statistical Test Suite.