Hacknite Wiki

SHA-1 (Secure Hash Algorithm 1) je funkcija sažetka (hash funkcija) koja za dani ulaz vraća 160-bitni sažetak. Jasni tekst dijeli se na 512-bitne blokove, nakon čega se nadopunjavanje zadnjeg bloka (padding) odvija na isti način kao i kod MD5. Osim toga, SHA-1 dijeli s MD5 i Merkle-Damgård konstrukciju.

Sažetak H od 160 bitova sastoji se od 5 nadovezanih 32-bitovnih varijabli koje se inicijaliziraju s heksadekadskim vrijednostima:

 	A0 = 67452301	 B0 =EFCDAB89	 C0 =98BADCFE	 D0 =10325476	 E0=C3D2E1F0

podblokovi M₀ , …, M₁₅ služe za stvaranje 80 riječi W₁, …,,W₈₀. Sažimanje svakog podbloka obavlja se u 4 kruga, svaki s po 20 koraka. Svaki od krugova koristi jednu od 4 funkcije i konstante:

 	Fi(x, y, z) = (X ^ Y) v (!X ^ Z)			1  ≤ i ≤ 20
 	Fi(x, y, z) = X ⊕ Y ⊕ Z				21 ≤ i ≤ 40
 	Fi(x, y, z) = (X ^ Y) v (X ^ Z) v (X ^ Z)		41 ≤ i ≤ 60
 	Fi(x, y, z) = X ⊕ Y ⊕ Z				61 ≤ i ≤ 80

 			   Ki = 5A827999 	1  ≤ i ≤ 20
 			   Ki = 6ED9EBA1 	21 ≤ i ≤ 40
 			   Ki = 8F1BBCDC 	41 ≤ i ≤ 60
 			   Ki = CA62C1D6	61 ≤ i ≤ 80

SHA-1 je kriptografski slomljena, a već 2005. se smatrala nesigurnom protiv napadača sa velikom količinom resursa zbog svoga kratkog sažetka. Danas se napadi na SHA-1 pomoću kolizijskog napada s odabranim prefiksom smatraju praktičnima, što je Google i dokazao 2017. generiranjem dvaju PDF-ova s istim sažetkom, tako da većina komercijalnih preglednika više ne prihvaća SSL certifikate temeljene na SHA-1 funkciji. Unatoč tome, SHA-1 se i dalje koristi.

SHA-2 je funkcija sažetka (hash funkcija) temeljena na istoj konstrukciji kao SHA-1 (Merkle-Damgård) i ima identične principe nadopunjavanja, ali uz značajno izmijenjene funkcije po kojima se sažetak računa. SHA-2 dolazi u 4 verzije različitih duljina ulaznog bloka – SHA-224, SHA-256, SHA-384 i SHA-512.

Pobliže ćemo proučiti verziju SHA-256.

U SHA-256 inicijalne heksadekadske vrijednosti 512-bitnog sažetka H su:

 	A0 = 6A09E667		B0 = BB67AE85 		C0 = 3C6EF372		D0 = A54FF53A	
	E0 = 510E527F		F0 = 9b05688C		G0 = 1F83D9AB 		H0 = 5BE0CD19

Zatim se obavljaju 64 runde računskih operacija po zadanim funkcijama i konstantama, uz zbrajanje po modulu 2³² :

Ch(X, Y, Z)  = (X ^ Y) v (!X ^ Z) 
Maj(X, Y, Z) = (X ^ Y) v (X ^ Z) v (X ^ Z)

S0(x) = ROTR2(x) ⊕ ROTR13(x) ⊕ ROTR22(x)
S1(x) = ROTR6(x) ⊕ ROTR11(x) ⊕ ROTR22(x)
F0(x) = ROTR7(x) ⊕ ROTR18(x) ⊕ SHR3(x) F1(x) = ROTR17(x)⊕ ROTR19(x) ⊕ SHR10(x)

Kt=5A827999				0 ≤ t ≤ 15
Kt=6Ed9EBA1				16 ≤ t ≤ 31
Kt=8F1BBCDC				32 ≤ t ≤ 47
Kt=CA62C1D6				48 ≤ t ≤ 64 		

Trenutno najbolji objavljeni napadi (Biclique napadi, varijanta meet-in-the-middle) na SHA-2 „lome“ samo 52 od 64 runde SHA-256, odnosno 57/80 rundi SHA-512. SHA-2 se stoga još uvijek smatra sigurnim i široko primjenjivim. Danas se koristi za osiguravanje komunikacijskih protokola (TLS, SSL, SSH, Ipsec), autentifikaciju paketa i poruka (DKIM) te verifikaciju transakcija (Bitcoin).

SHA-3 je funkcija sažetka (hash funkcija) temeljena na Keccak algoritmu, novoj spužvastoj konstrukciji te značajno izmijenjenim matematičkim principima u odnosu na prethodne iteracije SHA standarda. Izmijenjen je i način nadopunjavanja zadnjeg bloka teksta (padding) koji se u SHA-3 obavlja po shemi M||10*1

Kao i kod SHA-2, postoje 4 verzije SHA-3 algoritma, ovisno o duljini ulaznog bloka, ali se same duljine ulaznih blokova razlikuju. Tako razlikujemo SHA3-224 (1152 bitova), SHA3-256 (1088 bitova), SHA3-384 (832 bitova) i SHA3-512 (576 bitova).

Broj riječi i veličina bloka u SHA3 također ovise o verziji SHA-3 koja se koristi i računaju se po formuli 25w = c + r, gdje je w broj riječi, c kapacitet (2 puta veličina sažetka), a r veličina bloka (ostatak).

SHA-3 funkcija f se obavlja u nr = 12 + w koraka. Sama se funkcija sastoji od 5 osnovnih funkcija za manipulaciju bitovima stanja: θ, ρ, π, χ i ι. Pseudokod je dan u nastavku:

Keccak-f[b](A)
 	za i 0 do nr-1
 		// (x,y) element {0…4}
 		// funkcija θ
 		C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4];
 		D[x] = C[x-1] xor rot(C[x+1],1);
 		A[x,y] = A[x,y] xor D[x];

 		// funkcije ρ i π
  		B[y,2*x+3*y] = rot(A[x,y], r[x,y]);
  
                // funkcija χ
 	        A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]); 

 	        // funkcija ι
 	        A[0,0] = A[0,0] xor RC;
        return A; 
 

[1] Christof Paar, Jan Pelzl, Understanding Cryptography, Springer-Verlag Berlin Heidelberg, 2009.
[2] https://platforma.hacknite.hr/challenges
[3] Kriptografija i kriptoanaliza, predavanja, FER
[4] https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
[5] http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf
[6] https://eprint.iacr.org/2011/286.pdf
[7] https://keccak.team/index.html