Begrepet SHA ( akronym av den engelske Secure Hash Algorithm ) indikerer en familie av fem forskjellige kryptografiske hashfunksjoner utviklet siden 1993 av National Security Agency (NSA) og utgitt av NIST som en føderal standard av den amerikanske regjeringen ( FIPS PUB 180-4 ).
Som enhver hash - algoritme produserer SHA en meldingssammendrag med fast lengde, eller " meldingsfotavtrykk ", fra en melding med variabel lengde. Sikkerheten til en hash - algoritme ligger i det faktum at funksjonen ikke er inverterbar (det vil si at det ikke er mulig å gå tilbake til den opprinnelige meldingen med kun kunnskap om disse dataene) og at det aldri må være mulig å med vilje opprette to forskjellige meldinger med samme fordøyelse . Algoritmene til familien heter SHA-1 , SHA-224 , SHA-256 , SHA-384 og SHA-512 : de siste 4 variantene blir ofte referert til generisk som SHA-2 , for å skille dem fra den første. Den første produserer en sammendrag av meldingen på bare 160 biter , mens de andre produserer sammendrag av lengde i biter lik tallet angitt i deres forkortelse (SHA-256 produserer en sammendrag på 256 biter). SHA-1 er den mest utbredte algoritmen i SHA-familien og brukes i en rekke applikasjoner og protokoller, selv om den nå er usikker og snart vil bli erstattet av andre, mer moderne og effektive.
Sikkerheten til SHA-1 har blitt kompromittert av kryptoanalytikere . [1] Selv om angrep på SHA-2-varianter foreløpig ikke er kjent, har de en algoritme som ligner på SHA-1, så det arbeides med å utvikle alternative og forbedrede hashing- algoritmer. [2] [3] En åpen konkurranse for implementering av en ny SHA-3- funksjon ble kunngjort i Federal Register 2. november 2007 [4] av NIST og gjennom en offentlig konkurranse , tilsvarende den som ble vedtatt for utviklingsprosessen av AES , [5] førte 2. oktober 2012 til å kunngjøre Keccak - algoritmen som vinneren . Arbeidet til et team av italienske og belgiske analytikere, Keccak [6] ser derfor ut til å bli gradvis inkludert og tatt i bruk i de mest varierte IT-sikkerhetsløsningene.
23. februar 2017 kunngjorde et Google-team den første praktiske teknikken for å generere en hasjkollisjon . [7] [8]
Den originale algoritmespesifikasjonen ble publisert i 1993 som Secure Hash Standard , FIPS PUB 180, av NIST . Denne versjonen blir ofte referert til som SHA-0 for å skille den fra senere versjoner. Den ble trukket tilbake av NSA kort tid etter publisering og ble erstattet av en revidert versjon, publisert i 1995 (FIPS PUB 180-1) og vanligvis kjent som SHA-1 . SHA-1 skiller seg fra SHA-0 bare ved en enkeltbitrotasjon i meldingsforberedelsesprosessen til enveiskomprimeringsfunksjonen; dette ble gjort, ifølge NSA, for å rette opp en feil i den opprinnelige algoritmen, som reduserte den kryptografiske sikkerheten til SHA-0. NSA ga imidlertid ingen ytterligere klargjørende forklaring. Svakheter i både SHA-0- og SHA-1-koden ble deretter rapportert. SHA-1 ser ut til å tilby større motstand mot angrep, og støtter NSAs påstand om at endringen økte sikkerheten.
SHA-1 (samt SHA-0) produserer en 160-bits sammendrag fra en melding med en maksimal lengde på 2 64 -1 biter og er basert på prinsipper som ligner på de som ble brukt av Ronald L. Rivest fra MIT i utformingen av MD4 og MD5 algoritmer .
Trinn 1 (Padding): "Padding"-biter legges til den opprinnelige meldingen slik at den endelige lengden på meldingen er kongruent med 448 modulo 512, og dermed vil bitlengden til "melding + utfylling" delt på 512 gi resten 448.
Trinn 2 (Legg til lengde): Et usignert 64-bits heltall som inneholder lengden på den opprinnelige meldingen legges til bitsekvensen (melding + utfylling) opprettet i trinn 1. På slutten av disse to første trinnene får vi en sekvens av biter som er et multiplum av 512.
Trinn 3 (MD-bufferinitialisering): En 160-bits buffer delt inn i 5 registre på 32-bits hver lages for lagring av noen mellomtrinn. De 5 registrene vil være konvensjonelt indikert med (A, B, C, D, E) og initialisert med følgende heksadesimale verdier:
Trinn 4 (Behandling av 512bit-blokkene): Bitsekvensen "melding + utfylling + meldingslengde" er delt inn i 512-biters blokker, som vi vil identifisere med B n med n fra 0 til L. Kjernen i SHA-1-algoritmen er kalles kompresjonsfunksjon og består av 4 sykluser på 20 trinn hver. Sløyfer har en veldig lik struktur med hverandre bortsett fra det faktum at de bruker en annen primitiv logikkfunksjon. Hver blokk tas som en inngangsparameter av alle 4 sykluser sammen med en konstant K og verdiene til de 5 registrene. På slutten av beregningen vil vi få nye verdier for A, B, C, D, E som vi vil bruke for beregningen av neste blokk frem til siste blokk F.
I 2001 ga NIST ut fire ekstra hash -funksjoner fra SHA-familien, hver med en lengre sammendrag enn originalen, samlet referert til som SHA-2 (selv om dette begrepet aldri ble offisielt standardisert). Disse variantene er kjent, som nevnt, med lengden i biter av sammendraget generert etter den offisielle hash -forkortelsen : SHA-224 , SHA-256 , SHA-384 og SHA-512 , med henholdsvis hashes på 224, 256 , 384 og 512 biter. Det skal bemerkes at de tre siste algoritmene ble formalisert som standard i 2002 mens SHA-224 ble introdusert i februar 2004 : sistnevnte har en hash av identisk lengde som den for 2 Triple DES- nøkler .
Alle disse variantene er patentert av amerikanske myndigheter, men publisert under en gratis lisens. [9] .
Algoritmene SHA-256 og SHA-512 fungerer med henholdsvis 32 og 64 bits ord : de bruker et annet antall rotasjoner og ekstra konstanter, men strukturen deres er i det vesentlige identisk. Algoritmene SHA-224 og SHA-384 er ganske enkelt avkortede versjoner av de to foregående, med hashes beregnet med forskjellige startverdier.
SHA-2-algoritmene har ikke fått, i motsetning til SHA-1, mye oppmerksomhet fra kryptoanalytikermiljøet, så deres kryptografiske sikkerhet har ikke blitt fullstendig bevist. Gilbert og Handschuh ( 2003 ) studerte disse nye variantene og fant ingen sårbarheter [10] .
Konkurransen som førte til utgivelsen av den nye SHA-3- standarden ble offisielt lansert 2. november 2007 [4] . 2. oktober 2012 kunngjorde NIST Keccak SHA-3- algoritmen som vinneren .
Tabellen nedenfor viser hovedkarakteristikkene til algoritmene til SHA-familien ( Intern tilstand betyr den interne summen etter hver komprimering av en datablokk).
| Algoritme og variant |
Utdatastørrelse (bits) | Intern tilstandsstørrelse (bit) | Blokkstørrelse (bit) | Maks. meldingsstørrelse (bits) | Ordstørrelse ( bit ) | Trinn | Drift | Kollisjoner funnet | |
|---|---|---|---|---|---|---|---|---|---|
| SHA-0 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +, og, eller, xor, rotl | Jepp | |
| SHA-1 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +, og, eller, xor, rotl | Angrep 2 53 [11] | |
| SHA-2 | SHA-256/224 | 256/224 | 256 | 512 | 2 64 - 1 | 32 | 64 | +, og, eller, xor, shr, rotr | Ingen |
| SHA-512/384 | 512/384 | 512 | 1024 | 2 128 - 1 | 64 | 80 | +, og, eller, xor, shr, rotr | Ingen | |
SHA-1 er den mest brukte algoritmen i SHA-familien. Den danner grunnlaget for mange applikasjoner og protokoller, inkludert TLS og SSL , PGP , SSH , S / MIME og IPsec . SHA-1 brukes også i versjonskontrollsystemer , slik som Git , for å identifisere programvarerevisjon og som en kontrollsum for å verifisere integriteten til store filer i nettkataloger.
SHA-algoritmer brukes også i algoritmer for digital signering av dokumenter, slik som HMAC , og har blitt tatt som grunnlag for SHACAL -blokkchiffer .
Dette er et eksempel på en sammendrag generert av SHA-1 (alle meldinger er kodet i ASCII ):
SHA1 ("Cantami o diva of the pelide Achilles den fatale vrede") = 1f8a690b7366a2323e2d5b045120da7e93896f47Selv den minste variasjon i meldingen genererer uunngåelig en helt annen hasj på grunn av en kjedereaksjon kjent som skredeffekten . For eksempel, ved å erstatte Cantamimed Contamifår vi:
SHA1 ("C o ntami eller diva av pelis Achilles den fatale vrede") = e5f08d98bf18385e2f26b904cad23c734d530ffbSammendraget som tilsvarer den tomme strengen er:
SHA1 ("") = da39a3ee5e6b4b0d3255bfef95601890afd80709Pseudokode for SHA-1-algoritmen:
Merknader: Alle variabler er 32 biter uten fortegn og wrap modulo 2 32 ved beregning Initialiser variabler: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Forbehandling: legg til biten '1' i meldingen legge til k bits '0', hvor k er minimumstallet ≥ 0 slik at den resulterende meldingen lengde (i biter ) er kongruent med 448 (mod 512) legge til lengden på meldingen (før forhåndsbehandling), i bits , som 64-bits big-endian heltall Behandle meldingen i påfølgende 512-bits biter: dele meldinger i 512-bits biter for hver del del opp i seksten 32-bits big-endian-ord w [i], 0 <= i <= 15 Utvid de seksten 32-bits ordene til åtti 32-biters ord: for i fra 16 til 79 w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) venstreroter 1 Initialiser hash-verdi for denne delen: a = h0 b = h1 c = h2 d = h3 e = h4 Hovedsløyfe: 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 f = b xeller c xeller d k = 0x6ED9EBA1 ellers hvis 40 ≤ i ≤ 59 f = (b og c) eller (b og d) eller (c og d) k = 0x8F1BBCDC ellers hvis 60 ≤ i ≤ 79 f = b xeller c xeller d k = 0xCA62C1D6 temp = (en venstrerotering 5) + f + e + k + w [i] e = d d = c c = b venstreroter 30 b = a a = temp Legg til denne delens hash for å få resultatet så langt: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Produser den endelige hash-verdien (big-endian): digest = hash = h0 legg til h1 legg til h2 legg til h3 legg til h4Følgende formler kan brukes til å beregne fi hovedsyklusen publisert ovenfor i stedet for de originale som er publisert i det offisielle FIPS PUB 180-1-dokumentet:
(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)Pseudokode for SHA-256-algoritmen. Legg merke til økningen i bitblanding av ordene w[16..63]sammenlignet med SHA-1.
Merknader: Alle variabler er 32 biter uten fortegn og wrap modulo 2 32 ved beregning Initialiser variabler (første 32 biter av brøkdelene av kvadratrøttene til de første 8 primtall 2..19): h0: = 0x6a09e667 h1: = 0xbb67ae85 h2: = 0x3c6ef372 h3: = 0xa54ff53a h4: = 0x510e527f h5: = 0x9b05688c h6: = 0x1f83d9ab h7: = 0x5be0cd19 Initialiser tabellen med runde konstanter (første 32 biter av brøkdelene av kuberøttene til de første 64 primtall 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 Forbehandling: legg til biten '1' i meldingen legg til k bits '0', hvor k er minimumstallet> = 0 slik at den resulterende meldingen lengde (i biter ) er kongruent med 448 (mod 512) legge til lengden på meldingen (før forhåndsbehandling), i bits , som 64-bits big-endian heltall Behandle meldingen i påfølgende 512-bits biter: dele meldinger i 512-bits biter for hver del del opp i seksten 32-bits big-endian-ord w [0..15] Utvid de seksten 32-bits ordene til sekstifire 32-bits ord: for i fra 16 til 63 s0: = (w [i-15] høyreroter 7) xor (w [i-15] høyreroter 18) xor (w [i-15] høyreskift 3) s1: = (w [i-2] høyreroter 17) xor (w [i-2] høyreroter 19) xor (w [i-2] høyreskift 10) w [i]: = w [i-16] + s0 + w [i-7] + s1 Initialiser hash-verdi for denne delen: a: = h0 b: = h1 c: = h2 d: = h3 e: = h4 f: = h5 g: = h6 h: = h7 Hovedsløyfe: for i fra 0 til 63 s0: = (en høyreroter 2) xor (en høyreroter 13) xor (en høyreroterer 22) maj: = (a og b) xor (a og c) xor (b og c) t2: = s0 + maj s1: = (e høyreroter 6) xor (e høyreroter 11) xor (e høyreroter 25) ch: = (e og f) xor (( ikke e) og g) t1: = h + s1 + ch + k [i] + w [i] h: = g g: = f f: = e e: = d + t1 d: = c c: = b b: = a a: = t1 + t2 Legg til denne delens hash for å få resultatet så langt: h0: = h0 + a h1: = h1 + b h2: = h2 + c h3: = h3 + d h4: = h4 + e h5: = h5 + f h6: = h6 + g h7: = h7 + h Produser den endelige hash-verdien (big-endian): digest = hash = h0 legg til h1 legg til h2 legg til h3 legg til h4 legg til h5 legg til h6 legg til h7Funksjonene chog majkan optimaliseres som beskrevet for SHA-1.
SHA-224 er identisk med SHA-256 bortsett fra:
SHA-512 er identisk i konstruksjon, men:
SHA-384 er identisk med SHA-512 bortsett fra:
NESSIE - prosjektet tester vektorer for SHA-1 , SHA-256 , SHA-384 og SHA-512 .