Røllike algoritme

Yarrow - algoritmen er en kryptografisk sikker generator af pseudo-tilfældige tal . Røllike blev valgt som navn , hvis tørrede stængler tjener som en kilde til entropi i spådomskunst [1] .

Algoritmen blev udviklet i august 1999 af Bruce Schneier , John Kelsey og Niels Ferguson fra Counterpane Internet Security.[2] . Algoritmen er ikke patenteret og royaltyfri , og der kræves ingen licens for at bruge den. Yarrow er inkluderet i februar2002 med FreeBSD , OpenBSD og Mac OS X somen implementering af /dev/random [3] enheden .

Yarrows videre udvikling var Fergus og Schneiers skabelse af Fortuna-algoritmen , beskrevet i deres bog "Praktisk kryptografi" [4] .

Behovet for en algoritme

De fleste moderne kryptografiske applikationer bruger tilfældige tal. De er nødvendige for at generere nøgler , opnå engangs-tilfældige tal , skabe et salt osv. Hvis tilfældige tal er usikre, medfører dette tilsynekomsten af sårbarheder i applikationer, der ikke kan lukkes ved hjælp af forskellige algoritmer og protokoller [5] .

I 1998 foretog skaberne af Yarrow forskning i andre PRNG'er og identificerede en række sårbarheder i dem. De tilfældige talsekvenser, de producerede, var ikke sikre til kryptografiske applikationer [5] .

I øjeblikket er Yarrow-algoritmen en meget sikker pseudo-tilfældig talgenerator. Dette giver dig mulighed for at bruge det til en lang række opgaver: kryptering , elektronisk signatur , informationsintegritet osv. [5] .

Designprincipper

Under udviklingen af algoritmen fokuserede skaberne på følgende aspekter [6] :

Hastighed og effektivitet . Ingen af udviklerne vil bruge en algoritme, der i høj grad bremser applikationen.
Enkelhed . Enhver programmør uden meget viden om kryptografi burde være i stand til at bruge det sikkert.
Optimering . Hvor det er muligt, skal algoritmen bruge allerede eksisterende instruktionsblokke.

Algoritmestruktur

Komponenter

Røllike-algoritmen består af 4 uafhængige dele [7] :

Entropiakkumulator . Indsamler prøver fra entropikilder og lægger dem i to puljer.
komplikationsmekanisme . Periodisk komplicerer generatornøglen ved hjælp af entropi fra puljer.
generationsmekanisme . Genererer PRNG- udgangssignaler fra donglen.
Komplikationshåndteringsmekanisme . Angiver køretiden for komplikationen.

Entropiakkumulator

Entropiakkumulering er en proces, hvor en PRNG opnår en ny, ufattelig indre tilstand [8] . I denne algoritme akkumuleres entropi i to puljer : hurtig og langsom [9] . I denne sammenhæng er en pulje et lager af initialiserede og klar-til-brug bits. Hurtig pool giver hyppige nøglekomplikationer . Dette sikrer, at nøglekompromis har en kort varighed. Den langsomme pool giver sjældne, men betydelige nøglekomplikationer. Dette er nødvendigt for at sikre, at der opnås en sikker komplikation, selv i tilfælde, hvor entropi-estimaterne er stærkt overvurderet. Indgangsprøverne sendes skiftevis til de hurtige og langsomme puljer [10] .

Komplikationsmekanisme

Komplikationsmekanismen forbinder entropilageret med genereringsmekanismen. Når kompleksitetskontrolmekanismen bestemmer, at kompleksitet er nødvendig, så bruger kompleksitetsmotoren information fra en eller begge puljer, opdaterer nøglen, der bruges af genereringsmekanismen. Således, hvis angriberen ikke kender den aktuelle nøgle eller puljer, så vil nøglen være ukendt for ham efter komplikation. Det er også muligt, at kompleksiteten vil kræve en stor mængde ressourcer for at minimere succesen af et angreb baseret på at gætte inputværdierne [11] .

For at generere en ny nøgle bruger den hurtige poolkompleksitet den aktuelle nøgle og hasherne for alle de hurtige poolinputs siden den sidste nøglekompleksitet. Når dette er gjort, estimerer entropienfor den hurtige pool vil blive sat til nul [11] [12] .

Den langsomme pool-komplikation bruger den aktuelle nøgle og hasherne for de hurtige og langsomme pool-inputs. Efter generering af en ny nøgle nulstilles entropi-estimaterne for begge puljer til nul [13] .

Genereringsmekanisme

Genereringsmekanismen giver outputtet en sekvens af pseudo-tilfældige tal. Det skal være sådan, at en angriber, der ikke kender generatornøglen, ikke kan skelne den fra en tilfældig bitsekvens .[14] .

Genereringsmekanismen bør have følgende egenskaber [15] :

modstand mod kryptografiske angreb ;
produktivitet ( engelsk Efficiency );
evnen til at generere en meget lang sekvens af signaler uden komplikationer;
modstand mod brute-force-angreb med backtracking ( eng. Backtracking ) efter at nøglen er blevet kompromitteret .

Komplikationshåndteringsmekanisme

For at vælge sofistikeringstiden skal kontrolmekanismen tage højde for forskellige faktorer. For eksempel, at ændre nøglen for ofte gør et iterativt gætteangreb mere sandsynligt [16] . For langsomt giver tværtimod mere information til den angriber, der kompromitterede nøglen. Derfor skal kontrolmekanismen kunne finde en mellemvej mellem disse to forhold [17] .

Som prøver ankommer i hver puljeentropi-estimaterne for hver kilde gemmes. Så snart dette skøn for en kilde når grænseværdien, er der en komplikation fra hurtigpuljen. I langt de fleste systemer sker dette mange gange i timen. En komplikation fra den langsomme pulje opstår, når scorerne for nogen af kilderne i den langsomme pulje overstiger en tærskel [17] . $k$ $n$

I Yarrow-160 er denne grænse 100 bit for den hurtige pool og 160 bit for den langsomme. Som standard skal mindst to forskellige kilder i den langsomme pool være større end 160 bit, for at der kan opstå komplikationer fra den langsomme pool [18] .

Yarrow 160

En mulig implementering af Yarrow-algoritmen er Yarrow-160. Hovedideen med denne algoritme er brugen af en envejs-hash-funktion og en blokchiffer [19] . Hvis begge algoritmer er sikre, og PRNG'en modtager nok indledende entropi , så vil resultatet være en stærk sekvens af pseudo-tilfældige tal [20] . $h()$ $E_{K}()$

Hash-funktionen skal have følgende egenskaber [21] :

være irreversibel, det vil sige modstandsdygtig over for restaurering af prototypen ;
være modstandsdygtig over for kollisioner ;
giv output- bit. $m$

Yarrow-160 bruger SHA-1-algoritmen som [19] . $h()$

Blokchifferen skal have følgende egenskaber [22] :

have en nøgle med en længde på -bit og en datablok med en længde på -bit; $k$ $n$
være modstandsdygtig over for almindelig tekst og valgte tekstangreb ;
har gode statistiske egenskaber for udgangssignalerne, selv med meget skabelonindgangssignaler.

Yarrow-160 bruger 3-KEY Triple DES-algoritmen som [19] . $E_{K}()$

Generation

Generatoren er baseret på brugen af en blokcifre i tællertilstand (se fig. 2) [23] .

Der er en n-bit tællerværdi . For at generere de næste -bits af den pseudo-tilfældige sekvens, inkrementeres tælleren med 1 og krypteres med en blokchiffer ved hjælp af nøglen [24] : $C$ $n$ $C$ $K$

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

R\leftarrow E_{K}(C)

hvor er output fra PRNG , og er den aktuelle værdi af nøglen . $R$ $K$

Hvis nøglen på et tidspunkt er kompromitteret , er det nødvendigt at forhindre lækage af tidligere outputværdier, som en angriber kan få. Denne genereringsmekanisme har ikke beskyttelse mod angreb af denne art, så antallet af PRNG-outputblokke beregnes yderligere. Så snart en vis grænse er nået ( systemsikkerhedsindstillingen ${\displaystyle P_{g))$ , ), så genereres et -bit PRNG-output, som derefter bruges som en ny nøgle [15] . ${\displaystyle 1\leq P_{g}\leq 2^{n/3))$ $k$

K\leftarrow {\text{next k PRNG output bits))

I Yarrow-160 er den 10. Denne parameter er bevidst sat lavt for at minimere antallet af output, der kan læres ved hjælp af et backtracking - angreb [ 25 ] . ${\displaystyle P_{g))$

Komplikation

Udførelsestiden for komplikationsmekanismen afhænger af parameteren . Denne parameter kan fastgøres eller ændres dynamisk [26] . $P_{t}\geq 0$

Denne mekanisme består af følgende trin [26] :

Entropiakkumulatoren beregner hashen for alle poster i hurtigpuljen. Resultatet af denne beregning er angivet med . ${\displaystyle v_{0))$
Lad . $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)$ .
Nulstil alle entropitællere i puljer til 0.
Ryd den hukommelse, der gemmer mellemværdier.
Hvis seed-filen bruges , så overskriv indholdet af denne fil med de næste bits af output fra den pseudo-tilfældige sekvens . $2k$

En funktion er defineret i form af en funktion som følger [27] : $h^{'}$ $h$

s_{0}:=m

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

h^{'}(m,k):={\tekst{først))\ \ k\ \ {\tekst{bits))\;(s_{0}|s_{1}|\ldots )

Faktisk er det en størrelsestilpasningsfunktion, det vil sige, at den konverterer et input af enhver længde til et output af en specificeret længde. Hvis inputtet modtog flere data end forventet, tager funktionen de førende bits. Hvis størrelserne på input og output er de samme, er funktionen en identitetsfunktion . Hvis størrelsen af inputdataene er mindre end forventet, genereres yderligere bits ved hjælp af denne hash-funktion . Dette er en temmelig dyr PRNG-algoritme i form af beregning, men til små størrelser kan den bruges uden problemer [28] .

Indstilling af en ny værdi til tælleren sker ikke af sikkerhedsmæssige årsager, men for at give større implementeringsfleksibilitet og opretholde kompatibilitet mellem forskellige implementeringer [26] . $C$

Uløste problemer og planer for fremtiden

I dagens implementering af Yarrow-160-algoritmen, størrelsen af poolsentropiakkumulering er begrænset til 160 bit. Angreb på 3-KEY Triple DES-algoritmen er kendt for at være mere effektive end udtømmende søgning . Men selv for brute-force backtracking-angreb ændres nøgler ret ofte, og 160 bit er nok til at sikre sikkerhed i praksis [29] .

Emnet for igangværende forskning er forbedring af entropi-estimeringsmekanismer. Ifølge skaberne af Yarrow-160 kan algoritmen være sårbar netop på grund af dårlige entropi-estimater, og ikke ud fra et krypteringssynspunkt [30] .

Skaberne har planer for fremtiden om at bruge den nye AES-blokkrypteringsstandard . Den nye blokchiffer kan nemt passe ind i det grundlæggende design af Yarrow-algoritmen. Men som udviklerne understreger, vil det være nødvendigt enten at ændre kompleksitets-hash-funktionen eller komme med en ny hash-funktion for at sikre, at entropipuljen er fyldt med mere end 160 bit. For AES med 128 bit vil dette ikke være et problem, men for AES med 192 eller 256 bit skal dette problem løses. Det skal bemærkes, at den grundlæggende struktur af Yarrow-algoritmen er kombinationen af en AES-blokchiffer og en 256-bit hashfunktion [31] .

Regelsættet for komplikationshåndteringsmekanismen er stadig foreløbigt, men yderligere undersøgelser kan forbedre det. Af denne grund er det genstand for igangværende forskning [30] .

Noter

↑ 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 om Sikkerhed. Spørgsmål og svar om Yarrow . Dato for adgang: 1. december 2016. Arkiveret fra originalen 11. november 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 al., 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 al., 1998 , s. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , s. 28-29.
↑ Ferguson, Schneier, 2004 , s. 109-111.

Litteratur

på russisk

Shcherbakov, L. Yu. , Domashev, A. V. Anvendt kryptografi. Brug og syntese af kryptografiske grænseflader. - Russisk udgave, 2003. - 416 s. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Praktisk kryptografi. - Williams Publishing House, 2004. - 432 s. — ISBN 5-8459-0733-0.

på engelsk

Schneier, B. Anvendt Kryptografi. - 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 om teori og anvendelse af kryptografiske teknikker Amsterdam, Holland, 13.-15. april, 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. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption :, FSE' 98 Paris, Frankrig, 23.-25. marts 1998 Proceedings / S Vaudenay - Berlin , Heidelberg , New York, NY , London [etc.] : 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: Noter om design og analyse af 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 [etc.] : 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 En implementering af Yarrow PRNG for FreeBSD // 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 (engelsk) // 19th Annual Computer Security Applications Conference (ACSAC) 2003, 8.-12. december 2003, Las Vegas, NV, (USA) - IEEE Computer Society , 2003. - S. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318