SHA-1

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. října 2020; kontroly vyžadují 12 úprav .

SHA-1
Vývojáři	NSA s NIST
Vytvořeno	1995
zveřejněno	1995
Předchůdce	SHA-0
Nástupce	SHA-2
Velikost hash	160 bit
Počet kol	80
Typ	hashovací funkce

Secure Hash Algorithm 1 je kryptografický hashovací algoritmus . Popsáno v RFC 3174 . Pro vstupní zprávu s libovolnou délkou ( bity maximum, což se rovná přibližně 2 exabajtům ) algoritmus generuje 160bitovou (20bajtovou) hodnotu hash, nazývanou také message digest , která se obvykle zobrazuje jako 40místné hexadecimální číslo. číslo. Používá se v mnoha kryptografických aplikacích a protokolech. Doporučuje se také jako primární pro vládní agentury v USA . Principy SHA-1 jsou podobné principům, které používal Ronald Rivest při navrhování MD4 . $2^{64}-1$

Historie

V roce 1993 NSA spolupracovala s NIST na vývoji Secure Hash Algorithm (nyní známého jako SHA-0) (zveřejněného ve FIPS PUB 180) pro bezpečný hashovací standard. NSA však tuto verzi brzy stáhla s odvoláním na chybu, kterou objevili a která nebyla nikdy zveřejněna. A nahradil ji revidovanou verzí publikovanou v roce 1995 ve FIPS PUB 180-1. Tato verze je považována za to, co se nazývá SHA-1. Později, na konferenci CRYPTO v roce 1998 , dva francouzští výzkumníci představili útok na algoritmus SHA-0, který nefungoval na algoritmu SHA-1. To mohla být chyba objevená NSA .

Popis algoritmu

SHA-1 implementuje hashovací funkci , postavenou na myšlence kompresní funkce. Vstupy do funkce komprese jsou 512bitový blok zpráv a výstup předchozího bloku zpráv. Výstupem je hodnota všech hashových bloků do tohoto bodu. Jinými slovy, hash blok je . Hodnota hash celé zprávy je výstupem posledního bloku. $M_{i}$ $h_i = f(M_i, h_{i-1})$

Inicializace

Původní zpráva je rozdělena do bloků po 512 bitech. Poslední blok je vyplněn na násobek délky 512 bitů. Nejprve se přidá 1 (bity) a poté se přidají nuly, takže délka bloku bude 512 - 64 = 448 bitů. Zbývajících 64 bitů obsahuje délku původní zprávy v bitech (ve formátu big-endian ). Pokud má poslední blok délku více než 447, ale méně než 512 bitů, pak se výplň provede následovně: nejprve se přidá 1 (bit), potom se přidají nuly až na konec 512bitového bloku; poté se vytvoří další 512bitový blok, který se do 448 bitů zaplní nulami, načež se do zbývajících 64 bitů zapíše délka původní zprávy v bitech (ve formátu big-endian). Poslední blok je vždy vyplněn, i když zpráva již má požadovanou délku.

Je inicializováno pět 32bitových proměnných.

A=0x67452301 B=0xEFCDAB89 C=0x98BADCFE D=0x10325476 E=0xC3D2E1F0

Jsou definovány čtyři nelineární operace a čtyři konstanty.

$F_t(m, l, k) = (m \klín l) \vee (\neg{m} \klín k)$	$K_t$ = 0x5A827999	0≤t≤19
$F_t(m, l, k) = m \oplus l \oplus k$	$K_t$ = 0x6ED9EBA1	20≤t≤39
$F_t(m, l, k) = (m \klín l) \vee (m \klín k) \vee (l \klín k)$	$K_t$ = 0x8F1BBCDC	40≤t≤59
$F_t(m, l, k) = m \oplus l \oplus k$	$K_t$ = 0xCA62C1D6	60≤t≤79

Hlavní smyčka

Hlavní smyčka iterativně zpracovává každý 512bitový blok. Na začátku každé smyčky jsou zavedeny proměnné a, b, c, d, e, které jsou inicializovány hodnotami A, B, C, D, E. Blok zpráv se převede z 16 32bitových slov na 80 32bitových slov podle následujícího pravidla: $M_{i}$ $W_j$

W_t = M_t

pro 0≤t≤15 = ( -3-8-14-16 ) << 1 pro 16≤t≤79

W_{t}

W_{t}

\oplus

W_{t}

\oplus

W_{t}

\oplus

W_{t}

, kde "<<" je kruhový posun doleva.

pro 0 až 79 teplota = (a<<5) + ( b,c,d) + e + e = d d = c c = b<<30 b = a

t

F_t

W_t + K_t

a = tepl

, kde "+" je sčítání 32bitových celých čísel bez znaménka s přebytkem (33. bit) vyřazeným.

Poté se hodnoty a, b, c, d, e přidají k A, B, C, D, E. Začíná další iterace.

Konečná hodnota bude zřetězením pěti 32bitových slov (A, B, C, D, E) do jedné 160bitové hašovací hodnoty.

Pseudokód SHA-1

Pseudokód pro algoritmus SHA-1 je následující:

Poznámka: Všechny použité proměnné jsou 32bitové. Inicializace proměnné: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Předběžné zpracování: Ke zprávě připojte bit '1' Připojte k bitů „0“, kde k je nejmenší číslo ≥ 0, takže délka výsledné zprávy (v bitech) modulo 512 je srovnatelné s 448 (délka mod 512 == 448) Přidejte délku původní zprávy (před předzpracováním) jako 64bitové celé číslo Big-endian číslo, v bitech . V tomto procesu je zpráva rozdělena sekvenčně o 512 bitů: pro iteraci přes všechny takové části tento kousek jsme rozdělili na 16 částí, 32bitová slova (big-endian) w[i], 0 <= i <= 15 16 32bitových slov je doplněno na 80 32bitových slov: pro i od 16 do 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) otočit doleva 1 Inicializace hodnot hash této části: a = h0 b = h1 c = h2 d = h3 e=h4 Hlavní smyčka: pro i od 0 do 79 , pokud 0 ≤ i ≤ 19 , pak f = (bac) nebo ( ( ne b) ad ) k = 0x5A827999 jinak pokud 20 ≤ i ≤ 39 , pak f = b xor c xor d k = 0x6ED9EBA1 jinak pokud 40 ≤ i ≤ 59 , pak f = ( bac) nebo ( bad ) nebo (c a d ) k = 0x8F1BBCDC jinak pokud 60 ≤ i ≤ 79 , pak f = b xor c xor d k = 0xCA62C1D6 temp = ( otočit vlevo 5) + f + e + k + w[i] e=d d=c c = b levotočivé 30 b = a a = tepl Přidejte k výsledku hash hodnotu této části: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Konečná hodnota hash (h0, h1, h2, h3, h4 musí být převedena na big-endian): digest = hash = h0 append h1 append h2 append h3 append h4

Namísto původního znění FIPS PUB 180-1 jsou uvedeny následující ekvivalentní výrazy, které lze použít na počítači fv hlavní smyčce:

(0 ≤ i ≤ 19): f = d xor (ba ( c xor d)) (alternativa 1) (0 ≤ i ≤ 19): f = ( bac ) xor (( nikoli b) a d) ( alternativa 2) (0 ≤ i ≤ 19): f = ( bac ) + (( ne b) ad ) (alternativa 3) (40 ≤ i ≤ 59): f = ( bac) nebo (da ( b nebo c)) ( alternativa 1) (40 ≤ i ≤ 59): f = ( bac) nebo ( da ( b ) xor c)) (alternativa 2) (40 ≤ i ≤ 59): f = ( bac ) + (da ( b xor c)) (alternativa 3) (40 ≤ i ≤ 59): f = ( ba c) xor ( bad ) xor (c a d ) (alternativa 4)

Příklady

Následují příklady hash SHA-1. Předpokládá se, že všechny zprávy používají kódování UTF-8 .

Hash pangram v ruštině:

SHA-1("Byly by v houštinách na jihu citrusy? Ano, ale falešný!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b

Hash pangram v angličtině:

SHA-1(" Rychlá hnědá liška skáče přes líného psa ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926

Malá změna ve zdrojovém textu (jedno písmeno velké) vede k velké změně samotného hashe. Důvodem je lavinový efekt .

SHA-1("sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640

I pro prázdný řetězec se vypočítá netriviální hodnota hash.

SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Kryptoanalýza

Kryptoanalýza hashovacích funkcí je zaměřena na studium zranitelnosti vůči různým typům útoků. Hlavní jsou:

detekce kolize – situace, kdy dvě různé zdrojové zprávy odpovídají stejné hash hodnotě.
nalezení prototypu – původní zprávy – pomocí jeho hashe.

Při řešení metodou "hrubé síly" :

první úloha vyžaduje průměrně 2160/2 = 280 operací pomocí narozeninového útoku .
druhý vyžaduje 2 160 operací.

Bezpečnost elektronického digitálního podpisu pomocí tohoto hašovacího algoritmu závisí na stabilitě hašovací funkce při hledání kolizí . Odolnost předobrazu závisí na bezpečnosti ukládání hash hesel pro účely ověřování .

V lednu 2005 Vincent Rayman a Elisabeth Oswald publikovali útok na zkrácenou verzi SHA-1 (53 ran místo 80 ), který umožňuje nalézt kolize v méně než 280 operacích.

V únoru 2005 Xiaoyun Wang , Yiqun Lisa Yin a Hongbo Yu představili útok na plný SHA-1, který vyžaduje méně než 269 operací.

O metodě autoři píší:

Představujeme soubor strategií a souvisejících technik, které lze použít k překonání některých důležitých překážek při hledání kolizí v SHA-1. Nejprve hledáme téměř kolizní diferenciální cesty, které mají malou „Hammingovu váhu“ v „šumovém vektoru“, kde každý bit představuje 6-krokovou lokální kolizi. Potom podle toho upravíme cestu diferenciálu z prvního stupně na jinou přijatelnou cestu diferenciálu, abychom se vyhnuli nepřijatelným sériovým a zkráceným kolizím. Nakonec převedeme dvě jednoblokové téměř kolizní diferenciální cesty na jednu dvoublokovou kolizní cestu s dvojnásobnou výpočetní náročností. [jeden]

Původní text (anglicky)[ zobrazitskrýt]

Představujeme sadu strategií a odpovídajících technik, které lze použít k odstranění některých hlavních překážek při hledání kolizí pro SHA-1. Nejprve hledáme téměř srážkovou diferenciální cestu, která má nízkou Hammingovu váhu ve „vektoru narušení“, kde každý 1 bit představuje 6-krokovou lokální kolizi. Za druhé vhodně upravíme diferenciální dráhu v prvním kole na jinou možnou diferenciální dráhu, abychom se vyhnuli nemožným po sobě jdoucím lokálním kolizím a zkráceným lokálním kolizím. Zatřetí, transformujeme dvě jednoblokové diferenciální cesty blízké kolizi na dvoublokovou diferenciální kolizní cestu s dvojnásobnou složitostí vyhledávání.

Uvádějí také:

Naše analýza je založena zejména na původním diferenciálním útoku na SHA-0, "téměř kolizi" útoku na SHA-0, technice více bloků a původní technice úpravy zpráv používané při útocích na vyhledávání kolize na HAVAL - 128, MD4 , RIPEMD a MD5 .

Původní text (anglicky)[ zobrazitskrýt]

Naše analýza je postavena zejména na původním diferenciálním útoku na SHA-0, útoku blízké kolizi na SHA-0, technikách víceblokových kolizí a také technikách modifikace zpráv používaných při útocích na vyhledávání kolizí na HAVAL-128. , MD4, RIPEMD a MD5.

Článek popisující algoritmus byl publikován v srpnu 2005 na konferenci CRYPTO .

Ve stejném článku autoři publikovali útok na zkrácený SHA-1 (58 ran), který umožňuje najít kolize ve 233 operacích.

V srpnu 2005 na CRYPTO 2005 titíž odborníci představili vylepšenou verzi útoku na plnohodnotný SHA-1 s výpočetní náročností 263 operací. V prosinci 2007 byly podrobnosti tohoto zlepšení přezkoumány Martinem Cochranem.

Christophe de Kanier a Christian Rechberg později představili vylepšený útok na SHA-1, za který byli na konferenci ASIACRYPT v roce 2006 oceněni jako nejlepší článek . Představili kolizi dvou bloků na 64kolovém algoritmu s výpočetní složitostí asi 2 35 operací. [2]

Na Technické univerzitě v rakouském městě Graz byl zahájen rozsáhlý výzkumný projekt , který: „... využívá počítače připojené přes internet k provádění výzkumu v oblasti kryptoanalýzy. Do projektu se můžete zapojit stažením a spuštěním bezplatného programu na vašem počítači.“ [3]

Burt Kalinske , vedoucí výzkumu v „ laboratoři RSA “, předpovídá, že první předobrazový útok bude úspěšný v příštích 5 až 10 letech.

Vzhledem k tomu, že teoretické útoky na SHA-1 byly úspěšné, NIST plánuje zcela ukončit používání SHA-1 v digitálních podpisech. [čtyři]

Vzhledem k blokové a iterativní struktuře algoritmů a také nedostatku speciálního zpracování na konci hash jsou všechny hashovací funkce rodiny SHA zranitelné vůči útokům prodlužujícím zprávu a kolizím při částečném hashování zprávy. [5] Tyto útoky umožňují falšování zpráv podepsaných pouze hashem – nebo – prodloužením zprávy a přepočítáním hashe bez znalosti hodnoty klíče. Nejjednodušší opravou ochrany proti těmto útokům je zdvojnásobení hash - ( je blok nul o stejné délce jako hash funkční blok). $SHA(zpráva || klíč)$ $SHA(klíč || zpráva )$ $SHA_d(zpráva) = SHA(SHA(0^b || zpráva))$ $0^b$

2. listopadu 2007 NIST vyhlásil soutěž na vývoj nového algoritmu SHA-3 , který probíhal do roku 2012 . [6]

SHappening

8. října 2015 publikovali Marc Stevens, Pierre Karpman a Thomas Peyrin útok na kompresní funkci algoritmu SHA-1, který vyžaduje pouze 257 výpočtů .

Skutečný hack: SHAttered (detekce kolize)

Dne 23. února 2017 oznámili specialisté z Google a CWI praktický hack algoritmu zveřejněním 2 souborů PDF se stejným kontrolním součtem SHA-1 . To vyžadovalo hledání možností, což by pro 1 GPU trvalo 110 let [7] . $9\times 10^{18}$

Porovnání SHA-1 s jinými algoritmy

Srovnání s MD5

MD5 i SHA-1 jsou v podstatě vylepšená rozšíření MD4 .

podobnosti:

Čtyři etapy.
Každá akce se přičte k dříve získanému výsledku.
Velikost bloku zpracování je 512 bitů.
Oba algoritmy provádějí modulo 2 32 sčítání a jsou navrženy pro 32bitovou architekturu.

Rozdíly:

V SHA-1 je ve čtvrté fázi použita stejná funkce f jako ve druhé fázi.
V MD5 používá každá akce jedinečnou přírůstkovou konstantu. V SHA-1 jsou konstanty znovu použity pro každou ze čtyř skupin.
Do SHA-1 byla přidána pátá proměnná.
SHA-1 používá cyklický kód opravy chyb.
V MD5 se čtyři offsety použité v každém kroku liší od hodnot použitých v předchozích krocích. V SHA se v každé fázi používá konstantní hodnota posunu.
V MD5 jsou čtyři různé elementární logické funkce, v SHA-1 tři.
V MD5 je délka digestu 128 bitů, v SHA-1 je to 160 bitů.
SHA-1 obsahuje více kol (80 místo 64) a běží na 160bitové vyrovnávací paměti ve srovnání se 128bitovou vyrovnávací pamětí MD5 . SHA-1 by tedy měl na stejném hardwaru běžet asi o 25 % pomaleji než MD5 .

Bruce Schneier uzavírá: „SHA-1 je MD4 s přidáním rozšířené sádry, kroku navíc a vylepšené laviny. MD5 je MD4 s vylepšeným bit hašováním, krokem navíc a vylepšenou lavinou."

Srovnání s GOST R 34.11-94

Řada charakteristických rysů GOST R 34.11-94 :

Při zpracování bloků se používají transformace podle algoritmu GOST 28147-89 ;
Zpracuje se blok 256 bitů a výstupní hodnota je také dlouhá 256 bitů.
Uplatňují se protikolizní vyhledávací opatření založená na neúplnosti posledního bloku.
Bloky jsou zpracovávány podle šifrovacího algoritmu GOST 28147-89 , který obsahuje transformace na S-boxech , což výrazně komplikuje aplikaci metody diferenciální kryptoanalýzy při hledání kolizí algoritmu GOST R 34.11-94 . To je významné plus ve srovnání s SHA-1.
Teoretické zabezpečení GOST R 34.11-94 je 2128 , což je mnohonásobně větší než 280 pro SHA-1.

Srovnání s jinými SHA

V tabulce "střední velikost hash" znamená "velikost vnitřního hash součtu" po každé iteraci.

Variace algoritmů		Výstupní velikost hash (bity)	Mezilehlá velikost hash (bity)	Velikost bloku (bity)	Maximální délka vstupní zprávy (bity)	Velikost slova (bity)	Počet kol	Použité operace	Nalezené kolize
SHA-0		160	160	512	2 64 - 1	32	80	+,and, nebo, xor, rotl	Tady je
SHA-1		160	160	512	2 64 - 1	32	80	+,and, nebo, xor, rotl	2 52 operací
SHA-2	SHA-256/224	256/224	256	512	2 64 - 1	32	64	+,and, nebo, xor, shr, rotr	Ne
SHA-2	SHA-512/384	512/384	512	1024	2 128 - 1	64	80	+,and, nebo, xor, shr, rotr	Ne

Použití

Hashovací funkce se používají v systémech správy verzí , systémech elektronického podpisu a pro vytváření autentizačních kódů .

SHA-1 je nejběžnější z celé SHA a používá se v řadě široce používaných kryptografických aplikací a algoritmů.

SHA-1 se používá v následujících aplikacích:

S/MIME - výtahy zpráv.
SSL - výtahy zpráv.
IPSec - pro algoritmus kontroly integrity v připojení typu point-to-point.
SSH - pro kontrolu integrity přenášených dat.
PGP - pro vytvoření elektronického digitálního podpisu.
Git - k identifikaci každého objektu pomocí SHA-1 hash z informací uložených v objektu.
Mercurial - k identifikaci revizí
BitTorrent - pro kontrolu integrity stahovaných dat.

SHA-1 je základem blokové šifry SHACAL .

Prohlášení

Google již dlouho vyjadřuje nedůvěru vůči SHA-1, zejména pokud jde o použití této funkce k podepisování certifikátů TLS . V roce 2014, krátce po zveřejnění práce Marka Stevense, vývojový tým Chrome oznámil, že postupně vyřazuje SHA-1.

Od 25. dubna 2016 Yandex . Mail přestal podporovat starší mailery používající SHA-1 [8] .

Poznámky

↑ Hledání kolize v plném SHA-1 (anglicky) (stahování) . — Článek čínských výzkumníků o hacku SHA-1. Archivováno z originálu 23. srpna 2011.
↑ Nalezení charakteristik SHA-1 : Obecné výsledky a aplikace . Získáno 4. října 2017. Archivováno z originálu dne 26. července 2008.
↑ SHA-1 Collision Search Graz (anglicky) (odkaz není k dispozici) . — Výzkumný projekt Technické univerzity v Grazu. Archivováno z originálu 7. listopadu 2008.
↑ Komentáře NIST ke Cryptanalytic Attacks na SHA-1 ( nepřístupný odkaz) . — Oficiální komentář NIST k útokům SHA-1. Archivováno z originálu 13. října 2012.
↑ Niels Ferguson, Bruce Schneier a Tadayoshi Kohno, Cryptography Engineering (anglicky) (odkaz není dostupný) . Archivováno z originálu 13. října 2012. , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
↑ NIST Hash Competition (anglicky) (odkaz není dostupný) . — Soutěž o vývoj SHA-3. Archivováno z originálu 13. října 2012.
↑ První způsob generování kolizí pro SHA-1 . Získáno 9. března 2017. Archivováno z originálu dne 10. března 2017. (neurčitý)
↑ Aktualizace e-mailových programů – Mail – Yandex.Help . yandex.ru. Získáno 7. dubna 2016. Archivováno z originálu 20. dubna 2016. (neurčitý)

Literatura

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Nils Ferguson , Bruce Schneier . Praktická kryptografie = Praktická kryptografie: Navrhování a implementace bezpečných kryptografických systémů. - M . : Dialektika, 2004. - 432 s. - 3000 výtisků. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

Odkazy

RFC 3174
Přehled SHA-1 z World Wide Web Consortium Archived 4. března 2005 na Wayback Machine
SHA-1 Hack Archivováno 5. května 2017 na Wayback Machine
Zpráva o hacku SHA1
Bruce Schneier na SHA Hack Archivováno z originálu 1. prosince 2012. (Angličtina)
Důsledky úspěšných útoků SHA-1 Archivováno 26. prosince 2008 na Wayback Machine

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA