cryptographically secure pseudorandom number generator (tsz. cryptographically secure pseudorandom number generators)
Háttér A legtöbb kriptográfiai alkalmazás véletlen számokat igényel , például:
kulcsgenerálás inicializálási vektorok nonces sók bizonyos aláírási sémákban, beleértve az ECDSA-t és az RSASSA-PSS-t token generáció Az ezekhez az alkalmazásokhoz szükséges véletlenszerűség "minősége" változó. Például egy nonce létrehozásához bizonyos protokollokban csak egyediségre van szükség. Másrészt a mesterkulcs generálása magasabb minőséget igényel, például több entrópiát . Az egyszeri padok esetében pedig a tökéletes titoktartás információelméleti garanciája csak akkor áll fenn, ha a kulcsanyag valódi véletlenszerű forrásból származik, nagy entrópiával, és így bármilyen pszeudovéletlen számgenerátor nem elegendő.
Ideális esetben a véletlen számok generálása a CSPRNG-ben kiváló minőségű forrásból, általában az operációs rendszer véletlenszerűségi API-jából nyert entrópiát használ . Azonban több ilyen látszólag független folyamatban váratlan összefüggéseket találtak. Információelméleti szempontból a véletlenszerűség mértéke, a generálható entrópia megegyezik a rendszer által biztosított entrópiával. De néha gyakorlati helyzetekben több véletlenszerű számra van szükség, mint amennyit a rendelkezésre álló entrópia biztosítani tud. Ezenkívül a futó rendszerből a véletlenszerűséget kivonó folyamatok lassúak a gyakorlatban. Ilyen esetekben néha CSPRNG is használható. A CSPRNG több bitre is képes "kinyújtani" a rendelkezésre álló entrópiát.
Követelmények A hagyományos PRNG követelményeit a kriptográfiailag biztonságos PRNG is kielégíti, de fordítva ez nem igaz. A CSPRNG követelményei két csoportra oszthatók:
Átmennek a statisztikai véletlenszerűségi teszteken : Minden CSPRNG-nek meg kell felelnie a következő bit tesztjének . Ez azt jelenti, hogy egy véletlen sorozat első k bitjénél nincs olyan polinomiális idejű algoritmus, amely a ( k +1)-edik bitet 50%-nál nem elhanyagolhatóan nagyobb siker valószínűséggel tudná megjósolni. Andrew Yao 1982-ben bebizonyította, hogy a következő bit teszten átmenő generátor minden más polinomiális idejű statisztikai véletlenszerűségi teszten is megfelel. Jól bírják komoly támadásokat, még akkor is, ha kezdeti vagy futó állapotuk egy része elérhetővé válik a támadó számára: Minden CSPRNG-nek ellenállnia kell az „állapotkompromittáló kiterjesztési támadásoknak”. : 4 Abban az esetben, ha állapotának egy része vagy egésze kiderült (vagy helyesen sejtették), lehetetlennek kell lennie a véletlen számok folyamának rekonstrukciója a kinyilatkoztatás előtt. Ezen túlmenően, ha futás közben entrópia bemenet van, akkor lehetetlennek kell lennie a bemenet állapotának ismeretében a CSPRNG állapot jövőbeli feltételeinek előrejelzésére. Például, ha a szóban forgó PRNG a pi bitjeinek szekvenciális kiszámításával állít elő kimenetet, a bináris bővítés valamely ismeretlen pontjából kiindulva, akkor megfelelhet a következő bit tesztjének, és így statisztikailag véletlenszerű, mivel a pi egy normális szám . Ez az algoritmus azonban kriptográfiailag nem biztonságos; a támadó, aki meghatározza, hogy a pi melyik bitje van jelenleg használatban (azaz az algoritmus állapota), képes lesz az összes megelőző bitet is kiszámítani.
A legtöbb PRNG nem alkalmas CSPRNG-ként való használatra, és mindkét esetben meghiúsul. Először is, bár a legtöbb PRNG kimenete véletlenszerűnek tűnik a válogatott statisztikai tesztekben, nem állnak ellen a meghatározott visszafejtésnek. Speciális statisztikai teszteket találhatunk speciálisan olyan PRNG-re hangolva, amely azt mutatja, hogy a véletlen számok nem igazán véletlenszerűek. Másodszor, a legtöbb PRNG esetében, amikor az állapotuk felfedett, az összes múltbeli véletlen szám visszamenőleg visszaírható, így a támadó elolvashatja az összes múltbeli üzenetet, valamint a jövőbelieket is.
A CSPRNG-ket kifejezetten úgy tervezték, hogy ellenálljanak az ilyen típusú kriptoanalízisnek .