Puncte:1

Cum decriptează un atacator o funcție hash căutând liniaritatea?

drapel tn

Citirea răspunsului selectat la Proiectarea unei funcții hash din primele principii, mai degrabă decât în ​​funcție de euristică este foarte perspicace.

Secțiunea despre „neliniaritate” sugerează că transformarea fiecărei ecuații implicate în funcția hash într-una liniară înseamnă că atacatorul poate înțelege cu ușurință implementarea funcției hash.

Dacă încercați să faceți o funcție hash criptografică care folosește doar XOR și deplasare, ecuațiile vor fi liniare chiar și după infinit de runde, acum analistul este la o singură eliminare Gauss de a o rezolva și acum au capacitatea de a crea preimagini arbitrare .

Pentru a evita acest lucru, trebuie să vă faceți ecuațiile neliniare utilizând operatorul AND. Hashurile fac tot felul de deplasări și XOR-ing, dar acest pas neliniar este ceea ce le face sigure.

Dar a avea termeni neliniari nu este suficient. Trebuie să vă asigurați că atacatorul nu poate anula în mod eficient termenii neliniari din ecuațiile dvs. fixând unele intrări la 1 sau 0. De asemenea, trebuie să vă asigurați că termenii nu se vor anula dacă atacatorii iau diferența dintre două ecuații. Dacă aveți formula ++ pentru unul și altă formulă ++ pentru un alt bit. Adăugarea acestor două va da + care este acum liniar și permite atacatorului să o rezolve pentru a obține relația dintre doi biți. Fiecare ecuație liniară independentă pe care o poate crea un atacator va reduce securitatea hash-ului tău cu 1 bit.

Puteți explica mai detaliat cum ar funcționa asta? Având în vedere o funcție hash care a fost ruptă, cum ați putea arăta această situație de liniaritate pe acea funcție hash? Practic, să spunem că md5 este un exemplu (nesigur din anumite motive). Este nesigur din acest motiv de liniaritate? Dacă da, ce înseamnă asta în ceea ce privește funcția hash md5? Care sunt ecuațiile care s-au dovedit a fi liniare? Dacă md5 este un exemplu prost, care este un exemplu bun? Practic, cum căutați liniaritatea într-o funcție hash bit cu bit, care sunt tehnicile de utilizat?

Aș dori să știu tehnicile pe care le-ar putea folosi un atacator pentru a „rezolva” funcția hash bazată doar pe intrare/ieșire (fără a vedea implementarea). Dar, deoarece aceasta este probabil o întrebare prea generală sau prea implicată, această întrebare se concentrează doar pe acest aspect al ecuației liniare. Care sunt tehnicile de „ecuație liniară” pe care le-ar putea folosi un atacator pentru a rezolva o funcție hash?

kelalaka avatar
drapel in
Nu cred că poți găsi un atac atât de simplu.De exemplu, MD5 atacat cu [căi diferențiale](https://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf), trebuie să formați niște ecuația algebrică pentru a vedea asta. Dureaza...
Morrolan avatar
drapel ng
Domeniul algebrei liniare are un [set de instrumente bogat](https://en.wikipedia.org/wiki/System_of_linear_equations#Solving_a_linear_system) pentru a rezolva eficient sistemele de ecuații liniare, de ex. eliminarea gaussiană. Deci, dacă se poate exprima relația dintre intrarea și ieșirea unei funcții hash ca un sistem liniar, întreruperea acesteia este simplă.
kelalaka avatar
drapel in
@Morrolan problema nu este rezolvarea eficientă a sistemelor de ecuații liniare, ci mai degrabă cum să le construim având în vedere o funcție hash. Rezolvarea este partea ușoară, găsirea unei funcții hash care poate fi rezolvată este dificilă. De asemenea, în loc de relații liniare, dacă se obține ecuații de nivel scăzut, atunci un atac algebric ar putea ajuta.[Linearizare](https://crypto.stackexchange.com/q/75357/18298), XLS etc...
Morrolan avatar
drapel ng
@kelalaka Comentariul meu a vizat aspectul întrebării OP de ce o funcție hash pur liniară nu este viabilă - și anume pentru că există instrumente pentru a o rezolva în mod trivial.

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.