SHA-2

zestaw kryptograficznych funkcji skrótu

SHA-2 – zestaw kryptograficznych funkcji skrótu (SHA-224, SHA-256, SHA-384, SHA-512) zaprojektowany przez National Security Agency (NSA) i opublikowany w 2001 roku przez National Institute of Standards and Technology (NIST) jako Federalny standard przetwarzania informacji rządu Stanów Zjednoczonych. SHA oznacza Secure Hash Algorithm. SHA-2 zawiera szereg zmian odróżniających go od poprzednika SHA-1. SHA-2 składa się z zestawu czterech funkcji dających skróty wielkości 224, 256, 384 lub 512 bitów.

SHA-2
Ilustracja
Rodzaj algorytmu

kryptograficzna funkcja skrótu

Data stworzenia

2001

Autorzy

National Security Agency

Wielkość bloku wyjściowego

224/256 lub 384/512 [bit]

Liczba rund

64 lub 80

W roku 2005 zostały zidentyfikowane luki w bezpieczeństwie SHA-1, stwierdzono, że jest zbyt słaby i byłyby pożądane silniejsze funkcje skrótu[1]. Chociaż SHA-2 wykazuje pewne podobieństwo do algorytmu SHA-1, ataki te nie zostały skutecznie rozszerzone na SHA-2.

W 2012 roku wyłoniony został nowy standard SHA-3.

Funkcja skrótu

edytuj
 
Jedna iteracja w funkcji kompresji rodziny SHA-2. Niebieskie elementy wykonują następujące czynności:
       
Binarna rotacja używa innych stałych dla SHA-512. Podane liczby są dla SHA-256. Czerwony   jest dodaniem modulo 232.

NIST opublikował cztery dodatkowe funkcje skrótu z rodziny SHA, nazwane według ich długości skrótu (w bitach): SHA-224, SHA-256, SHA-384 i SHA-512. Algorytmy są zbiorczo określane jako SHA-2.

Algorytmy zostały opublikowane w 2001 roku w projekcie FIPS PUB 180-2, w którym to czasie zostały zaakceptowane przegląd i uwagi. FIPS PUB 180-2, który obejmuje również SHA-1, został wydany jako oficjalny standard w roku 2002. W lutym 2004 r. został opublikowany zapis o zmianie FIPS PUB 180-2, określając dodatkowy wariant, SHA-224, zdefiniowany w celu dopasowania do długości klucza dwóch kluczowych Triple DES. Warianty te są opatentowane w (US 6829355) Device for and method of one-way cryptographic hashing. (ang.). W Stanach Zjednoczonych ukazał się patent na mocy licencji royalty free[2].

SHA-256 i SHA-512 są nowatorskimi funkcjami skrótu liczonymi odpowiednio na 32- i 64-bitowych słowach. Używają różnych ilości przesunięcia i dodatkowych stałych, ale ich struktury są poza tym praktycznie identyczne, różnią się tylko liczbą rund. SHA-224 i SHA-384 są po prostu obciętymi wersjami dwóch pierwszych, obliczone z różnych wartości początkowych.

Funkcje SHA-2 wypierają przestarzałe SHA-1 szczególnie po tym, jak w 2017 roku została opracowana pierwsza praktyczna metoda generowania kolizji SHA-1[3]. SHA-256 służy do uwierzytelniania pakietów Debian oraz standardu podpisywania wiadomości DKIM; SHA-512 jest częścią systemu uwierzytelniania archiwalnych nagrań video z Międzynarodowym Trybunałem Karnym w ludobójstwie w Rwandzie[4]. SHA-256 i SHA-512 są proponowane do wykorzystania w DNSSEC[5]. Dostawcy Uniksa i Linuksa zmierzają do korzystania z 256- i 512-bitowego SHA-2 do bezpiecznego hashowania hasła[6]. Dyrektywa NIST mówi, że amerykańskie agencje rządowe muszą przestać używać SHA-1 po 2010 r.[7], a zakończenie prac nad SHA-3, może przyspieszyć migrację od SHA-1.

Obecnie najlepsze publiczne ataki łamią 41 z 64 rund SHA-256 lub 46 z 80 rund SHA-512, jak opisano w sekcji „Kryptoanaliza i walidacja” poniżej[8].

Porównanie funkcji SHA

edytuj

W tabeli poniżej wewnętrzny stan oznacza „wewnętrzną sumę hash” po każdej kompresji bloku danych.

Algorytm i
wariant
Rozmiar wyjścia (bity) Wewnętrzny rozmiar stanu (bity) Rozmiar bloku (bitów) Maksymalny rozmiar wiadomości (bitów) Rozmiar słowa (bity) Rundy Operacje Znalezione Kolizje Przykładowa wydajność (MB/s)
32b[9] 64b[10]
SHA-0 160 160 512 264−1 32 80 +,and,or,xor,rot Tak
SHA-1 160 160 512 264−1 32 80 +,and,or,xor,rot Tak[11] 153 192
SHA-2 SHA-256/224 256/224 256 512 264−1 32 64 +,and,or,xor,shr,rot Brak 111 139
SHA-512/384 512/384 512 1024 2128−1 64 80 +,and,or,xor,shr,rot Brak 99 154

Przedstawiona w tabeli wydajność służy do celów porównawczych. Testy przeprowadzano na platformie Intel Core 2 1,83 GHz z systemem Windows Vista w trybie 32-bitowym (dla wersji 32-bitowej) oraz AMD Opteron 8354 2,2 GHz z systemem Linux (dla wersji 64-bitowej).

Zastosowania

edytuj
Osobny artykuł: Funkcja skrótu.

Funkcja skrótu SHA-2 jest realizowana w niektórych powszechnie używanych aplikacjach bezpieczeństwa i protokołach, w tym TLS i SSL, PGP, SSH, S/MIME, Bitcoin i IPsec.

SHA-1 i SHA-2 są bezpiecznymi algorytmami wymaganymi przepisami prawa do stosowania w niektórych aplikacjach rządu Stanów Zjednoczonych, w tym do stosowania w innych algorytmach kryptograficznych i protokołach w celu ochrony poufnych informacji. FIPS PUB 180-1 zachęca również do wdrażania i stosowania SHA-1 przez organizacje prywatne i komercyjne. SHA-1 przestaje się już używać do większości zastosowań rządu; amerykański Narodowy Instytut Standaryzacji i Technologii zaleca: „Agencje federalne powinny jak najszybciej przestać używać SHA-1 do ... zastosowań wymagających odporności na kolizje, natomiast po 2010 muszą używać rodziny funkcji skrótu SHA-2 do tych zastosowań” (podkreślenie w oryginale)[12].

Kryptoanaliza i walidacja

edytuj

Dla funkcji skrótu znalezienie wiadomości, która odpowiada podanemu skrótowi, nazywa się atakiem preimage. Dla funkcji zwracającej skróty o długości L bitów może być on zawsze wykonany przy użyciu wyszukiwania brute force w 2L próbach, a jego praktyczność zależy od wielkości L i konkretnego środowiska komputerowego. Drugi rodzaj ataku, czyli znalezienie dwóch różnych wiadomości o tym samym skrócie, znany jest jako kolizja. Zużywa on średnio tylko 2L/2 obliczeń funkcji przy wykorzystaniu ataku urodzinowego.

Aplikacje używające skrótów kryptograficznych w zastosowaniach takich jak przechowywanie haseł są tylko w minimalnym stopniu narażone na atak kolizji. Wytworzenie hasła, które działa na danym koncie, wymaga ataku preimage, jak również dostępu do hasha z oryginalnego hasła (zwykle w pliku shadow), co może, ale nie musi, być trywialne. Odwrócenie szyfrowania haseł (np. do uzyskania hasła, aby spróbować wejść na konto użytkownika w innym miejscu) nie jest możliwe przez takie ataki (jednak nawet bezpieczny hash hasła nie może zapobiec skutecznym atakom brute-force na słabe hasła).

W przypadku podpisywania dokumentów, ataku kolizji nie da się użyć do uzyskania fałszywego podpisu istniejącego dokumentu. Atakujący musi wyprodukować parę dokumentów o tym samym skrócie: niewinny i szkodliwy, i nakłonić posiadacza klucza prywatnego do podpisania nieszkodliwego dokumentu. Istnieją praktyczne okoliczności, w których jest to możliwe, np. do końca 2008 roku udało się stworzyć fałszywe certyfikaty SSL za pomocą kolizji MD5[13].

Istnieją dwa ataki preimage typu meet-in-the-middle przeciw SHA-2 ze zmniejszoną liczbą rund. Pierwszy atakuje SHA-256 z 41 rundami (zamiast 64) ze złożonością czasową 2253,5 i złożonością miejsca 216 oraz SHA-512 z 46 rundami (zamiast 80) w czasie 2511,5 i z miejscem 23[14]. Drugi atakuje 42-rundowe SHA-256 ze złożonością czasową 2251,7 i złożonością miejsca 212 oraz 42-rundowe SHA-512 w czasie 2502 i z miejscem 222[15].

Oficjalne zatwierdzenie

edytuj
Osobny artykuł: CMVP(inne języki).

Wdrożenie wszystkich zatwierdzonych przez FIPS funkcji bezpieczeństwa może być oficjalnie zatwierdzone przez program CMVP, wspólnie przez National Institute of Standards and Technology (NIST) oraz Communications Security Establishment (CSE). Dla nieformalnej weryfikacji, pakiet do tworzenia dużej liczby wektorów testowych jest udostępniony do pobrania na stronie NIST; wynikowa weryfikacja jednak nie zastępuje w żaden sposób formalnego potwierdzenia CMVP, które jest wymagane przez prawo do pewnych zastosowań.

Przykłady wariantów SHA-2 (SHA224, SHA256, SHA384 oraz SHA512)

edytuj

Hash pustego łańcucha:

SHA224("")
0xd14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f
SHA256("")
0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA384("")
0x38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b
SHA512("")
0xcf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e

Nawet niewielka zmiana w wiadomości (z przeważającym prawdopodobieństwem) da w wyniku bardzo różniący się hash ze względu na efekt lawinowy(inne języki). Na przykład dodanie kropki do końca zdania:

SHA224("The quick brown fox jumps over the lazy dog")
0x730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525
SHA224("The quick brown fox jumps over the lazy dog.")
0x619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c
SHA256("The quick brown fox jumps over the lazy dog")
0xd7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
SHA256("The quick brown fox jumps over the lazy dog.")
0xef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c
SHA384("The quick brown fox jumps over the lazy dog")
0xca737f1014a48f4c0b6dd43cb177b0afd9e5169367544c494011e3317dbf9a509cb1e5dc1e85a941bbee3d7f2afbc9b1
SHA384("The quick brown fox jumps over the lazy dog.")
0xed892481d8272ca6df370bf706e4d7bc1b5739fa2177aae6c50e946678718fc67a7af2819a021c2fc34e91bdb63409d7
SHA512("The quick brown fox jumps over the lazy dog")
0x07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb642e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6
SHA512("The quick brown fox jumps over the lazy dog.")
0x91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bbc6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed

Pseudokod SHA-256 (wariant SHA-2)

edytuj

Pseudokod dla algorytmu SHA-256 jest następujący. Zauważmy wielki wzrost mieszania bitów w[16..63] słowa w stosunku do SHA-1.

Uwaga 1: Wszystkie zmienne są podpisane 32 bitowe bez znaku i przy obliczaniu zawijają się modulo 232 
Uwaga 2: Wszystkie stałe w tym pseudokodzie są w big endian 

Inicjowanie zmiennych 
(Pierwsze 32 bity ułamkowych części pierwiastków kwadratowych 8 pierwszych liczb pierwszych 2 .. 19):
h [0 .. 7]: =
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19

Inicjacja tablicy stałych rund 
(Pierwsze 32 bity ułamkowych części pierwiastka sześciennego pierwszych 64 liczb pierwszych 2 .. 311):
k [0 .. 63]: =
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Obróbka wstępna: 
dołącz bit '1 'do wiadomości
dołącz k bitów '0', gdzie k jest minimalną liczbą>=0 taką, że w wyniku
długość wiadomości (w bitach) mod 512 jest 448
dołącz długość wiadomości (przed wstępnego przetwarzaniem), w bitach, jako 64-bitową całkowitą big-endian 

Obróbka wiadomości w kolejnych 512-bitowych kawałkach: 
podziel wiadomość na 512-bitowe kawałki
dla  każdego kawałka
podziel kawałek na szesnaście 32-bitowych słów big-endian w [0..15]

Rozszerz szesnaście 32-bitowych słów na sześćdziesiąt cztery 32-bitowe słowa: 
for  i from  16 to 63
s0 := (w[i-15] rightrotate  7) xor (w[i-15] rightrotate  18) xor (w[i-15] rightshift  3)
s1 := (w[i-2] rightrotate  17) xor (w[i-2] rightrotate  19) xor (w[i-2] rightshift  10)
w[i] := w[i-16] +  s0 +  w[i-7] +  s1

Inicjalizuj wartość skrótu dla tego kawałka: 
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7

Pętla główna: 
for  i from  0 to 63
        s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        t1 := h + s1 + ch + k[i] + w[i]
        s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        t2 := s0 + maj

        h := g
        g := f
        f := e
        e := d + t1
        d := c
        c := b
        b := a
        a := t1 + t2

Dodaj ten hash kawałka do bieżącego rezultatu: 
h0: = h0 + a
h1: = h1 + b
h2: = h2 + c
h3: = h3 + d
h4: = h4 + e
h5: = h5 + f
h6: = h6 + g
h7: = h7 + h

Wyprodukuj ostateczną wartość skrótu (big-endian): 
digest = hash = h0 append  h1 append  h2 append  h3 append  h4 append  h5 append  h6 append  h7

Obliczanie wartości ch i maj może być zoptymalizowane w taki sam sposób, jak opisano dla SHA-1.

SHA-224 jest identyczne z SHA-256, z wyjątkiem:

  • początkowe wartości h0 do h7 są odmienne, i
  • wyjście jest zbudowane, pomijając h7.
Oto początkowe wartości zmiennych (w big endian):
(Drugie 32 bity ułamkowej części pierwiastków kwadratowych od 9. do 16. liczby pierwszej 23 .. 53)
h[0..7] :=
0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4

SHA-512 jest identyczne w konstrukcji, ale:

  • wiadomość jest podzielona na 1024-bitowe kawałki,
  • wszystkie liczby są 64 bitowe,
  • jest 80 rund, a nie 64,
  • wartości początkowe i dodatkowe stałe są rozszerzone do 64 bitów, i
  • ilość przesunięcia i rotacji jest odmienna.

SHA-384 jest identyczny z SHA-512, z wyjątkiem:

  • wartości początkowe h0 do h7 są odmienne (wzięte od 9. do 16. liczby pierwszej), a
  • wyjście jest zbudowane, pomijając h6 i h7.

Standardy: SHA-1, SHA-2

edytuj

Implementacje dla popularnych języków

edytuj

Funkcji SHA mieszania można znaleźć w wielu współczesnych językach programowania, takich jak Java[16], Python[17], PHP[18], Perl[19], C#[20] i R[21].

Inne implementacje

edytuj
Libgcrypt
Kryptograficzna biblioteka ogólnego zastosowania na podstawie kodu z GNU Privacy Guard.
OpenSSL
Szeroko stosowana biblioteka OpenSSL crypto zawierająca darmowe i otwarte implementacje SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512
Cryptlib
Biblioteka open source wieloplatformowego oprogramowania narzędzi zabezpieczających
Crypto++
Biblioteka C++ klas public domain systemów kryptograficznych, w tym implementacji algorytmów SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512.
Bouncy Castle
Bouncy Castle Library jest bezpłatną biblioteką klas Java i C# która zawiera implementacje algorytmów SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512, jak i innych algorytmów, takich jak Whirlpool,Tiger, RIPEMD, GOST-3411, MD2, MD4 i MD5.
jsSHA
Biblioteka JavaScript działająca w wielu przeglądarkach, oblicza hashe SHA pomimo faktu, że JavaScript nie obsługuje 64-bitowych operacji wymaganych do SHA-384 i SHA-512.
LibTomCrypt
Przenośny zestaw narzędzi kryptograficznych napisany w ISO C, dostępny w domenie publicznej.
Md5deep
Zestaw programów do obliczeń hashów MD5, SHA-1, SHA-256, Tiger, czy Whirlpool na dowolnej liczbie plików. Jest używany w dziedzinie bezpieczeństwa oraz administracji systemów do celów przeprowadzenia dużej liczby plików przez jeden z kilku różnych skrótów kryptograficznych. Jest podobny do sha1sum z GNU Core Utilities i md5sum.
sphlib
Darmowa biblioteka open-source, która realizuje wiele funkcji skrótu, w tym SHA-1 i SHA-2, zarówno w przenośnych (ale zoptymalizowanym) C i Java.
VHDL
Darmowy, open-source zbiór sprzętowych implementacji funkcje skrótu (w tym SHA-1 i SHA-2) w przenośnym (ale zoptymalizowanym) VHDL.

Przypisy

edytuj
  1. Schneier on Security: Cryptanalysis of SHA-1
  2. Licensing Declaration for US patent 6829355. [online], 17 lutego 2008.
  3. SHAttered [online], shattered.io [dostęp 2017-02-28] (ang.).
  4. John Markoff, A Tool to Verify Digital Records, Even as Technology Shifts, New York Times, 26 stycznia 2009
  5. J. Jansen, Use of SHA-2 Algorithms with RSA in DNSKEY and RRSIG Resource Records for DNSSEC, RFC 5702, IETF, październik 2009, DOI10.17487/RFC5702, ISSN 2070-1721, OCLC 943595667 (ang.).
  6. Ulrich Drepper, Unix crypt with SHA-256/512
  7. Secure Hashing – NIST Computer Security Division – Computer Security Resource Center. [w:] NIST [on-line]. [dostęp 2010-11-25].
  8. Yu Sasaki, Wang Lei, i Kazumaro Aoki, Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512, dostępne 3 stycznia 2010.
  9. Crypto++ 5.6.0 Benchmarks. [dostęp 2011-02-27].
  10. Crypto++ 5.6.0 Benchmarks (64b). [dostęp 2012-02-17].
  11. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov The first collision for full SHA-1
  12. National Institute on Standards and Technology Computer Security Resource Center, NIST's Policy on Hash Functions, dostęp 29 marca 2009.
  13. Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, MD5 considered harmful today: Creating a rogue CA certificate, dostęp 29 marca 2009
  14. Yu Sasaki, Lei Wang, Kazumaro Aoki, Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 [online], 25 listopada 2008.
  15. Jian Guo, Krystian Matusiewicz, Preimages for Step-Reduced SHA-2 [online], 25 listopada 2008.
  16. https://www.owasp.org/index.php/Hashing_Java # Complete_Java_Sample
  17. 15.1. hashlib — Secure hashes and message digests — Python 3.6.3 documentation [online], docs.python.org [dostęp 2017-11-26].
  18. PHP: hash – Manual [online], php.net [dostęp 2017-11-26] (ang.).
  19. http://search.cpan.org/ ~ mshelor/Digest-SHA-5.62/lib/Digest/SHA.pm
  20. Klasa SHA256 (System.Security.Cryptography) [online], msdn.microsoft.com [dostęp 2017-11-15] (pol.).
  21. Home [online], www.inside-r.org [dostęp 2017-12-27] (ang.).

Bibliografia

edytuj
  • Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193
  • Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard. „Federal Register”. 59 (131), s. 35317–35318, 1994-07-11. 

Zobacz też

edytuj

Linki zewnętrzne

edytuj