Algoritmus řebříčku

Algoritmus Yarrow je kryptograficky bezpečný generátor pseudonáhodných čísel . Jako název byl zvolen řebříček , jehož sušené natě slouží jako zdroj entropie při věštění [1] .

Algoritmus vyvinuli v srpnu 1999 Bruce Schneier , John Kelsey a Niels Ferguson z Counterpane Internet Security.[2] . Algoritmus není patentovaný a bez licenčních poplatků ak jeho použití není vyžadována žádná licence. Yarrow je zahrnut v únoru2002 sFreeBSD, OpenBSD a Mac OS X jako implementace zařízení /dev/random [3] .

Dalším vývojem Yarrowa bylo vytvoření algoritmu Fortuna od Ferguse a Schneiera , popsaného v jejich knize „Practical Cryptography“ [4] .

Potřeba algoritmu

Většina moderních kryptografických aplikací používá náhodná čísla. Jsou potřeba ke generování klíčů , získávání jednorázových náhodných čísel , vytváření soli atd. Pokud jsou náhodná čísla nebezpečná, pak to znamená výskyt zranitelností v aplikacích, které nelze uzavřít pomocí různých algoritmů a protokolů [5] .

V roce 1998 provedli tvůrci Yarrow výzkum dalších PRNG a identifikovali v nich řadu zranitelností. Sekvence náhodných čísel, které produkovaly, nebyly bezpečné pro kryptografické aplikace [5] .

V současné době je algoritmus Yarrow vysoce bezpečný generátor pseudonáhodných čísel. To vám umožňuje používat jej pro širokou škálu úkolů: šifrování , elektronický podpis , integrita informací atd. [5] .

Principy designu

Při vývoji algoritmu se tvůrci zaměřili na následující aspekty [6] :

Rychlost a efektivita . Žádný z vývojářů nepoužije algoritmus, který výrazně zpomaluje aplikaci.
Jednoduchost . Každý programátor bez větších znalostí kryptografie by jej měl umět bezpečně používat.
Optimalizace . Pokud je to možné, algoritmus by měl používat již existující bloky instrukcí.

Struktura algoritmu

Komponenty

Algoritmus Yarrow se skládá ze 4 nezávislých částí [7] :

Akumulátor entropie . Sbírá vzorky ze zdrojů entropie a dává je do dvou bazénů.
mechanismus komplikací . Periodicky komplikuje klíč generátoru pomocí entropie z poolů.
generační mechanismus . Generuje výstupní signály PRNG z hardwarového klíče.
Mechanismus řízení komplikací . Určuje dobu běhu komplikace.

Entropický akumulátor

Akumulace entropie je proces , při kterém PRNG získává nový, nepředvídatelný vnitřní stav [8] . V tomto algoritmu je entropie akumulována ve dvou poolech : rychle a pomalu [9] . V tomto kontextu je fond úložištěm inicializovaných bitů připravených k použití. Rychlý fond přináší časté klíčové komplikace . Tím je zajištěno, že kompromis klíče má krátké trvání. Pomalý fond poskytuje vzácné, ale významné klíčové komplikace. To je nezbytné pro zajištění bezpečné komplikace i v případech, kdy jsou odhady entropie značně nadhodnoceny. Vstupní vzorky jsou střídavě odesílány do rychlého a pomalého fondu [10] .

Mechanismus komplikací

Komplikační mechanismus propojuje ukládání entropie s mechanismem generování. Když mechanismus řízení složitosti určí, že je potřeba složitost, pak modul složitosti využívající informace z jednoho nebo obou fondů, aktualizuje klíč, který používá mechanismus generování. Pokud tedy útočník nezná aktuální klíč nebo fondy, bude mu klíč po komplikaci neznámý. Je také možné, že složitost bude vyžadovat velké množství zdrojů , aby se minimalizoval úspěch útoku na základě hádání vstupních hodnot [11] .

Ke generování nového klíče používá složitost rychlého fondu aktuální klíč a hodnoty hash všech vstupů rychlého fondu od poslední složitosti klíče. Jakmile je toto provedeno, odhaduje se entropiepro rychlý fond bude nastaven na nulu [11] [12] .

Komplikace pomalého fondu používá aktuální klíč a hash rychlých a pomalých vstupů fondu. Po vygenerování nového klíče se odhady entropie pro oba fondy vynulují [13] .

Generační mechanismus

Mechanismus generování dává výstupu sekvenci pseudonáhodných čísel. Musí být takové, aby útočník, který nezná klíč generátoru, jej nemohl odlišit od náhodné bitové sekvence .[14] .

Generovací mechanismus by měl mít následující vlastnosti [15] :

odolnost vůči kryptografickým útokům ;
produktivita ( anglicky Efficiency );
schopnost generovat velmi dlouhou sekvenci signálů bez komplikací;
odolnost proti útokům hrubou silou s backtrackingem ( angl. Backtracking ) poté , co byl klíč kompromitován .

Mechanismus řízení komplikací

Aby bylo možné zvolit dobu propracovanosti, musí kontrolní mechanismus zohlednit různé faktory. Například příliš častá změna klíče zvyšuje pravděpodobnost iterativního útoku [16] . Příliš pomalé naopak poskytuje více informací útočníkovi, který kompromitoval klíč. Proto musí být kontrolní mechanismus schopen najít střední cestu mezi těmito dvěma podmínkami [17] .

Jak vzorky dorazí do každého bazénujsou uloženy odhady entropie pro každý zdroj. Jakmile tento odhad pro jakýkoli zdroj dosáhne limitní hodnoty, nastává komplikace z rychlého poolu. V naprosté většině systémů se to děje mnohokrát za hodinu. Komplikace z pomalého fondu nastává, když skóre pro kterýkoli ze zdrojů v pomalém fondu překročí práh [17] . $k$ $n$

V Yarrow-160 je tento limit 100 bitů pro rychlý fond a 160 bitů pro pomalý fond. Ve výchozím nastavení musí být alespoň dva různé zdroje v pomalém fondu větší než 160 bitů, aby z pomalého fondu nastala komplikace [18] .

Řebříček 160

Jednou z možných implementací Yarrow algoritmu je Yarrow-160. Hlavní myšlenkou tohoto algoritmu je použití jednosměrné hašovací funkce a blokové šifry [19] . Pokud jsou oba algoritmy bezpečné a PRNG obdrží dostatek počáteční entropie , pak výsledkem bude silná sekvence pseudonáhodných čísel [20] . $h()$ $E_{K}()$

Hašovací funkce musí mít následující vlastnosti [21] :

být nevratný, to znamená odolný vůči restaurování prototypu ;
být odolný proti kolizím ;
dát výstupu -bit. $m$

Yarrow-160 používá algoritmus SHA-1 jako [19] . $h()$

Bloková šifra musí mít následující vlastnosti [22] :

mít klíč o délce -bitů a datový blok o délce -bitů; $k$ $n$
být odolný vůči otevřenému textu a vybraným textovým útokům ;
mají dobré statistické vlastnosti výstupních signálů, dokonce i s vysoce templátovanými vstupními signály.

Yarrow-160 používá algoritmus 3-KEY Triple DES jako [19] . $E_{K}()$

Generace

Generátor je založen na použití blokové šifry v režimu čítače (viz obr. 2) [23] .

Existuje n-bitová hodnota čítače . Pro vygenerování dalších -bitů pseudonáhodné sekvence se čítač zvýší o 1 a zašifruje se blokovou šifrou pomocí klíče [24] : $C$ $n$ $C$ $K$

C\leftarrow (C+1){\bmod {2}}^{n}

R\leftarrow E_{K}(C)

kde je výstup PRNG a je aktuální hodnota klíče . $R$ $K$

Pokud je v určitém okamžiku klíč kompromitován , je nutné zabránit úniku předchozích výstupních hodnot, které může útočník získat. Tento mechanismus generování nemá ochranu proti útokům tohoto druhu, takže se dodatečně počítá počet výstupních bloků PRNG. Jakmile je dosaženo určitého limitu ( nastavení zabezpečení systému ${\displaystyle P_{g))$ , ), pak se vygeneruje -bitový výstup PRNG, který se pak použije jako nový klíč [15] . ${\displaystyle 1\leq P_{g}\leq 2^{n/3))$ $k$

K\leftarrow {\text{dalších k PRNG výstupních bitů))

V Yarrow-160 je to 10. Tento parametr je záměrně nastaven na nízkou hodnotu, aby se minimalizoval počet výstupů, které lze naučit pomocí backtracking attack [ 25 ] . ${\displaystyle P_{g))$

Komplikace

Doba provedení mechanismu komplikací závisí na parametru . Tento parametr lze nastavit pevně nebo dynamicky změnit [26] . $P_{t}\geq 0$

Tento mechanismus se skládá z následujících kroků [26] :

Akumulátor entropie vypočítá hash všech položek v rychlém fondu. Výsledek tohoto výpočtu je označen . ${\displaystyle v_{0))$
Nechte _ $v_{i}:=h(v_{i-1}|v_{0}|i)~{\text{ for }}~i=1,\ldots ,t$
$K\leftarrow h^{'}(h(v_{P_{t))|K),k)$ .
$C\leftarrow E_{K}(0)$ .
Resetujte všechny čítače entropie v poolech na 0.
Vymažte paměť, která ukládá mezilehlé hodnoty.
Pokud je použit počáteční soubor , přepište obsah tohoto souboru dalšími bity výstupu pseudonáhodné sekvence . $2k$

Funkce je definována pomocí funkce takto [27] : $h^{'}$ $h$

s_{0}:=m

s_{i}:=h(s_{0}|\ldots |s_{i-1}),\ \ {\text{where))\ \ i=1,\ldots

h^{'}(m,k):={\text{firsts))\ \ k\ \ {\text{bits))\;(s_{0}|s_{1}|\ldots )

Ve skutečnosti je to funkce přizpůsobení velikosti, to znamená, že převádí vstup libovolné délky na výstup zadané délky. Pokud vstup přijal více dat, než se očekávalo, funkce vezme úvodní bity. Pokud jsou velikosti vstupu a výstupu stejné, pak je funkce funkcí identity . Pokud je velikost vstupních dat menší, než se očekávalo, jsou pomocí této hashovací funkce generovány další bity . Jedná se o výpočetně poměrně nákladný algoritmus PRNG, ale pro malé velikosti jej lze bez problémů použít [28] .

Nastavení nové hodnoty čítače se neprovádí z bezpečnostních důvodů, ale pro zajištění větší flexibility implementace a zachování kompatibility mezi různými implementacemi [26] . $C$

Nevyřešené problémy a plány do budoucna

V dnešní implementaci algoritmu Yarrow-160 velikost bazénůakumulace entropie je omezena na 160 bitů. Je známo, že útoky na algoritmus 3-KEY Triple DES jsou účinnější než vyčerpávající vyhledávání . I u brute-force backtracking útoků se však klíče mění poměrně často a k zajištění bezpečnosti v praxi stačí 160 bitů [29] .

Předmětem pokračujícího výzkumu je zlepšování mechanismů odhadu entropie. Podle tvůrců Yarrow-160 může být algoritmus zranitelný právě kvůli špatným odhadům entropie, a ne z hlediska kryptoanalýzy [30] .

Tvůrci mají do budoucna plány na využití nového standardu blokové šifry AES . Nová bloková šifra může snadno zapadnout do základního návrhu algoritmu Yarrow. Jak však vývojáři zdůrazňují, bude nutné buď změnit hashovací funkci složitosti, nebo přijít s novou hashovací funkcí, která zajistí zaplnění entropického fondu více než 160 bity. U AES se 128 bity to nebude problém, ale u AES se 192 nebo 256 bity bude nutné tento problém vyřešit. Je třeba poznamenat, že základní strukturou Yarrow algoritmu je kombinace blokové šifry AES a 256bitové hashovací funkce [31] .

Soubor pravidel pro mechanismus zvládání komplikací je zatím provizorní, nicméně další studie jej může zlepšit. Z tohoto důvodu je předmětem probíhajícího výzkumu [30] .

Poznámky

↑ Kelsey, Schneier, Ferguson, 2000 , str. 29.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 13.
↑ Murray, 2002 , str. 47.
↑ Ferguson, Schneier, 2004 , str. 183.
↑ 1 2 3 Schneier o bezpečnosti. Otázky a odpovědi o řebříčku . Datum přístupu: 1. prosince 2016. Archivováno z originálu 11. listopadu 2016.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 15-16.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 18-21.
↑ Shcherbakov, Domashev, 2003 , str. 232.
↑ Viega, 2003 , str. 132.
↑ Ferguson, Schneier, 2004 , str. 189-193.
↑ 1 2 Ščerbakov, Domašev, 2003 , str. 234-235.
↑ Ferguson, Schneier, 2004 , str. 234-235.
↑ Shcherbakov, Domashev, 2003 , str. 191-193.
↑ Ferguson, Schneier, 2004 , str. 183-184.
↑ 1 2 Ferguson, Schneier, 2004 , str. 183-185.
↑ Kelsey, Schneier, Wagner a kol., 1998 , str. 172.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , str. 22.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 28.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , str. 23.
↑ Ferguson, Schneier, 2004 , str. 202.
↑ Schneier, 1996 , str. 55-57.
↑ Shcherbakov, Domashev, 2003 , str. 236.
↑ Ferguson, Schneier, 2004 , str. 95-96,183-186.
↑ Ferguson, Schneier, 2004 , str. 95-96,183-188.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 25.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , str. 26-27.
↑ Kelsey, Schneier, Ferguson, 2000 , str. 27.
↑ Ferguson, Schneier, 2004 , str. 188-189.
↑ Kelsey, Schneier, Wagner a kol., 1998 , str. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , str. 28-29.
↑ Ferguson, Schneier, 2004 , str. 109-111.

Literatura

v Rusku

Shcherbakov, L. Yu. , Domashev, A. V. Aplikovaná kryptografie. Využití a syntéza kryptografických rozhraní. - Ruské vydání, 2003. - 416 s. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Praktická kryptografie. - Williams Publishing House, 2004. - 432 s. — ISBN 5-8459-0733-0.

v angličtině

Schneier, B. Aplikovaná kryptografie. - John Wiley & Sons, 1996. - 784 s. - ISBN 978-1-119-09672-6 .
Agnew G. Random Sources for Cryptographic Systems // Advances in Cryptology - EUROCRYPT '87 :Workshop on the Theory and Application of Cryptographic Techniques Amsterdam, Nizozemsko, 13.–15. dubna 1987 sborník / D. Chaum , W. L. Price - Springer Science + Obchodní média , 1988. - S. 77-81. — 316 s. — ISBN 978-3-540-19102-5 — doi:10.1007/3-540-39118-5_8
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
Kelsey J. , Schneier B. , Ferguson N. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator // Selected Areas in Cryptography :, SAC'99 Kingston, Ontario, Canada, August 9-10, 1999 Proceedings / H. M. Heys , C. Adams - Berlin , Heidelberg , New York, NY , London [atd.] : Springer Berlin Heidelberg , 2000. - S. 13-33. - ( Lecture Notes in Computer Science ; Vol. 1758) - ISBN 978-3-540-67185-5 - ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-46513-8_2
Murray, Mark RV Implementace Yarrow PRNG pro FreeBSD // BSDC'02 Sborník konference BSD 2002 o konferenci BSD. - USENIX, 2002. - S. 47-53 . - ISBN 1-880446-02-2 .
Viega J. Praktické generování náhodných čísel v softwaru (anglicky) // 19. výroční konference počítačových bezpečnostních aplikací (ACSAC) 2003, 8.–12. prosince 2003, Las Vegas, NV, (USA) - IEEE Computer Society , 2003. - S. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318

Odkazy

Yarrow – Algorithm page na webových stránkách B. Schneiera (anglicky)