SHA-2
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.
Rodzaj algorytmu | |
---|---|
Data stworzenia | |
Autorzy | |
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
edytujNIST 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
edytujW 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
edytujFunkcja 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
edytujDla 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
edytujWdroż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)
edytujHash 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 . 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)
edytujPseudokod 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
doh7
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
doh7
są odmienne (wzięte od 9. do 16. liczby pierwszej), a - wyjście jest zbudowane, pomijając
h6
ih7
.
Standardy: SHA-1, SHA-2
edytuj- Zestaw narzędzi kryptograficznych CSRC – Oficjalna strona NIST dla Secure Hash standardowa
- FIPS 180-3: Secure Hash Standard (SHS) (PDF, 236 kB) – Obecna wersja standardu Secure Hash (SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512), październik 2008
- wektory testowe dla SHA-256/384/512 z projektu Nessie
- Wektory testowe dla SHA-1, SHA-2 ze strony NIST
- NIST Cryptographic Hash Projekt. csrc.nist.gov. [zarchiwizowane z tego adresu (2010-05-05)]. SHA-3 konkurencji
- RFC 3874 ↓: 224-bit one-way function Hash: SHA-224.
- RFC 6234 ↓: US Secure Hash Algorithms SHA i SHA-oparty HMAC i HKDF). Zawiera próbki C realizacji.
Implementacje dla popularnych języków
edytujFunkcji 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- ↑ Schneier on Security: Cryptanalysis of SHA-1
- ↑ Licensing Declaration for US patent 6829355. [online], 17 lutego 2008 .
- ↑ SHAttered [online], shattered.io [dostęp 2017-02-28] (ang.).
- ↑ John Markoff, A Tool to Verify Digital Records, Even as Technology Shifts, New York Times, 26 stycznia 2009
- ↑ J. Jansen , Use of SHA-2 Algorithms with RSA in DNSKEY and RRSIG Resource Records for DNSSEC, RFC 5702, IETF, październik 2009, DOI: 10.17487/RFC5702, ISSN 2070-1721, OCLC 943595667 (ang.).
- ↑ Ulrich Drepper, Unix crypt with SHA-256/512
- ↑ Secure Hashing – NIST Computer Security Division – Computer Security Resource Center. [w:] NIST [on-line]. [dostęp 2010-11-25].
- ↑ Yu Sasaki, Wang Lei, i Kazumaro Aoki, Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512, dostępne 3 stycznia 2010.
- ↑ Crypto++ 5.6.0 Benchmarks. [dostęp 2011-02-27].
- ↑ Crypto++ 5.6.0 Benchmarks (64b). [dostęp 2012-02-17].
- ↑ Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov The first collision for full SHA-1
- ↑ National Institute on Standards and Technology Computer Security Resource Center, NIST's Policy on Hash Functions, dostęp 29 marca 2009.
- ↑ 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
- ↑ Yu Sasaki , Lei Wang , Kazumaro Aoki , Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 [online], 25 listopada 2008 .
- ↑ Jian Guo , Krystian Matusiewicz , Preimages for Step-Reduced SHA-2 [online], 25 listopada 2008 .
- ↑ https://www.owasp.org/index.php/Hashing_Java # Complete_Java_Sample
- ↑ 15.1. hashlib — Secure hashes and message digests — Python 3.6.3 documentation [online], docs.python.org [dostęp 2017-11-26] .
- ↑ PHP: hash – Manual [online], php.net [dostęp 2017-11-26] (ang.).
- ↑ http://search.cpan.org/ ~ mshelor/Digest-SHA-5.62/lib/Digest/SHA.pm
- ↑ Klasa SHA256 (System.Security.Cryptography) [online], msdn.microsoft.com [dostęp 2017-11-15] (pol.).
- ↑ 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ż
edytujLinki zewnętrzne
edytuj- R. Housley , A 224-bit One-way Hash Function: SHA-224, RFC 3874, IETF, wrzesień 2004, DOI: 10.17487/RFC3874, ISSN 2070-1721, OCLC 943595667 (ang.).
- D. Eastlake 3rd, T. Hansen , US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF), RFC 6234, IETF, maj 2011, DOI: 10.17487/RFC6234, ISSN 2070-1721, OCLC 943595667 (ang.).