SHA-1

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 29-én felülvizsgált verziótól ; az ellenőrzések 12 szerkesztést igényelnek .
SHA-1
Fejlesztők NSA és NIST
Létrehozva 1995
közzétett 1995
Előző SHA-0
Utód SHA-2
Hash méret 160 bites
A körök száma 80
Típusú hash függvény

A Secure Hash Algorithm 1 egy kriptográfiai kivonatolási  algoritmus . Az RFC 3174 -ben van leírva . Egy tetszőleges hosszúságú ( maximum bit, ami körülbelül 2 exabájt ) bemeneti üzenet esetén az algoritmus 160 bites (20 bájt) hash értéket generál, amelyet üzenetkivonatnak is neveznek , és amelyet általában 40 számjegyű hexadecimális formában jelenítenek meg. szám. Számos kriptográfiai alkalmazásban és protokollban használják. Elsődlegesként is ajánlott az Egyesült Államok kormányzati szervei számára . Az SHA-1 mögött meghúzódó elvek hasonlóak azokhoz, amelyeket Ronald Rivest használt az MD4 tervezésekor .

Történelem

1993- ban az NSA a NIST - szel együttműködve kifejlesztette a Secure Hash Algorithm (jelenleg SHA-0 néven ismert) (a FIPS PUB 180-ban megjelent) biztonságos kivonatolási szabványt. Az NSA azonban hamarosan visszavonta ezt a verziót egy felfedezett hibára hivatkozva, amelyet soha nem hoztak nyilvánosságra. És lecserélték egy átdolgozott változatra, amelyet 1995 -ben tettek közzé a FIPS PUB 180-1-ben. Ez a verzió az úgynevezett SHA-1. Később, az 1998-as CRYPTO konferencián két francia kutató bemutatta az SHA-0 algoritmus elleni támadást, amely nem működött az SHA-1 algoritmuson. Ez egy hiba lehetett, amelyet az NSA fedezett fel .

Az algoritmus leírása

Az SHA-1 hash függvényt valósít meg , amely a tömörítési függvény ötletére épül. A tömörítési funkció bemenetei egy 512 bites üzenetblokk és az előző üzenetblokk kimenete. A kimenet az összes hash blokk értéke addig a pontig. Más szóval, a hash blokk . A teljes üzenet hash értéke az utolsó blokk kimenete.

Inicializálás

Az eredeti üzenet 512 bites blokkokra van felosztva. Az utolsó blokk 512 bites többszörösére párnázott. Először 1-et (bit) adunk hozzá, majd nullákat adunk hozzá, így a blokk hossza 512 - 64 = 448 bit lesz. A fennmaradó 64 bit tartalmazza az eredeti üzenet hosszát bitben ( big-endian formátumban). Ha az utolsó blokk hossza több mint 447, de kevesebb, mint 512 bit, akkor a kitöltés a következőképpen történik: először 1 (bit) adunk hozzá, majd nullákat adunk össze az 512 bites blokk végéig; ezután jön létre egy újabb 512 bites blokk, amit 448 bitig nullákkal töltenek fel, majd a maradék 64 bitre az eredeti üzenet hosszát bitben (big-endian formátumban) írjuk. Az utolsó blokk mindig kitöltésre kerül, még akkor is, ha az üzenet már a kívánt hosszúságú.

Öt 32 bites változó inicializálódik.

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

Négy nemlineáris művelet és négy állandó van definiálva.

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

Main Loop

A főhurok iteratív módon dolgoz fel minden 512 bites blokkot. Minden ciklus elején a, b, c, d, e változók kerülnek bevezetésre, amelyeket az A, B, C, D, E értékekkel inicializálunk. Az üzenetblokk 16 32 bites szóról 80 32 bites szóra konvertálódik a következő szabály szerint:

0≤t≤15 esetén = ( -3 -8 -14 -16 ) << 1 16≤t≤79 esetén

, ahol a "<<" egy körkörös eltolás balra.

0 és 79 közötti hőmérsékleten = (a<<5) + ( b,c,d) + e + e = d d = c c = b<30 b = a





a = hőm

, ahol a "+" az előjel nélküli 32 bites egész számok hozzáadását jelenti a felesleges (33. bit) elvetésével.

Ezt követően az a, b, c, d, e értékeket hozzáadjuk A, B, C, D, E értékekhez. A következő iteráció kezdődik.

A végső érték öt 32 bites szó (A, B, C, D, E) összefűzése lesz egy 160 bites hash értékké.

SHA-1 pszeudokód

Az SHA-1 algoritmus pszeudokódja a következő:


Megjegyzés: Az összes használt változó 32 bites. Változó inicializálás: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Előzetes feldolgozás: Csatolja az "1" bitet az üzenethez Adjon hozzá k bitet '0', ahol k a legkisebb szám ≥ 0 úgy, hogy az eredményül kapott üzenet hossza (bitekben) a modulo 512 a 448-hoz hasonlítható (hosszúság 512 mod == 448) Adja hozzá az eredeti üzenet hosszát (előfeldolgozás előtt) 64 bites egész számként Big-endian szám, bitben . A folyamat során az üzenetet egymás után 512 bitre osztják fel: az összes ilyen rész iterálásához ezt a darabot 16 részre osztottuk, 32 bites szavak (big-endian) w[i], 0 <= i <= 15 16 32 bites szó 80 32 bites szóra párnázott: i esetén 16 és 79 között w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) forgatás balra 1 A rész hash értékeinek inicializálása: a = h0 b = h1 c = h2 d = h3 e=h4 Főhurok: i esetén 0 - tól 79 - ig, ha 0 ≤ i ≤ 19 , akkor f = (b és c) vagy (( nem b) és d) k = 0x5A827999 különben ha 20 ≤ i ≤ 39 akkor f = b xor c xor d k = 0x6ED9EBA1 különben, ha 40 ≤ i ≤ 59 , akkor f = (b és c) vagy (b és d) vagy (c és d) k = 0x8F1BBCDC különben ha 60 ≤ i ≤ 79 akkor f = b xor c xor d k = 0xCA62C1D6 hőmérséklet = ( balra forgatás 5) + f + e + k + w[i] e=d d=c c = b balra forgatás 30 b = a a = hőm Adja hozzá ennek a résznek a hash értékét az eredményhez: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e A végső hash értéket (h0, h1, h2, h3, h4 big-endianra kell konvertálni): digest = hash = h0 hozzáfűzés h1 hozzáfűzés h2 hozzáfűzés h3 hozzáfűzés h4

A FIPS PUB 180-1 eredeti szövege helyett a következő ekvivalens kifejezések vannak megadva, és fa fő hurokban használhatók számítógépen:

(0 ≤ i ≤ 19): f = d xor (b és (c x vagy d)) (1. alternatíva) (0 ≤ i ≤ 19): f = (b és c) xor (( nem b) és d) ( 2) alternatíva (0 ≤ i ≤ 19): f = (b és c) + (( nem b) és d) (3. alternatíva)   (40 ≤ i ≤ 59): f = (b és c) vagy (d és (b vagy c)) (1. alternatíva) (40 ≤ i ≤ 59): f = (b és c) vagy (d és (b ) x vagy c)) (2. alternatíva) (40 ≤ i ≤ 59): f = (b és c) + (d és (b x vagy c)) (3. alternatíva) (40 ≤ i ≤ 59): f = (b és c) xor (b és d) xor (c és d) (4. alternatíva)

Példák

Az alábbiakban példák találhatók az SHA-1 kivonatokra. Feltételezzük, hogy minden üzenet UTF-8 kódolást használ .

Hash pangram oroszul:

SHA-1 ("Lenne citrus a déli bozótosban? Igen, de hamis!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b

Hash pangram angolul:

SHA-1 (" A gyors barna róka átugrik a lusta kutyán ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1 ("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926

A forrásszöveg kis módosítása (egy betű nagybetűvel) magában a hashben jelentős változáshoz vezet. Ez a lavinahatásnak köszönhető .

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

Még egy üres karakterlánc esetén is kiszámít egy nem triviális hash értéket.

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

Kriptanalízis

A hash függvények kriptoanalízise a különféle típusú támadásokkal szembeni sebezhetőség tanulmányozását célozza. A főbbek a következők:

"Brute force" módszerrel történő megoldáskor :

Az elektronikus digitális aláírás biztonsága ezzel a hash algoritmussal attól függ, hogy a hash függvény milyen stabilitást mutat az ütközések megtalálásában . Az előkép ellenállása a jelszókivonatok hitelesítési célú tárolásának biztonságától függ .

2005 januárjában Vincent Rayman és Elisabeth Oswald közzétett egy támadást az SHA-1 csonkolt változata ellen ( 80 helyett 53 lövés), amely lehetővé teszi, hogy kevesebb mint 280 művelet során találjanak ütközéseket .

2005 februárjában Xiaoyun Wang , Yiqun Lisa Yin és Hongbo Yu egy teljes SHA-1 elleni támadást mutatott be, amely kevesebb mint 269 műveletet igényel.

A módszerről a szerzők a következőket írják:

Bemutatunk egy sor stratégiát és kapcsolódó technikát, amelyek segítségével néhány fontos akadály leküzdhető az ütközések megtalálása során az SHA-1-ben. Először azokat az ütközésközeli differenciálutakat keressük, amelyeknek kis "Hamming-súlyuk" van a "zajvektorban", ahol minden bit egy 6 lépésből álló helyi ütközést jelent. Ezután ennek megfelelően módosítjuk a differenciálpályát az első fokozattól egy másik elfogadható differenciálútra, hogy elkerüljük az elfogadhatatlan soros és csonka ütközéseket. Végül két egyblokkos ütközésközeli differenciálpályát alakítunk át egy kétblokkos ütközési úttá, amelynek számítási bonyolultsága kétszerese. [egy]

Eredeti szöveg  (angol)[ showelrejt]

Bemutatunk egy sor stratégiát és megfelelő technikát, amelyek segítségével eltávolíthatók néhány fő akadály az SHA-1 ütközéskeresése során. Először is egy ütközésközeli differenciálpályát keresünk, amely alacsony Hamming-súllyal rendelkezik a "zavar-vektorban", ahol minden 1 bit egy 6-lépéses lokális ütközést jelent. Másodszor, az első körben megfelelően igazítjuk a differenciálpályát egy másik lehetséges differenciálúthoz, hogy elkerüljük a lehetetlen egymást követő helyi ütközéseket és csonka lokális ütközéseket. Harmadszor, két egyblokkos ütközésközeli differenciálpályát alakítunk át egy kétblokkos ütközési differenciálúttá, amelynek keresési összetettsége kétszerese.

Azt is kijelentik:

Elemzésünk különösen az SHA-0 elleni eredeti differenciális támadáson, az SHA-0 elleni "ütközésközeli" támadáson, a többblokkos technikán és a HAVAL elleni ütközéskeresési támadásoknál használt eredeti üzenetmódosítási technikán alapul. 128, MD4 , RIPEMD és MD5 .

Eredeti szöveg  (angol)[ showelrejt]

Elemzésünk különösen az SHA-0 elleni eredeti differenciáltámadásra, az SHA-0 elleni ütközésközeli támadásra, a többblokkos ütközési technikákra, valamint a HAVAL-128 elleni ütközéskeresési támadásoknál használt üzenetmódosítási technikákra épül. , MD4, RIPEMD és MD5.

Az algoritmust leíró cikk 2005 augusztusában jelent meg a CRYPTO konferencián .

Ugyanebben a cikkben a szerzők egy csonka SHA-1 elleni támadást tettek közzé (58 lövés), amely lehetővé teszi az ütközések megtalálását 233 művelet során.

2005 augusztusában , a CRYPTO 2005 rendezvényen ugyanezek a szakértők bemutatták a teljes értékű SHA-1 elleni támadás továbbfejlesztett változatát, 263 művelet számítási bonyolultságával. 2007 decemberében Martin Cochran áttekintette a fejlesztés részleteit.

Christophe de Kanier és Christian Rechberg később egy továbbfejlesztett támadást mutatott be az SHA-1 ellen, amiért a 2006 -os ASIACRYPT konferencián a legjobb tanulmányt díjazták . Két blokkos ütközést mutattak be egy 64 körből álló algoritmuson, amelynek számítási bonyolultsága körülbelül 2 35 művelet. [2]

Van egy nagyszabású kutatási projekt, amely az osztrák Graz város Műszaki Egyetemén indult, amely: „... az interneten keresztül összekapcsolt számítógépeket használ a kriptoanalízis területén végzett kutatásokhoz. A projektben úgy tud részt venni, hogy letölti és futtatja számítógépén az ingyenes programot." [3]

Burt Kalinske , az " RSA labor" kutatási vezetője azt jósolja, hogy az első preimage támadás a következő 5-10 évben sikeres lesz.

Mivel az SHA-1 elleni elméleti támadások sikeresek voltak, a NIST azt tervezi, hogy fokozatosan megszünteti az SHA-1 használatát a digitális aláírásokban. [négy]

Az algoritmusok blokkos és iteratív felépítése, valamint a speciális feldolgozás hiánya miatt a hash végén az SHA család összes hash funkciója ki van téve az üzenethosszabbító támadásoknak és ütközéseknek egy üzenet részleges kivonatolása során. [5] Ezek a támadások csak hash-sel aláírt üzenetek hamisítását teszik lehetővé – vagy  – az üzenet meghosszabbításával és a hash újraszámításával a kulcs értékének ismerete nélkül. A legegyszerűbb megoldás az ilyen támadások elleni védelemre a dupla hash - (  olyan nullákból álló blokk, amely ugyanolyan hosszúságú, mint a hash funkcióblokk).

2007. november 2- án a NIST versenyt hirdetett egy új SHA-3 algoritmus kifejlesztésére, amely 2012 - ig futott . [6]

SHappening

2015. október 8-án Marc Stevens, Pierre Karpman és Thomas Peyrin támadást tettek közzé az SHA-1 algoritmus tömörítési funkciója ellen, amely mindössze 257 számítást igényel .

Valódi hack: SHAttered (ütközésészlelés)

2017. február 23-án a Google és a CWI szakemberei bejelentették az algoritmus gyakorlati feltörését, és közzétettek 2 PDF - fájlt ugyanazzal az SHA-1 ellenőrzőösszeggel . Ehhez az opciók után kutatni kellett , ami 1 GPU esetén 110 évig tartana [7] .

Az SHA-1 összehasonlítása más algoritmusokkal

Összehasonlítás az MD5-tel

Mind az MD5 , mind az SHA-1 az MD4 továbbfejlesztett kiterjesztései .

Hasonlóságok:

  1. Négy szakasz.
  2. Minden művelet hozzáadódik az előzőleg kapott eredményhez.
  3. A feldolgozó blokk mérete 512 bit.
  4. Mindkét algoritmus modulo 2 32 összeadást hajt végre , és 32 bites architektúrára tervezték.

Különbségek:

  1. Az SHA-1-ben ugyanazt az f függvényt használják a negyedik szakaszban, mint a második szakaszban.
  2. Az MD5 -ben minden művelet egyedi növekményes állandót használ. Az SHA-1-ben az állandókat mind a négy csoporthoz újra felhasználják.
  3. Az SHA-1-hez hozzáadtunk egy ötödik változót.
  4. Az SHA-1 ciklikus hibajavító kódot használ.
  5. Az MD5 -ben az egyes lépésekben használt négy eltolás eltér az előző lépésekben használt értékektől. Az SHA -ban minden szakaszban állandó eltolási értéket használnak.
  6. Az MD5  -ben négy különböző elemi logikai függvény van, az SHA-1-ben három.
  7. Az MD5 -ben a kivonat hossza 128 bit, az SHA-1-ben 160 bit.
  8. Az SHA-1 több kört tartalmaz (64 helyett 80-at), és 160 bites pufferrel fut az MD5 128 bites pufferéhez képest . Tehát az SHA-1-nek körülbelül 25%-kal lassabban kell futnia, mint az MD5 -nek ugyanazon a hardveren.

Bruce Schneier így folytatja : „Az SHA-1 egy MD4 , szélesedő kazettával, extra lépcsővel és javított lavinával. Az MD5  egy MD4 , továbbfejlesztett bitkivonattal, egy extra lépéssel és javított lavinával."

Összehasonlítás a GOST R 34.11-94-el

A GOST R 34.11-94 számos megkülönböztető jellemzője :

  1. A blokkok feldolgozásakor a transzformációkat a GOST 28147-89 algoritmus szerint használjuk ;
  2. Egy 256 bites blokk kerül feldolgozásra, és a kimeneti érték is 256 bit hosszú.
  3. Az utolsó blokk hiányosságán alapuló ütközésgátló keresési intézkedéseket alkalmaznak.
  4. A blokkok feldolgozása a GOST 28147-89 titkosítási algoritmus szerint történik, amely az S- boxokon végzett transzformációkat tartalmaz , ami jelentősen megnehezíti a differenciális kriptográfiai módszer alkalmazását a GOST R 34.11-94 algoritmus ütközéseinek keresésére . Ez jelentős plusz az SHA-1-hez képest.
  5. A GOST R 34.11-94 elméleti biztonsága 2128 , ami sokszor nagyobb, mint 280 az SHA-1 esetében.

Összehasonlítás más SHA-kkal

A táblázatban a "köztes hash méret" jelentése "belső hash összege" minden iteráció után.

Algoritmus variációk Kimeneti hash mérete (bit) Köztes hash méret (bit) Blokkméret (bit) A bemeneti üzenet maximális hossza (bit) Szóméret (bit) A körök száma Használt műveletek Talált ütközéseket
SHA-0 160 160 512 2 64 - 1 32 80 +,és, vagy, xor, rotl Van
SHA-1 160 160 512 2 64 - 1 32 80 +,és, vagy, xor, rotl 2 52 művelet
SHA-2 SHA-256/224 256/224 256 512 2 64 - 1 32 64 +,és, vagy, xor, shr, rotr Nem
SHA-512/384 512/384 512 1024 2 128-1 _ 64 80 +,és, vagy, xor, shr, rotr Nem

Használat

A hash függvényeket verziókezelő rendszerekben , elektronikus aláírási rendszerekben és hitelesítési kódok létrehozásában használják .

Az SHA-1 a legelterjedtebb a teljes SHA , és számos széles körben használt kriptográfiai alkalmazásban és algoritmusban használják.

Az SHA-1 a következő alkalmazásokban használatos:

  • S/MIME  – üzenet kivonatok.
  • SSL  – üzenet kivonatok.
  • IPSec  – az integritás-ellenőrző algoritmushoz pont-pont kapcsolatnál.
  • SSH  - az átvitt adatok integritásának ellenőrzése.
  • PGP  - elektronikus digitális aláírás létrehozásához.
  • Git  – minden objektum azonosítása SHA-1 hash segítségével az objektumban tárolt információk alapján.
  • Mercurial  – a revíziók azonosítására
  • BitTorrent  – ​​a letöltött adatok sértetlenségének ellenőrzése.

Az SHA-1 a SHACAL blokk titkosítás alapja .

Jogi nyilatkozat

A Google régóta nem bízik az SHA-1-ben, különösen amiatt, hogy ezt a funkciót TLS -tanúsítványok aláírására használja . Még 2014-ben, nem sokkal Mark Stevens munkájának közzététele után, a Chrome fejlesztőcsapata bejelentette, hogy fokozatosan megszüntetik az SHA-1-et.

2016. április 25. óta a Yandex . A Mail már nem támogatja a régebbi, SHA-1-et használó levelezőket [8] .

Jegyzetek

  1. ↑ Ütközések keresése a teljes SHA-1-ben  (angol)  (lefelé irányuló kapcsolat) . - Kínai kutatók cikke az SHA-1 feltöréséről. Archiválva az eredetiből 2011. augusztus 23-án.
  2. ↑ Az SHA-1 jellemzőinek megtalálása : Általános eredmények és alkalmazások  . Letöltve: 2017. október 4. Az eredetiből archiválva : 2008. július 26..
  3. ↑ SHA-1 Collision Search Graz  (angol)  (hivatkozás nem érhető el) . — A Grazi Műszaki Egyetem kutatási projektje. Az eredetiből archiválva: 2008. november 7.
  4. ↑ NIST megjegyzések az SHA-1 kriptanalitikus támadásaihoz  (  elérhetetlen hivatkozás ) . — Hivatalos NIST kommentár az SHA-1 támadásokról. Az eredetiből archiválva : 2012. október 13.
  5. ↑ Niels Ferguson, Bruce Schneier és Tadayoshi Kohno, Cryptography Engineering  (angol)  (a hivatkozás nem érhető el) . Az eredetiből archiválva : 2012. október 13. , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  6. ↑ NIST Hash Competition  (angol)  (a link nem érhető el) . — Verseny az SHA-3 fejlesztéséért. Az eredetiből archiválva : 2012. október 13.
  7. ↑ Az ütközések generálásának első módja az SHA-1 számára . Letöltve: 2017. március 9. Az eredetiből archiválva : 2017. március 10.
  8. ↑ E-mail programok frissítése - Mail - Yandex.Help . yandex.ru. Letöltve: 2016. április 7. Az eredetiből archiválva : 2016. április 20.

Irodalom

  • Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 .
  • Nils Ferguson , Bruce Schneier . Gyakorlati kriptográfia = Gyakorlati kriptográfia: Biztonságos kriptográfiai rendszerek tervezése és megvalósítása. - M .  : Dialektika, 2004. - 432 p. - 3000 példányban.  — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

Linkek

 Hash függvények
Általános rendeltetésű
Kriptográfia
Kulcsgenerálási funkciók
Csekkszám ( összehasonlítás )
Hashes