ネットワーク WG
Request for Comments: 2104
分類: 情報提供
H. Krawczyk
IBM
M. Bellare
UCSD
R. Canetti
IBM
1997年 2月

 

HMAC: メッセージ認証のための鍵付ハッシング
(HMAC: Keyed-Hashing for Message Authentication)

このメモの位置付け 

このメモは、インターネット・コミュニティに対して情報を提供するものである。このメモは、何らインターネットの標準を規定するものではない。このメモの配布に制限はない。

要旨

この文書では、暗号ハッシュ関数を使用してメッセージ認証を行なう仕組みである HMAC について記述する。HMAC は、MD5 や SHA-1 などの反復暗号ハッシュ関数を秘密の共有鍵と組み合わせて使用する。HMAC の暗号としての強度は、使用しているハッシュ関数のプロパティに依存する。

1.はじめに 

信頼できないメディア上を伝送し、蓄積される情報のインテグリティをチェックする方法を提供することは、開かれたコンピューティングと通信の世界において最初に必要とされることである。秘密鍵に基づくそのようなインテグリティチェックを提供する仕組みを、通常「メッセージ認証コード」(MAC) と呼んでいる。通常、メッセージ認証コードは、秘密鍵を共有する 2 つの組織の間で送られる情報を認証するために使用される。この文書では、このような暗号ハッシュ関数に基づく MAC の仕組みについて示す。この HMAC と呼ばれる仕組みは、[BCK1] の著者らによる成果に基づいている。その文献では、その構造が示されており、暗号的に分析されている。この文書では、HMAC の正当性とセキュリティ分析について詳細に言及し、他の鍵付ハッシュ法との比較についても言及する。

HMAC は、どのような反復暗号ハッシュ関数とも組み合わせて使用することができる。MD5 と SHA-1 は、そのようなハッシュ関数の例である。また、HMAC はその計算とメッセージ認証値の確認の際に秘密鍵を使用する。
この構造の主な目的は、

この文書では、一般的な暗号ハッシュ関数(H によって示す)を使用する HMAC について指定する。個々の HMAC のインスタント化には、個々のハッシュ関数の定義が必要とされる。そのようなハッシュ関数の現在の候補には、SHA-1 [SHA]、MD5 [MD5]、RIPEMD-128/160 [RIPEMD] があげられる。異なるこれらの HMAC の実現法は、HMAC-SHA1、HMAC-MD5、HMAC-RIPEMD、その他として示される。

注:この文書の執筆時点では、MD5 と SHA-1 が、最も広く使用されている暗号ハッシュ関数である。MD5 は、最近、衝突サーチ攻撃に対して弱いことが示された [Dobb]。この攻撃や他に現在知られている MD5 の欠点は、この文書にて指定されるような HMAC での MD5 の使用を妥協させるようなものではない([Dobb] を見よ)。しかし、SHA-1 の方が暗号的に強固な関数であるようである。MD5 の優れた性能が重要なアプリケーションは、現在、その MD5 を HMAC で使用することを検討することが可能である。いずれにせよ、実装者と利用者は、これらの暗号ハッシュ関数に対する暗号解析の開発の可能性と、その結果として起こる基本となるハッシュ関数の置き換えの必要性について知っておく必要がある。(HMAC のセキュリティについてのさらなる情報については、6 章を参照のこと)

2. HMAC の定義 

HMAC を定義するためには、H によって示す暗号ハッシュ関数と、秘密鍵 K が必要となる。ここで、H は基本的な圧縮関数をデータブロック単位で繰り返すことによってデータがハッシュされるような暗号ハッシュ関数であると仮定する。また、そのブロックのバイト長を B によって示し (これまでであげたハッシュ関数の例であればすべて B=64 となる) 、ハッシュ出力のバイト長を L によって示す (MD5 であれば L=16、SHA-1 であれば L=20 となる)。認証鍵 K は、最大そのハッシュ関数のブロック長 B までその長さを取ることができる。B バイトより長い鍵を使用するアプリケーションは、最初に H で鍵をハッシュし、その結果生じる L バイトの文字列を HMAC への実際の鍵として使用する。どのような場合においても K の長さは(ハッシュ出力長として)最低 L バイトまでが推奨される。鍵のさらなる情報については、3 章を参照のこと。

以下のように 2 つの異なる固定文字列 ipad と opad を定義する (その 'i' と 'o' は、inner と outer を連想させるように付けてある):

ipad = バイト値 0x36 を 64 回繰り返した文字列
opad = バイト値 0x5C を 64 回繰り返した文字列

データ `text' に対して HMAC を計算するためには、以下のようにする。

H(K XOR opad, H(K XOR ipad, text))

すなわち、

  1. B バイトの文字列を作るように K の終わりまでゼロを追加する
    (例えば、K が 20 バイトの長さで B=64 であるならば、K に 44 個のゼロのバイト値 0x00 が追加される)
  2. ステップ (1) で計算された B バイトの文字列と ipad との XOR(ビット毎の排他的論理和)を計算する。
  3. ステップ (2) の結果生じた B バイトの文字列に、データ `text' のストリームを追加する。
  4. ステップ (3) で生成されたストリームに H を適用する。
  5. ステップ (1) で計算された B バイトの文字列と opad との XOR(ビット毎の排他的論理和)を計算する。
  6. ステップ (5) の結果生じた B バイトの文字列に、ステップ (4) の H の結果を追加する。
  7. ステップ (6) で生成されたストリームに H を適用し、その結果を出力する。

解説のために、MD5 に基づいた見本のコードを付録として提供する。

3. 鍵 

HMAC において使用される鍵は、どのような長さのものでもよい(B バイトより長い鍵は最初に H でハッシュされる)。しかし L バイトより短いものは、その関数のセキュリティ強度が減少するため使用してはならない。L バイトより長い鍵も受け入れられるが、その余分の長さは、あまり関数の強度を増さないだろう。(その鍵の乱数的性質が弱いとみなされる場合には、より長い鍵が勧められるかもしれない。)

鍵は無作為に選ばれ(または、ランダムな種を与えた暗号的に強い疑似乱数発生器を使って生成され)、定期的にリフレッシュされる必要がある。(現在の攻撃は、実際には不可能であるため、これらの攻撃からでは推奨するある特定の鍵の変更回数は示せない。 しかし、定期的な鍵のリフレッシュは、その関数と鍵の潜在的な欠点を補うものであり、鍵が見つけられた場合の損害を制限する基本的なセキュリティ技法である。)

4. 実装上の注意 

HMAC は、基本となるハッシュ関数 H のコードを修正することなく利用できるように定義される。特に HMAC では、関数 H をあらかじめ定義された初期値 IV(それぞれの反復ハッシュ関数で指定される圧縮関数を初期化するための定数)と共に使用する。しかし、性能の改善が望まれるのであれば、動的 IV をサポートするように H のコードを修正する犠牲を被れば(おそらく)成し遂げることが可能である。

B バイトのブロック(K XOR ipad)と(K XOR opad)の圧縮関数の中間結果を鍵 K の生成時、あるいは、最初に使用する前に、事前に一回だけ計算しておくという案もある。この中間結果は保存され、メッセージを認証する必要がある度に、H の IV を初期化するために使用される。この方法では、認証されるメッセージそれぞれにおいて、2 個の B バイトのブロック(すなわち(K XOR ipad)と(K XOR opad))に H の圧縮関数を適用する処理が省かれる。このような節約は、短いデータストリームを認証する場合は重要となる可能性がある。また、保存された中間値は秘密鍵と同じように扱い、保護する必要があることを強調しておく。

HMAC を上記の方法で実装しようとすることは、ローカルの実装で決定することであり、相互接続性に影響を及ぼすものではない。

5. 省略された出力 

メッセージ認証コードの有名な実施法に、MAC の出力を省略し、そのビットの一部のみを出力する方法がある(例えば [MM,ANSI])。Preneel と van Oorschot [PV] は、ハッシュに基づく MAC 関数の出力を省略することのいくつかの分析上の利点を示している。この分野での結果は、省略のセキュリティ上の利点の全体に関して言えば、絶対的なものではない。それには、利点(攻撃者にとって利用できるハッシュ結果の情報がより少ないこと)と欠点(攻撃者にとって予測するビット数が少ないこと)がある。HMAC のアプリケーションは、あるパラメータ t に対して HMAC 計算の左から t ビットまでを出力することによって、HMAC の出力を省略することができる。(すなわち、その計算は、前述の 2 章にて定義されるような通常の方法によってなされるが、その最終結果が t ビットに省略される。)出力長 t はハッシュ出力の半分の長さ(誕生日攻撃の限界と一致する)より短くなく、80 ビット(攻撃者の予測に対して必要なビット数の適切な下限界)より短くならないようにすることが推奨される。t ビットを出力し、ハッシュ関数 H を使用する HMAC の実現法を HMAC-H-t と示すことにする。例えば、HMAC-SHA1-80 は、 SHA-1 関数を使って計算され、その出力を 80 ビットに省略する HMAC を示す。(例えば、HMAC-MD5 のようにパラメータ t が指定されない場合は、そのハッシュのすべてのビットが出力されるとする。)

6. セキュリティ

ここに示されたメッセージ認証の仕組みに関するセキュリティは、ハッシュ関数 H の暗号的性質:衝突の発見への抵抗性(その初期値が秘密でランダムな場合と、その関数の出力が攻撃者に明らかに利用されないという場合に限られる)と個々のブロックに適用する際の圧縮関数 H のメッセージ認証に関する性質(HMAC では、これらのブロックに内側の H 計算の結果が含まれるため、攻撃者にはこれらのブロックの一部は知られない。特に、これらのブロックすべてを攻撃者が選ぶことはできない)に依存する。

一般に、HMAC で使用されるハッシュ関数には、これらの性質、そして実際にはさらに強い性質が仮定される。特に、上記の性質が保たれないハッシュ関数は、そのような関数に基づいた代替のメッセージ認証スキームを含んだほとんどの(多分、すべての)暗号アプリケーションにとって不適当である。(HMAC 関数の完全な解析と正当性については、[BCK1] を参照のこと。)

候補となるハッシュ関数の暗号強度が信頼できるものとすると、次に、HMAC の構造の以下の 2 つの性質とメッセージ認証の安全な利用法に目を向けることが重要である:

1. 構造が、使用するハッシュ関数 H の細部からは独立しており、後に他のどのような安全な(反復)暗号ハッシュ関数とも置き換えることができる。

2. 暗号化に対してメッセージ認証は、「はかない」効果を持つ。あるメッセージ認証スキームが破られたことが公表された場合、そのスキームの置き換えには至るが、過去に認証された情報には悪影響を及ぼすことはない。これは、暗号化とは明らかな違いがある。暗号化の場合は、将来暗号アルゴリズムが破られた場合に、現在暗号化されている情報の内容が明らかにされてしまう可能性があるからである。

HMAC に対して知られている最も強力な攻撃は、ハッシュ関数 H の衝突の頻度に基づいており(「誕生日攻撃」)[PV,BCK2]、最低限の道理にかなったハッシュ関数に対しては、全く役に立たないものである。

例として、出力長が L=16 バイト(128 ビット)である MD5 のようなハッシュ関数を考えた場合、攻撃者は約 2**64 の既知の平文から(「同じ」秘密鍵 K で)計算された正しいメッセージ認証タグを得る必要がある。これは、H によって少なくとも 2**64 ブロックを処理するという、現実的には全く不可能な作業が要求される(これは 64 バイトのブロック長では、連続した 1Gbps のリンクにおいて 250,000 年かかり、しかもこの間は秘密鍵 K が変更されてはならない)。この攻撃は、関数 H の衝突のふるまいに重大な欠陥が発見された場合のみ現実となる可能性がある(例えば、2**30 メッセージの後に衝突が発見される場合など)。このような発見がされれば、関数 H を即座に置き換えることが決定されるだろう(このような失敗は、デジタル署名、公開鍵証明書などにおける H の伝統的な利用には、さらに厳しく影響する)。

注:この攻撃を、秘密鍵が含まれず、衝突を発見するのに 2**64 のオフラインで並列の (!) 処理で十分な暗号ハッシュ関数に対する通常の衝突攻撃と十分に比較してみる必要がある。HMAC への誕生日攻撃が全く非現実的であるのに対して、後者の攻撃は実現の可能性に近づいている [VW]。(上記の例では、もし出力が 160 ビットのハッシュ関数を使うのであれば、2**64 は 2**80 に置き換えられる)

以上の構造の正確な実装、ランダム(あるいは、暗号的に擬似ランダム)な鍵の選択、安全な鍵交換の仕組み、頻繁な鍵のリフレッシュと鍵の念入りな秘密保護が、HMAC によって提供されるインテグリティの確認の仕組みに関するセキュリティの本質的な成分のすべてである。


補遺 -- 見本コード 

解説のために、HMAC-MD5 の見本の実装コードを、いくつかの対応するテストベクトルと共に提供する(コードは、[MD5] において記述されている MD5 の コードに基づいている)。

/*
** Function: hmac_md5
*/

void
hmac_md5(text, text_len, key, key_len, digest)
unsigned char*  text;                /* pointer to data stream */
int             text_len;            /* length of data stream */
unsigned char*  key;                 /* pointer to authentication key */
int             key_len;             /* length of authentication key */
caddr_t         digest;              /* caller digest to be filled in */

{
        MD5_CTX context;
        unsigned char k_ipad[65];    /* inner padding -
                                      * key XORd with ipad
                                      */
        unsigned char k_opad[65];    /* outer padding -
                                      * key XORd with opad
                                      */
        unsigned char tk[16];
        int i;
        /* if key is longer than 64 bytes reset it to key=MD5(key) */
        if (key_len > 64) {

                MD5_CTX      tctx;

                MD5Init(&tctx);
                MD5Update(&tctx, key, key_len);
                MD5Final(tk, &tctx);

                key = tk;
                key_len = 16;
        }

        /*
         * the HMAC_MD5 transform looks like:
         *
         * MD5(K XOR opad, MD5(K XOR ipad, text))
         *
         * where K is an n byte key
         * ipad is the byte 0x36 repeated 64 times
         * opad is the byte 0x5c repeated 64 times
         * and text is the data being protected
         */

        /* start out by storing key in pads */
        bzero( k_ipad, sizeof k_ipad);
        bzero( k_opad, sizeof k_opad);
        bcopy( key, k_ipad, key_len);
        bcopy( key, k_opad, key_len);

        /* XOR key with ipad and opad values */
        for (i=0; i<64; i++) {
                k_ipad[i] ^= 0x36;
                k_opad[i] ^= 0x5c;
        }
        /*
         * perform inner MD5
         */
        MD5Init(&context);                   /* init context for 1st
                                              * pass */
        MD5Update(&context, k_ipad, 64)      /* start with inner pad */
        MD5Update(&context, text, text_len); /* then text of datagram */
        MD5Final(digest, &context);          /* finish up 1st pass */
        /*
         * perform outer MD5
         */
        MD5Init(&context);                   /* init context for 2nd
                                              * pass */
        MD5Update(&context, k_opad, 64);     /* start with outer pad */
        MD5Update(&context, digest, 16);     /* then results of 1st
                                              * hash */
        MD5Final(digest, &context);          /* finish up 2nd pass */
}

Test Vectors (Trailing '\0' of a character string not included in test):

  key =         0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
  key_len =     16 bytes
  data =        "Hi There"
  data_len =    8  bytes
  digest =      0x9294727a3638bb1c13f48ef8158bfc9d

  key =         "Jefe"
  data =        "what do ya want for nothing?"
  data_len =    28 bytes
  digest =      0x750c783e6ab0b503eaa86e310a5db738

  key =         0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

  key_len       16 bytes
  data =        0xDDDDDDDDDDDDDDDDDDDD...
                ..DDDDDDDDDDDDDDDDDDDD...
                ..DDDDDDDDDDDDDDDDDDDD...
                ..DDDDDDDDDDDDDDDDDDDD...
                ..DDDDDDDDDDDDDDDDDDDD
  data_len =    50 bytes
  digest =      0x56be34521d144c88dbb8c733f0e8b3f6

謝辞 

Pau-Chen Cheng、Jeff Kraemer と Michael Oehler は、初期のドラフトの段階において役に立つコメントを提供し、この仕様の初の相互接続性試験をしてくれた。Jeff と Pau-Chen は、親切にも付録の見本コードとテストベクトルを提供してくれた。Burt Kaliski、Bart Preneel、Matt Robshaw、Adi Shamir と Paul van Oorschot は、HMAC 構造の調査の間、役に立つコメントと提案をしてくれた。

参考文献 

[ANSI] ANSI X9.9, "American National Standard for Financial Institution Message Authentication (Wholesale)," American Bankers Association, 1981年. Revised 1986年.

[Atk] Atkinson, R., "IP Authentication Header", RFC 1826, 1995年 8月.

[BCK1] M. Bellare, R. Canetti, and H. Krawczyk, "Keyed Hash Functions and Message Authentication", Proceedings of Crypto'96, LNCS 1109, pp. 1-15. (http://www.research.ibm.com/security/keyed-md5.html)

[BCK2] M. Bellare, R. Canetti, and H. Krawczyk, "Pseudorandom Functions Revisited: The Cascade Construction", Proceedings of FOCS'96.

[Dobb] H. Dobbertin, "The Status of MD5 After a Recent Attack", RSA Labs' CryptoBytes, Vol. 2 No. 2, Summer 1996年. http://www.rsa.com/rsalabs/pubs/cryptobytes.html

[PV] B. Preneel and P. van Oorschot, "Building fast MACs from hash functions", Advances in Cryptology -- CRYPTO'95 Proceedings, Lecture Notes in Computer Science, Springer-Verlag Vol.963, 1995年, pp. 1-14.

[MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 1992年 4月.

[MM] Meyer, S. and Matyas, S.M., Cryptography, New York Wiley, 1982年.

[RIPEMD] H. Dobbertin, A. Bosselaers, and B. Preneel, "RIPEMD-160: A strengthened version of RIPEMD", Fast Software Encryption, LNCS Vol 1039, pp. 71-82. ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/ripemd/.

[SHA] NIST, FIPS PUB 180-1: Secure Hash Standard, 1995年 4月.

[Tsu] G. Tsudik, "Message authentication with one-way hash functions", In Proceedings of Infocom'92, 1992年 5月. (Also in "Access Control and Policy Enforcement in Internetworks", Ph.D. Dissertation, Computer Science Department, University of Southern California, 1991年 4月.)

[VW] P. van Oorschot and M. Wiener, "Parallel Collision Search with Applications to Hash Functions and Discrete Logarithms", Proceedings of the 2nd ACM Conf. Computer and Communications Security, Fairfax, VA, 1994年 11月.

著者のアドレス

Hugo Krawczyk
IBM T.J. Watson Research Center
P.O.Box 704
Yorktown Heights, NY 10598

EMail: hugo@watson.ibm.com

Mihir Bellare
Dept of Computer Science and Engineering
Mail Code 0114
University of California at San Diego
9500 Gilman Drive
La Jolla, CA 92093

EMail: mihir@cs.ucsd.edu

Ran Canetti
IBM T.J. Watson Research Center
P.O.Box 704
Yorktown Heights, NY 10598

EMail: canetti@watson.ibm.com
 

翻訳者のアドレス

東京都中央区新川1-21-2 茅場町タワー
株式会社 NTTデータ
開発本部
馬場 達也

EMail: baba@rd.nttdata.co.jp

著作権表記全文

Copyright (C) The Internet Society (1997). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.