Kriptográfiailag biztonságos pszeudo-véletlen számgenerátor

A kriptográfiailag biztonságos álvéletlenszám-generátor (CSPRNG ) egy  pszeudovéletlen számgenerátor , amelynek bizonyos tulajdonságai lehetővé teszik a kriptográfiában való használatát .

A kriptográfia számos alkalmazása véletlen számokat igényel, például:

• Kulcsgenerálás
• Egyszeri véletlen számok ( angol  Nonces )
• Egyszer használatos titkosító lapok
• Só a digitális aláírási sémákban , például az ECDSA

Kihívás

A véletlenszerűség szükséges „minősége” feladatról feladatra változik. Például egyetlen véletlen szám generálása egyes protokollokban csak egyediséget igényel, míg egy mesterkulcs vagy egyszeri rejtjelező mező generálása nagy entrópiát igényel . Ideális esetben a véletlen számok generálása PRNG-ben egy rendkívül megbízható entrópiaforrást használ , amely lehet hardveres véletlenszám-generátor vagy a rendszerben előre nem látható folyamatok lefolyása – bár mindkét esetben előfordulhatnak váratlan sebezhetőségek [1] [2] . Információelméleti szempontból a véletlenszerűség mértéke, a megszerezhető entrópia megegyezik a rendszer által biztosított entrópiával. De gyakran valós helyzetekben több véletlenszámra van szükség, mint amennyit a meglévő entrópiával megkaphatunk. Ezenkívül a rendszerből a véletlenszerűség megszerzésének eljárása sok erőforrást (memória és idő) igényel. Ilyen esetekben indokolt a KSPRCH használata - ez lehetővé teszi a rendelkezésre álló entrópia nagyobb bitszámmal való "kinyújtását". Ha a kriptográfiai algoritmus végrehajtása előtt az összes entrópia rendelkezésre áll, egy adatfolyam titkosítást kapunk [3] . Egyes titkosítási rendszerek azonban lehetővé teszik az entrópia hozzáadását munka közben, ebben az esetben az algoritmus nem egyenértékű a stream titkosítással, és nem használható. Így a stream titkosítások és a CRNG fejlődése szorosan összefügg.

Követelmények

A hagyományos pszeudo-véletlenszám-generátorral szemben támasztott követelményeket [4] [5] a kriptográfiailag biztonságos PRNG is teljesíti, fordítva nem igaz. A CRRC követelményei két csoportra oszthatók: először is át kell menniük a véletlenszerűségi statisztikai teszteken ; másodszor pedig kiszámíthatatlannak kell maradniuk, még akkor is, ha eredeti vagy jelenlegi állapotuk egy része a kriptoanalitikus számára ismertté válik . Ugyanis:

• A PRNG-nek meg kell felelnie a " következő bittesztnek ". A teszt jelentése a következő: ne létezzen olyan polinomiális algoritmus , amely egy véletlen sorozat első k bitjének ismeretében 50%-nál nagyobb valószínűséggel tudja megjósolni a ( k + 1)-edik bitet. Andrew Yao 1982 -ben bebizonyította, hogy az a generátor, amely átmegy a "következő bitteszten", minden más statisztikai véletlenszerűségi teszten is megfelel, amely polinomiális időben elvégezhető.
• A PRNG-nek megbízhatónak kell maradnia még akkor is, ha egyes vagy összes állapota ismertté vált (vagy helyesen lett kiszámítva). Ez azt jelenti, hogy ne legyen lehetséges a generátor által generált véletlenszerű sorozat megszerzése, mielőtt a kriptaelemző megszerezte volna ezt a tudást. Ezenkívül, ha a működés során extra entrópiát használnak, a bemenettel kapcsolatos ismeretek felhasználása számításilag lehetetlen. Példa A generátor a π szám bináris reprezentációjának bitjeinek kimenetén alapuljon, valamilyen ismeretlen pontból kiindulva. Egy ilyen generátor esetleg átmenne a "következő bitteszten", mivel a π véletlenszerű sorozatnak tűnik (ez akkor garantált, ha π normális szám ). Ez a megközelítés azonban kriptográfiailag nem biztonságos – ha a kriptoanalizátor meghatározza, hogy a pi melyik bitje van jelenleg használatban, ki tudja számítani az összes korábbi bitet is.

A legtöbb pszeudo-véletlenszám-generátor nem alkalmas PRNG-ként való használatra mindkét feltétel esetén. Először is, annak ellenére, hogy sok PRNG olyan szekvenciát állít elő, amely a különböző statisztikai tesztek szempontjából véletlenszerű, nem megbízhatóak a visszafejtéssel szemben . Speciális, speciálisan hangolt teszteket találhatunk, amelyek megmutatják, hogy a PRNG által előállított véletlenszámok nem igazán véletlenszerűek. Másodszor, a legtöbb PRNG képes a teljes pszeudovéletlen sorozatot kiszámítani , ha állapotuk veszélybe kerül, így a kriptoanalizátor nem csak a jövőbeli üzenetekhez férhet hozzá, hanem az összes korábbi üzenethez. A KSHRNG fejlesztése során figyelembe vették a különféle típusú kriptoanalízisekkel szembeni ellenállást .

Megvalósítások

Tekintsük a KSPRCH megvalósításának három osztályát:

1. Titkosító algoritmusok alapján
2. Számításilag összetett matematikai problémák alapján
3. Speciális megvalósítások

Ez utóbbiak gyakran használnak további entrópiaforrásokat, ezért szigorúan véve nem "tiszta" generátorok, mivel a kibocsátásukat nem teljesen határozza meg a kezdeti állapot. Ez további védelmet tesz lehetővé a kezdeti állapot meghatározását célzó támadásokkal szemben.

Titkosító algoritmusokon alapuló megvalósítások

• A biztonságos blokk titkosítás CRNG-re konvertálható, ha számláló módban futtatja . Így egy véletlenszerű kulcs kiválasztásával megkaphatja a következő véletlenszerű blokkot, ha az algoritmust az egymást követő természetes számokra alkalmazza . A számolást bármely természetes számtól kezdheti. Nyilvánvaló, hogy a periódus nem lehet több 2 n -nél egy n bites blokkrejtjel esetében. Az is nyilvánvaló, hogy egy ilyen rendszer biztonsága teljes mértékben a kulcs titkosságától függ.

• Egy kriptográfiailag erős hash függvény is konvertálható CRNG-re. Ebben az esetben a számláló eredeti értékének titokban kell maradnia. Néhány szerző azonban óva int a hash függvények ilyen használatától [6] .

• A legtöbb adatfolyam titkosítás úgy működik, hogy pszeudo-véletlen bitfolyamot generál, amelyet valamilyen módon (szinte mindig XOR művelettel) kombinálnak a nyílt szöveg bitekkel . Egy ilyen titkosítás futtatása természetes számok sorozatán új pszeudo-véletlen sorozatot ad, talán még hosszabb periódussal is. Ez a módszer csak akkor biztonságos, ha maga a stream titkosítás erős CRNG-t használ (ami nem mindig van így). A számláló kezdeti állapotának ismét titkosnak kell maradnia.

Matematikai feladatokon alapuló megvalósítások

• A Bloom–Blum–Shub algoritmus nagy kriptográfiai erősséggel rendelkezik az egész számok faktorizálásának észlelt összetettsége alapján . Ez az algoritmus azonban nagyon lassú.
• A Blum- Micali  algoritmus a diszkrét logaritmus problémán alapul .

Speciális megvalósítások

Számos gyakorlati PRNG létezik, amelyeket például a kriptográfiai erősség figyelembevételével fejlesztettek ki

• Yarrow algoritmus [ 7] , amely megpróbálja meghatározni a bemeneti adatok entrópiáját .  FreeBSD - ben , OpenBSD -ben és Mac OS X -ben használatos
• Algorithm Fortuna ( eng.  Fortuna algorithm ), a Yarrow algoritmus utódja.
• Egy speciális UNIX OS fájl /dev/random , különösen a /dev/urandom Linux alatt .
• A CryptGenRandom funkció a Microsoft CryptoAPI - jában [8]
• Az ISAAC az RC4 változaton alapul .

Jegyzetek

1. ↑ Zvi Gutterman. Támadásra nyitott: A Linux véletlenszám-  generátorának sebezhetősége . Letöltve: 2010. november 15. Az eredetiből archiválva : 2011. február 27..
2. ↑ Stealthy Dopant-Level Hardware Trojans Archiválva : 2013. december 5. a Wayback Machine -nél (a trójaiak esetleges bevezetéséről a hardveres véletlenszám-generátorba).
3. ↑ Schneier B. 16 Álvéletlen szekvenciagenerátorok és adatfolyam-rejtjelek // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 .
4. ↑ Schneier B. 2.8 Véletlenszerű és pszeudovéletlen sorozatok generálása // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 .
5. ↑ Gutmann Péter. Gyakorlatilag erős véletlenszámok szoftvergenerálása  //  Proceedings of the 7th USENIX Security Symposium : folyóirat. - 1998. Archiválva : 2012. július 4.
6. ↑ Adam Young, Moti Yung. Rosszindulatú kriptográfia : A kriptovirológia leleplezése . - 3.2. szekta: John_Wiley_%26_Sons , 2004. - P. 416. - ISBN 978-0-7645-4975-5 .  
7. ↑ Cickafark . Letöltve: 2010. november 15. Az eredetiből archiválva : 2012. november 8.. (határozatlan)
8. ↑ Az MSDN CryptoGenRandom funkciójának  leírása . Microsoft . Letöltve: 2010. november 15. Az eredetiből archiválva : 2012. július 4..

Linkek

• Jurij Lifshits. 9. előadás: Álvéletlen generátorok // A kriptográfia modern problémái . - Előadó tanfolyam.  (nem elérhető link)
•  Kriptográfiai véletlen számok
• A véletlenszám-  generálás elmélete és gyakorlata
• Zvi Gutterman, Benny Pinkas, Tzachy Reinman. A Linux véletlenszám-generátor elemzése 
• Statisztikai tesztcsomag véletlenszerű és pszeudovéletlen számgenerátorokhoz kriptográfiai alkalmazásokhoz  NIST SP 800-22