SHA
SHA (Secure Hash Algorithm) je familija funkcija sažetka (hash funkcija) koje su naprednije od MD5. Vraćaju sažetke koji su veličine između 160 i 512 bitova, dok su oni od MD5 128-bitovni. Iz tog razloga manja je vjerojatnost da će dva različita inputa proizvesti isti sažetak, odnosno kažemo da SHA ima bolji collision resistance. SHA funkcije su zato sigurnije od MD5 te se danas upotrebljavaju u većini sustava koji zahtijevaju određenu razinu sigurnosti. Trenutno postoje tri verzije, SHA-1, SHA-2 i SHA-3, a svaka od njih ima još nekoliko inačica
SHA-1
SHA-1 je prva inačica SHA. 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 M0 , …, M15 služe za stvaranje 80 riječi W1, …,,W80. 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 s velikom količinom resursa zbog svoga sažetka. Danas se napadi na SHA-1 uz pomoć 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
SHA-2 temeljena je 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 232 :
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
SHA-3 temeljena je 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;
Izvori
[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