Algoritmul Yarrow

Algoritmul Yarrow este un generator de numere pseudoaleatoare, sigur din punct de vedere criptografic . Ca nume a fost aleasă șoricelul , ale cărui tulpini uscate servesc ca sursă de entropie în divinație [1] .

Algoritmul a fost dezvoltat în august 1999 de Bruce Schneier , John Kelsey și Niels Ferguson de la Counterpane Internet Security.[2] . Algoritmul nu este brevetat și nu este gratuitși nu este necesară nicio licență pentru a-l folosi . Yarrow este inclusă în februarie2002 cuFreeBSD , OpenBSD și Mac OS X ca implementare a dispozitivului /dev/random [3] .

Dezvoltarea ulterioară a lui Yarrow a fost crearea de către Fergus și Schneier a algoritmului Fortuna , descris în cartea lor „Practical Cryptography” [4] .

Necesitatea unui algoritm

Majoritatea aplicațiilor criptografice moderne folosesc numere aleatorii. Ele sunt necesare pentru a genera chei , pentru a obține numere aleatoare unice , pentru a crea o sare etc. Dacă numerele aleatoare sunt nesigure, atunci aceasta implică apariția unor vulnerabilități în aplicații care nu pot fi închise folosind diverși algoritmi și protocoale [5] .

În 1998, creatorii Yarrow au efectuat cercetări asupra altor PRNG -uri și au identificat o serie de vulnerabilități în ele. Secvențele de numere aleatorii pe care le-au produs nu erau sigure pentru aplicațiile criptografice [5] .

În prezent, algoritmul Yarrow este un generator de numere pseudo-aleatoare foarte sigur. Acest lucru vă permite să îl utilizați pentru o gamă largă de sarcini: criptare , semnătură electronică , integritatea informațiilor etc. [5] .

Principii de proiectare

În timpul dezvoltării algoritmului, creatorii s-au concentrat pe următoarele aspecte [6] :

Viteza si eficienta . Niciunul dintre dezvoltatori nu va folosi un algoritm care încetinește foarte mult aplicația.
Simplitate . Orice programator fără prea multe cunoștințe de criptografie ar trebui să o poată folosi în siguranță.
Optimizare . Acolo unde este posibil, algoritmul ar trebui să utilizeze blocuri de instrucțiuni preexistente.

Structura algoritmului

Componente

Algoritmul Yarrow este format din 4 părți independente [7] :

Acumulator de entropie . Colectează mostre din surse de entropie și le pune în două grupuri.
mecanism de complicare . Complica periodic cheia generatorului folosind entropia din pool-uri.
mecanism de generare . Generează semnale de ieșire PRNG de la dongle.
Mecanism de management al complicațiilor . Specifică durata de rulare a complicației.

Acumulator de entropie

Acumularea de entropie este un proces în care un PRNG dobândește o nouă stare internă de neghicit [8] . În acest algoritm, entropia este acumulată în două grupuri : rapid și lent [9] . În acest context, un pool este un depozit de biți inițializați și gata de utilizare. Piscina rapidă oferă complicații cheie frecvente . Acest lucru asigură că compromisul cheie are o durată scurtă. Piscina lentă oferă complicații cheie rare, dar semnificative. Acest lucru este necesar pentru a se asigura că se obține o complicație sigură chiar și în cazurile în care estimările entropiei sunt mult supraestimate. Eșantioanele de intrare sunt trimise alternativ la pool-urile rapide și lente [10] .

Mecanismul de complicare

Mecanismul de complicație conectează stocarea entropiei cu mecanismul de generare. Atunci când mecanismul de control al complexității determină că este nevoie de complexitate, atunci motorul de complexitate, folosind informații din unul sau ambele grupuri, actualizează cheia care este utilizată de mecanismul de generare. Astfel, dacă atacatorul nu cunoaște cheia sau pool-urile curente, atunci cheia îi va fi necunoscută după complicație. De asemenea, este posibil ca complexitatea să necesite o cantitate mare de resurse pentru a minimiza succesul unui atac pe baza ghicirii valorilor de intrare [11] .

Pentru a genera o nouă cheie , complexitatea pool-ului rapid utilizează cheia curentă și hash -urile tuturor intrărilor de pool rapid de la ultima complexitate a cheii. Odată făcut acest lucru, entropia este estimatăpentru pool-ul rapid va fi setat la zero [11] [12] .

Complicația pool-ului lentă utilizează cheia curentă și hash-urile intrărilor rapide și lente ale pool-ului. După generarea unei noi chei, estimările de entropie pentru ambele grupuri sunt resetate la zero [13] .

Mecanism de generare

Mecanismul de generare oferă rezultatului o secvență de numere pseudoaleatoare. Trebuie să fie astfel încât un atacator care nu cunoaște cheia generatorului să nu o poată distinge de o secvență de biți aleatorie .[14] .

Mecanismul de generare ar trebui să aibă următoarele proprietăți [15] :

rezistență la atacuri criptografice ;
productivitate ( Eficiență în limba engleză );
capacitatea de a genera o secvență foarte lungă de semnale fără complicații;
rezistență la atacuri de forță brută cu backtracking ( ing. Backtracking ) după ce cheia a fost compromisă .

Mecanism de gestionare a complicațiilor

Pentru a alege timpul de sofisticare, mecanismul de control trebuie să țină cont de diverși factori. De exemplu, schimbarea cheii prea des face ca un atac iterativ ghicitor să fie mai probabil [16] . Prea lent, dimpotrivă, oferă mai multe informații atacatorului care a compromis cheia. Prin urmare, mecanismul de control trebuie să poată găsi o cale de mijloc între aceste două condiții [17] .

Pe măsură ce probele ajung în fiecare bazinestimările entropiei pentru fiecare sursă sunt stocate. De îndată ce această estimare pentru orice sursă atinge valoarea limită, apare o complicație de la pool-ul rapid. În marea majoritate a sistemelor, acest lucru se întâmplă de mai multe ori pe oră. O complicație de la pool-ul lent apare atunci când scorurile pentru oricare dintre sursele din pool-ul lent depășesc un prag [17] . $k$ $n$

În Yarrow-160, această limită este de 100 de biți pentru pool-ul rapid și de 160 de biți pentru cel lent. În mod implicit, cel puțin două surse diferite din pool-ul lent trebuie să fie mai mari de 160 de biți pentru ca complicații să apară din pool-ul lent [18] .

Yarrow 160

O posibilă implementare a algoritmului Yarrow este Yarrow-160. Ideea principală a acestui algoritm este utilizarea unei funcții hash unidirecționale și a unui cifru bloc [19] . Dacă ambii algoritmi sunt siguri și PRNG primește suficientă entropie inițială , atunci rezultatul va fi o secvență puternică de numere pseudo-aleatoare [20] . $h()$ $E_{K}()$

Funcția hash trebuie să aibă următoarele proprietăți [21] :

să fie ireversibilă, adică rezistentă la restaurarea prototipului ;
să fie rezistent la coliziuni ;
da ieșirea -bit. $m$

Yarrow-160 folosește algoritmul SHA-1 ca [19] . $h()$

Cifrul bloc trebuie să aibă următoarele proprietăți [22] :

au o cheie cu lungimea de -biți și un bloc de date cu lungimea de -biți; $k$ $n$
să fie rezistent la atacurile text clar și text ales ;
au proprietăți statistice bune ale semnalelor de ieșire, chiar și cu semnale de intrare foarte modelate.

Yarrow-160 folosește algoritmul Triple DES cu 3 CHEI ca [19] . $E_{K}()$

Generație

Generatorul se bazează pe utilizarea unui cifru bloc în modul contor (vezi Fig. 2) [23] .

Există o valoare de contor de n biți . Pentru a genera următorii -biți ai secvenței pseudo-aleatoare, contorul este incrementat cu 1 și criptat cu un cifru bloc folosind cheia [24] : $C$ $n$ $C$ $K$

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

R\leftarrow E_{K}(C)

unde este ieșirea PRNG și este valoarea curentă a cheii . $R$ $K$

Dacă la un moment dat cheia este compromisă , atunci este necesar să se prevină scurgerea valorilor anterioare de ieșire pe care le poate obține un atacator. Acest mecanism de generare nu are protecție împotriva atacurilor de acest fel, astfel încât numărul de blocuri de ieșire PRNG este calculat suplimentar. De îndată ce se atinge o anumită limită ( setarea de securitate a sistemului $P_{g)$ , ), apoi este generată o ieșire PRNG -bit, care este apoi folosită ca o nouă cheie [15] . $1\leq P_{g}\leq 2^{n/3)$ $k$

K\leftarrow {\text{următorii k biți de ieșire PRNG)}

În Yarrow-160 este 10. Acest parametru este setat în mod deliberat la un nivel scăzut pentru a minimiza numărul de ieșiri care pot fi învățate folosind un atac de backtracking [ 25 ] . $P_{g)$

Complicație

Timpul de execuție al mecanismului de complicație depinde de parametru . Acest parametru poate fi fixat sau modificat dinamic [26] . $P_{t}\geq 0$

Acest mecanism constă din următorii pași [26] :

Acumulatorul de entropie calculează hash-ul tuturor intrărilor din pool -ul rapid. Rezultatul acestui calcul este notat cu . $v_{0)$
Lasă . $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)$ .
Resetați toate contoarele de entropie din pool-uri la 0.
Ștergeți memoria care stochează valorile intermediare.
Dacă se folosește fișierul seed , atunci suprascrieți conținutul acestui fișier cu următorii biți ai rezultatului secvenței pseudo-aleatorie . $2k$

O funcție este definită în termeni de funcție după cum urmează [27] : $h^{'}$ $h$

s_{0}:=m

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

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

De fapt, este o funcție de adaptare la dimensiune, adică convertește o intrare de orice lungime într-o ieșire de o lungime specificată. Dacă intrarea a primit mai multe date decât se aștepta, atunci funcția ia biții de început. Dacă dimensiunile intrării și ieșirii sunt aceleași, atunci funcția este o funcție de identitate . Dacă dimensiunea datelor de intrare este mai mică decât cea așteptată, atunci biți suplimentari sunt generați folosind această funcție hash . Acesta este un algoritm PRNG destul de costisitor din punct de vedere al calculului, dar pentru dimensiuni mici poate fi folosit fără probleme [28] .

Setarea unei noi valori la contor nu se face din motive de securitate, ci pentru a oferi o mai mare flexibilitate de implementare și pentru a menține compatibilitatea între diferitele implementări [26] . $C$

Probleme nerezolvate și planuri pentru viitor

În implementarea de astăzi a algoritmului Yarrow-160, dimensiunea piscineloracumularea de entropie este limitată la 160 de biți. Se știe că atacurile asupra algoritmului Triple DES cu 3 CHEI sunt mai eficiente decât căutarea exhaustivă . Cu toate acestea, chiar și pentru atacurile de backtracking cu forță brută, cheile se schimbă destul de des, iar 160 de biți este suficient pentru a asigura securitatea în practică [29] .

Subiectul cercetărilor în curs este îmbunătățirea mecanismelor de estimare a entropiei. Potrivit creatorilor Yarrow-160, algoritmul poate fi vulnerabil tocmai din cauza estimărilor slabe ale entropiei, și nu din punctul de vedere al criptoanalizei [30] .

Creatorii au planuri pentru a utiliza pe viitor noul standard de cifrare în bloc AES . Noul cifru bloc se poate încadra cu ușurință în designul de bază al algoritmului Yarrow. Cu toate acestea, după cum subliniază dezvoltatorii, va fi necesar fie să se schimbe funcția hash de complexitate, fie să se creeze o nouă funcție hash pentru a se asigura că pool-ul de entropie este umplut cu mai mult de 160 de biți. Pentru AES cu 128 de biți, aceasta nu va fi o problemă, dar pentru AES cu 192 sau 256 de biți, această problemă va trebui rezolvată. Trebuie remarcat faptul că structura de bază a algoritmului Yarrow este combinația dintre un cifru bloc AES și o funcție hash de 256 de biți [31] .

Setul de reguli pentru mecanismul de management al complicațiilor este încă provizoriu, cu toate acestea, studii suplimentare îl pot îmbunătăți. Din acest motiv, face obiectul cercetărilor în curs [30] .

Note

↑ Kelsey, Schneier, Ferguson, 2000 , p. 29.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 13.
↑ Murray, 2002 , p. 47.
↑ Ferguson, Schneier, 2004 , p. 183.
↑ 1 2 3 Schneier despre securitate. Întrebări și răspunsuri despre Yarrow . Data accesului: 1 decembrie 2016. Arhivat din original pe 11 noiembrie 2016.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 15-16.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 18-21.
↑ Şcerbakov, Domaşev, 2003 , p. 232.
↑ Viega, 2003 , p. 132.
↑ Ferguson, Schneier, 2004 , p. 189-193.
↑ 1 2 Șcherbakov, Domashev, 2003 , p. 234-235.
↑ Ferguson, Schneier, 2004 , p. 234-235.
↑ Şcerbakov, Domaşev, 2003 , p. 191-193.
↑ Ferguson, Schneier, 2004 , p. 183-184.
↑ 1 2 Ferguson, Schneier, 2004 , p. 183-185.
↑ Kelsey, Schneier, Wagner et al., 1998 , p. 172.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , p. 22.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 28.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , p. 23.
↑ Ferguson, Schneier, 2004 , p. 202.
↑ Schneier, 1996 , p. 55-57.
↑ Şcerbakov, Domaşev, 2003 , p. 236.
↑ Ferguson, Schneier, 2004 , p. 95-96,183-186.
↑ Ferguson, Schneier, 2004 , p. 95-96,183-188.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 25.
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , p. 26-27.
↑ Kelsey, Schneier, Ferguson, 2000 , p. 27.
↑ Ferguson, Schneier, 2004 , p. 188-189.
↑ Kelsey, Schneier, Wagner et al., 1998 , p. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , p. 28-29.
↑ Ferguson, Schneier, 2004 , p. 109-111.

Literatură

in rusa

Shcherbakov, L. Yu. , Domashev, A. V. Criptografia aplicată. Utilizarea și sinteza interfețelor criptografice. - Ediția Rusă, 2003. - 416 p. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Criptografie practică. - Editura Williams, 2004. - 432 p. — ISBN 5-8459-0733-0.

în limba engleză

Schneier, B. Criptografie aplicată. - John Wiley & Sons, 1996. - 784 p. - 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, The Netherlands, April 13–15, 1987 Proceedings / D. Chaum , W. L. Price - Springer Science + Business Media , 1988. - P. 77-81. — 316 p. — 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, Franța, 23–25 martie 1998 Proceedings / S Vaudenay - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 1998. - P. 168-188. - ( Note de curs în Informatică ; 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 , Londra [etc.] : Springer Berlin Heidelberg , 2000. - P. 13-33. - ( Note de curs în Informatică ; Vol. 1758) - ISBN 978-3-540-67185-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-46513-8_2
Murray, Mark RV O implementare a Yarrow PRNG pentru 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 (English) // A 19-a Conferință anuală de aplicații de securitate a computerelor (ACSAC) 2003, 8-12 decembrie 2003, Las Vegas, NV, (SUA) - IEEE Computer Society , 2003. - P. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318

Link -uri

Yarrow - Pagina de algoritm pe site-ul lui B. Schneier (engleză)