SHA-1 | |
---|---|
Kehittäjät | NSA ja NIST |
Luotu | 1995 |
julkaistu | 1995 |
Edeltäjä | SHA-0 |
Seuraaja | SHA-2 |
Hash-koko | 160 bittiä |
Kierrosten lukumäärä | 80 |
Tyyppi | hash-toiminto |
Secure Hash Algorithm 1 on kryptografinen hajautusalgoritmi . Kuvattu RFC 3174 :ssä . Satunnaisen pituiselle syöttöviestille ( enintään bittiä, joka on suunnilleen 2 eksatavua ) algoritmi luo 160-bittisen (20 tavua) hajautusarvon, jota kutsutaan myös sanoman tiivisteeksi ja joka näytetään yleensä 40-numeroisena heksadesimaalilukuna. määrä. Käytetään monissa kryptografisissa sovelluksissa ja protokollissa. Suositellaan myös Yhdysvaltain valtion virastojen ensisijaiseksi tehtäväksi . SHA-1:n periaatteet ovat samanlaiset kuin Ronald Rivestin MD4 :n suunnittelussa käyttämät periaatteet .
Vuonna 1993 NSA teki yhteistyötä NIST :n kanssa Secure Hash Algorithmin (nykyisin nimellä SHA-0) kehittämiseksi (julkaistu FIPS PUB 180:ssa) suojattua hajautusstandardia varten. NSA kuitenkin peruutti pian tämän version vedoten löytämäänsä vikaan, jota ei koskaan paljastettu. Ja korvasi sen tarkistetulla versiolla, joka julkaistiin vuonna 1995 FIPS PUB 180-1:ssä. Tätä versiota pidetään nimellä SHA-1. Myöhemmin vuoden 1998 CRYPTO-konferenssissa kaksi ranskalaista tutkijaa esitti hyökkäyksen SHA-0-algoritmia vastaan, joka ei toiminut SHA-1-algoritmilla. Tämä saattoi olla NSA:n havaitsema virhe .
SHA-1 toteuttaa hajautusfunktion , joka perustuu pakkausfunktion ideaan. Pakkaustoiminnon tulot ovat 512-bittinen viestilohko ja edellisen viestilohkon lähtö. Tulos on kaikkien hajautuslohkojen arvo siihen pisteeseen asti. Toisin sanoen hash-lohko on . Koko viestin hash-arvo on viimeisen lohkon tulos.
Alkuperäinen viesti on jaettu 512 bitin lohkoihin. Viimeinen lohko on pehmustettu 512 bitin pituiseksi kerrannaisiksi. Ensin lisätään 1 (bittiä) ja sitten nollia niin, että lohkon pituudeksi tulee 512 - 64 = 448 bittiä. Loput 64 bittiä sisältävät alkuperäisen viestin pituuden bitteinä ( big-endian- muodossa). Jos viimeisen lohkon pituus on yli 447 mutta vähemmän kuin 512 bittiä, täyte suoritetaan seuraavasti: ensin lisätään 1 (bitti), sitten nollia 512-bittisen lohkon loppuun asti; sen jälkeen luodaan toinen 512-bittinen lohko, joka täytetään 448 bittiin saakka nollia, jonka jälkeen alkuperäisen viestin pituus bitteinä (big-endian-muodossa) kirjoitetaan jäljellä oleviin 64 bittiin. Viimeinen lohko on aina täytetty, vaikka viestillä olisi jo haluttu pituus.
Viisi 32-bittistä muuttujaa alustetaan.
A=0x67452301 B = 0xEFCDAB89 C=0x98BADCFE D = 0x10325476 E=0xC3D2E1F0Neljä epälineaarista operaatiota ja neljä vakiota määritellään.
= 0x5A827999 | 0≤t≤19 | |
= 0x6ED9EBA1 | 20≤t≤39 | |
= 0x8F1BBCDC | 40≤t≤59 | |
= 0xCA62C1D6 | 60≤t≤79 |
Pääsilmukka käsittelee iteratiivisesti jokaisen 512-bittisen lohkon. Jokaisen silmukan alussa otetaan käyttöön muuttujat a, b, c, d, e, jotka alustetaan arvoilla A, B, C, D, E, vastaavasti. Sanomalohko muunnetaan 16 32-bittisestä sanasta 80 32-bittiseksi sanaksi seuraavan säännön mukaisesti:
arvolle 0≤t≤15 = ( -3 -8 -14 -16 ) << 1 arvolle 16≤t≤79, jossa "<<" on pyöreä siirto vasemmalle.
0-79 lämpötilalle = (a << 5) + ( b,c,d) + e + e = d d = c c = b <<30 b = a, jossa "+" on etumerkittämättömien 32-bittisten kokonaislukujen lisäys ja ylimääräinen (33. bitti) hylätty.
Sen jälkeen arvot a, b, c, d, e lisätään vastaavasti A, B, C, D, E. Seuraava iteraatio alkaa.
Lopullinen arvo on viiden 32-bittisen sanan (A, B, C, D, E) ketjuttaminen yhdeksi 160-bittiseksi hash-arvoksi.
SHA-1-algoritmin pseudokoodi on seuraava:
FIPS PUB 180-1:n alkuperäisen sanamuodon sijasta annetaan seuraavat vastaavat ilmaisut, joita voidaan käyttää fpääsilmukan tietokoneessa:
(0 ≤ i ≤ 19): f = d xor (b ja (c xtai d)) (vaihtoehto 1) (0 ≤ i ≤ 19): f = (b ja c) xor (( ei b) ja d) ( vaihtoehto 2) (0 ≤ i ≤ 19): f = (b ja c) + (( ei b) ja d) (vaihtoehto 3) (40 ≤ i ≤ 59): f = (b ja c) tai (d ja (b tai c)) (vaihtoehto 1) (40 ≤ i ≤ 59): f = (b ja c) tai (d ja (b ) xtai c)) (vaihtoehto 2) (40 ≤ i ≤ 59): f = (b ja c) + (d ja (b x tai c)) (vaihtoehto 3) (40 ≤ i ≤ 59): f = (b ja c) xor (b ja d) xor (c ja d) (vaihtoehto 4)Seuraavat ovat esimerkkejä SHA-1-tiivisteistä. Kaikkien viestien oletetaan käyttävän UTF-8- koodausta .
Hash pangram venäjäksi:
SHA-1("Löytyisikö etelän metsikköistä sitrushedelmiä? Kyllä, mutta väärennös!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1bHash pangram englanniksi:
SHA-1 (" Nopea ruskea kettu hyppää laiskan koiran yli ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926Pieni muutos lähdetekstissä (yksi kirjain isoilla kirjaimilla) johtaa suureen muutokseen itse hashissa. Tämä johtuu lumivyöryvaikutuksesta .
SHA-1("sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640Jopa tyhjälle merkkijonolle lasketaan ei-triviaali hash-arvo.
SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709Hajautusfunktioiden krypta -analyysin tarkoituksena on tutkia haavoittuvuutta erityyppisille hyökkäyksille. Tärkeimmät ovat:
Kun ratkaistaan "raaka voima" -menetelmällä :
Tätä hajautusalgoritmia käyttävän sähköisen digitaalisen allekirjoituksen turvallisuus riippuu hajautusfunktion stabiilisuudesta törmäysten löytämisessä . Esikuvan vastustuskyky riippuu salasanojen hajautusten tallentamisen turvallisuudesta todennustarkoituksiin .
Tammikuussa 2005 Vincent Rayman ja Elisabeth Oswald julkaisivat hyökkäyksen SHA-1:n katkaistua versiota vastaan (53 laukausta 80 kierroksen sijaan ), mikä mahdollistaa törmäysten havaitsemisen alle 280 operaatiossa.
Helmikuussa 2005 Xiaoyun Wang , Yiqun Lisa Yin ja Hongbo Yu esittivät hyökkäyksen täyttä SHA-1:tä vastaan, joka vaatii alle 269 operaatiota.
Kirjoittajat kirjoittavat menetelmästä:
Esittelemme joukon strategioita ja niihin liittyviä tekniikoita, joita voidaan käyttää ratkaisemaan tärkeitä esteitä törmäysten löytämisessä SHA-1:ssä. Etsimme ensin törmäyksen läheisiä differentiaalipolkuja, joilla on pieni "Hamming-paino" "kohinavektorissa", jossa jokainen bitti edustaa 6-vaiheista paikallista törmäystä. Säädämme sitten differentiaalipolun ensimmäisestä vaiheesta toiseen hyväksyttävään differentiaalipolkuun vastaavasti välttääksemme ei-hyväksyttäviä sarja- ja katkaistuja törmäyksiä. Lopuksi muunnamme kaksi yhden lohkon lähes törmäysdifferentiaalipolkua yhdeksi kahden lohkon törmäysreitiksi, jonka laskennallinen monimutkaisuus on kaksinkertainen. [yksi]
Alkuperäinen teksti (englanniksi)[ näytäpiilottaa]Esittelemme joukon strategioita ja vastaavia tekniikoita, joita voidaan käyttää poistamaan joitain suuria esteitä SHA-1:n törmäyshaussa. Ensinnäkin etsimme lähellä törmäystä olevaa differentiaalipolkua, jolla on pieni Hamming-paino "häiriövektorissa", jossa jokainen 1-bitti edustaa 6-vaiheista paikallista törmäystä. Toiseksi, sovitamme ensimmäisen kierroksen differentiaalipolun sopivasti toiseen mahdolliseen differentiaalipolkuun, jotta vältetään mahdottomat peräkkäiset paikalliset törmäykset ja katkaistut paikalliset törmäykset. Kolmanneksi muunnamme kaksi yhden lohkon lähes törmäysdifferentiaalipolkua kahden lohkon törmäysdifferentiaalipoluksi, jolla on kaksinkertainen haun monimutkaisuus.
He myös ilmoittavat:
Erityisesti analyysimme perustuu alkuperäiseen differentiaalihyökkäykseen SHA-0:a vastaan, "lähes törmäyksen" hyökkäykseen SHA-0:a vastaan, monilohkotekniikkaan ja alkuperäiseen viestien muokkaustekniikkaan, jota käytettiin HAVALin törmäyshakuhyökkäyksissä. 128, MD4 , RIPEMD ja MD5 .
Alkuperäinen teksti (englanniksi)[ näytäpiilottaa]Erityisesti analyysimme perustuu alkuperäiseen differentiaalihyökkäykseen SHA-0:a vastaan, SHA-0:n lähellä tapahtuvaan törmäyshyökkäykseen, usean lohkon törmäystekniikoihin sekä HAVAL-128:n törmäyshakuhyökkäyksissä käytettyihin viestien muokkaustekniikoihin. , MD4, RIPEMD ja MD5.
Algoritmia kuvaava artikkeli julkaistiin elokuussa 2005 CRYPTO - konferenssissa .
Samassa artikkelissa kirjoittajat julkaisivat hyökkäyksen katkaistua SHA-1:tä vastaan (58 laukausta), joka mahdollistaa törmäysten löytämisen 233 operaatiossa.
Elokuussa 2005 CRYPTO 2005 -tapahtumassa samat asiantuntijat esittelivät parannetun version täysimittaiseen SHA-1:een kohdistuvasta hyökkäyksestä, jonka laskennallinen monimutkaisuus on 263 toimintoa. Joulukuussa 2007 Martin Cochran tarkasteli tämän parannuksen yksityiskohdat.
Christophe de Kanier ja Christian Rechberg esittelivät myöhemmin parannetun hyökkäyksen SHA-1:tä vastaan, josta heidät palkittiin parhaana paperina vuoden 2006 ASIACRYPT- konferenssissa . He esittivät kahden lohkon törmäyksen 64 kierroksen algoritmilla, jonka laskennallinen monimutkaisuus on noin 2 35 operaatiota. [2]
Itävallassa Grazin kaupungin teknillisessä yliopistossa on käynnissä laajamittainen tutkimusprojekti , joka: "... käyttää Internetin kautta kytkettyjä tietokoneita krypta-analyysin alan tutkimukseen. Voit osallistua projektiin lataamalla ja ajamalla ilmaisen ohjelman tietokoneellesi." [3]
Burt Kalinske , " RSA -laboratorion " tutkimusjohtaja, ennustaa, että ensimmäinen esikuvahyökkäys onnistuu seuraavien 5-10 vuoden aikana.
Koska teoreettiset hyökkäykset SHA-1:tä vastaan ovat onnistuneet, NIST aikoo luopua kokonaan SHA-1:n käytöstä digitaalisissa allekirjoituksissa. [neljä]
Algoritmien lohkon ja iteratiivisen rakenteen sekä tiivisteen lopussa olevan erikoiskäsittelyn puutteen vuoksi kaikki SHA-perheen hajautustoiminnot ovat alttiina viestien pitkittämishyökkäyksille ja törmäyksille, kun viestiä osittain hajautetaan. [5] Nämä hyökkäykset mahdollistavat vain hashilla allekirjoitettujen viestien väärentämisen - tai - pidentämällä viestiä ja laskemalla hash-arvon uudelleen tietämättä avaimen arvoa. Yksinkertaisin korjaus suojautua näitä hyökkäyksiä vastaan on kaksinkertaistaa hash - ( on nollien lohko, joka on samanpituinen kuin hash-funktiolohko).
NIST ilmoitti 2. marraskuuta 2007 kilpailun kehittääkseen uutta SHA-3- algoritmia , joka oli voimassa vuoteen 2012 asti . [6]
SHappening8. lokakuuta 2015 Marc Stevens, Pierre Karpman ja Thomas Peyrin julkaisivat hyökkäyksen SHA-1-algoritmin pakkausfunktiota vastaan, joka vaatii vain 257 laskentaa .
Todellinen hakkerointi: SHAttered (törmäyksen havaitseminen)23. helmikuuta 2017 Googlen ja CWI :n asiantuntijat ilmoittivat käytännöllisen algoritmin hakkeroinnin julkaisemalla kaksi PDF - tiedostoa samalla SHA-1- tarkistussummalla . Tämä vaati vaihtoehtojen etsimistä, mikä kestäisi 110 vuotta 1 GPU :lla [7] .
Sekä MD5 että SHA-1 ovat olennaisesti MD4 :n parannettuja laajennuksia .
Samankaltaisuudet:
Erot:
Bruce Schneier päättelee: ”SHA-1 on MD4 , johon on lisätty leventävä kipsi, ylimääräinen askelma ja parannettu lumivyöry. MD5 on MD4 , jossa on parannettu bittihajautus, lisäaskel ja parannettu lumivyöry."
Useita GOST R 34.11-94 :n erityispiirteitä :
Taulukossa "välikoko" tarkoittaa "sisäistä hajautussumman kokoa" jokaisen iteraation jälkeen.
Algoritmin variaatiot | Tulostustiivistekoko (bittiä) | Keskikokoinen tiivistekoko (bittiä) | Lohkon koko (bittiä) | Syötetyn viestin enimmäispituus (bittiä) | Sanan koko (bittiä) | Kierrosten lukumäärä | Käytetyt toiminnot | Löytyi törmäyksiä | |
---|---|---|---|---|---|---|---|---|---|
SHA-0 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +,ja, tai, xor, rotl | On | |
SHA-1 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +,ja, tai, xor, rotl | 2 52 operaatiota | |
SHA-2 | SHA-256/224 | 256/224 | 256 | 512 | 2 64 - 1 | 32 | 64 | +,ja, tai, xor, shr, rotr | Ei |
SHA-512/384 | 512/384 | 512 | 1024 | 2 128 - 1 | 64 | 80 | +,ja, tai, xor, shr, rotr | Ei |
Hash-funktioita käytetään versionhallintajärjestelmissä , sähköisissä allekirjoitusjärjestelmissä ja todennuskoodien rakentamisessa .
SHA-1 on yleisin koko SHA , ja sitä käytetään useissa laajalti käytetyissä kryptografisissa sovelluksissa ja algoritmeissa.
SHA-1:tä käytetään seuraavissa sovelluksissa:
SHA-1 on SHACAL - lohkosalauksen perusta .
Google on pitkään ilmaissut epäluottamuksensa SHA-1:tä kohtaan, varsinkin tämän ominaisuuden käyttämisestä TLS -varmenteiden allekirjoittamiseen . Vuonna 2014, pian Mark Stevensin työn julkaisun jälkeen, Chromen kehitystiimi ilmoitti luopuvansa SHA-1:stä.
25. huhtikuuta 2016 lähtien Yandex . Mail on lakannut tukemasta vanhempia SHA-1:tä käyttäviä sähköpostiviestejä [8] .
Hash-funktiot | |
---|---|
yleinen tarkoitus | |
Kryptografinen | |
Avainten luontitoiminnot | |
Tarkista numero ( vertailu ) | |
Hashes |
|