SHA-2

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
SHA-2
SHA-2.svg
Rodzaj algorytmu kryptograficzna funkcja skrótu
Rodzaj szyfru (SHA-0), SHA-1, SHA-2, SHA-3
Data stworzenia 2001
Autorzy National Security Agency
Wielkość bloku wyjściowego 224/256 lub 384/512 [bit]
Liczba rund 64 lub 80

W kryptografii SHA-2 to 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.

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.

Information icon.svg Osobny artykuł: SHA-3.

Funkcja skrótu[edytuj | edytuj kod]

Jedna iteracja w funkcji kompresji rodziny SHA-2. Niebieskie elementy wykonują następujące czynności:
\operatorname{Ch}(E,F,G) = (E \and F) \oplus (\neg E \and G) \operatorname{Ma}(A,B,C) = (A \and B) \oplus (A \and C) \oplus (B \and C) \Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22) \Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)
Binarna rotacja używa innych stałych dla SHA-512. Podane liczby są dla SHA-256. Czerwony \color{red}\boxplus 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 nie są tak powszechnie stosowane jak SHA-1, pomimo lepszego bezpieczeństwa. Przyczyny mogą obejmować brak wsparcia dla SHA-2 w systemach Windows XP z dodatkiem SP2 lub starszym[3], brak postrzegania pilności, gdyż kolizje SHA-1 nie zostały jeszcze znalezione lub chęć czekania na ustandaryzowanie się SHA-3. SHA-256 służy do uwierzytelniania pakietów Debiana[4] oraz standardu podpisywania wiadomości DKIM; SHA-512 jest częścią systemu uwierzytelniania archiwalnych video z Międzynarodowym Trybunałem Karnym w ludobójstwie w Rwandzie[5] SHA-256 i SHA-512 są proponowane do wykorzystania w DNSSEC[6]. Dostawcy Uniksa i Linuksa zmierzają do korzystania z 256- i 512-bitowego SHA-2 do bezpiecznego hashowania hasła[7]. Dyrektywa NIST mówi, że amerykańskie agencje rządowe muszą przestać używać SHA-1 po 2010 r.[8], 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[9].

Porównanie funkcji SHA[edytuj | edytuj kod]

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 [10] 64b [11]
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 Teoretyczny atak (251)[12] 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 | edytuj kod]

Information icon.svg 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)[13].

Kryptoanaliza i walidacja[edytuj | edytuj kod]

Dla funkcji skrótu, dla których L oznacza liczbę bitów w skrócie wiadomości, znalezienie wiadomości, która odpowiada danemu skrótowi wiadomości, zawsze może być wykonane przy użyciu brute force wyszukiwania w 2L próbach. Nazywa się to atakiem preimage i może lub nie może być on praktyczny w zależności od L i konkretnego środowiska komputerowego. Drugie kryterium, znalezienie dwóch różnych wiadomości, które dają ten sam skrótu wiadomości, znany jako kolizja zużywa średnio tylko 2 L/2 obliczeń za pomocą ataku urodzinowego.

W kategoriach praktycznego bezpieczeństwa, głównym problemem tych ataków jest to, że mogą utorować drogę do bardziej wydajnych. Czy tak jest, to się jeszcze okaże, ale migrację do silniejszego mieszania uważa się za rozsądną. Te aplikacje, które używają 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 lub nie może 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, osoba atakująca nie może po prostu dać fałszywego podpisu do istniejącego dokumentu, osoba atakująca musi wyprodukować parę dokumentów, jeden niewinny i jeden szkodliwy i uzyskać klucz prywatny posiadacza do podpisania nieszkodliwego dokumentu. Istnieją praktyczne okoliczności, w których jest to możliwe. Do końca 2008 roku, udało się stworzyć fałszywe certyfikaty SSL za pomocą kolizji MD5[14]

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

Oficjalne zatwierdzenie[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: CMVP.

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 | edytuj kod]

Hash pustego łańcucha:

SHA224 ("")

0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f

SHA256 ("")

0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

SHA384 ("")

0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b

SHA512 ("")

0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e

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. Na przykład dodanie kropki do końca zdania:

SHA224("The quick brown fox jumps over the lazy dog")

0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525

SHA224("The quick brown fox jumps over the lazy dog.")

0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c

SHA256("The quick brown fox jumps over the lazy dog")

0x d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592

SHA256("The quick brown fox jumps over the lazy dog.")

0x ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c

SHA384("The quick brown fox jumps over the lazy dog")

0x ca737f1014a48f4c0b6dd43cb177b0afd9e5169367544c494011e3317dbf9a509cb1e5dc1e85a941bbee3d7f2afbc9b1

SHA384("The quick brown fox jumps over the lazy dog.")

0x ed892481d8272ca6df370bf706e4d7bc1b5739fa2177aae6c50e946678718fc67a7af2819a021c2fc34e91bdb63409d7

SHA512("The quick brown fox jumps over the lazy dog")

0x 07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb642e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6

SHA512("The quick brown fox jumps over the lazy dog.")

0x 91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bbc6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed

Pseudokod SHA-256 (wariant SHA-2)[edytuj | edytuj kod]

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 podzielony 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 .

Zobacz też[edytuj | edytuj kod]

Standardy: SHA-1, SHA-2[edytuj | edytuj kod]

Implementacje dla popularnych języków[edytuj | edytuj kod]

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

Inne implementacje[edytuj | edytuj kod]

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

  1. Schneier on Security: Cryptanalysis of SHA-1
  2. Licensing Declaration for US patent 6829355.. , 2008-02-17. 
  3. Microsoft Corporation, Overview of Windows XP Service Pack 3
  4. Debian codebase w Google Code
  5. John Markoff, A Tool to Verify Digital Records, Even as Technology Shifts , New York Times, 26 stycznia 2009
  6. RFC 5702, RFC-Editor.org
  7. Ulrich Drepper, Unix crypt with SHA-256/512
  8. Secure Hashing - NIST Computer Security Division - Computer Security Resource Center. W: NIST [on-line]. [dostęp 2010-11-25].
  9. Yu Sasaki, Wang Lei, i Kazumaro Aoki, Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 , dostępne 3 stycznia 2010.
  10. Crypto++ 5.6.0 Benchmarks. [dostęp 2011-02-27].
  11. Crypto++ 5.6.0 Benchmarks (64b). [dostęp 2012-02-17].
  12. Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1
  13. National Institute on Standards and Technology Computer Security Resource Center, NIST's Policy on Hash Functions , dostęp 29 marca 2009.
  14. 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.
  15. Yu Sasaki, Lei Wang, and Kazumaro Aoki. Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512. , 2008-11-25. 
  16. Jian Guo, Krystian Matusiewicz. Preimages for Step-Reduced SHA-2. , 2008-11-25. 
  17. https://www.owasp.org/index.php/Hashing_Java # Complete_Java_Sample
  18. 14.1. hashlib — Secure hashes and message digests — Python v2.7.2 documentation
  19. PHP: hash - Manual
  20. http://search.cpan.org/ ~ mshelor/Digest-SHA-5.62/lib/Digest/SHA.pm

Bibliografia[edytuj | edytuj kod]

  • 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.