SHA-1

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. oktober 2020; checks kræver 12 redigeringer .
SHA-1
Udviklere NSA med NIST
Oprettet 1995
offentliggjort 1995
Forgænger SHA-0
Efterfølger SHA-2
Hash størrelse 160 bit
Antal runder 80
Type hash funktion

Secure Hash Algorithm 1 er en kryptografisk hashing-  algoritme . Beskrevet i RFC 3174 . For en inputmeddelelse af vilkårlig længde ( maksimum bit, hvilket er omtrent lig med 2 exabyte ), genererer algoritmen en 160-bit (20 bytes) hashværdi, også kaldet beskedsammendraget , som normalt vises som en 40-cifret hexadecimal nummer. Anvendes i mange kryptografiske applikationer og protokoller. Anbefales også som primær for offentlige myndigheder i USA . Principperne bag SHA-1 ligner dem, Ronald Rivest brugte ved design af MD4 .

Historie

I 1993 arbejdede NSA sammen med NIST om at udvikle Secure Hash Algorithm (nu kendt som SHA-0) (udgivet i FIPS PUB 180) til en sikker hashing-standard. NSA trak dog snart denne version tilbage med henvisning til en fejl, de opdagede, som aldrig blev afsløret. Og erstattede den med en revideret version udgivet i 1995 i FIPS PUB 180-1. Denne version betragtes som det, der kaldes SHA-1. Senere, på CRYPTO-konferencen i 1998 , præsenterede to franske forskere et angreb på SHA-0-algoritmen, som ikke fungerede på SHA-1-algoritmen. Dette kan have været en fejl opdaget af NSA .

Beskrivelse af algoritmen

SHA-1 implementerer en hash-funktion , bygget på ideen om en komprimeringsfunktion. Indgangene til komprimeringsfunktionen er en 512-bit beskedblok og outputtet fra den forrige beskedblok. Outputtet er værdien af ​​alle hash-blokke indtil det tidspunkt. Med andre ord er hash- blokken . Hashværdien af ​​hele meddelelsen er output fra den sidste blok.

Initialisering

Den oprindelige besked er opdelt i blokke på 512 bit hver. Den sidste blok er polstret til et længdemultipel på 512 bit. Først tilføjes 1 (bit), og derefter tilføjes nuller, så bloklængden bliver 512 - 64 = 448 bit. De resterende 64 bit indeholder længden af ​​den originale meddelelse i bit (i big-endian- format). Hvis den sidste blok har en længde på mere end 447, men mindre end 512 bit, udføres udfyldningen som følger: først tilføjes 1 (bit), derefter tilføjes nuller op til slutningen af ​​512-bit blokken; derefter oprettes endnu en 512-bit blok, som fyldes op til 448 bit med nuller, hvorefter længden af ​​den oprindelige besked i bit (i big-endian format) skrives til de resterende 64 bit. Den sidste blok er altid polstret, selvom beskeden allerede har den ønskede længde.

Fem 32-bit variabler initialiseres.

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

Fire ikke-lineære operationer og fire konstanter er defineret.

= 0x5A827999 0≤t≤19
= 0x6ED9EBA1 20≤t≤39
= 0x8F1BBCDC 40≤t≤59
= 0xCA62C1D6 60≤t≤79

Hovedsløjfe

Hovedsløjfen behandler iterativt hver 512-bit blok. I begyndelsen af ​​hver sløjfe introduceres variablerne a, b, c, d, e, som initialiseres med henholdsvis værdierne A, B, C, D, E. Meddelelsesblokken konverteres fra 16 32-bit ord til 80 32-bit ord i henhold til følgende regel:

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

, hvor "<<" er et cirkulært skift til venstre.

for 0 til 79 temp = (a<<5) + ( b,c,d) + e + e = d d = c c = b<<30 b = a





a = temp

, hvor "+" er tilføjelsen af ​​32-bit heltal uden fortegn med det overskydende (33. bit) kasseret.

Derefter tilføjes værdierne a, b, c, d, e til henholdsvis A, B, C, D, E. Den næste iteration begynder.

Den endelige værdi vil være sammenkædningen af ​​fem 32-bit ord (A, B, C, D, E) til én 160-bit hashværdi.

SHA-1 pseudokode

Pseudokoden for SHA-1-algoritmen er som følger:


Bemærk: Alle anvendte variable er 32 bit. Variabel initialisering: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Foreløbig behandling: Vedhæft bit '1' til beskeden Tilføj k bit '0', hvor k er det mindste tal ≥ 0, således at længden af ​​den resulterende meddelelse (i bit) modulo 512 er sammenlignelig med 448 (længde mod 512 == 448) Tilføj længden af ​​den originale meddelelse (før forbehandling) som et 64-bit heltal Big-endian tal, i bits . I processen opdeles meddelelsen sekventielt med 512 bit: for iteration over alle sådanne dele vi opdeler dette stykke i 16 dele, 32-bit ord (big-endian) w[i], 0 <= i <= 15 16 32-bit ord er polstret til 80 32-bit ord: for i fra 16 til 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) drej til venstre 1 Initialisering af hashværdierne for denne del: a = h0 b = h1 c = h2 d = h3 e=h4 Hovedsløjfe: for i fra 0 til 79 , hvis 0 ≤ i ≤ 19 , så f = (b og c) eller (( ikke b) og d) k = 0x5A827999 ellers hvis 20 ≤ i ≤ 39 , så er f = b x eller c x eller d k = 0x6ED9EBA1 ellers hvis 40 ≤ i ≤ 59 , så er f = (b og c) eller (b og d) eller (c og d) k = 0x8F1BBCDC ellers hvis 60 ≤ i ≤ 79 så f = b x eller c x eller d k = 0xCA62C1D6 temp = (en venstredrejning 5) + f + e + k + w[i] e=d d=c c = b venstredrej 30 b = a a = temp Tilføj hashværdien af ​​denne del til resultatet: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Endelig hashværdi(h0, h1, h2, h3, h4 skal konverteres til big-endian): digest = hash = h0 tilføj h1 tilføj h2 tilføj h3 tilføj h4

I stedet for den oprindelige ordlyd af FIPS PUB 180-1 er følgende ækvivalente udtryk givet og kan bruges på en computer fi hovedsløjfen:

(0 ≤ i ≤ 19): f = d xor (b og (c xor d)) (alternativ 1) (0 ≤ i ≤ 19): f = (b og c) xor (( ikke b) og d) ( alternativ 2) (0 ≤ i ≤ 19): f = (b og c) + (( ikke b) og d) (alternativ 3)   (40 ≤ i ≤ 59): f = (b og c) eller (d og (b eller c)) (alternativ 1) (40 ≤ i ≤ 59): f = (b og c) eller (d og (b ) xor c)) (alternativ 2) (40 ≤ i ≤ 59): f = (b og c) + (d og (b xor c)) (alternativ 3) (40 ≤ i ≤ 59): f = (b og c) xor (b og d) xor (c og d) (alternativ 4)

Eksempler

Følgende er eksempler på SHA-1 hashes. Alle meddelelser antages at bruge UTF-8- kodning .

Hash pangram på russisk:

SHA-1("Ville der være citrus i sydens krat? Ja, men en falsk!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b

Hash pangram på engelsk:

SHA-1 (" Den hurtige brune ræv hopper over den dovne hund ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1 ("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926

En lille ændring i kildeteksten (et bogstav med stort) fører til en stor ændring i selve hashen. Dette skyldes lavineeffekten .

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

Selv for en tom streng beregnes en ikke-triviel hashværdi.

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

Krypteringsanalyse

Krypteringsanalyse af hash-funktioner er rettet mod at studere sårbarheden over for forskellige typer angreb. De vigtigste er:

Når du løser med "brute force"-metoden :

Sikkerheden af ​​den elektroniske digitale signatur ved hjælp af denne hash-algoritme afhænger af hashfunktionens stabilitet til at finde kollisioner . Preimage-modstand afhænger af sikkerheden ved lagring af password-hashes til godkendelsesformål .

I januar 2005 offentliggjorde Vincent Rayman og Elisabeth Oswald et angreb på en afkortet version af SHA-1 (53 runder i stedet for 80 ), som gør det muligt at finde kollisioner i mindre end 280 operationer.

I februar 2005 præsenterede Xiaoyun Wang , Yiqun Lisa Yin og Hongbo Yu et angreb på fuld SHA-1, der kræver mindre end 269 operationer.

Om metoden skriver forfatterne:

Vi præsenterer et sæt strategier og relaterede teknikker, der kan bruges til at overvinde nogle vigtige forhindringer i at finde kollisioner i SHA-1. Vi leder først efter nær-kollisions-differentialveje, der har en lille "Hamming-vægt" i "støjvektoren", hvor hver bit repræsenterer en 6-trins lokal kollision. Vi justerer derefter differentialvejen fra det første trin til en anden acceptabel differentialvej i overensstemmelse hermed for at undgå uacceptable serielle og trunkerede kollisioner. Til sidst konverterer vi to en-bloks-nær-kollisions-differentialveje til en to-blok-kollisionsvej med dobbelt så meget beregningsmæssig kompleksitet. [en]

Originaltekst  (engelsk)[ Visskjule]

Vi introducerer et sæt strategier og tilsvarende teknikker, der kan bruges til at fjerne nogle større forhindringer i kollisionssøgning efter SHA-1. For det første leder vi efter en nær-kollisions-differentialbane, som har lav Hamming-vægt i "forstyrrelsesvektoren", hvor hver 1-bit repræsenterer en 6-trins lokal kollision. For det andet tilpasser vi passende differentialvejen i første runde til en anden mulig differentialvej for at undgå umulige på hinanden følgende lokale kollisioner og trunkerede lokale kollisioner. For det tredje transformerer vi to en-bloks-nær-kollisions-differentialveje til en to-blok-kollisionsdifferential-sti med dobbelt søgekompleksitet.

De siger også:

Vores analyse er især baseret på det oprindelige differentielle angreb på SHA-0, "nær-kollisions"-angrebet på SHA-0, multi-blok-teknikken og den originale beskedmodifikationsteknik, der blev brugt i kollisionssøgningsangrebene på HAVAL - 128, MD4 , RIPEMD og MD5 .

Originaltekst  (engelsk)[ Visskjule]

Især er vores analyse bygget på det oprindelige differentielle angreb på SHA-0, angrebet tæt på kollisionen på SHA-0, multi-blok kollisionsteknikkerne samt de meddelelsesmodifikationsteknikker, der blev brugt i kollisionssøgningsangrebene på HAVAL-128 , MD4, RIPEMD og MD5.

En artikel, der beskriver algoritmen, blev offentliggjort i august 2005 på CRYPTO- konferencen .

I samme artikel publicerede forfatterne et angreb på trunkeret SHA-1 (58 runder), som gør det muligt at finde kollisioner i 233 operationer.

I august 2005, ved CRYPTO 2005, præsenterede de samme eksperter en forbedret version af angrebet på den fuldgyldige SHA-1, med en beregningsmæssig kompleksitet på 263 operationer. I december 2007 blev detaljerne i denne forbedring gennemgået af Martin Cochran.

Christophe de Kanier og Christian Rechberg præsenterede senere et forbedret angreb på SHA-1, for hvilket de blev tildelt det bedste papir på ASIACRYPT- konferencen i 2006 . De præsenterede en to-blok kollision på en 64-rund algoritme med en beregningsmæssig kompleksitet på omkring 2 35 operationer. [2]

Der er et storstilet forskningsprojekt, der startede på University of Technology i den østrigske by Graz , som: "... bruger computere forbundet via internettet til at udføre forskning inden for kryptoanalyse. Du kan deltage i projektet ved at downloade og køre det gratis program på din computer." [3]

Burt Kalinske , forskningschef ved " RSA -laboratoriet ", forudser, at det første preimage-angreb vil lykkes i de næste 5 til 10 år.

Da teoretiske angreb på SHA-1 har været succesfulde, planlægger NIST helt at udfase brugen af ​​SHA-1 i digitale signaturer. [fire]

På grund af algoritmernes blokering og iterative struktur, samt manglen på speciel behandling i slutningen af ​​hashen, er alle hash-funktioner i SHA-familien sårbare over for beskedforlængende angreb og kollisioner, når en besked delvis hash-has. [5] Disse angreb tillader forfalskning af meddelelser, der kun er signeret med hash - eller  - ved at forlænge meddelelsen og genberegne hashen uden at kende værdien af ​​nøglen. Den enkleste rettelse til at beskytte mod disse angreb er at fordoble hash - (  er en blok med nuller af samme længde som hash-funktionsblokken).

Den 2. november 2007 annoncerede NIST en konkurrence om at udvikle en ny SHA-3- algoritme , der kørte indtil 2012 . [6]

SHappening

Den 8. oktober 2015 offentliggjorde Marc Stevens, Pierre Karpman og Thomas Peyrin et angreb på komprimeringsfunktionen af ​​SHA-1-algoritmen, der kun kræver 257 beregninger .

Rigtigt hack: SHAttered (kollisionsdetektion)

Den 23. februar 2017 annoncerede specialister fra Google og CWI et praktisk hack af algoritmen ved at udgive 2 PDF - filer med den samme SHA-1 kontrolsum . Dette krævede en søgning af muligheder, hvilket ville tage 110 år for 1 GPU [7] .

Sammenligning af SHA-1 med andre algoritmer

Sammenligning med MD5

Både MD5 og SHA-1 er væsentligt forbedrede udvidelser af MD4 .

Ligheder:

  1. Fire stadier.
  2. Hver handling føjes til det tidligere opnåede resultat.
  3. Behandlingsblokstørrelsen er 512 bit.
  4. Begge algoritmer udfører modulo 2 32 addition og er designet til 32-bit arkitektur.

Forskelle:

  1. I SHA-1 bruges den samme funktion f i det fjerde trin som i det andet trin.
  2. I MD5 bruger hver handling en unik inkrementel konstant. I SHA-1 genbruges konstanter for hver af de fire grupper.
  3. En femte variabel er blevet tilføjet til SHA-1.
  4. SHA-1 bruger en cyklisk fejlkorrektionskode.
  5. I MD5 er de fire forskydninger, der bruges i hvert trin, forskellige fra de værdier, der blev brugt i de foregående trin. I SHA bruges en konstant skiftværdi på hvert trin.
  6. I MD5  er der fire forskellige elementære logiske funktioner, i SHA-1 er der tre.
  7. I MD5 er fordøjelængden 128 bit, i SHA-1 er den 160 bit.
  8. SHA-1 indeholder flere runder (80 i stedet for 64) og kører på en 160-bit buffer sammenlignet med MD5 's 128-bit buffer . Så SHA-1 burde køre omkring 25 % langsommere end MD5 på den samme hardware.

Bruce Schneier konkluderer: "SHA-1 er MD4 med tilføjelsen af ​​et udvidet støbt, et ekstra trin og forbedret lavine. MD5  er MD4 med forbedret bit-hashing, et ekstra trin og forbedret lavine."

Sammenligning med GOST R 34.11-94

En række karakteristiske træk ved GOST R 34.11-94 :

  1. Ved behandling af blokke bruges transformationer i henhold til GOST 28147-89-algoritmen ;
  2. En blok på 256 bit behandles, og outputværdien er også 256 bit lang.
  3. Antikollisionssøgningsforanstaltninger baseret på ufuldstændigheden af ​​den sidste blok anvendes.
  4. Blokke behandles i henhold til GOST 28147-89- krypteringsalgoritmen , som indeholder transformationer på S-bokse , hvilket betydeligt komplicerer anvendelsen af ​​den differentielle kryptoanalysemetode til søgningen efter kollisioner af GOST R 34.11-94- algoritmen . Dette er et betydeligt plus i forhold til SHA-1.
  5. Den teoretiske sikkerhed for GOST R 34.11-94 er 2128 , hvilket er mange gange større end 280 for SHA-1.

Sammenligning med andre SHA'er

I tabellen betyder "mellemhashstørrelse" "intern hashsumstørrelse" efter hver iteration.

Algoritme variationer Output hash-størrelse (bits) Mellemhashstørrelse (bits) Blokstørrelse (bits) Maksimal længde på inputmeddelelse (bit) Ordstørrelse (bits) Antal runder Anvendte operationer Fundet kollisioner
SHA-0 160 160 512 2 64 - 1 32 80 +,og, eller, xor, rotl Der er
SHA-1 160 160 512 2 64 - 1 32 80 +,og, eller, xor, rotl 2 52 operationer
SHA-2 SHA-256/224 256/224 256 512 2 64 - 1 32 64 +,og, eller, xor, shr, rotr Ikke
SHA-512/384 512/384 512 1024 2 128 - 1 64 80 +,og, eller, xor, shr, rotr Ikke

Brug

Hash-funktioner bruges i versionskontrolsystemer , elektroniske signatursystemer og til at bygge godkendelseskoder .

SHA-1 er den mest almindelige af hele SHA - og bruges i en række udbredte kryptografiske applikationer og algoritmer.

SHA-1 bruges i følgende applikationer:

  • S/MIME  - beskedsammendrag.
  • SSL  - beskedsammendrag.
  • IPSec  - til integritetskontrolalgoritmen i en punkt-til-punkt-forbindelse.
  • SSH  - for at kontrollere integriteten af ​​de overførte data.
  • PGP  - til oprettelse af en elektronisk digital signatur.
  • Git  - for at identificere hvert objekt ved hjælp af SHA-1-hash fra informationen gemt i objektet.
  • Mercurial  - for at identificere revisioner
  • BitTorrent  - for at kontrollere integriteten af ​​downloadede data.

SHA-1 er grundlaget for SHACAL -blokchifferet .

Ansvarsfraskrivelse

Google har længe udtrykt sin mistillid til SHA-1, især for at bruge denne funktion til at signere TLS -certifikater . Tilbage i 2014, kort efter offentliggørelsen af ​​Mark Stevens' arbejde, annoncerede Chrome -udviklingsteamet , at de var ved at udfase SHA-1.

Siden 25. april 2016 Yandex . Mail er holdt op med at understøtte ældre mailere, der bruger SHA-1 [8] .

Noter

  1. ↑ Find kollisioner i den fulde SHA-1  (engelsk)  (downlink) . — En artikel af kinesiske forskere om SHA-1 hacket. Arkiveret fra originalen den 23. august 2011.
  2. ↑ At finde SHA-1-karakteristika : Generelle resultater og anvendelser  . Hentet 4. oktober 2017. Arkiveret fra originalen 26. juli 2008.
  3. ↑ SHA-1 Collision Search Graz  (engelsk)  (link ikke tilgængeligt) . — Forskningsprojekt fra Graz University of Technology. Arkiveret fra originalen den 7. november 2008.
  4. ↑ NIST-kommentarer om kryptanalytiske angreb på SHA-1  (  utilgængeligt link) . — Officiel NIST-kommentar om SHA-1-angreb. Arkiveret fra originalen den 13. oktober 2012.
  5. ↑ Niels Ferguson, Bruce Schneier og Tadayoshi Kohno, Cryptography Engineering  (engelsk)  (link ikke tilgængeligt) . Arkiveret fra originalen den 13. oktober 2012. , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  6. ↑ NIST Hash Competition  (engelsk)  (link ikke tilgængeligt) . — Konkurrence om udviklingen af ​​SHA-3. Arkiveret fra originalen den 13. oktober 2012.
  7. ↑ Den første måde at generere kollisioner for SHA-1 . Hentet 9. marts 2017. Arkiveret fra originalen 10. marts 2017.
  8. ↑ Opdatering af e-mail-programmer - Mail - Yandex.Help . yandex.ru. Hentet 7. april 2016. Arkiveret fra originalen 20. april 2016.

Litteratur

  • Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer.  - ISBN 5-89392-055-4 .
  • Nils Ferguson , Bruce Schneier . Praktisk kryptografi = Praktisk kryptografi: Design og implementering af sikre kryptografiske systemer. - M .  : Dialektik, 2004. - 432 s. - 3000 eksemplarer.  — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

Links

 Hash funktioner
generelle formål
Kryptografisk
Nøglegenereringsfunktioner
Tjek nummer ( sammenligning )
Hashes