Puncte:3

Compoziția funcțiilor hash criptografice

drapel tr

Am dat peste multe pareri, asa ca intreb si eu despre ele.

Lăsa $H(x)$ și $F(x)$ fie funcții hash.

  • este $H(F(x))$ sau $F(H(x))$ mai sigur decât $H(x)$ sau $F(x)$
  • este $H(F(x))$ sau $F(H(x))$ în siguranță când $H(x)$ sau $F(x)$ devine vulnerabil
  • este $H(H(x))$ mai sigur decât $H(x)$

fundal

Făcând propriile mele cercetări, am găsit afirmații care sugerează această combinare H și F este o practică obișnuită de a rămâne în siguranță atunci când unul dintre ele devine nesigur, dar au existat opinii contradictorii când vine vorba despre dacă o astfel de combinație este la fel de sigură ca MAX(H, F) sau MIN(H, F) În ceea ce privește siguranța, aproape nimeni nu a sugerat că siguranța va fi mai mare sau mai mică decât aceasta.

De asemenea, am aflat că unii algoritmi care implică parole folosesc SHA256d, ceea ce este în esență SHA256(SHA256(x)), și că, în teorie, utilizarea mai multor runde ar crește siguranța hashului, care nu este atât de departe de a combina hash-ul cu el însuși.

Am și câteva gânduri personale despre asta, care provin din matematica școlară. Mi se pare evident că dacă f:A -> B si foarte mult |A| > |B| și g:B -> C si foarte mult |B| > |C| atunci g(f(x)) ar trebui să aibă mult mai multe ciocniri decât f sau g. Dar și faptul că combinăm două funcții complexe ar trebui să fie ceva mai greu de „spărțit”.

Deci, propria mea intuiție este că g(f(x)) are mai multe coliziuni, dar este mai greu să găsești o metodă pentru a găsi o coliziune intenționată și în cazul unor funcții precum SHA sau BLAKE creșterea coliziunilor nu este o problemă, dar beneficiul de securitate merită.

poncho avatar
drapel my
În practică, dacă vrem să ne bazăm pe mai multe funcții hash (și căutăm rezistență la coliziune sau a doua preimagine), mergem cu $F(x) | H(x)$ (unde $|$ este concatenare); este simplu să arătăm că (presupunând că $F$ sau $H$ are o ieșire cu lungime fixă) rezultatul este rezistent la coliziuni/a doua preimagine dacă $F$ sau $H$ este rezistent la coliziuni/a doua preimagine
kelalaka avatar
drapel in
Toate pentru asta? [Cum să hașez parolele în siguranță?](https://security.stackexchange.com/questions/211/how-to-securely-hash-passwords)
Kuba Chrabański avatar
drapel tr
Cred că încă încerci să ai sens din întrebările mele în ansamblu, când nu există. Am câteva lucruri de făcut, complet separate, pe care le-am împărțit în mici subîntrebări, pe care apoi le-am recompus ca câteva întrebări mai mari
Kuba Chrabański avatar
drapel tr
Întreb despre cazuri specifice pentru a construi o anumită intuiție, care poate, în viitor, să reducă setul de soluții de testat.
kelalaka avatar
drapel in
Criptografia nu este o divizare, rezolvare și combinare, în special pentru începători. Diavolul în detalii și combinarea a două sigure poate face modele nesigure. Spun pur și simplu că opriți-vă puțin, luați-vă timp și definiți-vă problema reală, inclusiv ceea ce ați găsit acolo și aici, în postarea cu întrebări.
Puncte:7
drapel ru

Compoziția nu este cea mai bună modalitate de a combina funcțiile hash, dar riscul este o întrebare a proprietăților de securitate de care aveți nevoie.

Pentru rezistența la coliziune, găsirea unei coliziuni pe $H(F(X))$ nu este mai greu decât să găsești o coliziune de $F(X)$ si asa daca $F$ este compromisă coliziunea, atunci așa este $H(F(X))$. Pentru a vedea asta, hai $m_1$ și $m_2$ fie la două intrări distincte astfel încât $F(m_1)=F(m_2)$ apoi pentru că $H$ este o funcție pe care o avem $H(F(m_1))=H(F(m_2))$. În cazul particular $F=H$, $H(H(X))$ nu este mai rezistent la coliziune decât $H(X)$.

În mod similar, dacă $H(X)$ este compromisă coliziunea și $F(X)$ este compromisă înainte de imagine (extrem de compromisă, astfel încât imaginile prealabile necesită mai puțin decât munca de naștere), putem compromite coliziunea $H(F(X))$ prin găsirea unei coliziuni pe $H$ și apoi găsirea imaginilor prealabile pentru ambele mesaje care se ciocnesc.

Observați diferența dintre funcțiile interioare și exterioare. În prezent, putem găsi mesaje $m_1$ și $m_2$ astfel încât $\mathrm{SHA3}(\mathrm{SHA1}(m_1))=\mathrm{SHA3}(\mathrm{SHA1}(m_2))$, dar nu putem găsi $m_3$ și $m_4$ astfel încât $\mathrm{SHA1}(\mathrm{SHA3}(m_3))=\mathrm{SHA1}(\mathrm{SHA3}(m_4))$.

În mod similar, pentru rezistența a doua pre-imagine, dacă funcția interioară este compromisă a doua pre-imagine, atunci la fel este și compoziția.

Pentru o rezistență completă la pre-imagine, cu siguranță putem găsi o pre-imagine completă pentru compoziție dacă putem găsi pre-imagini complete pentru ambele $H$ și $F$. Compromisul înainte de imagine al unei singure funcții hash este insuficient: luați în considerare un hash liniar $L(X)$ care este trivial pre-imagine ruptă. Pentru o țintă $Y$, nu găsim niciunul $X$ astfel încât $\mathrm{SHA3}(L(X))=Y$ nici $L(\mathrm{SHA3}(X))=Y$.

Puncte:6
drapel cn

Înțelepciunea generală

Ca un pic de înțelepciune generală, combinarea primitivelor criptografice este rareori un câștig direct. Poate întări unele proprietăți dacă este făcut corect, dar slăbește alte proprietăți.Așa că ar trebui făcut doar dacă întărește proprietățile la care îți pasă și nu slăbește proprietățile care îți pasă.

combinarea H și F este o practică obișnuită pentru a rămâne în siguranță atunci când unul dintre ele devine nesigur, dar au existat păreri contradictorii când vine vorba de dacă o astfel de combinație este la fel de sigură ca MAX(H, F) sau MIN(H, F) în ceea ce privește siguranța, aproape nimeni nu a sugerat că siguranța va fi mai mare sau mai mică decât aceasta.

Ai găsit păreri mixte pentru că depinde cum faci combinația. (Asta, sau pentru că oamenii erau neinformați. Se întâmplă.)

Am și câteva gânduri personale despre asta, care provin din matematica școlară. Mi se pare evident că dacă f:A -> B si foarte mult |A| > |B| și g:B -> C si foarte mult |B| > |C| atunci g(f(x)) ar trebui să aibă mult mai multe coliziuni decât f sau g.

Numărarea coliziunilor este irelevantă. Ceea ce contează este dificultatea de a le găsi. MD5(x)||SHA1(x) este un hash de 288 de biți și probabil are mai puține coliziuni pe șiruri de 257 de biți decât SHA256(x) â de fapt, este plauzibil ca MD5(x)||SHA1(x) nu are deloc coliziuni pe șiruri de 257 de biți, în timp ce SHA256(x) trebuie să aibă ciocniri după principiul porumbeilor. Dar știm cum să găsim coliziuni pe MD5(x)||SHA1(x) pentru șiruri puțin mai lungi într-un timp lung, dar realizabil (este doar puțin mai scump decât coliziunile SHA1), în timp ce nu știm deloc cum să găsim coliziunile SHA256.

Dar și faptul că combinăm două funcții complexe ar trebui să fie ceva mai greu de „spărțit”.

Nu, acesta nu este un fapt. Depinde complet de ce combini și cum.

Alcătuirea a două hasheuri

In ceea ce priveste hashuri și rezistenta la coliziune, alcătuirea a două hashuri reduce securitatea. Cu alte cuvinte, $H \circ F$ este mai puțin rezistent la coliziune decât $H$ sau $F$ pe cont propriu.

Este ușor de văzut că dacă $F$ are o coliziune, atunci la fel $H \circ F$: dacă $F(x_1 = F(x_2)$ cu $x_1 \ne x_2$ atunci $(H \circ F)(x_1) = H(F(x_1)) = H(F(x_2)) = (H \circ F)(x_2)$. Numai acest lucru înseamnă că alcătuirea a două hashe-uri este, în cel mai bun caz, inutilă dacă ceea ce îți pasă este rezistența la coliziune: ai putea la fel de bine să folosești $F$.

Rezistența la coliziune a $H \circ F$ poate fi mai bun decât cel al $H$ singur. Dacă $H$ are o coliziune $H(y_1) = H(y_2)$ cu $y_1 \ne y_2$, pentru a folosi acest fapt pentru a găsi o coliziune pentru $H \circ F$, trebuie să găsiți o preimagine pentru ambele $y_1$ și $y_2$. Deci ai încredere că $F$ este rezistent la coliziuni și rezistent la preimagine, atunci $H \circ F$ poate fi mai sigur decât $H$ în ceea ce privește rezistența la coliziune. Cu toate acestea, deoarece nu este mai sigur decât $F$, singurul motiv pentru a folosi această construcție este dacă îmbunătățește o altă proprietate.

Dacă $H \circ F$ are o coliziune, adică dacă $H(F(x_1)) = H(F(x_2))$ cu $x_1 \ne x_2$, atunci fie $F(x_1) = F(x_2)$ iar aceasta este o coliziune pentru $F$, sau $F(x_1) \ne F(x_2)$ iar aceasta este o coliziune pentru $H$. Deci compoziția nu este mai proastă decât cea mai proastă dintre cele două, pentru rezistența la ciocnire.

Alcătuirea a două hashuri poate îmbunătăți rezistența preimagine. Pentru a profita de structura lui $H \circ F$ atunci când căutați o preimagine, trebuie să găsiți amândoi o preimagine $H$ și apoi o preimagine a acesteia prin $F$. Cu toate acestea, nicio funcție hash criptografică pe care aș califica-o ca fiind mainstream nu a avut vreodată ruptă rezistența preimagine, deci nu este o preocupare practică.

Rezistența preimagine este o preocupare pentru parola funcții de hashing. Dar funcțiile hash de parole sunt un tip complet diferit de primitivă criptografică față de funcțiile hash „obișnuite”. Au parametri diferiți și obiective de securitate diferite. Rezistența la coliziune nu este relevantă pentru hashingul parolei. Alcătuirea a două funcții de hashing a parolei poate avea sens, dar trebuie să fii atent: cu siguranță este posibil să o faci greșit.

Alcătuirea a două hashuri poate îmbunătăți și proprietățile de securitate, altele decât proprietățile care definesc o funcție hash criptografică. Hashes-urile sunt adesea folosite ca oracole aleatorii, și hashurile utilizate în mod obișnuit (cum ar fi familia SHA-2) sunt cunoscute a fi imperfecte ca oracole aleatorii din cauza unei atac de extensie de lungime. Alcătuirea a două hashuri, chiar și aceeași funcție, ca în SHA256d(x) = SHA256(SHA256(x)), elimină atacul de extensie a lungimii și nu introduce o altă slăbiciune cunoscută de la sine. (âÎn sineâ este important: dacă amestecați SHA256d și SHA256 pe aceleași date, rezultatele pot fi dezastruoase.)

Concatenarea a două hashuri

Un alt mod simplu de a combina două hashuri este să le concatenați: $H(x) || F(x)$. Aceasta este o îmbunătățire clară în ceea ce privește rezistența la coliziune: dacă există o coliziune pentru $H || F$, este și o coliziune pentru $H$ și $F$. Concatenarea se îmbunătățește și ea rezistența la a doua preimagine: daca stii $H(x_1) || F(x_1)$ si vrei sa gasesti $x_2 \ne x_1$ astfel încât $H(x_1) || F(x_1) = H(x_2) || F(x_2)$, trebuie să găsiți o a doua preimagine pentru ambele $F$ și $H$. Atât pentru rezistența la coliziune, cât și pentru rezistența la a doua preimagine, concatenarea este cel puțin la fel de puternică ca cea mai slabă dintre cele două și, posibil, mai puternică.

Un exemplu în care concatenarea a fost folosită într-un protocol real este versiunile mai vechi ale protocol SSL/TLS, până la versiunea 1.1. Ei au folosit MD5(x)||SHA1(x) pentru semnătura de strângere de mână, unde preocuparea esențială de securitate este rezistența la a doua preimagine. TLS 1.2 a înlocuit-o cu o singură funcție hash personalizabilă (de obicei SHA-256 sau SHA-384): complexitatea suplimentară nu a meritat (și oricum nu exista o funcție hash populară sensibilă care să fie combinată cu SHA-256 la momentul respectiv).

Concatenarea nu este o victorie clară. De exemplu, se reduce rezistența la prima imagine la cea mai slabă dintre cele două funcţii: dacă ştii $H(x) || F(x)$ atunci poți găsi $x$ dacă știi cum să faci asta fie prin $H(x)$ sau prin $F(x)$.

Xoring două hashe-uri

Un alt mod de a combina două hashe-uri este să le xor: $H(x) \oplus F(x)$. Proprietățile de securitate ale rezultatului depind de alegerea funcțiilor. Acest lucru are un potențial evident de a merge îngrozitor de greșit: cazul special $H = F$ rezultă o ieșire care este toți biții-zero. Pe de altă parte, dacă $H$ și $F$ sunt independente, atunci $H \oplus F$ este cel puțin la fel de bun ca cel mai puternic dintre cei doi ca un oracol întâmplător. Nu sunt sigur dacă există o condiție sensibilă care ar oferi vreo garanție privind rezistența la coliziune.

Kuba Chrabański avatar
drapel tr
„Rezistența înainte de imagine este o preocupare pentru funcțiile de hashing a parolei.” La asta mă așteptam, bine, dar contează aici rezistența a doua preimagine? Eu cred că nu, cel puțin nu într-un mod direct, cum ar fi: „lipsa rezistenței preimagine nu implică o a doua rezistență preimagine” și se aplică într-o direcție
Gilles 'SO- stop being evil' avatar
drapel cn
@KubaChrabaÅski Într-adevăr, pentru o parolă, rezistența a doua preimagine este la fel de irelevantă ca și rezistența la coliziune. Dacă adversarul cunoaște o preimagine, treaba lui este gata.
Kuba Chrabański avatar
drapel tr
Bine, mulțumesc, răspuns foarte bun și cuprinzător!
Puncte:4
drapel in

Securitatea țintă a funcțiilor hash criptografice precum SHAx, BLAKE etc. este rezistența la coliziune. Costul clasic de atac de coliziune generic este $\mathcal{O}(2^{n/2})$-timp din cauza atacului de ziua de nastere.

Acum, uită-te la compozițiile tale hash în detaliu;

  • este $H(F(x))$ sau $F(H(x))$ mai sigur decât $H(x)$ sau $F(x)$
  • Atacul de extensie de lungime;

Hashingul dublu este propus de Bruce Schneier pentru a atenua atac de extensie de lungime a funcțiilor hash bazate pe MD. Atacul de extensie de lungime este efectuat împotriva prefix-secret $H(secret||mesaj)$. Hashingul dublu este conceput ca $H(H(x))$ și Bitcoin folosește SHA256d pentru a avea o minare lentă. Cazul dvs. este diferit, cu toate acestea, acest atac funcționează numai dacă doriți să utilizați acest hash pentru a construi un MAC cu construcție prefix-secretă. În hash-ul dublu, atacatorii nu pot extinde hash-ul intern, deci este în siguranță împotriva extinderii lungimii, chiar și hash-urile simple nu sunt. Este, totuși, consumator de timp, folosiți SHA3, SHA-512/256, BLAKE2, Shake care sunt deja securizate în acest mod chiar și pentru posibilul computer cuantic criptografic.

Orice funcție hash criptografică cu atac de extensie de lungime nu este Random Oracle. Prin urmare, SHA3 și BLAKE2 sunt mai aproape de oracole aleatorii.

  • **

  • Coliziune

rezistenţă**

Dacă hashurile interne $H$ sau $F$ nu este rezistent la coliziune, atunci hashurile combinate $H(F(x))$ sau $F(H(x))$ nu va fi rezistent la ciocniri. Dat $x,y$ cu $x\neq y$, dacă $H(x)=H(y)$ atunci $F((H(x))=F(H(y))$ este coliziune pentru compoziție și, în mod similar, pentru $H(F(\cdot))$ caz.

Dacă doriți să atenuați atacul de coliziune al funcției hash interne, răspunsul simplu; nu-l folosi.

  • Rezistență înainte de imagine

    Prima și a doua rezistență pre-imagine au aceeași problemă, omisă aici.

  • este $H(F(x))$ sau $F(H(x))$ în siguranță când $H(x)$ sau $F(x)$ devine vulnerabil

Când $F(x)$ are o coliziune atunci $H(F(x))$ are răspuns la o coliziune banală în prima parte.

Lăsa $F(x)$ sigur (fără coliziune, fără prelungire a lungimii, fără pre-imagine), dar nu $H(x)$ atunci ce zici $H(F(x))$? Acest lucru este un pic dificil, pentru a utiliza atacul de coliziune de $H$ trebuie să găsim imagini prealabile ale $F$ deci acest lucru este mai sigur.

  • este $H(H(x))$ mai sigur decât $H(x)$

Puțin da; $H(H(x))$ este sigur împotriva atacului de extensie de lungime. Dacă există o coliziune de $H$, $H(x)=H(y)$ cu $x \neq y$ atunci este o coliziune pentru dublu $H(H(x)) = H(H(y))$, de asemenea.

De asemenea, am aflat că unii algoritmi care implică parole folosesc SHA256d, care este în esență SHA256(SHA256(x)) și că, teoretic, utilizarea mai multor runde ar crește siguranța hash-ului, care nu este atât de departe de a combina hash-ul cu el însuși.

Cine folosește SHA256d pentru hashing parole, nu știe nimic despre ei. Hashingul parolei necesită timp, memorie și consum de fire pentru a atenua căutările masive cu CPU, GPU sau ASIC.

SHA256d este folosit în Bitcoin pentru a avea minerit lent. Orice sistem nou proiectat pentru hashing parole ar trebui să folosească cel puțin Scrypt sau Argon2 mai bun, iar sistemele vechi ar trebui să fie migrate cât mai curând posibil.


Pentru un rezultat academic detaliat despre combinatoarele hash, începeți să citiți de la

Și chiar și ei pot genera coliziuni multiple;

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.