HMAC

Material iz Vikipedii -- svobodnoi entsiklopedii
Tekushchaia versiia stranitsy poka ne proverialas' opytnymi uchastnikami i mozhet znachitel'no otlichat'sia ot versii, proverennoi 31 avgusta 2017 goda; proverki trebuiut 44 pravki.
Pereiti k navigatsii Pereiti k poisku

HMAC (inogda rasshifrovyvaetsia kak angl. hash-based message authentication code, kod autentifikatsii (proverki podlinnosti) soobshchenii, ispol'zuiushchii khesh-funktsii, ili kak angl. keyed-hash message authentication code, kod autentifikatsii soobshchenii, ispol'zuiushchii khesh-funktsii s kliuchom) -- v informatike (kriptografii), odin iz mekhanizmov proverki tselostnosti informatsii, pozvoliaiushchii garantirovat' to, chto dannye, peredavaemye ili khraniashchiesia v nenadiozhnoi srede, ne byli izmeneny postoronnimi litsami (sm. chelovek poseredine). Mekhanizm HMAC ispol'zuet imitovstavku (MAC), opisan v RFC 2104, v standartakh organizatsii ANSI, IEF, ISO i NIST. MAC -- standart, opisyvaiushchii sposob obmena dannymi i sposob proverki tselostnosti peredavaemykh dannykh s ispol'zovaniem sekretnogo kliucha. Dva klienta, ispol'zuiushchie MAC, kak pravilo, ispol'zuiut obshchii sekretnyi kliuch. HMAC -- nadstroika nad MAC; mekhanizm obmena dannymi s ispol'zovaniem sekretnogo kliucha (kak v MAC) i khesh-funktsii. V nazvanii mozhet utochniat'sia ispol'zuemaia khesh-funktsiia[1]: HMAC-MD5, HMAC-SHA1, HMAC-RIPEMD128, HMAC-RIPEMD160 i t. p.

Istoriia

[pravit' | pravit' kod]

Bylo zamecheno[kem?], chto skorost' raboty khesh-funktsii (naprimer, MD5, SHA-1, RIPEMD128, RIPEMD-160) obychno vyshe skorosti raboty simmetrichnykh blochnykh shifrov (naprimer, DES). Vozniklo zhelanie ispol'zovat' khesh-funktsii v MAC, a nalichie gotovykh bibliotek s realizatsiiami razlichnykh khesh-funktsii tol'ko podtolknulo etu ideiu.

No ispol'zovat' nekotorye khesh-funktsii v MAC bylo nevozmozhno. Naprimer, khesh-funktsiia MD5 ne mozhet primeniat'sia v MAC, tak kak prinimaet tol'ko odin argument -- dannye (stroku, posledovatel'nost' bait) i ne ispol'zuet sekretnogo kliucha.

V iiune 1996 goda[2] Kh'iugo Kravchik (angl. Hugo Krawczyk, sotrudnik firmy IBM), Mikhir Bellar[angl.] (angl. Mihir Bellare, sotrudnik kaliforniiskogo universiteta v San-Diego (UCSD)) i Ran Kannetti (angl. Ran Canetti, sotrudnik firmy IBM) opublikovali opisanie mekhanizma HMAC, a v fevrale 1997 goda imi zhe byl vypushchen RFC 2104. V HMAC dannye <> s kliuchom, i khesh-funktsiia primenialas' dvazhdy.

Byli predlozheny i drugie mekhanizmy, pozvoliaiushchie odnovremenno ispol'zovat' dannye i sekretnyi kliuch v sushchestvuiushchikh algoritmakh kheshirovaniia, no HMAC poluchil naibol'shuiu podderzhku[istochnik ne ukazan 1722 dnia].

Preimushchestva HMAC:

  • vozmozhnost' ispol'zovaniia khesh-funktsii, uzhe imeiushchikhsia v programmnom produkte;
  • otsutstvie neobkhodimosti vneseniia izmenenii v realizatsii sushchestvuiushchikh khesh-funktsii (vnesenie izmenenii mozhet privesti k ukhudsheniiu proizvoditel'nosti i/ili ukhudsheniiu kriptostoikosti);
  • vozmozhnost' zameny khesh-funktsii v sluchae poiavleniia bolee bezopasnoi ili bolee bystroi khesh-funktsii.

Mekhanizm HMAC byl opisan v standartakh organizatsii ANSI, IETF, ISO i NIST.

Primenenie

[pravit' | pravit' kod]

Realizatsiia HMAC iavliaetsia obiazatel'noi (angl. mandatory to implement) dlia protokola IPsec.

HMAC ispol'zuetsia i v drugikh protokolakh interneta, naprimer, TLS.

Opisanie algoritma

[pravit' | pravit' kod]
Oboznacheniia
  • b, block_size -- razmer bloka v baitakh;
  • H, hash -- khesh-funktsiia;
  • ipad -- blok vida ( 0x36 0x36 0x36 ... 0x36 ), gde bait 0x36 povtoriaetsia b raz; 0x36 -- konstanta, magicheskoe chislo, privedionnoe v RFC 2104; <> ot <>[1];
  • K, key -- sekretnyi kliuch (obshchii dlia otpravitelia i poluchatelia);
  • K0 -- izmenionnyi kliuch K (umen'shennyi ili uvelichennyi do razmera bloka (do b bait));
  • L -- razmer v baitakh stroki, vozvrashchaemoi khesh-funktsiei H; L zavisit ot vybrannoi khesh-funktsii i obychno men'she razmera bloka;
Khesh-funktsiia H b, bait L, bait
MD5 64 16
SHA-1 64 20
SHA-224 64 28
SHA-256 64 32
SHA-512/224 128 28
SHA-512/256 128 32
SHA-384 128 48
SHA-512 128 64
SHA3-224 144 28
SHA3-256 136 32
SHA3-384 104 48
SHA3-512 72 64
out = H( in )
b = length( in )
L = length( out )
  • opad -- blok vida ( 0x5c 0x5c 0x5c ... 0x5c), gde bait 0x5c povtoriaetsia b raz; 0x5c -- konstanta, magicheskoe chislo, privedionnoe v RFC 2104; <> ot <>[1];
  • text -- soobshchenie (dannye), kotoroe budet peredavat'sia otpravitelem i podlinnost' kotorogo budet proveriat'sia poluchatelem;
  • n -- dlina soobshcheniia text v bitakh.

Algoritm HMAC mozhno zapisat' v vide odnoi formuly[1]: HMAC K ( t e x t ) = H ( ( K 0 o p a d ) || H ( ( K 0 i p a d ) || t e x t ) ) , {\displaystyle \operatorname {HMAC} _{K}(text)=\operatorname {H} {\Bigg (}(K_{0}\oplus opad)\|\operatorname {H} {\Big (}(K_{0}\oplus ipad)\|text{\Big )}{\Bigg )},} gde:

  • << {\displaystyle \oplus } >> -- operatsiia <iskliuchaiushchee ILI>> ili <>;
  • << || {\displaystyle \|} >> -- operatsiia <<skleika strok>> (posledovatel'nostei bait).

Skhema raboty algoritma HMAC privedena na risunkakh.

Realizatsiia HMAC-MD5
Realizatsiia HMAC-SHA1

Etapy raboty algoritm HMAC perechislennye nizhe.

  1. Poluchit' K0 putiom umen'sheniia ili uvelicheniia kliucha K do razmera bloka (do b bait).
1.1. Esli dlina kliucha K ravna razmeru bloka, to kopiruem K v K0 bez izmenenii i perekhodim k shagu 2.
IF length( K ) == b THEN :
K_0 = K
END_IF
1.2. Esli dlina kliucha K bol'she razmera bloka, to k kliuchu K primeniaem khesh-funktsiiu H, poluchaem stroku razmerom v L bait, dobavliaem nuli k pravoi chasti etoi stroki dlia sozdaniia stroki razmerom v b bait, kopiruem rezul'tat v K0 i perekhodim k shagu 2.
IF length( K ) > b THEN :
x = H( K ) // length( x ) == L
K_0 = zeros( x, b - L )
END_IF
1.3. Esli dlina kliucha K men'she razmera bloka, to dobavliaem nuli k pravoi chasti K dlia sozdaniia stroki razmerom v b bait, kopiruem rezul'tat v K0 (naprimer, esli length( K ) = 20 (v baitakh) i b = 64 (v baitakh), to k pravoi chasti K budet dobavleno 64 - 20 = 44 nulevykh baita (0x00)) i perekhodim k shagu 2.
IF length( K ) < b THEN :
K_0 = zeros( K, b - length( K ) )
END_IF
  1. Poluchit' blok Si razmerom v b bait s pomoshch'iu operatsii <iskliuchaiushchee ILI>> (<>, << {\displaystyle \oplus } >>):
Si = xor( K0, ipad ) = K0 {\displaystyle \oplus } ipad.
  1. Poluchit' blok So razmerom v b bait s pomoshch'iu operatsii <iskliuchaiushchee ILI>>:
So = xor( K0, opad ) = K0 {\displaystyle \oplus } opad.
  1. Razbit' soobshchenie (dannye, nabor bait) text na bloki razmerom b bait.
  2. Skleit' stroku (posledovatel'nost' bait) Si s kazhdym blokom soobshcheniia M.
  3. K stroke, poluchennoi na proshlom shage, primenit' khesh-funktsiiu N.
  4. Skleit' stroku So so strokoi, poluchennoi ot khesh-funktsii H na proshlom shage.
  5. K stroke, poluchennoi na proshlom shage, primenit' khesh-funktsiiu N.

Kliuchi razmerom men'she L bait, schitaiutsia[1] nebezopasnymi (angl. strongly discouraged). Rekomenduetsia[1] vybirat' kliuchi sluchainym obrazom i reguliarno ikh meniat'. Kliuchi razmerom bol'she L bait, sushchestvenno ne uvelichivaiut[1] stoikost' funktsii, mogut ispol'zovat'sia, esli imeiutsia somneniia v sluchainosti dannykh, ispol'zuemykh dlia sozdaniia kliucha i poluchaemykh ot generatora sluchainykh chisel.

Razmer kliucha K dolzhen byt' bol'she ili raven L/2 bait[istochnik ne ukazan 3983 dnia].

Na risunke pokazana bolee effektivnaia[utochnit'] realizatsiia algoritma HMAC-MD5. Realizatsiia otlichaetsia ispol'zovaniem funktsii F. Ispol'zovanie etoi realizatsii tselesoobrazno, esli bol'shinstvo soobshchenii, dlia kotorykh vychisliaetsia MAC, korotkie. Funktsiia F -- funktsiia szhatiia dlia khesh-funktsii H. V kachestve argumentov F prinimaet peremennuiu n i blok dlinoi v b bait. F proizvodit razbienie bloka na tsepochku zven'ev s dlinoi kazhdogo zvena v n bait. Funktsiia F vyzyvaetsia dlia kazhdogo novogo kliucha odin raz.

Psevdokod

[pravit' | pravit' kod]

Dalee privedion primer realizatsii HMAC na psevdokode:

FUNCTION hmac( key, msg ) :
// Esli razmer kliucha bol'she, chem razmer bloka ...
IF length( key ) > block_size THEN :
// Ukorachivaem kliuch do razmera rezul'tata khesh-funktsii
key = hash( key )
// (Razmer rezul'tata khesh-funktsii obychno men'she (a ne raven), chem razmer bloka khesh-funktsii)
END_IF
// Esli kliuch men'she, chem razmer bloka khesh-funktsii ...
IF length( key ) < block_size THEN:
// Dopolniaem kliuch nulevoi posledovatel'nost'iu
key = key zeroes( block_size - length( key ))
// operator "" vypolniaet skleiku strok (posledovatel'nostei bait)
END_IF

ipad = [ '\x36' * block_size ]
// operator "*" ukazyvaet kolichestvo povtorenii posledovatel'nosti bait,
// a block_size - razmer bloka khesh-funktsii,
opad = [ '\x5c' * block_size ]

ikeypad = ipad key
// operator "" vypolniaet pobitovoe iskliuchaiushchee ILI (xor)
okeypad = opad key

RETURN hash( okeypad hash( ikeypad msg ) )
// Operator "" vypolniaet skleiku strok
END_FUNCTION

Primery koda

[pravit' | pravit' kod]

Primer realizatsii algoritma HMAC-MD5 s pomoshch'iu funktsii standartnoi biblioteki iazyka Python[3]:

import hmac, hashlib
print(hmac.new(
key=b'secret_shared_key',
msg=open('message.txt', 'rb').read(),
digestmod=hashlib.md5
).hexdigest())

Odna iz vozmozhnykh realizatsii algoritma HMAC-MD5 na iazyke PHP[4]:

function hmac ( $key, $data ) {
$b = 64; // block size according RFC 2104
if ( strlen( $key ) > $b ) {
$key = pack( "H*", md5( $key ) );
}
$key = str_pad( $key, $b, chr(0x00) );
$ipad = str_pad( '', $b, chr(0x36) );
$opad = str_pad( '', $b, chr(0x5c) );
$k_ipad = $key ^ $ipad ;
$k_opad = $key ^ $opad;
return md5( $k_opad . pack("H*", md5( $k_ipad . $data ) ) );
}

Primery raboty

[pravit' | pravit' kod]

Prodemonstriruem primer raboty algoritma dlia razlichnykh vkhodnykh dannykh.

Pervyi parametr -- kliuch K razmerom v 160 bit (20 bait). Vtoroi parametr -- soobshchenie text, kotoroe budet peredavat'sia otpravitelem i podlinnost' kotorogo budet proveriat'sia poluchatelem. Na vykhode my poluchaem kod autentifikatsii razmerom v 160 bit.

HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000000, "" ) = 740ca4e7a701540b385df12fe57cff57
HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000000, "Hello World" ) = a0e026219366a56cf843bd2051831327
HMAC( K, text ) = HMAC( 0000000000000000000000000000000000000001, "1" ) = c6b1d8489a204918643086ce346b86bc

Bolee podrobno rassmotrim algoritm HMAC-SHA1 s kliuchom razmerom v 20 bait.

Imeem: tekstovoe soobshchenie text = "Hello World" i 20-baitovyi kliuch v shestnadtsaterichnom vide K = 0x707172737475767778797a7b7c7d7e7f80818283

Shag 1. Dopolniaem kliuch K nulevymi baitami do razmera bloka. Razmer bloka khesh-funktsii SHA-1 raven 64 baitam.

K0:
70717273 74757677 78797a7b 7c7d7e7f
80818283 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

Shag 2. Vypolniaem operatsiiu <> c konstantoi 0x36.

K0 {\displaystyle \oplus } ipad :
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636

Shag 3. Vypolniaem skleiku iskhodnogo soobshcheniia so strokoi, poluchennoi na shage 2.

( K {\displaystyle \oplus } ipad ) || text :
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636
48656c6c 6f20576f 726c64

Shag 4. Primenim khesh-funktsiiu SHA-1 k stroke, poluchennoi na proshlom shage.

H( ( K {\displaystyle \oplus } ipad ) || text ) :
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a

Shag 5. Vypolnim operatsiiu <> c konstantoi 0x5c.

K0 {\displaystyle \oplus } opad :
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c

Shag 6. Skleika stroki, poluchennoi na shage 4, so strokoi, poluchennoi na shage 5.

( K0 {\displaystyle \oplus } opad ) || H( ( K {\displaystyle \oplus } ipad ) || text ) :
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
0d42b899 d804e19e bfd86fc4 4f414045
dfc9e39a

Shag 7. Primenim khesh-funktsiiu SHA-1 k stroke, poluchennoi na proshlom shage.

HMAC( K, text ) = H( ( K0 {\displaystyle \oplus } opad ) || H( ( K {\displaystyle \oplus } ipad ) || text ) ) :
2e492768 aa339e32 a9280569 c5d02626 2b912431

Itog.
Poluchili stroku HMAC( K, text ) razmerom v 20 bait.

Voprosy ispol'zovaniia

[pravit' | pravit' kod]

Poluchennyi kod autentichnosti pozvoliaet ubedit'sia v tom, chto dannye ne izmenialis' kakim by to ni bylo sposobom s tekh por, kak oni byli sozdany, peredany ili sokhraneny doverennym istochnikom. Dlia takogo roda proverki neobkhodimo, chtoby, naprimer, dve doveriaiushchie drug drugu storony zaranee dogovorilis' ob ispol'zovanii sekretnogo kliucha, kotoryi izvesten tol'ko im. Tem samym garantiruetsia autentichnost' istochnika i soobshcheniia. Nedostatok takogo podkhoda ocheviden -- neobkhodimo nalichie dvukh doveriaiushchikh drug drugu storon.

Bezopasnost'

[pravit' | pravit' kod]

Bezopasnost' liuboi funktsii MAC na osnove vstroennykh khesh-funktsii zavisit ot kriptostoikosti bazovoi khesh-funktsii. Privlekatel'nost' HMAC -- v tom, chto ego sozdateli smogli dokazat' tochnoe sootnoshenie mezhdu stoikost'iu vstroennykh khesh-funktsii i stoikost'iu HMAC.

Bezopasnost' funktsii imitovstavki (MAC) obychno vyrazhaetsia v terminakh veroiatnosti uspeshnogo vzloma s kolichestvom vremeni, potrachennogo na eto, a takzhe na poluchenie pary (soobshchenie -- MAC), sozdannoi s tem zhe kliuchom. V sushchnosti, eto dokazano v BELL96a, chto pri dannom urovne usiliia (vremia, soobshchenie -- MAC) na soobshchenie, sgenerirovannoe konechnym pol'zovatelem, veroiatnost' uspeshnoi ataki na HMAC ekvivalentna atake, proizvedionnoi na vstroennuiu khesh-funktsiiu:

  1. V pervom tipe ataki my mozhem rassmatrivat' funktsii szhatiia F v kachestve ekvivalenta khesh-funktsii, primeniaemoi dlia soobshcheniia, sostoiashchie iz edinichnogo bloka dlinoi B bit. Dlia etogo na vkhod khesh-funktsii podaiotsia sluchainoe znachenie dlinoi N bit. Napadenie na khesh-funktsiiu trebuet ili polnogo perebora kliucha, kotoryi obladaet urovnem slozhnosti poriadka 2 n {\displaystyle 2^{n}} , ili s pomoshch'iu ataki <>, kotoraia iavliaetsia chastnym sluchaem vtorogo napadeniia, chto obsuzhdaetsia dalee.
  2. Vo vtorom tipe ataki zloumyshlennik ishchet dva soobshcheniia M i M', kotorye poluchaiutsia ot odinakovoi khesh-funktsii: H( M ) = H( M' ). Etot tip ataki izvesten takzhe kak ataka <>. Uroven' slozhnosti dannoi ataki raven 2 n / 2 {\displaystyle 2^{n/2}} dlia khesha dliny n. Iskhodia iz etogo, bezopasnost' khesh-funktsii MD5 stavitsia pod vopros, potomu chto uroven' slozhnosti dlia nego 2 64 {\displaystyle 2^{64}} , chto uzhe ne vygliadit nevozmozhnym pri pomoshchi sovremennykh[kogda?] tekhnologii. Oznachaet li eto, chto 128-bitnaia khesh-funktsiia, takaia, kak MD5, ne podkhodit dlia HMAC? Otvet na etot vopros -- net, chto posleduet iz sleduiushchikh argumentov[istochnik ne ukazan 1722 dnia]. Pri atake na MD5 zloumyshlennik mozhet vybrat' liuboi nabor soobshchenii i rabotat' offlain nad poiskom kollizii. Tak kak zloumyshlennik znaet algoritm kheshirovaniia i nachal'nye usloviia, zloumyshlennik mozhet sozdat' khesh-kod dlia kazhdogo iz soobshchenii. Odnako, pri atake HMAC, zloumyshlennik ne smozhet generirovat' paru (<>, <>) v udalionnom (offlain) rezhime, tak kak zloumyshlennik ne znaet kliucha K. Takim obrazom, zloumyshlennik dolzhen sledit' za posledovatel'nost'iu soobshchenii, porozhdaemykh HMAC s tem zhe kliuchom, i vypolniat' ataku na nikh. Dlia khesh-koda dlinoi 128 bit trebuetsia 2 64 {\displaystyle 2^{64}} blokov ili 2 72 {\displaystyle 2^{72}} bitov, sgenerirovannykh s pomoshch'iu togo zhe kliucha. Dlia 1-Gbit soedineniia nuzhno bylo by sledit' za potokom soobshchenii, esli kliuch K ne izmeniaetsia, v techenie 150 000 let dlia togo chtoby dobit'sia uspekha. Takim obrazom, esli skorost' imeet znachenie, vpolne priemlemo ispol'zovat' MD5, a ne SHA-1 v kachestve vstroennykh khesh-funktsii dlia HMAC.

Sm. takzhe

[pravit' | pravit' kod]

Istochniki

[pravit' | pravit' kod]
  • Blek U. Internet protokoly bezopasnosti. Moskva: izdatel'stvo <>. 2001. ISBN 5-318-00002-9 (ISBN originala na angliiskom iazyke: ISBN 0-13-014249-2).
  • RFC 2104. Krawczyk H., Bellare M., Canetti R. <>. Fevral' 1997.
  • Stallings W. Cryptography and network security principles and practices. 2005. ISBN 0-13-187316-4.

Primechaniia

[pravit' | pravit' kod]
  1. | 1 2 3 4 5 6 7 Krawczyk H., Bellare M., Canetti R. <>. RFC 2104 Arkhivnaia kopiia ot 15 aprelia 2021 na Wayback Machine. Fevral' 1997.
  2. | Mihir Bellare, Ran Canetti i Hugo Krawczyk. <>. 1996. Skachat' PDF Arkhivnaia kopiia ot 9 maia 2009 na Wayback Machine.
  3. | realizatsiia na iazyke Python (angl.). -- source code. Arkhivirovano iz originala 4 iiunia 2012 goda.
  4. | realizatsiia na iazyke PHP (angl.). -- source code. Arkhivirovano iz originala 4 iiunia 2012 goda.
  • HMAC (angl.).
  • RFC 2104. HMAC. Fevral' 1997.
  • RFC 4226. M'Raihi D., Bellare M., Hoornaert F., Naccache D., Ranen O. <<HOTP: an HMAC-based one-time password algorithm>>. Dekabr' 2005.
  • Generate HMAC Online. Onlain-generator HMAC.
Istochnik -- https://ru.wikipedia.org/w/index.php?title=HMAC&oldid=149832823