In teoria matematica functiile surjective nu admit inverse decat daca sunt si injective deci bijective. Cu toate acestea daca consideram un hash o functie surjectiva ajungem la concluzia ca din cauza coliziunilor putem totusi afla una din posibilele valori initiale. Acest articol are ca scop demonstrarea faptului ca in anumite situatii, cand ne intereseaza doar aflarea unei posibile valori initiale, o functie hash care are foarte multe coliziuni poate admite o astfel de inversa.

Definitie
Numim o functie f s-inversabila daca ea este surjectiva (oricare y exista x astfel incat f(x)=y) si daca exista o functie g astfel incat f(g(y))=y. Deci g(y)=A, unde A reprezinta multimea tuturor valorilor x pentru care f(x)=y.

Cel mai simplu exemplu de o astfel de functie este:
f(x)=x MOD 2=y, deci y poate fi 0 sau 1
Definim g(y)=y, deci f(g(y))=f(y)=y MOD 2. Cum y este 0 sau 1 => f(y)=y.

Acest rationament merge aplicat in inversarea anumitor parti din functiile hash deoarece cel care “verifica” un hash este interesat de o posibila valoare initiala si nu de cea “originala”.

Fie functia:

f(44)=105. f(27)=105. Am gasit deci ca functia prezinta coliziuni.

Incepem sa construim functia g pornind de la functia f si respectand rationamentul prezentat anterior. Vrem sa aflam o posibila valoare x pentru care f(x)=105. Generalizam la f(x)=y.
Pasul 1. Scadem din y 90
Pasul 2. Nu ne intereseaza functia modulo (vezi exemplul anterior)
Pasul 3. Scadem 5.

Deci functia g va fi:

Pentru f(x)=105, vom afla un g(105)=10. f(10)=f(27)=f(44)=…=105.
Am aflat deci ca functia f este s-inversabila si admite s-inversa g.

Trecand la ultimul rationament care ne va ajuta in aflarea unei s-inverse, precizam faptul ca o functie hash criptografica are lungime fixa (MD5, SHA1, SHA224, etc) si deci ne putem imagina ca textul initial este impaturit pana cand ajunge la lungimea dorita.

Ca sa ne dam seama cum am putea trece de acest impediment, mai intai trebuie sa observam ca trebuie sa declaram o functie f cu mai multi parametrii (imaginati-va ca fiecare parametru reprezinta un caracter) care returneaza o singura valoare.

Fie f definita pe ZxZ cu valori in Z: f(a,b)=a^b=y, unde ^ reprezinta operatia logica XOR. g va trebui sa returneze 2 parametrii a si b. Nu ne intereseaza absolut deloc cine sunt a si b. Cele doua valori xor-ate trebuie sa dea y si atat! Ca acest lucru sa ne fie usor consideram b = y iar a = 0.

In binar vom avea urmatoarea reprezentare:
a= 0 0 0 0 0 … 0
b= 0 a1 a2 … aJ unde a1,a2,.. aJ reprezinta cifre binare iar J numarul lor.

Este clar ca a^b=b=y. Deci f(g(y))=y, unde g(y) returneaza pe 0 si pe y.

Putem generaliza acest rationament la n parametrii usor asa ca nu vom mai trata inca un exemplu. Observam ca folosind acest rationament din n parametrii putem obtine k valori unde k este un numar fixat iar n o variabila.

De asemenea in loc de operatia ^ putem extinde algoritmul la a trata fel de fel de operatii si ne putem extinde chiar si la notiunea de grupuri, morfisme, monoide etc.

Mentionez ca exista vesti cum ca anumiti cercetatori chinezi ar fi reusit sa gaseasca o astfel de s-inversa pentru functia hash MD5. Totusi aceasta stire ramane un zvon si nimic mai mult.

Acest articol se poate privi ca o parte care completeaza articolul http://hackpedia.info/viewtopic.php?f=139&t=11186 scris de begood si astfel ne apropiem de un rezultat cat de cat notabil.

Trecand la solutii practice, daca inca folositi MD5…
Probabil multi dintre dumneavoastra folositi: md5(md5(text)+salt) in momentul cand hashuiti un text sau o parola si probabil multi o faceti fiindca stiti ca asa e bine. Chiar daca MD5 ar deveni inversabil noi nu vom afla (cel putin in teorie) inversand primul md5 varianta md5(text)+salt ci o alta posibila solutie. Totusi, pentru a afla un alt text care genereaza acelasi hash noi trebuie sa avem prima solutie de tipul mentionat mai sus, altfel nu vom putea inversa si al doilea hash. Acest lucru depinde si de hashul folosit (MD5, SHA etc) si de numarul de coliziuni. Daca probabilitatea de coliziune este foarte mica atunci vom afla dupa prima inversare chiar solutia de tipul md5(text)+salt.

In concluzie, daca nimeriti un hash mai slabut ati putea incerca metodele mentionate mai sus pentru a obtine o “s-inversa”.

Autor: Paunoiu Alexandru (dranaxum)

PS: Nu va feriti sa dati feedback.