|
ネットワーク WG Request for Comments： 2104 分類： 情報提供 |
H. Krawczyk IBM M. Bellare UCSD R. Canetti IBM 1997年 2月 |
このメモは、 インターネット・コミュニティに対して情報を提供するものである。 このメモは、何らインターネットの標準を規定するものではない。 このメモの配布に制限はない。
この文書では、 暗号ハッシュ関数を使用してメッセージ認証を行なう仕組みであるHMACについて記述する。 HMACは、 MD5やSHA-1などの反復暗号ハッシュ関数を秘密の共有鍵と組み合わせて使用する。 HMACの暗号としての強度は、 使用しているハッシュ関数のプロパティに依存する。
信頼できないメディア上を伝送し、 蓄積される情報のインテグリティをチェックする方法を提供することは、 開かれたコンピューティングと通信の世界において最初に必要とされることである。 秘密鍵に基づくそのようなインテグリティチェックを提供する仕組みを、 通常「メッセージ認証コード」(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章を参照のこと)
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))
すなわち、
解説のために、MD5に基づいた見本のコードを付録として提供する。
HMACにおいて使用される鍵は、 どのような長さのものでもよい（Bバイトより長い鍵は最初にHでハッシュされる）。 しかしLバイトより短いものは、 その関数のセキュリティ強度が減少するため使用してはならない。 Lバイトより長い鍵も受け入れられるが、その余分の長さは、 あまり関数の強度を増さないだろう。 （その鍵の乱数的性質が弱いとみなされる場合には、 より長い鍵が勧められるかもしれない。）
鍵は無作為に選ばれ（または、 ランダムな種を与えた暗号的に強い疑似乱数発生器を使って生成され）、 定期的にリフレッシュされる必要がある。 （現在の攻撃は、実際には不可能であるため、 これらの攻撃からでは推奨するある特定の鍵の変更回数は示せない。 しかし、定期的な鍵のリフレッシュは、 その関数と鍵の潜在的な欠点を補うものであり、 鍵が見つけられた場合の損害を制限する基本的なセキュリティ技法である。)
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を上記の方法で実装しようとすることは、 ローカルの実装で決定することであり、 相互接続性に影響を及ぼすものではない。
メッセージ認証コードの有名な実施法に、 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が指定されない場合は、 そのハッシュのすべてのビットが出力されるとする。）
ここに示されたメッセージ認証の仕組みに関するセキュリティは、 ハッシュ関数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.