Funcția hash criptografică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 mai 2019; verificările necesită 58 de modificări .

Funcțiile hash criptografice sunt o clasă distinctă de funcții hash care au anumite proprietăți care le fac potrivite pentru utilizarea în criptografie .

Principii de construcție

Circuit secvenţial iterativ

În cazul general, construcția unei funcții hash se bazează pe o schemă secvențială iterativă. Miezul algoritmului este o funcție de comprimare - conversia k de intrare în n biți de ieșire, unde n este lungimea funcției hash și k este un număr arbitrar mai mare decât n . În acest caz, funcția de comprimare trebuie să îndeplinească toate condițiile de rezistență criptografică .

Fluxul de intrare este împărțit în blocuri de ( k - n ) biți. Algoritmul folosește o variabilă temporară de dimensiunea n biți, a cărei valoare inițială este un număr binecunoscut. Fiecare bloc următor de date este combinat cu valoarea de ieșire a funcției de micșorare la iterația anterioară. Valoarea funcției hash este rezultatul n biți ai ultimei iterații. Fiecare bit al valorii de ieșire a unei funcții hash depinde de întregul flux de date de intrare și de valoarea inițială. Astfel, se obține un efect de avalanșă .

Când se proiectează funcții hash bazate pe o schemă iterativă, există o problemă cu dimensiunea fluxului de date de intrare. Mărimea fluxului de date de intrare trebuie să fie un multiplu de ( k−n ) . De regulă, înainte de începerea algoritmului, datele sunt extinse într-un fel cunoscut dinainte.

Pe lângă algoritmii cu o singură trecere, există algoritmi cu mai multe treceri în care efectul de avalanșă este îmbunătățit și mai mult. În acest caz, datele sunt mai întâi repetate, apoi extinse la dimensiunea necesară.

Funcție de contracție bazată pe algoritmul blocului simetric

Algoritmul de cifrare bloc simetrică poate fi utilizat ca funcție de compresie . Pentru a asigura o mai mare securitate, puteți utiliza blocul de date destinat pentru hashing la această iterație ca o cheie și rezultatul funcției anterioare de compresie ca intrare. Apoi rezultatul ultimei iterații va fi rezultatul algoritmului. Într-un astfel de caz, securitatea funcției hash se bazează pe securitatea algoritmului utilizat.

De obicei, la construirea unei funcții hash, se folosește un sistem mai complex. Schema generalizată a algoritmului de criptare bloc simetric este prezentată în Fig. 2.

Astfel, obținem 64 de opțiuni pentru construirea unei funcții de contracție. Cele mai multe dintre ele sunt fie banale, fie nesigure. Mai jos sunt cele patru cele mai sigure scheme pentru toate tipurile de atacuri.

Principalul dezavantaj al funcțiilor hash concepute pe baza algoritmilor bloc este viteza lor scăzută. Puterea criptografică necesară poate fi atinsă și într-un număr mai mic de operații asupra datelor de intrare. Există algoritmi de hashing mai rapidi concepuți de dvs., de la zero, pe baza cerințelor de putere criptografică. Cele mai comune dintre ele sunt MD5 , SHA-1 , SHA-2 .

Cerințe

Cerințele pentru funcțiile hash criptografice sunt:

1. Prima rezistență la căutarea înainte de imagine : Având în vedere un hash , ar trebui să fie dificil să găsiți un mesaj astfel încât . Această proprietate este legată de noțiunea de funcție unidirecțională . Funcțiile cărora le lipsește această proprietate sunt vulnerabile la primele atacuri preimagine . $h$ $m$ $h=hash(m)$

2. Rezistența la căutarea celei de-a doua preimagine : având în vedere un mesaj , ar trebui să fie dificil să găsești un alt mesaj (care nu este egal cu ) astfel încât . Această proprietate este uneori denumită rezistență slabă la coliziune. Funcțiile cărora le lipsește această proprietate sunt vulnerabile la atacurile de căutare a doua înainte de imagine. $m_1$ $m_2$ $m_1$ $hash(m_{1})=hash(m_{2})$

3. Rezistenta la ciocniri

O coliziune a funcției hash este o pereche de valori și ′, ′ pentru care . Deoarece numărul de texte clare posibile este mai mare decât numărul de valori posibile ale convoluției, atunci pentru unele convoluții există multe preimagini și, prin urmare, există în mod necesar coliziuni pentru funcțiile hash. De exemplu, să fie lungimea preimaginei hash de 6 biți, lungimea convoluției să fie de 4 biți. Atunci numărul de pliuri diferite este , iar numărul de preimagini hash este , adică de 4 ori mai mult, ceea ce înseamnă că cel puțin una dintre toate pliurile corespunde la 4 preimagini. $m$ $m$ $m\neq m$ $H(m)=H(m')$ $2^{4}=16$ $2^6=64$

Rezistența unei funcții hash la coliziuni înseamnă că nu există un algoritm polinom eficient pentru a găsi coliziuni.

Aceste proprietăți nu sunt independente:

O funcție inversabilă este instabilă la restaurarea celei de-a doua preimagine și coliziuni.
O funcție care nu este rezistentă la restabilirea celei de-a doua preimagine nu este rezistentă la coliziuni; inversul nu este adevărat.
Funcția este rezistentă la coliziuni, rezistentă la a doua preimagine.
O funcție hash rezistentă la coliziuni nu este neapărat unidirecțională.

Este important pentru criptografie ca valorile hash se schimbă foarte mult cu cea mai mică modificare a argumentului ( efect de avalanșă ). Valoarea hash nu ar trebui să scurgă informații nici măcar despre biți individuali ai argumentului.

La dezvoltarea standardului rus modern GOST R 34.11-2012 (Stribog) , au fost formulate următoarele cerințe pentru funcțiile hash criptografice:

Dificultate în calcularea preimaginei: dacă valoarea funcției este cunoscută, atunci ar trebui să fie dificil să găsiți un astfel de mesaj, a cărui funcție hash este egală cu cea cunoscută;
Securitatea calculului celei de-a doua preimagine: să existe o singură valoare, iar codul hash al acestei valori este cunoscut. Atunci ar trebui să fie dificil pentru un atacator să găsească o altă astfel de valoare, astfel încât funcția sa hash să coincidă cu funcția hash a primei valori;
Dificultate în găsirea coliziunilor: ar trebui să fie dificil să găsești două astfel de mesaje care nu sunt egale, dar au aceleași coduri hash;
Rezistența la prelungirea imaginii: dacă un atacator nu cunoaște mesajul, dar îi cunoaște lungimea și codul hash din el, atunci ar trebui să fie dificil pentru el să preia un mesaj care, atunci când este adăugat la original, va oferi o funcție hash cunoscută. . Cu alte cuvinte, nu ar trebui să fie posibil ca un atacator să schimbe ceva adăugând la mesaj în timp ce face cunoscută rezultatul. Acest lucru poate fi pus în alt mod: funcția hash nu trebuie să fie bine „căptușită”.

4. Pseudo -aleatorie : Ar trebui să fie dificil să distingem un generator de numere pseudo-aleatorie bazat pe hash de un generator de numere aleatoare, de exemplu, acesta trece testele obișnuite de aleatorie .

Funcții hash sigure

Securitatea unei funcții hash poate fi asigurată de complexitatea unei probleme matematice, cu condiția să existe dovezi că atacurile care vizează încălcarea cerințelor pentru aceasta sunt la fel de dificile ca și rezolvarea acestei probleme. [unu]

O funcție hash criptografică este dovedibil rezistentă la coliziuni dacă problema găsirii coliziunilor poate fi mediată în timp polinomial dintr-o problemă care este considerată de nerezolvată în timp polinomial . Cu alte cuvinte, dacă algoritmul ar permite rezolvarea problemei găsirii coliziunilor în timp polinomial dacă există un algoritm reducător care funcționează și în timp polinomial, atunci acesta din urmă ar permite algoritmului să rezolve problema în timp polinomial, ceea ce contrazice complexitatea acesteia. , ceea ce înseamnă că problema găsirii coliziunilor nu este mai ușoară decât sarcina . $P$ $A$ $R$ $A$ $P$ $P$

Securitatea dovedibilă împotriva căutării primei și a doua preimagini este definită în mod similar.

Rezistența la căutarea celei de-a doua preimagine decurge din rezistența dovedită la ciocniri, de aceea, în practică, uneori se demonstrează teoretic doar rezistența la găsirea primei preimagine și rezistența la ciocniri. [2]

Câteva probleme care se presupune că sunt de nerezolvat în timp polinomial, care pot fi folosite pentru a construi astfel de funcții:

Dezavantajele abordării bazate pe dovezi

În prezența garanțiilor teoretice ale complexității, abordarea bazată pe dovezi are și dezavantaje semnificative:

Actualii algoritmi de hashing siguri sunt prea complexi din punct de vedere computațional pentru a fi utilizați în practică. În comparație cu funcțiile hash obișnuite, acestea sunt destul de lente.
Crearea de funcții hash sigure este mult mai consumatoare de timp decât abordările clasice.
Dovada de securitate în sine se bazează adesea pe o problemă care are complexitatea necesară medie sau cel mai rău caz. Cel mai rău caz de complexitate descrie cel mai adesea situații patologice mai degrabă decât cele tipice pentru sarcină. Chiar și reducerea la o problemă cu complexitate în medie oferă o securitate limitată, deoarece poate fi găsit un algoritm care rezolvă cu ușurință problema pentru un anumit subset de date probleme. Deci, de exemplu, s-a demonstrat că pentru doi dintre cei trei parametri propuși în articolul original pentru funcția de hash Fast Syndrome-Based , există mai multe atacuri optime decât cele propuse de creatori pentru a dovedi securitatea. [3]

SWIFFT este un exemplu de funcție hash care ocolește oarecum problema de securitate descrisă. Se poate demonstra că pentru orice algoritm care rupe SWIFFT cu probabilitate în timp, există un algoritm care rezolvă o anumită problemă matematică în cel mai rău caz în timp în funcție de și . [patru] $P$ $T$ $T'$ $P$ $T$

Exemple de funcții hash sigure

VSH - Funcția Very Smooth Hash - este o funcție sigură, rezistentă la coliziune, care se bazează pe dificultatea de a găsi rădăcini pătrate non-triviale modulo un număr compus n (care este la fel de dificil ca factorizarea n ).
MuHASH
ECOH - Curba eliptică numai hash - funcție hash bazată pe ideea curbelor eliptice , problema sumei submulțimii și sumarea polinomială. Dovada de securitate s-a bazat pe presupunerea completității NP a problemei matematice de bază, dar a fost găsită o vulnerabilitate pentru atacul generalizat de „zile de naștere” al lui Wagner, legat de căutarea celei de-a doua preimagine. [5]
FSB - Funcția hash bazată pe sindromul rapid - Se poate demonstra că ruperea FSB este cel puțin la fel de dificilă ca rezolvarea problemei NP-complete cunoscută sub numele de decodare obișnuită a sindromului. [6]
SWIFFT - SWIFFT se bazează pe FFT și se dovedește sigur în baza unei ipoteze destul de slabe despre dificultatea în cel mai rău caz de a găsi vectori scurti într-o rețea ciclică/ideală. [7]
Funcția hash Chaum, van Heijst, Pfitzmann - o funcție în care găsirea coliziunilor este la fel de laborioasă ca atunci când găsirea unui logaritm discret într-un grup finit . $F_{2p+1}$
Funcțiile hash bazate pe rucsac sunt o familie de funcții hash bazate pe problema rucsacului .
Există o abordare generală pentru construirea de algoritmi de hashing siguri bazați pe orice protocol sigma adecvat . O versiune mai rapidă a VSH (numită VSH*) poate fi obținută în acest fel.

Funcția hash criptografică ideală

O funcție hash criptografică ideală este o funcție hash criptografică care are cinci proprietăți de bază:

Determinism . Cu aceleași date de intrare, rezultatul funcției hash va fi același (același mesaj duce întotdeauna la același hash);
Calcularea de mare viteză a valorii hash pentru orice mesaj dat;
Incapacitatea de a genera un mesaj din valoarea sa hash, cu excepția încercării de a crea toate mesajele posibile;
Efect de avalanșă. O mică modificare a mesajelor ar trebui să modifice valorile hash atât de larg încât noile valori hash nu se potrivesc cu vechile valori hash;
Incapacitatea de a găsi două mesaje diferite cu aceeași valoare hash.

Astfel, o funcție hash criptografică ideală, care are lungimea n (adică, ieșirea este de n biți), trebuie să necesite cel puțin operații pentru a calcula preimaginea. $2^{n}$

Un atacator va căuta o pre-imagine pentru o funcție hash ideală în felul următor: are un număr h și trebuie să găsească m astfel încât H(m) = h. Dacă aceasta este o funcție hash ideală, atunci atacatorul poate doar să parcurgă toate M posibile și să verifice cu ce este egală funcția hash din acest mesaj. Rezultatul calculului, dacă m este repetat complet, este de fapt un număr aleatoriu. Dacă numărul h se află în intervalul de la 0 la , atunci, în medie, atacatorul va petrece iterații căutând h dorit. Astfel, calculul preimaginei va lua jumătate din mai multe iterații decât în cazul ideal. $2^{n}$ $2^{{n-1}}$

Calculul celei de-a doua preimagine rămâne . În căutarea coliziunilor, scorul va da , iar acesta nu este un rezultat complet exact. Această evaluare provine dintr-o evaluare a așa-numitului „ Paradox al zilei de naștere ”. $2^{n}$ $2^{n}$

Dacă un atacator dorește să scrie un program pentru a găsi coliziuni, ar fi optim pentru el să obțină mai întâi un dicționar de coliziuni. În consecință, apoi calculează funcția hash din următorul mesaj și verifică dacă această funcție hash aparține următorului mesaj sau nu. Dacă se întâmplă, atunci coliziunea este găsită și apoi mesajul original cu codul hash dat poate fi găsit în dicționar. Dacă nu, atunci completează dicționarul. În practică, această metodă nu este implementată, deoarece nu ar exista suficientă memorie pentru un astfel de dicționar.

Atacul zilei de naștere

Atacul zilei de naștere este un nume folosit în criptoanaliza pentru o metodă de detectare a coliziunilor cu funcția hash bazată pe paradoxul zilei de naștere. Esența paradoxului este că într-un grup de 23 sau mai multe persoane, probabilitatea coincidenței zilelor de naștere (ziua și lună) pentru cel puțin două persoane depășește 50%. De exemplu, dacă într-o clasă sunt 23 sau mai mulți elevi, atunci este mai probabil ca ziua de naștere a unui colegi de clasă să fie în aceeași zi decât ca fiecare să aibă propria zi de naștere unică.

Efectul de avalanșă

Să luăm în considerare acest efect și rolul său pe exemplul procesului de hashing blockchain. Această proprietate înseamnă că dacă facem mici modificări la șirul de intrare, atunci hashurile (adică rezultatul funcției criptografice) vor fi drastic diferite unele de altele. Să verificăm această proprietate pe un exemplu simplu. Luați în considerare, de exemplu, rezultatul unei funcții hash din familia MD - MD5. La intrare, vom furniza valori care vor diferi doar în cazul primelor caractere - șirurile sunt aproape identice. Cu toate acestea, hashurile lor (rezultatul funcției hash) sunt diferite.

Un exemplu despre cum funcționează algoritmul de criptare MD5
Intrare	Ieșire
bitcoin	0xCD5B1E4947E304476C788CD474FB579A
bitcoin	0xD023EC040F79F1A9B2AC960B43785089

„Entropie înaltă”

Funcțiile hash bune au proprietatea „High Entropie ”. Aceasta înseamnă că hashurile matricelor de date ar trebui să fie distribuite maxim în sistem în timpul procesului de hashing, adică ar trebui să aibă o entropie mare în sensul informației. După cum știți, entropia în sensul de informație este o măsură a incertitudinii unui anumit sistem, în special, impredictibilitatea apariției unui simbol.

Deci, de exemplu, luăm în considerare ecuația , unde este concatenarea unui șir și a unui șir și este o funcție hash criptografică. Dacă valoarea are un indice de entropie mare, atunci va fi aproape imposibil să găsiți o valoare care să satisfacă ecuația. $OUTPUT=H(K|INPUT)$ $K|INPUT$ $K$ $INPUT$ $H$ $K$ $INPUT$

Termenul „entropie mare” în contextul funcțiilor hash înseamnă o stare în care o valoare este aleasă dintr-o gamă atât de largă de opțiuni posibile, încât încercările de a ghici prin selecție aleatorie nu au șanse de succes. De exemplu, un număr care este între 1 și 10 are o entropie scăzută, în timp ce un număr care este între 1 și , dimpotrivă, are o entropie mare. $2^{256}$

Familia de funcții hash MD și SHA

Până în prezent, majoritatea covârșitoare a aplicațiilor de funcții hash sunt „preluate” de algoritmii MD5 , SHA-1 , SHA-256 , iar în Rusia - de asemenea GOST R 34.11-2012 (Stribog) . Desigur, există mulți alți algoritmi care sunt mai puțin cunoscuți sau obișnuiți doar în comunitățile înguste (de exemplu, RIPEMD , TIGER , Panama , etc.), cu toate acestea, acești algoritmi nu sunt atât de obișnuiți. Mai jos este o analiză a funcțiilor hash MD4 , care a fost predecesorul MD5, precum și a funcției hash SHA.

Tip de	Descriere
MD4	Cel mai rapid, optimizat pentru mașini pe 32 de biți din familia de funcții MD. O funcție hash dezvoltată de profesorul de la Universitatea din Massachusetts Ronald Rivest în 1990 și descrisă pentru prima dată în RFC 1186. Conține trei bucle a câte 16 pași fiecare. În 1993, a fost descris algoritmul de cracare MD4, așa că astăzi această funcție nu este recomandată pentru utilizare cu aplicații reale.
MD5	Cele mai comune din familia de funcții MD. Similar cu MD4, dar îmbunătățirile de securitate îl fac cu 33% mai lent decât MD4. Conține patru cicluri a câte 16 pași fiecare. Oferă controlul integrității datelor. Primele încercări reușite de a sparge această funcție hash datează din 1993: cercetătorii Bert den Boer și Anton Bossilaris au arătat că pseudo-coliziunile sunt posibile în algoritm. În 1996, Hans Dobbertin a arătat posibilitatea unor coliziuni și a descris teoretic algoritmul de hacking. Pe 24 august 2004, patru cercetători independenți - Wang Xiaoyun, Feng Dengguo, Lai Xuejia și Yu Hongbo - au descoperit o vulnerabilitate a algoritmului care permite găsirea coliziunilor folosind o metodă analitică într-un timp mai mult sau mai puțin acceptabil. În 2005, Vlastimil Klima a publicat un algoritm de detectare a coliziunilor în câteva ore. Pe 18 martie 2006, un cercetător a publicat un algoritm care găsește coliziunile într-un minut, care mai târziu a fost numit „tunnel”. Începând de astăzi, MD5 nu este recomandat pentru utilizare în aplicații din lumea reală.
SHA-1 (Sigur Hash Algoritmul 1)	În 1993, NSA a colaborat cu NIST pentru a dezvolta algoritmul Secure Hash (cunoscut acum ca SHA-0) (publicat în FIPS PUB 180) pentru un standard de hashing securizat. Cu toate acestea, NSA a retras în curând această versiune, invocând o eroare pe care au descoperit-o și care nu a fost niciodată dezvăluită. Și l-a înlocuit cu o versiune revizuită publicată în 1995 în FIPS PUB 180-1. Această versiune este considerată a fi ceea ce se numește SHA-1 . Mai târziu, la conferința CRYPTO din 1998, doi cercetători francezi au prezentat un atac asupra algoritmului SHA-0 care nu a funcționat pe algoritmul SHA-1. Este posibil să fi fost o eroare descoperită de NSA. SHA-1 creează o valoare de 160 de biți, numită și rezumat de mesaje. Conține patru etape. Atât MD5, cât și SHA-1 sunt în esență extensii îmbunătățite ale MD4. Diferențe: În SHA-1, a patra etapă folosește aceeași funcție ca a doua etapă. În MD5, fiecare acțiune folosește o constantă incrementală unică. În SHA-1, constantele sunt reutilizate pentru fiecare dintre cele patru grupuri. O a cincea variabilă a fost adăugată la SHA-1. SHA-1 utilizează un cod ciclic de corectare a erorilor. MD5 are patru funcții booleene elementare diferite, în timp ce SHA-1 are trei. În MD5, lungimea rezumatului este de 128 de biți, în SHA-1 este de 160 de biți. SHA-1 conține mai multe runde (80 în loc de 64) și rulează pe un buffer de 160 de biți în comparație cu tamponul de 128 de biți al MD5 . Deci, SHA-1 ar trebui să ruleze cu aproximativ 25% mai lent decât MD5 pe același hardware.
SHA-2	O familie de algoritmi criptografici - funcții hash, inclusiv algoritmii SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 și SHA-512/224. În 2003, Gilbert și Handschuh au efectuat un studiu asupra SHA-2 , dar nu au găsit vulnerabilități. Cu toate acestea, în martie 2008, cercetătorii indieni Somitra Kumar Sanadiya și Palash Sarkar au publicat coliziunile pe care le-au găsit pentru 22 de iterații ale lui SHA-256 și SHA-512. În septembrie același an, au prezentat o metodă de construire a coliziunilor pentru versiunile trunchiate de SHA-2 (21 de iterații). Studiile au arătat [8] că algoritmii SHA-2 funcționează de 2-3 ori mai lent decât algoritmii hash MD5 , SHA-1 .
SHA-256	Separat, iese în evidență algoritmul SHA-256, care este folosit în algoritmii de hashing pentru bitcoin și alte criptomonede. După cum sugerează numele funcției hash criptografice, hash-ul de ieșire are o lungime de 256 de biți, entropia corespunzătoare poate fi definită ca un set de valori de la 1 la 2 la puterea de 256 - un număr mare de valori, ceea ce face cracarea iar decriptarea este un proces extrem de consumator de timp, bazat pe enumerarea secvențială.
SHA-3 ( Keccak)	Funcția hash SHA-3 (numită și Keccak) este o funcție de biți variabili dezvoltată de un grup de autori condus de Joan Dymen . Pe 2 octombrie 2012, Keccak a devenit câștigătorul concursului de algoritmi criptografici susținut de Institutul Național de Standarde și Tehnologie din SUA [9] . La 5 august 2015, algoritmul funcției a fost aprobat și publicat ca standard FIPS 202 [10] [11] . Algoritmul funcției SHA-3 este construit pe principiul unui burete criptografic .

Aplicații

Semnătura electronică

Pentru a vă asigura că mesajul a fost trimis de un anumit expeditor, împreună cu mesajul este transmisă o așa-numită semnătură electronică. Destinatarul verifică dacă semnătura electronică aparține într-adevăr mesajului dat.

Datorită faptului că utilizarea criptografiei cu chei publice (semnarea, verificarea semnăturilor etc.) este un proces foarte lent, în plus, dacă semnați întregul mesaj, atunci dimensiunea acestei semnături va fi comparabilă cu dimensiunea mesaj, nu semnați mesajul și o funcție hash din mesaj. Și apoi destinatarul, când decriptează semnătura, primește o funcție hash. În continuare, el compară funcția hash din mesajul primit și funcția hash care a fost obținută ca urmare a decriptării. Datorită faptului că funcția hash are o lungime fixă, este mai mică decât mesajul în sine. Acest lucru vă permite să calculați rapid semnătura digitală. Dimensiunea acestei semnături va fi mică în comparație cu dimensiunea mesajului.

Verificarea frazei de acces

În cele mai multe cazuri, frazele de acces nu sunt stocate pe ținte, sunt stocate doar valorile hash ale acestora. Nu este recomandabil să stocați fraze de acces, deoarece în cazul accesului neautorizat la un fișier cu fraze, un atacator va cunoaște toate frazele de acces și le va putea folosi imediat, iar la stocarea valorilor hash, va învăța doar valorile hash care nu sunt reversibile la datele originale, în acest caz - într-o frază de acces. În timpul procedurii de autentificare, valoarea hash a frazei de acces introduse este calculată și comparată cu cea stocată.

Exemple în acest caz sunt GNU/Linux și Microsoft Windows XP . Ele stochează numai valori hash ale frazelor de acces din conturile de utilizator .

Acest sistem presupune transmiterea unui mesaj pe un canal securizat, adică un canal din care este imposibil ca un criptoanalist să intercepteze mesaje sau să le trimită pe ale sale. În caz contrar, el poate intercepta expresia de acces și o poate folosi pentru autentificare ilegală ulterioară. Vă puteți proteja de astfel de atacuri folosind metoda provocare-răspuns .

Lăsați un client numit nume să se autentifice cu o expresie de acces, transmite , la un server. Serverul stochează valoarea hash H ( pass , R2 ) , unde R2 este un număr pseudo - aleatoriu, preselectat. Clientul trimite o cerere ( nume , R 1 ), unde R 1 este un pseudo-aleatoriu, de fiecare dată un număr nou. Ca răspuns , serverul trimite valoarea R2 . Clientul calculează valoarea hash H ( R 1 , H ( pass , R 2 )) și o trimite la server. Serverul calculează și valoarea H ( R 1 , H ( trece , R 2 )) și o verifică cu cea primită. Dacă valorile se potrivesc, autentificarea este corectă.

Într -o astfel de situație, parola nu este stocată în mod deschis pe server și chiar și după interceptarea tuturor mesajelor dintre client și server, criptoanalistul nu poate recupera parola, iar valoarea hash transmisă este diferită de fiecare dată.

Hashing Bitcoin

Tranzacțiile sistemului de plată Bitcoin , care sunt prezentate ca o anumită serie de date, sunt combinate în blocuri (în continuare, totalitatea tuturor blocurilor va fi numită blockchain ) și trec printr-un algoritm de hashing, adică datele lor de câmp sunt transmise la intrare. a unei funcții hash criptografice. Fiecare tranzacție indică de unde sunt debitate fondurile și unde se duc. Pentru a specifica destinatarul, se folosește cheia publică a acestuia (un identificator unic în rețeaua bitcoin). Pentru ca destinatarul să poată folosi banii primiți în cadrul protocolului bitcoin (excludem vânzarea propriului portofel - Portofel), acesta trebuie să creeze o nouă tranzacție care să preia moneda de pe cea anterioară și să o redirecționeze către o altă adresă folosind cheie publică. În consecință, noua tranzacție, împreună cu tranzacțiile altor utilizatori ai rețelei bitcoin, se va încadra într-un nou bloc. Astfel, numărul de blocuri din blockchain crește. Cu toate acestea, fiecare tranzacție trebuie să fie aprobată - sistemul trebuie să ajungă la un consens. Există mai multe moduri de a face acest lucru, dar Bitcoin folosește principiul Proof-of-Work (PoW). După ce tranzacția este acceptată, aceasta este considerată reală și criptomoneda se mută de la un portofel la altul.

Sistemul Bitcoin este un sistem descentralizat fără centre dedicate de generare a blocurilor. Fiecare participant poate lua un set de tranzacții care așteaptă să fie înregistrate și să formeze un nou bloc. Mai mult, în sisteme precum BitCoin, un astfel de participant (miner) va primi și un bonus sub forma unei anumite sume sau comision din tranzacțiile acceptate în bloc.

Dar nu puteți să luați și să formați un bloc în sistemele descentralizate. Sistemul trebuie să ajungă la consens, adică să obțină aprobare. Există mai multe moduri de a face acest lucru, dar Bitcoin folosește principiul Proof-of-Work (PoW). Fiabilitatea unor astfel de sisteme se bazează tocmai pe faptul că un nou bloc nu poate fi format mai rapid (în medie) decât într-un anumit timp. De exemplu, în 10 minute (BitCoin).

Structura de bloc a blockchain-ului BitCoin

camp	Descriere	mărimea
Magia nr	valoarea întotdeauna 0xD9B4BEF9	4 octeți
dimensiunea blocului	numărul de octeți care urmează până la sfârșitul blocului	4 octeți
blockheader	format din 6 articole	80 de octeți
contor de tranzacții	număr întreg pozitiv	1-4 octeți
tranzacții	lista de tranzacții <nevide>	<Contor tranzacții> - multe tranzacții

Structura Blockheader în blocul Blockchain BitCoin

camp	Scop	Actualizați când...	mărimea
versiune	bloc numărul de versiune	Faceți upgrade de software și a specificat o nouă versiune	patru
hashPrevBlock	Hash pe 256 de biți din antetul blocului anterior	Apare un nou bloc	32
hashMerkelRoot	Hash de 256 de biți bazat pe toate tranzacțiile din bloc	O tranzacție este acceptată	32
Timp	marcaj temporal actual în secunde de la 1970-01-01 T00:00 UTC	La fiecare câteva secunde	patru
biți	ținta curentă în format compact	Dificultatea este ajustată	patru
nonce	număr pe 32 de biți (începe de la 0)	Un hash este obosit (crește)	patru

dificultatea este numărul de biți zero care va fi la începutul numărului țintă .

target este numărul pe care hash-ul blocului trebuie să fie mai mic decât pentru ca blocul să fie considerat valid. Ținta sau, mai precis, dificultatea depinde de puterea actuală a rețelei și trebuie să modificați dificultatea la fiecare n (în rețeaua BitCoin - 2016) blocuri, astfel încât să fie generat un bloc la fiecare 10 minute. Să presupunem că blocurile 2016 sunt generate în rețea și fiecare client verifică cât timp a fost creat fiecare bloc. Dacă acest timp este mai lung decât cel calculat, adică mai mult de 10 minute, atunci complexitatea scade.

nonce este un număr aleatoriu pe care minerii trebuie să-l ridice pentru a face un bloc.

Structura structurii de date bitcoin

După cum am menționat mai sus, un set de tranzacții Bitcoin sunt reprezentate ca blocuri de date conectate - blockchain . Structura dispozitivului blockchain în sine este prezentată ca o listă legată cu indicatori.

Fiecare bloc are un pointer care conține o legătură către blocul de date anterior. Astfel, pentru a merge la n + 1 blocuri, este necesar să urmați pointerii celor n blocuri anterioare. În consecință, pointerii adaugă adresa unui nou bloc numai după ce blocul de date original a trecut prin algoritmul de hashing bitcoin - acest lucru vă permite să faceți conexiunea fiabilă și sigură.

Un astfel de sistem este mai puțin probabil să fie atacat de intruși care ar putea încerca să schimbe datele din blockchain, de exemplu, pentru a efectua propria tranzacție la adresa aleasă. După cum sa menționat deja, hash-ul fiecărui bloc din blockchain depinde nu numai de propriul său conținut, ci și de conținutul blocului anterior. Astfel, orice modificare a datelor din blocul original implică o modificare a datelor din alte blocuri. Acest lucru garantează imuabilitatea blockchain-ului și securitatea sistemului, deoarece este extrem de dificil să „falsăm” blockchain-ul. Cu toate acestea, trebuie remarcat faptul că hash-ul fiecărui bloc trebuie să fie unic, altfel urmărirea încercărilor de atac va deveni imposibilă.

Arborele Merkle

Toate tranzacțiile sunt reprezentate ca șiruri de caractere în format hexazecimal, care sunt indexate pentru a obține ID-uri de tranzacție. Pe baza acestora se construiește un hash de bloc, care este luat în considerare de blocul următor, asigurând imuabilitate și coerență. O singură valoare hash de bloc este colectată folosind un arbore Merkle .

Un arbore Merkle este un arbore binar complet , ale cărui vârfuri ale frunzei conțin hash -uri din tranzacții, iar vârfurile interioare conțin hash-uri de la adăugarea de valori în nodurile copil, iar nodul rădăcină al arborelui (Top Hash) conține un hash din întregul set de date.

Construcția arborelui Merkle pentru blockchain-ul bitcoin este după cum urmează:

$H(L_{i})$ - rezultatul funcției hash din tranzacție $L_{i}$

Se calculează hashe-urile tranzacțiilor plasate în blocuri: H(L1), H(L2), H(L3) și așa mai departe.
Hashurile sunt calculate din suma hashurilor tranzacțiilor, de exemplu H(H(L1) + H(L2)). Deoarece arborele Merkle este binar, numărul de elemente la fiecare iterație trebuie să fie par. Prin urmare, dacă un bloc conține un număr impar de tranzacții, atunci acesta din urmă este duplicat și adăugat la sine: hash (H(L3) + H(L3)).
În plus, hashe-urile sunt calculate din nou din suma hashe-urilor. Procesul se repetă până când se obține un singur hash - rădăcina arborelui Merkle. Este o dovadă criptografică a integrității blocului (adică că toate tranzacțiile sunt în ordinea declarată). Valoarea rădăcinii este fixată în antetul blocului.

În același timp, atunci când tranzacția L1, de exemplu, este cheltuită, atunci datele despre aceasta pot fi eliminate din bloc și numai hash-ul său poate fi lăsat pentru verificarea blocului. Când tranzacțiile L1 și L2 sunt cheltuite, atunci putem șterge hashurile lor (Hash 0-0 și Hash 0-1), lăsând doar Hash 0, din nou în scopul verificării blocurilor. În momentul în care sunt folosite toate tranzacțiile, atunci toate hashurile pot fi șterse, cu excepția Top Hash-ului, deoarece informațiile despre aceste tranzacții nu vor mai fi necesare.

Astfel, pentru a obține un hash pentru un nou bloc de lanț, este necesar să se țină cont de toate hashurile tranzacțiilor anterioare. Modificarea hash-ului a cel puțin unuia dintre blocurile anterioare va duce la o modificare a hash-ului următorului bloc, respectiv, o astfel de tranzacție poate fi imediat identificată ca nevalidă.

Mining Bitcoin

Mineritul este procesul de găsire a consensului asupra principiului Proof-Of-Work - obținerea aprobării pentru crearea unui nou bloc. De fapt, în rețeaua BitCoin, aceasta se rezumă la numărarea hash-ului din bloc și compararea acestuia cu numărul țintă : dacă hash-ul este mai mic decât țintă, atunci se generează un nou bloc, altfel nu este.

Minerii asigură creșterea continuă a blockchain-ului. Pentru aceasta, se folosește o putere de calcul uriașă - fiecare miner contribuie la creșterea hashrate-ului total al bitcoin (putere de calcul). Ponderea operațiunii de hashing bitcoin de către fiecare miner depinde de indicatorul hashrate total - cu cât este mai mare rata hash totală a rețelei, cu atât trebuie să facă mai multă muncă de calcul în mai puțin timp pentru a menține dimensiunea medie a recompensei sale miniere.

Procesul de substituire a unui nonce într-un șir continuă până când se găsește soluția corectă. Uneori, numărul de încercări poate ajunge până la milioane de ori. Minerul care găsește primul soluția potrivită adaugă blocul în blockchain și primește o recompensă pentru asta.

Procesul de selecție nonce se bazează pe metoda forței brute . Prin urmare, echipamentul minier generează continuu șiruri aleatorii până când este găsită valoarea nonce necesară .

Exemple de criptomonede care folosesc funcția hash SHA-256 pentru criptare

SHA-256 este un algoritm clasic pentru criptomonede: pe el este construită principala criptomonedă, Bitcoin. În consecință, acest algoritm este folosit și în Bitcoin forks: în Bitcoin Cash, Bitcoin SV. În același timp, în Bitcoin Gold, minerii folosesc o funcție cripto - Equihash

Pe lângă acestea, SHA-256 este utilizat și în:

Steemit;
peercoin ;
NameCoin ;
Ocoin;
Zetacoin;
emercoin .

De asemenea, algoritmul SHA-256 este folosit ca subrutină în criptomoneda Litecoin, iar algoritmul principal pentru extragerea acesteia este Scrypt.

Vezi și

Note

↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. O funcție hash criptografică rapidă și sigură . - 2003. - Nr. 230 . - P. 3-4 . Arhivat din original pe 8 decembrie 2019.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. O funcție hash criptografică rapidă și sigură . - 2003. - Nr. 230 . - S. 3 . Arhivat din original pe 8 decembrie 2019.
↑ Jean-Sebastien Coron, Antoine Joux. Criptanaliză a unei funcții hash criptografice sigure . - 2004. - Nr 013 . - S. 1.3 . Arhivat din original pe 7 decembrie 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: O propunere modestă pentru hashing FFT // Criptare rapidă a software-ului. — Springer, Berlin, Heidelberg, 10.02.2008. — P. 65 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Arhivat din original pe 8 aprilie 2019.
↑ Michael A. Halcrow, Niels Ferguson. Un al doilea atac înainte de imagine împotriva curbei eliptice Only Hash (ECOH) . - 2009. - Nr. 168 . Arhivat din original pe 24 decembrie 2018.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. O funcție hash criptografică rapidă și sigură . - 2003. - Nr. 230 . Arhivat din original pe 8 decembrie 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: O propunere modestă pentru hashing FFT // Criptare rapidă a software-ului. — Springer, Berlin, Heidelberg, 10.02.2008. - P. 54-72 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Arhivat din original pe 8 aprilie 2019.
↑ Comparație de viteză a algoritmilor criptografici populari . www.cryptopp.com. Preluat la 22 decembrie 2017. Arhivat din original la 2 iulie 2017.
↑ Swenson, Gayle . NIST selectează câștigătorul competiției Secure Hash Algorithm (SHA-3) (ing.) , NIST (2 octombrie 2012). Arhivat din original pe 5 octombrie 2012. Preluat la 23 decembrie 2017.
↑ Hernandez, Paul . NIST lansează SHA-3 Cryptographic Hash Standard , NIST ( 5 august 2015). Arhivat din original pe 24 ianuarie 2018. Preluat la 23 decembrie 2017.
↑ Morris J. Dworkin. Standard SHA-3: Funcții hash și ieșire extensibile bazate pe permutare // Federal Inf. proces. Stds. (NIST FIPS) - 202. - 2015-08-04. Arhivat din original pe 17 septembrie 2017.

Literatură

Bruce Schneier. Criptografia aplicată. Protocoale, algoritmi, texte sursă în limbaj C. - M . : Triumf, 2002. - ISBN 5-89392-055-4 .
Laponina O.R. Fundamentele criptografice ale securității . - M . : Internet University of Information Technologies - INTUIT.ru, 2004. - P. 320. - ISBN 5-9556-00020 -5.

Link -uri

Informații despre semnătura digitală electronică . (nedefinit)
Funcția Keccak Hash și construcția bureților ca o cripto-primitivă universală, pgpru.com, 2010-2013 (tradus din noekon.org)
Textul standardului oficial GOST R 34.11-2012 în Wikisource

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 Centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ