Yarrow algoritmi

Yarrow - algoritmi on kryptografisesti turvallinen pseudosatunnaislukugeneraattori . Nimeksi valittiin Siankärsämö , jonka kuivatut varret toimivat ennustamisen entropian lähteenä [1] .

Algoritmin kehittivät elokuussa 1999 Bruce Schneier , John Kelsey ja Nils Ferguson Counterpane Internet Securitysta.[2] . Algoritmi ei ole patentoitu ja rojaltivapaa, eikä sen käyttö vaadi lisenssiä . Yarrow sisältyy helmikuussa2002 FreeBSD :n , OpenBSD : n ja Mac OS X :n kanssa toteutuksena /dev/random [3] -laitteeseen .

Yarrow'n jatkokehitys oli Fergusin ja Schneierin luoma Fortuna-algoritmi , joka on kuvattu kirjassaan "Practical Cryptography" [4] .

Algoritmin tarve

Useimmat nykyaikaiset salaussovellukset käyttävät satunnaislukuja. Niitä tarvitaan avainten luomiseen , kertaluonteisten satunnaislukujen hankkimiseen , suolan luomiseen jne. Jos satunnaisluvut eivät ole turvallisia, tämä aiheuttaa haavoittuvuuksien ilmaantumista sovelluksissa, joita ei voida sulkea erilaisilla algoritmeilla ja protokollilla [5] .

Vuonna 1998 Yarrow'n luojat suorittivat tutkimusta muista PRNG:istä ja tunnistivat niissä useita haavoittuvuuksia. Niiden tuottamat satunnaislukusekvenssit eivät olleet turvallisia salaussovelluksiin [5] .

Tällä hetkellä Yarrow-algoritmi on erittäin turvallinen pseudosatunnaislukugeneraattori. Tämän ansiosta voit käyttää sitä monenlaisiin tehtäviin: salaukseen , sähköiseen allekirjoitukseen , tiedon eheyteen jne. [5] .

Suunnitteluperiaatteet

Algoritmia kehitettäessä tekijät keskittyivät seuraaviin näkökohtiin [6] :

Nopeus ja tehokkuus . Kukaan kehittäjistä ei käytä algoritmia, joka hidastaa suuresti sovellusta.
Yksinkertaisuus . Jokaisen ohjelmoijan, jolla ei ole paljoakaan tietoa kryptografiasta, pitäisi pystyä käyttämään sitä turvallisesti.
Optimointi . Mikäli mahdollista, algoritmin tulee käyttää jo olemassa olevia käskylohkoja.

Algoritmin rakenne

Komponentit

Yarrow-algoritmi koostuu 4 itsenäisestä osasta [7] :

Entropiaakku . Kerää näytteitä entropialähteistä ja sijoittaa ne kahteen pooliin.
komplikaatiomekanismi . Monimutkaistaa generaattoriavainta ajoittain käyttämällä poolien entropiaa.
sukupolven mekanismi . Luo PRNG - lähtösignaaleja donglesta.
Komplikaatioiden hallintamekanismi . Määrittää komplikaation suoritusajan.

Entropiaakku

Entropian kerääntyminen on prosessi , jossa PRNG saa uuden arvaamattoman sisäisen tilan [8] . Tässä algoritmissa entropia kertyy kahteen pooliin : nopea ja hidas [9] . Tässä yhteydessä pooli on alustettujen ja käyttövalmiiden bittien varasto. Nopea allas tarjoaa usein keskeisiä komplikaatioita . Tämä varmistaa, että avainkompromissi on lyhytkestoinen. Hidas allas tarjoaa harvinaisia, mutta merkittäviä avainkomplikaatioita. Tämä on tarpeen, jotta varmistetaan turvallinen komplikaatio myös tapauksissa, joissa entropiaestimaatit ovat suuresti yliarvioituja. Syöttönäytteet lähetetään vuorotellen nopeille ja hitaille poolille [10] .

Komplikaatiomekanismi

Komplikaatiomekanismi yhdistää entropiavaraston generointimekanismiin. Kun monimutkaisuuden ohjausmekanismi määrittää, että monimutkaisuutta tarvitaan, monimutkaisuusmoottori käyttää tietoja toisesta tai molemmista poolista, päivittää avaimen, jota sukupolvimekanismi käyttää. Siten, jos hyökkääjä ei tiedä nykyistä avainta tai pooleja, avain on hänelle tuntematon komplikaatioiden jälkeen. On myös mahdollista, että monimutkaisuus vaatii paljon resursseja hyökkäyksen onnistumisen minimoimiseksi syötearvojen arvaamisen perusteella [11] .

Uuden avaimen luomiseksi nopea poolin monimutkaisuus käyttää nykyistä avainta ja kaikkien nopean poolin syötteiden hajautusarvoja edellisen avaimen monimutkaisuuden jälkeen. Kun tämä on tehty, entropia arvioinopea pooli asetetaan nollaan [11] [12] .

Hitaan poolin komplikaatio käyttää nykyistä avainta ja nopean ja hitaan poolin syötteiden hajautusarvoja. Uuden avaimen luomisen jälkeen kummankin poolin entropiaarviot nollataan [13] .

Sukupolvimekanismi

Generointimekanismi antaa ulostulolle näennäissatunnaisten lukujen sarjan. Sen on oltava sellainen, että hyökkääjä, joka ei tiedä generaattoriavainta, ei voi erottaa sitä satunnaisesta bittisekvenssistä .[14] .

Generointimekanismilla tulisi olla seuraavat ominaisuudet [15] :

vastustuskyky kryptografisia hyökkäyksiä vastaan ;
tuottavuus ( Englanti Efficiency );
kyky tuottaa erittäin pitkä signaalisarja ilman komplikaatioita;
kestävyys raa'an voiman hyökkäyksiä vastaan backtracking ( eng. Backtracking ) jälkeen , kun avain on vaarantunut .

Komplikaatioiden hallintamekanismi

Kehittymisajan valitsemiseksi ohjausmekanismissa on otettava huomioon useita tekijöitä. Esimerkiksi avaimen vaihtaminen liian usein tekee iteratiivisesta arvaushyökkäyksestä todennäköisemmän [16] . Liian hidas päinvastoin antaa enemmän tietoa avaimen vaarantaneelle hyökkääjälle. Siksi ohjausmekanismin on kyettävä löytämään keskitie näiden kahden ehdon välillä [17] .

Kun näytteet saapuvat jokaiseen pooliinkunkin lähteen entropiaarviot tallennetaan. Heti kun tämä arvio jonkin lähteen osalta saavuttaa raja-arvon, nopea pooli aiheuttaa ongelmia. Suurimmassa osassa järjestelmiä tämä tapahtuu useita kertoja tunnissa. Hitaan poolin aiheuttama komplikaatio syntyy, kun jonkin hitaan poolin lähteen pisteet ylittävät kynnyksen [ 17] . $k$ $n$

Yarrow-160:ssä tämä raja on 100 bittiä nopealle poolille ja 160 bittiä hitaalle. Oletusarvon mukaan vähintään kahden eri lähteen hitaassa poolissa on oltava yli 160 bittiä, jotta hitaan poolin aiheuttamia komplikaatioita esiintyy [18] .

Yarrow 160

Yksi mahdollinen Yarrow-algoritmin toteutus on Yarrow-160. Tämän algoritmin pääideana on yksisuuntaisen hash-funktion ja lohkosalauksen käyttö [19] . Jos molemmat algoritmit ovat turvallisia ja PRNG saa tarpeeksi alkuentropiaa , tuloksena on vahva pseudosatunnaislukujen sarja [20] . $h()$ $E_{K}()$

Hajautusfunktiolla on oltava seuraavat ominaisuudet [21] :

olla peruuttamaton, toisin sanoen vastustuskykyinen prototyypin palauttamiselle ;
kestää törmäyksiä ;
anna tulos -bitti. $m$

Yarrow-160 käyttää SHA-1 - algoritmia [19] . $h()$

Lohkosalauksella on oltava seuraavat ominaisuudet [22] :

on avain, jonka pituus on -bittiä, ja datalohko, jonka pituus on -bittiä; $k$ $n$
vastustaa selkeän tekstin ja valitun tekstin hyökkäyksiä ;
niillä on hyvät lähtösignaalien tilastolliset ominaisuudet jopa erittäin mallinetuilla tulosignaaleilla.

Yarrow-160 käyttää 3-KEY Triple DES -algoritmia [ 19] . $E_{K}()$

Sukupolvi

Generaattori perustuu lohkosalauksen käyttöön laskuritilassa (katso kuva 2) [23] .

Siellä on n-bittinen laskuriarvo . Pseudosatunnaisen sekvenssin seuraavien -bittien luomiseksi laskuria kasvatetaan 1:llä ja se salataan lohkosalauksella avaimella [24] : $C$ $n$ $C$ $K$

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

R\leftarrow E_{K}(C)

missä on PRNG : n lähtö ja avaimen nykyinen arvo . $R$ $K$

Jos jossain vaiheessa avain vaarantuu , on välttämätöntä estää hyökkääjän saamien aikaisempien lähtöarvojen vuotaminen. Tällä sukupolvimekanismilla ei ole suojaa tällaisia hyökkäyksiä vastaan, joten PRNG-lähtölohkojen määrä lasketaan lisäksi. Heti kun tietty raja saavutetaan ( järjestelmän suojausasetus ${\displaystyle P_{g))$ , ), sitten generoidaan -bittinen PRNG-lähtö, jota käytetään sitten uutena avaimena [15] . ${\displaystyle 1\leq P_{g}\leq 2^{n/3))$ $k$

K\leftarrow {\text{seuraava k PRNG-lähtöbittiä))

Yarrow-160: ssä se on 10. Tämä parametri on asetettu tarkoituksella alhaiseksi, jotta voidaan minimoida niiden lähtöjen määrä, jotka voidaan oppia käyttämällä backtracking - hyökkäystä [ 25 ] . ${\displaystyle P_{g))$

Komplikaatio

Komplikaatiomekanismin suoritusaika riippuu parametrista . Tämä parametri voidaan vahvistaa tai muuttaa dynaamisesti [26] . $P_{t}\geq 0$

Tämä mekanismi koostuu seuraavista vaiheista [26] :

Entropiakeräin laskee kaikkien nopean poolin merkintöjen tiivisteen. Tämän laskelman tulos on merkitty . ${\displaystyle v_{0))$
Anna . $v_{i}:=h(v_{i-1}|v_{0}|i)~{\text{ }}~i=1,\ldots ,t$
$K\leftarrow h^{'}(h(v_{P_{t))|K),k)$ .
$C\leftarrow E_{K}(0)$ .
Nollaa kaikki poolien entropialaskurit nollaan.
Tyhjennä väliarvot tallentava muisti.
Jos siementiedostoa käytetään , kirjoita tämän tiedoston sisältö päälle pseudosatunnaissekvenssin tulosteen seuraavilla biteillä . $2k$

Funktio määritellään funktiona seuraavasti [27] : $h^{'}$ $h$

s_{0}:=m

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

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

Itse asiassa se on koon mukautusfunktio, eli se muuntaa minkä tahansa pituisen syötteen tietynpituiseksi ulostuloksi. Jos tulo vastaanotti odotettua enemmän dataa, funktio ottaa johtavat bitit. Jos tulon ja lähdön koot ovat samat, funktio on identiteettifunktio . Jos syötetyn datan koko on odotettua pienempi, tämän hash-funktion avulla luodaan lisäbittejä . Tämä on laskennallisesti melko kallis PRNG-algoritmi, mutta pienissä kooissa sitä voidaan käyttää ongelmitta [28] .

Uuden arvon asettaminen laskuriin ei ole tehty turvallisuussyistä, vaan paremman toteutuksen joustavuuden takaamiseksi ja yhteensopivuuden ylläpitämiseksi eri toteutusten välillä [26] . $C$

Ratkaisemattomia ongelmia ja tulevaisuuden suunnitelmia

Nykypäivän Yarrow-160-algoritmin toteutuksessa altaiden kokoentropian kerääntyminen on rajoitettu 160 bittiin. Hyökkäykset 3-KEY Triple DES -algoritmia vastaan tiedetään olevan tehokkaampia kuin tyhjentävä haku . Kuitenkin jopa brute-force backtracking -hyökkäyksissä avaimet vaihtuvat melko usein ja 160 bittiä riittää varmistamaan turvallisuuden käytännössä [29] .

Meneillään olevan tutkimuksen aiheena on entropian estimointimekanismien parantaminen. Yarrow-160:n tekijöiden mukaan algoritmi voi olla haavoittuva juuri huonojen entropiaestimaattien takia, ei krypta -analyysin kannalta [30] .

Tekijillä on tulevaisuuden suunnitelmissa uuden AES-lohkosalausstandardin käyttäminen . Uusi lohkosalaus sopii helposti Yarrow-algoritmin perussuunnitteluun. Kuitenkin, kuten kehittäjät korostavat, on tarpeen joko muuttaa monimutkaisuuden hash-funktiota tai keksiä uusi hash-funktio sen varmistamiseksi, että entropiapooli on täynnä yli 160 bittiä. 128 bitin AES:lle tämä ei ole ongelma, mutta 192 tai 256 bitin AES :lle tämä ongelma on ratkaistava. On huomattava, että Yarrow-algoritmin perusrakenne on AES-lohkosalauksen ja 256-bittisen hash-funktion yhdistelmä [31] .

Komplikaatioiden hallintamekanismin säännöt ovat vielä alustavia, mutta lisätutkimukset voivat parantaa sitä. Tästä syystä se on jatkuvan tutkimuksen kohteena [30] .

Muistiinpanot

↑ Kelsey, Schneier, Ferguson, 2000 , s. 29.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 13.
↑ Murray, 2002 , s. 47.
↑ Ferguson, Schneier, 2004 , s. 183.
↑ 1 2 3 Schneier turvallisuudesta. Kysymyksiä ja vastauksia Yarrowsta . Käyttöpäivä: 1. joulukuuta 2016. Arkistoitu alkuperäisestä 11. marraskuuta 2016.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 15-16.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 18-21.
↑ Shcherbakov, Domashev, 2003 , s. 232.
↑ Viega, 2003 , s. 132.
↑ Ferguson, Schneier, 2004 , s. 189-193.
↑ 1 2 Shcherbakov, Domashev, 2003 , s. 234-235.
↑ Ferguson, Schneier, 2004 , s. 234-235.
↑ Shcherbakov, Domashev, 2003 , s. 191-193.
↑ Ferguson, Schneier, 2004 , s. 183-184.
↑ 1 2 Ferguson, Schneier, 2004 , s. 183-185.
↑ Kelsey, Schneier, Wagner et ai., 1998 , s. 172.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , s. 22.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 28.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , s. 23.
↑ Ferguson, Schneier, 2004 , s. 202.
↑ Schneier, 1996 , s. 55-57.
↑ Shcherbakov, Domashev, 2003 , s. 236.
↑ Ferguson, Schneier, 2004 , s. 95-96,183-186.
↑ Ferguson, Schneier, 2004 , s. 95-96,183-188.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 25.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , s. 26-27.
↑ Kelsey, Schneier, Ferguson, 2000 , s. 27.
↑ Ferguson, Schneier, 2004 , s. 188-189.
↑ Kelsey, Schneier, Wagner et ai., 1998 , s. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , s. 28-29.
↑ Ferguson, Schneier, 2004 , s. 109-111.

Kirjallisuus

venäjäksi

Shcherbakov, L. Yu. , Domashev, A. V. Sovellettu kryptografia. Salausrajapintojen käyttö ja synteesi. - Venäjän painos, 2003. - 416 s. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Practical Cryptography. - Williams Publishing House, 2004. - 432 s. — ISBN 5-8459-0733-0.

englanniksi

Schneier, B. Applied Cryptography. - 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, Alankomaat, 13.–15. huhtikuuta 1987 Proceedings / D. Chaum , W. L. Price - Springer Science + Business Media , 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. , Hall C. Salausanalyysit näennäissatunnaisten numerogeneraattoreiden kimppuun // Fast Software Encryption :, FSE' 98 Paris, Ranska , 23.–25. maaliskuuta 1998, Berliini Proceedings / S Vaudenay Heidelberg , New York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 1998. - P. 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: Huomautuksia Yarrow-salauksen pseudosatunnaislukugeneraattorin suunnittelusta ja analysoinnista // Valitut alueet kryptografiassa :, SAC'99 Kingston, Ontario, Kanada, elokuu 9-10, 1999 Proceedings / H. M. Heys , C. Adams - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 2000. - P. 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 Yarrow PRNG:n toteutus FreeBSD:lle // BSDC'02 Proceedings of the BSD Conference 2002 on BSD Conference. - USENIX, 2002. - S. 47-53 . - ISBN 1-880446-02-2 .
Viega J. Practical Random Number Generation in Software (englanniksi) // 19th Annual Computer Security Applications Conference (ACSAC) 2003, 8.-12. joulukuuta 2003, Las Vegas, NV, (USA) - IEEE Computer Society , 2003. - P. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318

Linkit

Yarrow - Algoritmisivu B. Schneierin verkkosivustolla (englanniksi)