Reversing SHA256 & SHA512 ?

[Che]

Se zice ca cine poate sa faca reverse la SHA256/512 va fi cel mai bogat om din lume (pe asta se bazeaza minarea de criptomonede) dar si ca internetul din acel moment nu va mai fi sigur.

Si totusi, ceva nu inteleg.

 

In cazul algoritmilor de public key encription, cei care folosesc certificate of trust si se bazeaza pe algoritmii de criptare Diffie Helman practic se bazeaza pe inmultirea cu un numar prim care este secret si pe care il stie doar serverul in momentul generarii si nimeni altcineva, pe urma se ia modulo din numarul rezultat si key-pair se bazeaza daca au acelasi modulo si pot fi reconstruite la loc. Acest lucru ar fi practic imposibil prin bruteforce fiindca tu nu stii nici acel modulo si chiar daca il stii tu nu stii din inmultirea caror numere a rezultat, deci este practic super sigur si imposibil de spart.

 

Ok. Asta este in cazul algoritmilor de public key encription.

Dar in cazul algoritmului SHA256 sau SHA512 acesta nu se bazeaza pe lucruri necunoscute. Corect?

Tu ai si algorimtul, il poti citi de la cap la coada si vezi exact ce si cum face. Vezi si acele constante de radicali de ordinul 3 din numere prime care sunt tot timpul aceleasi si stii ca face asta de 80 de ori pana sa ajunga la hash-ul final.

Si atunci, din moment ce ai toate astea, care este impendimentul?

De ce nu se poate sa pornesti de la hash-ul rezultat si sa rescrii algoritmul sa faca pasii in ordine inversa adica sa decomprime la loc de 80 de ori si apoi sa imparta rezultatul de fiecare data la acele constante de numere prime care sunt tot timpul aceleasi pentru a rezulta in final input-ul de la care s-a plecat?

@Nytro Am vazut ca esti si tu pasionat de chestiile astea, poate ma poti lamuri, te rog.

Multumesc!

[Dragos]

Un exemplu simplu: ai numarul 6 si trebuie sa gasesti din ce numere a fost format. Utilizatorul a facut operatia 1+5, dar tu poti sa ai urmatoarele variante 0+6, 1+5, 2+4, 3+3, 4+2+5+1 si 6+0, pe langa scaderi, inmultiri, impartiri, etc. Cum stii pe care o alegi?

 

La fel si cu functiile injective, iti fac o "insumare" (depinde de algoritm) de date, pierzand mare parte din ele. Cand incerci sa faci reverse, te vei lovi de problema de mai sus.

Singura posibilitate de "decriptare" a unui hash este prin criptarea tuturor cuvintelor, parolelor, etc. care ar rezulta hash-ul. Poti face bruteforce, dictionary attack sau folosi rainbow tables, gen https://cmd5.org/. Pentru sha-256 sau sha-512 posibilitatea de coliziune (doua stringuri criptate sa dea acelasi "hash") este mica, dar fara un calculator cuantic, o sa stai ani sau sute de ani de zile sa incerci toate combinatiile.

[Nytro]

Salut, SHA256/SHA512 etc nu se pot inversa pentru ca sunt algoritmi de hashing. 

De exemplu, un hash sha256 pentru textul "Gigel" va fi 38810d5f65b12d1433aaff068818bc1f298a322b2a45a8f335645c8fe3af3510

Un hash pentru "Gigel se duce la plimbare si vede o fata de care se indragosteste apoi uita de ea cand vede un Lamborghini si gaseste 10 RON pe jos" va avea urmatorul hash: 299c91444f0f7f8ee3cf12ffc4a9483bc1caf5f43f68b0593b1dddd84a0b44be

Dupa cum vezi, indiferent de lungimea textului, lungimea hash-ului este aceeasi. Chiar daca textul (sau binarul) are 1KB sau 2 TB, un hash va avea aceeasi lungime si va fi mereu acelasi pentru acelasi input. De aceea sunt folosite pentru a nu stoca parolele in plain-text in baza de date. 

 

Ca sa luam un exemplu mai simplu: CNP. Acesta contine sexul, data nasterii, judetul ... iar ultima cifra este o "suma de control". Algoritmul exact este descris aici: https://ro.wikipedia.org/wiki/Cod_numeric_personal_(România) - asa se calculeaza acea ultima cifra. Dar sa luam un exemplu mai simplu, sa zicem ca pentru CNP 1881111111116 suma de control este cifra "6" de la final si ca se calculeaza doar adunand cifrele si scotand restul impartirii la 10 (%10 adica). 

Un hash, ca idee, e ceva asemanator. Un hash reprezinta de fapt acel "6" de la final. Poti din acel 6 sa deduci CNP-ul? E destul de clar ca nu.

 

Singurul lucru care se poate face pe hash-uri e bruteforce, care poate fi optimizat din cauza unor "probleme" in algoritmul hash-urilor. Adica sa incerci a faci hash din orice combinatii de text: aaaaaa, aaaaab, aaaaac etc pana ajungi la hash-ul dorit. 

Discutia se poate prelungi. 

[yoyois]

Ca sa completez. Ca vad ca ai cautat aritmetica modulara.

 

Cum zice si Nytro: hashul foloseste o functie one way(adica "ireversibila")

Ezista multe functii de hashing, ca exemplus usor de inteles e ridicarea la putere.

 

Daca tu ai o parola: 125

un 'hash' ar fi (125*125) = 15625.

p^2 e usor de calculat. insa sqrt(h) e mai greu.

 

daca faci parola^2^2^2^2 de 20 de ori. rezultatul este foarte greu de reversat.

 

In practica ridicarea la putere modulo Z este o functie criptografica secure(mimc sponge, posseidon)

Desigur ca se folosesc niste constante publice care au rolul de a acoperi solutiile triviale. (adica daca parola ta e 1, 1^2=1) de aia se adauga constante.

 

SHA, MD5 functioneaza pe principii asamanatoare, insa ele sunt optimizate pt a lucra pe biti (1010). Avantajul e ca un PC poate lucra extrem de repede cu biti. De aia se folosesc functii de scrambling binare.

 

In teorie ele sunt reversibile, dar puterea de calcul necesara pt a calcula inversul este mai mare decat putere de calcul de a face bruteforce.

PS: e greu sa calculezi radacina patrata a lui 24968157501988569494928780504830941785667. Similar e la fel greu sa calculezi precursorul unei runde SHA, chiar daca functia este diferita.

[Rocons]

@yoyois Rezultatul este: 1.5801315610413E+20

Nimic nu este imposibil ! 

Edited April 13, 2021 by Rocons

[yoyois]

2 hours ago, Rocons said:

@yoyois Rezultatul este: 1.5801315610413E+20

Nimic nu este imposibil ! 

Wow. Ai invatat de google recent?

 

Am dat un exemplu. In practica se foloseste aritmetica modulara in modul 256 bit sau 512 bit. Si se folosesc sute de runde.

 

Am zis "destul de greu". Bine ca am gasit un asa mare hacker care sa sparga NASA cu calc.exe

[Rocons]

Era in spirit de gluma si incurajare.

[andr82]

Am incercat o apropiere cu ceva rezultate dar inca este prototip

Daca ai

0000001

0000002

0000003

0000004

0000005

si le treci prin sha256

atunci intr-una din conversile (bin, hex, etc) obtinute pe codul criptat va rezulta un tipar ce poate fi identificat prin AI sau chiar prin alte softuri de statistica avansata. Sha256 aranjeaza bitii intr-o anumita ordine iar daca cunosti secventa din care face parte elementul care trebuie decriptat te poti apropia de range-ul elementului pe care doresti sa-l decriptezti, oferindu-ti un interval mic de posibilitati.

Ex. vrei sa aflii 0000003 si ai asa

0000001 = e27ada58f8898bde36c4bd6bbc544263d7522718603bb9f42917f49932d97c79

0000002 = 0084a86da59989f5beb2dd2d4eb84f0659f61d756c1d09414421ccf7734bc14f

0000003 = 5fd226692d4dc9ff0c8084951820d43495d67e8873669537d9b8189fb46f2147

0000004 = 8b0c3cce2a3c48571b52e5d8af08fb5c9f6c3182ba7a700dbaf1327dd674a13f

0000005 = 9166d3f4c413513a6f972f7094ddedbce740283f85b85b81d4e838257b878767

0000006 =  ed9e66523e2aa5ecdcb7abe2a0358f72d7082356dc6bb3c06f4013c159aaefa8

0000007 =  5c63149677f996191ec5857f4b452ee3d31c2190628d4252e7e428666d670450

Din moment ce sha256 ofera un hash in format hexa rezulta 64 impartit la 2 = 32

pentru 0000001

e2 7a da 58 f8 89 8b de 36 c4 bd 6b bc 54 42 63 d7 52 27 18 60 3b b9 f4 29 17 f4 99 32 d9 7c 79

conversie decimala

226 122 218 88 248 137 139 222 54 196 189 107 188 84 66 99 215 82 39 24 96 59 185 244 41 23 244 153 50 217 124 121

pentru 0000003

5f d2 26 69 2d 4d c9 ff 0c 80 84 95 18 20 d4 34 95 d6 7e 88 73 66 95 37 d9 b8 18 9f b4 6f 21 47

95 210 38 105 45 77 201 255 12 128 132 149 24 32 212 52 149 214 126 136 115 102 149 55 217 184 24 159 180 111 33 71

----------

pentru 0000002

00 84 a8 6d a5 99 89 f5 be b2 dd 2d 4e b8 4f 06 59 f6 1d 75 6c 1d 09 41 44 21 cc f7 73 4b c1 4f

0 132 168 109 165 153 137 245 190 178 221 45 78 184 79 6 89 246 29 117 108 29 9 65 68 33 204 247 115 75 193 79

s.a.m.d

rezulta final

226    122    218 88 248 137 139 222 54 196 189 107 188 84 66 99 215 82 39 24 96 59 185 244 41 23 244 153 50 217 124 121

95    210    38 105 45 77 201 255 12 128 132 149 24 32 212 52 149 214 126 136 115 102 149 55 217 184 24 159 180 111 33 71

0    132    168 109 165 153 137 245 190 178 221 45 78 184 79 6 89 246 29 117 108 29 9 65 68 33 204 247 115 75 193 79

139    12    60 206 42 60 72 87 27 82 229 216 175 8 251 92 159 108 49 130 186 122 112 13 186 241 50 125 214 116 161 63

145    102   211 244 196 19 81 58 111 151 47 112 148 221 237 188 231 64 40 63 133 184 91 129 212 232 56 37 123 135 135 103

237   158    102 82 62 42 165 236 220 183 171 226 160 53 143 114 215 8 35 86 220 107 179 192 111 64 19 193 89 170 239 168

92   99    20 150 119 249 150 25 30 197 133 127 75 69 46 227 211 28 33 144 98 141 66 82 231 228 40 102 109 103 4 80

se grupeaza pe coloane si se observa daca criptarea este total random sau daca prezinta tipare apropiate (cifre care merg pe corelatie pozitiva sau negativa si in ce masura), bine se lureza pe seturi mai mari de date consecutive, aici am scris doar de exemplu.

Daca se continua se va observa pattern pe 80% din coloane (grupe hex) DAR...

Utilizand aceste modele de analiza nu se poate decripta sau restrange range-ul necunoscutei daca celelalte date nu sunt consecutive si sa cunosti input-ul anterior ca sa ai un punct de reper si cred ca imposibil daca este 2xsha256 dublu pe string. Si metoda sha256 difera uneori...

Rezultatetele sunt multumitoare la ce am eu nevoie dar e departe de o solutie care sa poata decripta, plus ca ce am facut eu mai sus apare si intr-un doc security advisory inca din 1994.

Mai pe scurt sa inteleaga toti, la un moment dat poti deduce o grupare hex pe baza anterioarei reducand range-ul pentru brute force sau chiar pentru analiza, nu am sa zic aici tot ce se poate obtine dar am dat un exemplu.

 

 

 

 

 

 

 

 

 

Edited April 13, 2021 by andr82