SHA-1

Secure Hash Algorithm
	; Funkcja kompresji algorytmu SHA-1
Data stworzenia	1993 (SHA-0), 1995 (SHA-1)
Autorzy	NSA
Liczba rund	80

Ten artykuł należy dopracować:

od 2018-02 → napisać/poprawić definicję.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

SHA (Secure Hash Algorithm) – rodzina powiązanych ze sobą kryptograficznych funkcji skrótu zaprojektowanych przez NSA (National Security Agency) i publikowanych przez National Institute of Standards and Technology.

Pierwszy z nich opublikowany w 1993 oficjalnie nazwany SHA (nieoficjalnie, żeby nie pomylić z następcami określany jako SHA-0).

SHA-1 opublikowany został w 1995 i całkowicie zastąpił wycofany (ze względu na nieujawnione oficjalnie wady) z użytku SHA-0. SHA-0 i SHA-1 tworzą 160-bitowy skrót z wiadomości o maksymalnym rozmiarze 2⁶⁴ bitów i jest oparty na podobnych zasadach co MD5. Algorytm SHA-1 nie powinien być używany w nowych aplikacjach^[1].

W 2001 powstały cztery następne warianty określane jako SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512).

Podstawowym celem publikacji SHA był amerykański Standard Podpisu Cyfrowego (Digital Signature Standard). SHA jest podstawą szyfru blokowego SHACAL.

W 2009 NIST przeprowadził publiczny konkurs na następcę dotychczasowych funkcji skrótu w duchu podobnym do procesu wyłaniania algorytmu szyfrującego AES. Zostało zgłoszonych kilkadziesiąt kandydatur, które zostały rygorystycznie ocenione. Zwycięski algorytm wyłoniony w 2012 nosi miano SHA-3.

Porównanie funkcji SHA

Algorytm		Rozmiar skrótu (bity)	Rozmiar stanu (bity)	Rozmiar bloku (bity)	Maks. rozmiar danych (bity)	Rozmiar słowa (bity)	Liczba kroków	Operacje	Znalezione kolizje
SHA-0		160	160	512	2⁶⁴ – 1	32	80	+,and,or,xor, rot	Tak
SHA-1		160	160	512	2⁶⁴ – 1	32	80	+,and,or,xor, rot	Tak (2⁵¹)^[2]
SHA-2	SHA-256/224	256/224	256	512	2⁶⁴ – 1	32	64	+,and,or,xor, shr, rot	Nie
SHA-2	SHA-512/384	512/384	512	1024	2¹²⁸ – 1	64	80	+,and,or,xor, shr, rot	Nie

Pseudokod

Wartości początkowe:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

Przetwarzanie wstępne:
dopisz '1' do wiadomości;
dopisz k '0', gdzie 0 ⩽ k < 512 jest liczbą taką, że wynikowa długość wiadomości jest kongruentna do 448 modulo 512;
dopisz długość wiadomości w bitach (przed wypełnieniem) jako 64-bitową liczbę całkowitą zakodowaną big endian.

Przetwarzaj wiadomość 512-bitowymi porcjami:
podziel wiadomość na 512-bitowe porcje

 for (każda porcja)
 podziel porcję na 16 32-bitowych słów kodowanych big-endian w(i), 0 ⩽ i ⩽ 15

 Rozszerz 16 32-bitowych słów w 80 32-bitowych słów:
 for i from 16 to 79
  w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) <<< 1

 Zainicjuj zmienne dla tej porcji:
 a := h0
 b := h1
 c := h2
 d := h3
 e := h4

 Główna pętla:
 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

  temp := (a <<< 5) + f + e + k + w(i)
  e := d
  d := c
  c := b <<< 30
  b := a
  a := temp

 Dodaj skrót tej porcji do dotychczasowego wyniku:
 h0 := h0 + a
 h1 := h1 + b
 h2 := h2 + c
 h3 := h3 + d
 h4 := h4 + e

Wytwórz ostateczną wartość skrótu (zakodowaną big-endian):
skrót = h0 dopisz h1 dopisz h2 dopisz h3 dopisz h4

Jedyna różnica pomiędzy algorytmami SHA-0 i SHA-1 występuje w drugim kroku algorytmu i polega na nieobecności w SHA-0 1-bitowego przesunięcia (obrotu), tzn.:

   SHA-1:
       w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) <<< 1

   SHA-0:
       w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16))

Ataki

W 2004 zgłoszono udane ataki na funkcje skrótu mające strukturę podobną do SHA-1, co podniosło kwestię długotrwałego bezpieczeństwa SHA-1.

Pomiędzy rokiem 2005 a 2008 opublikowano szereg ataków zarówno na uproszczoną wersję SHA-1, jak i na pełną. Najlepszy z tych ataków wymaga jedynie około 2⁶³ operacji funkcji kompresującej (w porównaniu do 2⁸⁰ metodą brute-force).

NIST ogłosił, że do 2010 zaprzestanie stosowania SHA-1 na rzecz różnych wariantów SHA-2^[1].

W 2017 Google wraz z Centrum Wiskunde & Informatica(inne języki) ogłosiło, że przeprowadziło praktyczny atak, generując dwa różne pliki PDF o tym samym skrócie SHA-1^[3]^[4]

Przypisy

↑ ^a ^b Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (2013-05-28)].
↑ Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1.
↑ Ogłosznie przez Google pierwszej kolizja SHA-1.
↑ Pierwsza kolizja SHA-1.

Linki zewnętrzne

D. Eastlake 3rd, P.P. Jones P.P., US Secure Hash Algorithm 1 (SHA1), RFC 3174, IETF, wrzesień 2001, DOI: 10.17487/RFC3174, ISSN 2070-1721, OCLC 943595667 (ang.).
FIPS PUB 180-2, Secure Hash Standard (SHA-1, SHA-256, SHA-384, i SHA-512)
ISO/IEC 10118-3:2004, Information technology -- Security techniques -- Hash-functions -- Part 3: Dedicated hash-functions, Clause 9

[secBlog-1] Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (2013-05-28)].

[2] Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1.

[3] Ogłosznie przez Google pierwszej kolizja SHA-1.

[4] Pierwsza kolizja SHA-1.

[1]

[2]

[3]

[4]