Hash funkce SHA-1

SHA-1 je základní hash funkce, která se dnes stále velmi frekventovaně využívá. Není však považována za bezpečnou, firma Google již prezentovala úspěšný útok (viz zde https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html), kde inženýři z Googlu vypočítali, že k úspěšnému prolomení hash funkce je třeba cca rok času a 110 GPU procesorů (grafických procesorů). Hash funkci SHA-1 tedy již není možné považovat za bezpečnou. Pro důležité aplikace je vhodné využívat funkcí řady SHA-2 či MD6. Formálním předchůdcem SHA-1 byla funkce SHA-0, která se však dnes již zcela nepoužívá (kvůli bezpečnostním mezerám).

Výstupem hash funkce je 160 bitový řetězec (tzv. digest size), vstupem jsou bloky o velikosti 512 bitů. Výpočet probíhá v 80 rundách.

Princip

V následujícím pseudokódu je popsán princip algoritmu pro výpočet hash funkce (schéma hlavní smyčky v programu je v obrázku výše):

//Poznámka A: všechny proměnné jsou 32 bitové integery bez znaménka (unsigned int), pouze ml je 64 bitová velikost zprávy a hh je výsledný hash (160 bitů)
//Poznámka B: hash funkce (na rozdíl např. od MD5) využívá big-endian formu (přirozenější)

//Výchozí hodnota (později představuje uložené hodnoty hash funkce:
h0 = 0x67452301 //A
h1 = 0xEFCDAB89 //B
h2 = 0x98BADCFE //C
h3 = 0x10325476 //D
h4 = 0xC3D2E1F0 //E

//Uloží velikost zprávy v bitech
ml = velikost zprávy v bitech mod 2^64.

//Předzpracování (identické s MD5):
přidej bit s hodnotou "1" na konec zprávy
přidávej bity "0" na konec zprávy (případně i s celým novým blokem) tak, aby na konci zprávy zbylo právě 64 bitů volných
zapiš hodnotu ml (velikost zprávy v bitech) do volných 64 bitů na samém konci posledního bloku

//Rozděl zprávu do 512 bitových bloků a pro každý blok prováděj následující operace
for each (blok 512 bitů)
    rozděl blok do šestnácti 32 bitových unsigned integerů, tím vznikne pole w[i] (0 <= i <= 15)
    
    //Rozšíření 16 integerů v poli w[i] na 80:
    for i from 16 to 79
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 //leftrotate je rotace o 1 vlevo

    //Inicializace hodnot pro blok:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    //Hlavní smyčka (viz schéma výše):
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d) 
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

        //Vlastní permutace
        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    //Přidává se do výsledků
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

//Tvorba hash hodnoty z A, B, C, D a E hodnot (uložených v proměnných h0 až h4)
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4
//Výsledek (SHA-1 hash vstupu) je uložen v hh