Î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.