Útok na PRNG

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. ledna 2021; kontroly vyžadují 2 úpravy .

Útok na generátor pseudonáhodných čísel je útok zaměřený na odhalení parametrů generátoru pseudonáhodných čísel ( PRNG ) za účelem další predikce pseudonáhodných čísel.

Relevance

Bezpečnost kryptografických systémů často závisí na některých datech, která by měli znát pouze oprávnění uživatelé a která by útočník měl jen těžko uhodnout. Příklady takových dat mohou být klíče relace, které inicializují vektory, salt , jedinečné parametry ve funkcích EDS a mnoho dalších objektů. K dosažení požadované úrovně nepředvídatelnosti je vzhledem k častému generování náhodných čísel nutný spolehlivý zdroj náhodných čísel. Bohužel mnoho kryptografických aplikací nemá spolehlivý zdroj náhodných sekvencí hodnot, jako je tepelný šum v elektrických obvodech nebo přesný čas mezi párem Geigerových čítačů. Místo toho musíte použít generátory pseudonáhodných čísel (PRNG). PRNG přijímá jako vstup datový tok ze zdroje s nízkou entropií a snaží se jej převést na sekvenci hodnot, která je prakticky nerozeznatelná od skutečné náhodné sekvence. Úspěšný útok na PRNG může zlomit mnoho kryptografických systémů, bez ohledu na to, jak pečlivě byly navrženy. Některé systémy však používají špatně navržené PRNG nebo tak činí způsobem, který snižuje složitost útoků. Navíc ke kompromitaci celého systému stačí pouze jedna úspěšná infiltrace.

Typy útoků na PRNG

V závislosti na tom, která data PRNG lze snadněji sledovat (výstupní hodnoty, vstupní hodnoty nebo vnitřní stav), lze implementovat následující typy útoků.

Přímý kryptoanalytický útok

Pokud je útočník schopen přímo monitorovat výstup PRNG a zkoumat vzorec jeho výskytu, jedná se o přímý kryptanalytický útok. Tento typ útoku se vztahuje na většinu algoritmů, které používají PRNG. Pokud se však například PRNG používá pouze pro generování klíčů, jako je tomu v Triple DES , pak nemůže být zranitelný vůči tomuto druhu útoku, protože výstupy PRNG nejsou nikdy přímo viditelné.

Útoky založené na vstupu

Tento typ útoku je možný v případech, kdy útočník může využít znalosti vstupních signálů PRNG nebo je ovládat. Útoky založené na vstupu lze rozdělit na útoky se známými vstupy, útoky s reprodukovatelnými vstupy a útoky proti vybraným vstupům.

Známé útoky na vstupy jsou proveditelné v situacích, kdy se některé vstupy, u kterých návrhář systému očekává, že budou obtížně předvídatelné, v některých konkrétních případech dají snadno uhodnout.

Reprodukovatelné vstupní útoky lze použít ve stejných situacích, ale vyžadují méně sofistikované hackerské systémy a méně sofistikovanou analýzu ze strany útočníka.

Vybrané vstupní útoky lze prakticky realizovat na systémech pomocí čipových karet nebo tokenů. Takový útok může být také nebezpečný pro aplikace, které používají textové zprávy, uživatelsky definovaná hesla, síťové statistiky, čas atd. jako vstupní signály v PRNG.

Útoky založené na odhalení vnitřního stavu

Při provádění tohoto typu útoku se útočník snaží využít dříve úspěšné útoky na PRNG, které odhalily jeho vnitřní stav, aby v rámci možností předpověděl stav budoucích nebo předchozích stavů PRNG. Takové útoky mohou být úspěšné, když PRNG začíná ze známého nebo předvídatelného stavu. V praxi je velmi obtížné určit skutečnost, že došlo k ohrožení vnitřního stavu. Proto musí PRNG odolávat ohrožení vnitřního stavu. Pro takový útok existují minimálně 4 možnosti:

Útok rollback používá otevřený stav PRNG v určitém časovém okamžiku k obnovení stavů PRNG a podle toho i jeho výstupů do předchozích bodů v čase. $S$ $t_0$

Trvalé kompromitování stavu je možné u systémů, ve kterých, jakmile je stav v určitém okamžiku odhalen, jsou všechny předchozí a následující stavy zranitelné vůči následným útokům. $S$ $t_0$

Iterativní odhadový útok využívá znalost stavu v čase t a mezivýstupy PRNG, aby v čase t zjistil, kdy jsou vstupy shromážděné během tohoto časového období pro útočníka uhádnutelné (ale neznámé). $S$ $t_0$ $S$ $t_{0}+\Delta t$

Setkání uprostřed je v podstatě kombinací iterativního hádání útoku a rollback útoku. Znalosti v bodech v čase a umožňují útočníkovi obnovit stav v bodech v čase , stejně jako v celém časovém intervalu od do . $S$ $t_0$ $t_{0}+2\Delta t$ $S$ $t_{0}+\Delta t$ $t_0$ $t_{0}+2\Delta t$

Příklady nespolehlivých systémů

Dřívější verze šifrovacího protokolu Netscape SSL používaly pseudonáhodná čísla generovaná PRNG, jehož zdrojem entropie byly hodnoty tří proměnných: čas dne, ID procesu a ID nadřazeného procesu. Tyto veličiny jsou předvídatelné a mají relativně nízkou entropii. V souladu s tím byla tato verze SSL považována za nezabezpečenou. Netscape byl na problém upozorněn Phillipem Halam-Bakerem v roce 1994, tehdejším výzkumníkem v CERNu . Problém však nebyl vyřešen až do vydání softwarového produktu. Později, v roce 1995, o problému znovu hovořili Ian Goldberg a David A. Wagner [1] . Museli provést zpětnou analýzu objektových modulů , protože Netscape odmítl prozradit podrobnosti o generování náhodných čísel. PRNG byl opraven v pozdějších verzích (verze 2 a novější) změnou zdroje entropie tak, aby byl více náhodný a s vyšší úrovní entropie.

Microsoft používá ke generování náhodných čísel v operačních systémech Windows nepublikovaný algoritmus . Tento algoritmus je uživateli k dispozici prostřednictvím nástroje CryptGenRandom . V listopadu 2007 publikoval Leo Dorredorf spolu se spoluautory z Haifské univerzity a Hebrejské univerzity v Jeruzalémě článek s názvem Kryptoanalýza generátoru náhodných čísel operačního systému Windows [2] . Článek demonstruje vážné nedostatky algoritmu prezentovaného společností Microsoft. Závěry uvedené v článku byly formulovány jako výsledek studia rozloženého kódu systému Windows 2000 , ale podle Microsoftu se mohou vztahovat i na Windows XP [3] .

National Institute of Standards and Technology (USA) v březnu 2007 zveřejnil doporučené „deterministické generátory pseudonáhodných čísel“, které byly standardizovány v NIST Special Publication 800-90 [4] . Jeden z daných PRNG, Dual EC DRBG , zavedený do standardu Národní bezpečnostní agenturou [5] , je založen na eliptické kryptografii a obsahuje určitou sadu doporučených konstant. V srpnu 2007 Dan Shumov a Nils Fergeson z Microsoftu ukázali, že konstanty lze volit takovým způsobem, že v algoritmu mohou nastat zadní vrátka [6] .

V květnu 2008 publikoval výzkumník Luciano Bello článek, v němž uvádí, že změny provedené v roce 2006 v PRNG v balíčku openssl distribuovaném s Debian Linuxem a dalšími distribucemi založenými na Debianu výrazně snižují entropii generovaných hodnot, takže klíče jsou náchylné k útoku. [1] [2] Problém byl způsoben změnami, které provedl jeden z vývojářů Debianu v kódu openssl v reakci na varování kompilátoru ohledně zdánlivě nadbytečného kódu. Tato chyba zabezpečení byla opravena ve stejný den, kdy se stala známou [7] .

Způsoby ochrany proti útokům na PRNG

Pomocí hašovacích funkcí skryjte skutečné výstupní hodnoty PRNG. Použijte výsledky hashovací funkce z výstupních hodnot PRNG namísto hodnot samotných, abyste zabránili přímým kryptoanalytickým útokům. Tato technika, i když nezaručuje úplnou bezpečnost, činí systém spolehlivějším.
Hash zdroje entropie pomocí časových značek, hodnot čítačů nebo jiných neustále se měnících hodnot. Hašování zdroje entropie nějakou neustále se měnící hodnotou před vstupem do PRNG je schopno chránit systém před útoky založenými na vstupu.
Pravidelně měňte vnitřní stav PRNG. Čas od času zcela změňte vnitřní stav PRNG. To pomůže bránit se útokům na základě odhalení vnitřního stavu nebo alespoň snížit poškození způsobené úspěšným útokem.

Viz také

Generátor pseudonáhodných čísel

Poznámky

↑ Náhodnost a prohlížeč Netscape . Získáno 9. prosince 2011. Archivováno z originálu dne 22. května 2016. (neurčitý)
↑ Kryptoanalýza generátoru náhodných čísel operačního systému Windows, Leo Dorrendorf (odkaz není k dispozici) . Získáno 9. prosince 2011. Archivováno z originálu dne 6. září 2012. (neurčitý)
↑ Microsoft potvrzuje, že XP obsahuje chybu generátoru náhodných čísel Archivováno 22. června 2008.
↑ Doporučení pro generování náhodných čísel pomocí deterministických generátorů náhodných bitů, speciální publikace NIST 800-90 Archivováno 26. 9. 2007 .
↑ Dala NSA do nového šifrovacího standardu tajná zadní vrátka?
↑ O možnosti zadních vrátek v NIST SP800-90 Dual Ec Prng . Datum přístupu: 9. prosince 2011. Archivováno z originálu 26. února 2014. (neurčitý)
↑ Bezpečnostní chyba Debian OpenSSL . Získáno 9. prosince 2011. Archivováno z originálu 6. září 2018. (neurčitý)

Literatura

Randomness and the Netscape Browser , Ian Goldberg a David Wagner, Dr. Dobb's Journal , leden 1996, str. 66-70.
Kelsey J. , Schneier B. , Wagner D. A. , hala C. Kryptoanalytické útoky na generátory pseudonáhodných čísel // Rychlé softwarové šifrování :, FSE' 98 Paříž, Francie, 23.–25. března 1998 sborník / Berlín S Vaudenay - Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 1998. - S. 168-188. - ( Lecture Notes in Computer Science ; Vol. 1372) - ISBN 978-3-540-64265-7 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-69710-1_12
Analýza linuxového generátoru náhodných čísel Zvi Gutterman, Benny Pinkas a Tzachy Reinman v IEEE S&P (Oakland Conference), květen 2006, str. 371-385.
Požadavky na náhodnost pro bezpečnost. D. Eastlake, J. Schiller, S. Crocker, RFC 4086 (zastaralé RFC1750), 2006.
Doporučení pro generování náhodných čísel pomocí deterministických generátorů náhodných bitů , Elaine Barker a John Kelsey, speciální publikace NIST 800-90. březen 2007