SHA-1 - SHA-1

W kryptografii , SHA-1 ( Secure Hash Algorytm 1 ) jest kryptograficzną funkcję mieszania , które trwa sygnał wejściowy i wytwarza 160- nieco (20- bajt ), wartość skrótu zwanego Message Digest - zazwyczaj świadczone w szesnastkowym ilości 40 cyfr, . Został zaprojektowany przez Agencję Bezpieczeństwa Narodowego Stanów Zjednoczonych i jest amerykańskim federalnym standardem przetwarzania informacji .

Od 2005 roku SHA-1 nie jest uważany za bezpieczny przed dobrze finansowanymi przeciwnikami; od 2010 r. wiele organizacji zalecało jego zastąpienie. NIST formalnie zaniechał używania SHA-1 w 2011 r. i zabronił jego używania do podpisów cyfrowych w 2013 r. Od 2020 r. ataki z wybranymi prefiksami na SHA-1 są praktyczne. W związku z tym zaleca się jak najszybsze usunięcie SHA-1 z produktów i zamiast tego użycie SHA-2 lub SHA-3 . Zastąpienie SHA-1 jest pilne, gdy używa się go do podpisów cyfrowych .

Wszyscy główni dostawcy przeglądarek internetowych przestali akceptować certyfikaty SSL SHA-1 w 2017 r. W lutym 2017 r. CWI Amsterdam i Google ogłosiły, że przeprowadziły atak kolizyjny na SHA-1, publikując dwa odmienne pliki PDF, które dawały ten sam skrót SHA-1. Jednak SHA-1 jest nadal bezpieczny dla HMAC .

Firma Microsoft zakończyła obsługę podpisywania kodu SHA-1 dla usługi Windows Update 7 sierpnia 2020 r.

Rozwój

Jedna iteracja w ramach funkcji kompresji SHA-1:
A, B, C, D i E to 32-bitowe słowa stanu;
F jest funkcją nieliniową, która się zmienia; oznacza obrót bitów w lewo o n miejsc; n zmienia się dla każdej operacji; W _t jest rozszerzonym słowem wiadomości rundy t; K _t jest stałą zaokrąglenia rundy t; oznacza dodawanie modulo 2 ³² .
${\ Displaystyle \ lll _ {n}}$

SHA-1 tworzy skrót wiadomości w oparciu o zasady podobne do tych stosowanych przez Ronalda L. Rivesta z MIT przy projektowaniu algorytmów skrótu wiadomości MD2 , MD4 i MD5 , ale generuje większą wartość skrótu (160 bitów w porównaniu do 128 bitów).

SHA-1 został opracowany w ramach projektu Capstone rządu USA . Oryginalna specyfikacja algorytmu została opublikowana w 1993 roku pod tytułem Secure Hash Standard , FIPS PUB 180, przez amerykańską agencję normalizacyjną NIST (National Institute of Standards and Technology). Ta wersja jest teraz często nazywana SHA-0 . Został wycofany przez NSA wkrótce po publikacji i został zastąpiony poprawioną wersją, opublikowaną w 1995 roku w FIPS PUB 180-1 i powszechnie oznaczoną jako SHA-1 . SHA-1 różni się od SHA-0 tylko pojedynczą rotacją bitową w harmonogramie komunikatów funkcji kompresji . Według NSA zrobiono to w celu naprawienia błędu w oryginalnym algorytmie, który zmniejszał jego bezpieczeństwo kryptograficzne, ale nie dostarczył żadnych dalszych wyjaśnień. Publicznie dostępne techniki rzeczywiście wykazały kompromis SHA-0 w 2004 r. przed SHA-1 w 2017 r. Zobacz #Ataki

Aplikacje

Kryptografia

SHA-1 stanowi część kilku powszechnie używanych aplikacji i protokołów bezpieczeństwa, w tym TLS i SSL , PGP , SSH , S/MIME i IPsec . Te aplikacje mogą również korzystać z MD5 ; zarówno MD5, jak i SHA-1 są potomkami MD4 .

SHA-1 i SHA-2 to algorytmy skrótu wymagane przez prawo do stosowania w niektórych aplikacjach rządowych Stanów Zjednoczonych , w tym w innych algorytmach i protokołach kryptograficznych, w celu ochrony poufnych, niesklasyfikowanych informacji. FIPS PUB 180-1 zachęcał również do przyjęcia i używania SHA-1 przez organizacje prywatne i komercyjne. SHA-1 jest wycofywany z większości zastosowań rządowych; Amerykański Narodowy Instytut Standardów i Technologii powiedział: „Agencje federalne powinny przestać używać SHA-1 do… aplikacji, które wymagają odporności na kolizje tak szybko, jak to możliwe, i muszą używać funkcji skrótu z rodziny SHA-2 do tych zastosowań po 2010 r.” (podkreślenie w oryginale), chociaż później zostało to złagodzone, aby umożliwić użycie SHA-1 do weryfikacji starych podpisów cyfrowych i znaczników czasu.

Główną motywacją do publikacji Secure Hash Algorithm był Standard Podpisu Cyfrowego , w którym jest on włączony.

Funkcje skrótu SHA zostały użyte jako podstawa szyfrów blokowych SHACAL .

Integralność danych

Systemy kontroli wersji , takie jak Git , Mercurial i Monotone, używają SHA-1 nie do celów bezpieczeństwa, ale do identyfikacji wersji i zapewnienia, że ​​dane nie uległy zmianie z powodu przypadkowego uszkodzenia. Linus Torvalds powiedział o Gicie:

Jeśli masz uszkodzenie dysku, jeśli masz uszkodzenie pamięci DRAM, jeśli masz jakiekolwiek problemy, Git je zauważy. To nie jest kwestia tego, czy to gwarancja. Możesz mieć ludzi, którzy próbują być złośliwi. Nie odniosą sukcesu. ... Nikt nie był w stanie złamać SHA-1, ale chodzi o to, że SHA-1, jeśli chodzi o Git, nie jest nawet funkcją bezpieczeństwa. To czysta kontrola spójności. Części bezpieczeństwa są gdzie indziej, więc wiele osób zakłada, że ​​skoro Git używa SHA-1, a SHA-1 używa się do rzeczy zabezpieczonych kryptograficznie, myślą, że to potężna funkcja bezpieczeństwa. To nie ma nic wspólnego z bezpieczeństwem, to po prostu najlepszy skrót, jaki możesz uzyskać. ...

Gwarantuję Ci, że jeśli umieścisz swoje dane w Git, możesz zaufać faktowi, że pięć lat później, po przekonwertowaniu ich z dysku twardego na DVD na jakąkolwiek nową technologię i skopiowaniu ich, pięć lat później możesz zweryfikować, że dane, które otrzymujesz, są dokładnie tymi samymi danymi, które wprowadziłeś. ...

Jednym z powodów, dla których zależy mi na jądrze, mieliśmy włamanie do jednej z witryn BitKeeper , gdzie ludzie próbowali uszkodzić repozytoria kodu źródłowego jądra. Jednak Git nie wymaga drugiej odporności na obraz wstępny SHA-1 jako funkcji bezpieczeństwa, ponieważ zawsze woli zachować najwcześniejszą wersję obiektu na wypadek kolizji, zapobiegając ukradkiem nadpisywania plików przez atakującego.

Kryptanaliza i walidacja

W przypadku funkcji mieszającej, dla której L jest liczbą bitów w podsumowaniu wiadomości, znalezienie wiadomości odpowiadającej danemu skrótowi wiadomości zawsze można przeprowadzić za pomocą wyszukiwania brute force w około 2 ocenach ^L. Nazywa się to atakiem przedobrazowym i może być lub nie być praktyczne w zależności od L i konkretnego środowiska komputerowego. Jednak kolizja polegająca na znalezieniu dwóch różnych wiadomości, które generują ten sam skrót wiadomości, wymaga średnio tylko około 1,2 × 2 ^{L /2} ocen przy użyciu ataku urodzinowego . Tak więc siła funkcji skrótu jest zwykle porównywana do symetrycznego szyfru o długości połowy skrótu wiadomości. Pierwotnie uważano, że SHA-1, który zawiera 160-bitowy skrót wiadomości, ma 80-bitową siłę.

W 2005 r. kryptolodzy Xiaoyun Wang , Yiqun Lisa Yin i Hongbo Yu stworzyli pary kolizji dla SHA-0 i znaleźli algorytmy, które powinny generować kolizje SHA-1 w znacznie mniejszej liczbie niż pierwotnie oczekiwano 2 ⁸⁰ ocen.

Niektóre aplikacje wykorzystujące skróty kryptograficzne, takie jak przechowywanie haseł, są tylko w minimalnym stopniu dotknięte atakiem kolizyjnym. Skonstruowanie hasła, które działa dla danego konta, wymaga ataku preimage , a także dostępu do skrótu oryginalnego hasła, co może, ale nie musi być trywialne. Ataki nie umożliwiają odwrócenia szyfrowania hasła (np. w celu uzyskania hasła do próby z kontem użytkownika w innym miejscu). (Jednak nawet bezpieczny skrót hasła nie może zapobiec atakom brute-force na słabe hasła .)

W przypadku podpisywania dokumentów osoba atakująca nie może po prostu sfałszować podpisu z istniejącego dokumentu: osoba atakująca musiałaby przedstawić parę dokumentów, jeden nieszkodliwy, a drugi uszkadzający, i zmusić posiadacza klucza prywatnego do podpisania nieszkodliwego dokumentu. Istnieją praktyczne okoliczności, w których jest to możliwe; do końca 2008 roku możliwe było tworzenie fałszywych certyfikatów SSL przy użyciu kolizji MD5 .

Ze względu na blokową i iteracyjną strukturę algorytmów oraz brak dodatkowych kroków końcowych, wszystkie funkcje SHA (z wyjątkiem SHA-3) są podatne na ataki polegające na rozszerzaniu długości i kolizji częściowej wiadomości. Ataki te pozwalają napastnikowi sfałszować wiadomość podpisaną tylko haszem z kluczem – SHA( wiadomość || klucz ) lub SHA( klucz || wiadomość ) – poprzez rozszerzenie wiadomości i ponowne obliczenie skrótu bez znajomości klucza. Prostym usprawnieniem zapobiegającym tym atakom jest dwukrotne haszowanie: SHA _d ( wiadomość ) = SHA(SHA(0 ^b || wiadomość )) (długość 0 ^b , zero bloku, jest równa rozmiarowi bloku funkcji mieszającej) .

Ataki

Na początku 2005 roku Vincent Rijmen i Elisabeth Oswald opublikowali atak na zmniejszoną wersję SHA-1 – 53 na 80 pocisków – która wykrywa kolizje przy wysiłku obliczeniowym wynoszącym mniej niż 2 ⁸⁰ operacji.

W lutym 2005 roku ogłoszono atak Xiaoyun Wang , Yiqun Lisa Yin i Hongbo Yu. Ataki mogą znaleźć kolizje w pełnej wersji SHA-1, wymagającej mniej niż ²⁶⁹ operacji. ( Przeszukiwanie metodą brute-force wymagałoby 2 ⁸⁰ operacji.)

Autorzy piszą: „Nasza analiza opiera się w szczególności na oryginalnym ataku różnicowym na SHA-0, ataku bliskiej kolizji na SHA-0, technikach kolizji wieloblokowych, a także technikach modyfikacji wiadomości stosowanych w ataku polegającym na wyszukiwaniu kolizji na MD5. Przełamanie SHA-1 nie byłoby możliwe bez tych potężnych technik analitycznych.” Autorzy przedstawili kolizję dla 58-rundowego SHA-1, znalezionego przy 2 ³³ operacjach haszujących. Artykuł z pełnym opisem ataku został opublikowany w sierpniu 2005 roku na konferencji CRYPTO.

W wywiadzie Yin stwierdza, że: „Z grubsza wykorzystujemy następujące dwie słabości: po pierwsze, etap wstępnego przetwarzania plików nie jest wystarczająco skomplikowany; po drugie, niektóre operacje matematyczne w pierwszych 20 rundach mają nieoczekiwane problemy z bezpieczeństwem”.

W dniu 17 sierpnia 2005 r. na sesji CRYPTO 2005 Rump Session w imieniu Xiaoyun Wang , Andrew Yao i Frances Yao ogłoszono ulepszenie ataku SHA-1 , zmniejszając złożoność wymaganą do znalezienia kolizji w SHA-1 do ²⁶³ . W dniu 18 grudnia 2007 roku szczegóły tego wyniku wyjaśnił i zweryfikował Martin Cochran.

Christophe De Cannière i Christian Rechberger udoskonalili atak na SHA-1 w „Znalezienie charakterystyki SHA-1: Ogólne wyniki i zastosowania”, otrzymując nagrodę za najlepszy papier na ASIACRYPT 2006. Zderzenie dwóch bloków dla 64- nabojowego SHA-1 zostało zaprezentowane, znalezione przy użyciu niezoptymalizowanych metod z 2 ³⁵ ocenami funkcji kompresji. Ponieważ atak ten wymaga równowartości około ²³⁵ ocen, uważa się go za znaczącą przerwę teoretyczną. Ich atak został przedłużony do 73 rund (z 80) w 2010 roku przez Grechnikova. Jednak aby znaleźć rzeczywistą kolizję w pełnych 80 rundach funkcji skrótu, wymagana jest ogromna ilość czasu komputera. W tym celu 8 sierpnia 2007 r. rozpoczęto wyszukiwanie kolizji SHA-1 przy użyciu platformy obliczeniowej BOINC , zorganizowanej przez Politechnikę w Graz . Wysiłek został porzucony 12 maja 2009 r. z powodu braku postępów.

Podczas Rump Session w CRYPTO 2006 Christian Rechberger i Christophe De Cannière twierdzili, że odkryli atak kolizyjny na SHA-1, który umożliwiłby atakującemu wybranie przynajmniej części wiadomości.

W 2008 roku metodologia ataku Stéphane'a Manuela wykazała kolizje haszowe o szacowanej teoretycznej złożoności od 2 ⁵¹ do 2 ⁵⁷ operacji. Jednak później wycofał się z tego twierdzenia po stwierdzeniu, że lokalne ścieżki kolizji nie są w rzeczywistości niezależne, i ostatecznie zacytował najbardziej wydajny wektor kolizji, który był już znany przed tą pracą.

Cameron McDonald, Philip Hawkes i Josef Pieprzyk przedstawili atak kolizji hash o deklarowanej złożoności 2 ⁵² podczas Rump Session w Eurocrypt 2009. Jednak towarzyszący dokument „Differential Path for SHA-1 with complex O (2 ⁵² )” został wycofany ze względu na odkrycie autorów, że ich oszacowanie było błędne.

Jednym z ataków na SHA-1 był Marc Stevens, którego szacowany koszt wyniósł 2,77 mln USD (2012), aby złamać pojedynczą wartość skrótu, wypożyczając moc procesora z serwerów w chmurze. Stevens opracował ten atak w projekcie o nazwie HashClash, wdrażając atak na ścieżkę różnicową. W dniu 8 listopada 2010 r. twierdził, że miał w pełni działający atak bliski kolizji na pełny SHA-1 działający z szacowaną złożonością równą 2 ^57,5 uciśnięć SHA-1. Oszacował, że atak ten mógłby zostać rozszerzony do pełnej kolizji o złożoności około ²⁶¹ .

SHappening

8 października 2015 r. Marc Stevens, Pierre Karpman i Thomas Peyrin opublikowali atak kolizyjny freestart na funkcję kompresji SHA-1, który wymaga tylko 2 ^{57 ocen} SHA-1. Nie przekłada się to bezpośrednio na kolizję pełnej funkcji skrótu SHA-1 (gdzie atakujący nie może swobodnie wybrać początkowego stanu wewnętrznego), ale podważa roszczenia bezpieczeństwa SHA-1. W szczególności po raz pierwszy zademonstrowano atak na pełną SHA-1 ; wszystkie wcześniejsze ataki były zbyt drogie, aby ich autorzy mogli je przeprowadzić. Autorzy nazwali ten znaczący przełom w kryptoanalizie SHA-1 The SHAppening .

Metoda została oparta na ich wcześniejszych pracach, a także na technice przyspieszania ścieżek pomocniczych (lub bumerangach) z Joux i Peyrin oraz na wykorzystaniu wysokowydajnych/opłacalnych kart GPU firmy NVIDIA . Kolizja została wykryta na 16-węzłowym klastrze z 64 kartami graficznymi. Autorzy oszacowali, że podobną kolizję można znaleźć kupując 2000 USD czasu GPU na EC2 .

Autorzy oszacowali, że koszt wynajmu wystarczającej ilości czasu CPU/GPU EC2 do wygenerowania pełnej kolizji dla SHA-1 w momencie publikacji wynosił od 75 tys. do 120 tys. wspomnieć o krajowych agencjach wywiadowczych . W związku z tym autorzy zalecili jak najszybsze wycofanie SHA-1.

SHAttered – pierwsza publiczna kolizja

23 lutego 2017 r. CWI (Centrum Wiskunde & Informatica) i Google ogłosiły atak SHAttered , w którym wygenerowały dwa różne pliki PDF z tym samym hashem SHA-1 w około 2 ^63,1 ocenach SHA-1. Atak ten jest około 100 000 razy szybszy niż brutalne wymuszenie kolizji SHA-1 z atakiem urodzinowym , który oszacowano na 2 ^{80 ocen} SHA-1. Atak wymagał „równoważnej mocy obliczeniowej 6500 lat obliczeń na jednym procesorze i 110 lat obliczeń na jednym GPU”.

Birthday-Near-Collision Attack – pierwszy praktyczny atak z wybranym prefiksem

W dniu 24 kwietnia 2019 r. artykuł Gaëtana Leurenta i Thomasa Peyrina zaprezentowany na Eurocrypt 2019 opisywał ulepszenie poprzednio najlepszego ataku z wybranym prefiksem w funkcjach skrótu typu Merkle-Damgård opartych na szyfrach blokowych Daviesa-Meyera . Dzięki tym ulepszeniom metoda ta jest w stanie znaleźć kolizje wybranych prefiksów w około 2 ⁶⁸ ocenach SHA-1. Jest to około miliard razy szybsze (i teraz możliwe do wykorzystania w wielu atakach ukierunkowanych, dzięki możliwości wybrania prefiksu, na przykład złośliwego kodu lub sfałszowanych tożsamości w podpisanych certyfikatach) niż 2 ^77,1 ocen poprzedniego ataku (ale bez wybranego prefiksu, co był niepraktyczny w przypadku większości ataków ukierunkowanych, ponieważ znalezione kolizje były prawie losowe) i jest wystarczająco szybki, aby był praktyczny dla zaradnych atakujących, wymagając około 100 000 USD przetwarzania w chmurze. Ta metoda jest również w stanie znaleźć kolizje z wybranymi prefiksami w funkcji MD5 , ale przy złożoności 2 ^46,3 nie przewyższa wcześniejszej najlepszej dostępnej metody na poziomie teoretycznym (2 ³⁹ ), choć potencjalnie na poziomie praktycznym (≤2 ⁴⁹ ). Ten atak wymaga ponad 500 GB pamięci.

5 stycznia 2020 r. autorzy opublikowali ulepszony atak. W tym artykule demonstrują atak kolizyjny z wybranym prefiksem o złożoności ^263,4 , który w momencie publikacji kosztowałby 45 tys. USD za wygenerowaną kolizję.

SHA-0

Na CRYPTO 98, dwóch francuskich badaczy, Florent Chabaud i Antoine Joux , zaprezentowało atak na SHA-0: można znaleźć kolizje o złożoności 2 ⁶¹ , mniejszej niż 2 ⁸⁰ dla idealnej funkcji mieszającej o tym samym rozmiarze.

W 2004 r. Biham i Chen znaleźli bliskie kolizje dla SHA-0 – dwie wiadomości, które mieszają się do prawie tej samej wartości; w tym przypadku 142 ze 160 bitów jest równych. Odkryli również, że pełne kolizje SHA-0 zostały zredukowane do 62 z 80 pocisków.

Następnie, 12 sierpnia 2004 r., Joux, Carribault, Lemuet i Jalby ogłosili kolizję pełnego algorytmu SHA-0. Dokonano tego za pomocą uogólnienia ataku Chabaud i Joux. Znalezienie kolizji miało złożoność 2 ⁵¹ i zajęło około 80 000 godzin pracy procesora na superkomputerze z 256 procesorami Itanium 2 (co odpowiada 13 dniom pełnego czasu korzystania z komputera).

17 sierpnia 2004 r. podczas sesji Rump Session CRYPTO 2004 Wang , Feng, Lai i Yu ogłosili wstępne wyniki ataku na MD5 , SHA-0 i inne funkcje haszujące. Złożoność ich ataku na SHA-0 wynosi 2 ⁴⁰ , znacznie lepiej niż atak Joux et al.

W lutym 2005 roku, atak przez Xiaoyun Wang , Yiqun Lisa Yin i Hongbo Yu ogłoszono które mogłyby znaleźć kolizji w SHA-0 w 2 ³⁹ operacji.

Kolejny atak z 2008 r., w którym zastosowano atak bumerangowy, sprowadził złożoność znajdowania kolizji do 2 ^33,6 , co szacowano na 1 godzinę na przeciętnym komputerze PC z 2008 roku.

W świetle wyników dla SHA-0 niektórzy eksperci sugerowali, że należy ponownie rozważyć plany wykorzystania SHA-1 w nowych kryptosystemach . Po opublikowaniu wyników CRYPTO 2004, NIST ogłosił, że planuje wycofać użycie SHA-1 do 2010 roku na rzecz wariantów SHA-2.

Oficjalna walidacja

Implementacje wszystkich funkcji bezpieczeństwa zatwierdzonych przez FIPS mogą być oficjalnie weryfikowane za pośrednictwem programu CMVP , prowadzonego wspólnie przez Narodowy Instytut Standardów i Technologii (NIST) oraz Communications Security Establishment (CSE). W celu nieformalnej weryfikacji udostępniono pakiet do generowania dużej liczby wektorów testowych do pobrania na stronie NIST; wynikowa weryfikacja nie zastępuje jednak formalnej walidacji CMVP, która jest wymagana przez prawo dla niektórych aplikacji.

Według stanu na grudzień 2013 r. istnieje ponad 2000 zweryfikowanych implementacji SHA-1, z których 14 jest w stanie obsługiwać komunikaty o długości w bitach nie będącej wielokrotnością ośmiu (patrz Lista walidacji SHS ).

Przykłady i pseudokod

Przykładowe skróty

Są to przykłady skrótów komunikatów SHA-1 w postaci szesnastkowej i binarnej Base64 na kodowanie tekstu ASCII .

• SHA1("The quick brown fox jumps over the lazy dog")
  • Dane szesnastkowe na wyjściu: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
  • Wyprowadzany plik binarny Base64 do kodowania tekstu ASCII :L9ThxnotKPzthJ7hu3bnORuT6xI=

Nawet niewielka zmiana w komunikacie, z ogromnym prawdopodobieństwem, spowoduje zmianę wielu bitów z powodu efektu lawinowego . Na przykład zmiana dogna cogdaje hash z różnymi wartościami dla 81 ze 160 bitów:

• SHA1("The quick brown fox jumps over the lazy cog")
  • Dane szesnastkowe na wyjściu: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
  • Wyprowadzany plik binarny Base64 do kodowania tekstu ASCII :3p8sf9JeGzr60+haC9F9mxANtLM=

Hash ciągu o zerowej długości to:

• SHA1("")
  • Dane szesnastkowe na wyjściu: da39a3ee5e6b4b0d3255bfef95601890afd80709
  • Wyprowadzany plik binarny Base64 do kodowania tekstu ASCII :2jmj7l5rSw0yVb/vlWAYkK/YBwk=

Pseudokod SHA-1

Pseudokod algorytmu SHA-1 wygląda następująco:

Note 1: All variables are unsigned 32-bit quantities and wrap modulo 232 when calculating, except for
        ml, the message length, which is a 64-bit quantity, and
        hh, the message digest, which is a 160-bit quantity.
Note 2: All constants in this pseudo code are in big endian.
        Within each word, the most significant byte is stored in the leftmost byte position

Initialize variables:

h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

ml = message length in bits (always a multiple of the number of bits in a character).

Pre-processing:
append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
   is congruent to −64 ≡ 448 (mod 512)
append ml, the original message length in bits, as a 64-bit big-endian integer. 
   Thus, the total length is a multiple of 512 bits.

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    Message schedule: extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        Note 3: SHA-0 differs by not having this leftrotate.
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Main loop:
    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 leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Add this chunk's hash to result so far:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produce the final hash value (big-endian) as a 160-bit number:
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

Liczba hhjest skrótem wiadomości, który można zapisać w systemie szesnastkowym (podstawa 16).

Przyjęto, że wybrane wartości stałe użyte w algorytmie to nic z moich liczb w rękawie :

• Cztery okrągłe stałe kto 2 ³⁰ razy pierwiastki kwadratowe z 2, 3, 5 i 10. Jednak zostały niepoprawnie zaokrąglone do najbliższej liczby całkowitej zamiast do najbliższej nieparzystej liczby całkowitej, przy zrównoważonych proporcjach bitu zero i jeden. Ponadto wybranie pierwiastka kwadratowego z 10 (co nie jest liczbą pierwszą) uczyniło go wspólnym czynnikiem dla dwóch pozostałych wybranych pierwiastków kwadratowych liczb pierwszych 2 i 5, z możliwymi do wykorzystania właściwościami arytmetycznymi w kolejnych rundach, zmniejszając siłę algorytmu przeciwko znajdowanie kolizji na niektórych bitach.
• Pierwsze cztery wartości początkowe dla parametru h0through h3są takie same w przypadku algorytmu MD5, a piąta (for h4) jest podobna. Jednak nie zostały odpowiednio zweryfikowane pod kątem odporności na odwrócenie kilku pierwszych rund, aby wywnioskować możliwe kolizje na niektórych bitach, które można wykorzystać w atakach różnicowych wieloblokowych.

Zamiast sformułowania z oryginalnego FIPS PUB 180-1 pokazanego, do obliczeń fw powyższej pętli głównej można użyć następujących równoważnych wyrażeń :

Bitwise choice between c and d, controlled by b.
(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (alternative 1)
(0  ≤ i ≤ 19): f = (b and c) or ((not b) and d)           (alternative 2)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (alternative 3)
(0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       (alternative 4)
 [premo08]
Bitwise majority function.
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (alternative 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (alternative 2)
(40 ≤ i ≤ 59): f = (b and c) xor (d and (b xor c))        (alternative 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (alternative 4)
(40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d)                 (alternative 5)

Wykazano również, że dla rund 32–79 obliczano:

w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

można zastąpić:

w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) leftrotate 2

Ta transformacja utrzymuje wszystkie 64-bitowe operandy i, usuwając zależność w[i]on w[i-3], umożliwia wydajną implementację SIMD z długością wektora 4, jak instrukcje SSE x86 .

Porównanie funkcji SHA

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

Realizacje

Poniżej znajduje się lista bibliotek kryptograficznych obsługujących SHA-1:

• Botan
• Dmuchany zamek
• kryptlib
• Krypto++
• Libgcrypt
• Mbed TLS
• Pokrzywa
• LibreSSL
• OpenSSL
• GnuTLS
• SBC Kush

Przyspieszenie sprzętowe zapewniają następujące rozszerzenia procesora:

• Rozszerzenia Intel SHA : dostępne w niektórych procesorach Intel i AMD x86.
• PRZEZ Kłódkę
• Rozszerzenia kryptograficzne ARMv8

Zobacz też

• Porównanie kryptograficznych funkcji skrótu
• Podsumowanie bezpieczeństwa funkcji haszującej
• Międzynarodowe Stowarzyszenie Badań Kryptologicznych
• Bezpieczny standard skrótu

Uwagi

Bibliografia

Zewnętrzne linki

• CSRC Cryptographic Toolkit – Oficjalna strona NIST dla Bezpiecznego Standardu Hash
• FIPS 180-4: Bezpieczny standard skrótu (SHS)
• RFC  3174 (z implementacją próbki C)
• Wywiad z Yiqun Lisa Yin dotyczący ataku na SHA-1
• Wyjaśnienie udanych ataków na SHA-1 (3 strony, 2006)
• Badania kryptograficzne – Hash Collision — pytania i odpowiedzi
• SHA-1 w Curlie
• Wykład na temat SHA-1 (1h 18m) na YouTube wygłoszony przez Christofa Paar