Network Working Group M. Friedl Request for Comments: 4419 N. Provos Category: Standards Track W. Simpson March 2006 セキュア シェル (SSH) トランスポート層プロトコルのための Diffie-Hellman 群交換 このメモの位置づけ この文書は, インターネットコミュニティに対するインターネットの標準トラックプロトコルを定義している. また, 改善のための議論と示唆を求めている. このプロトコルの標準化の状態と状況は "Internet Official Protocol Standards" (STD 1) の現在の版を参照してほしい. このメモの配布は制限しない. 著作権情報 Copyright (C) The Internet Society (2006). 訳者: 春山 征吾 . 概要 このメモは, セキュア シェル (SSH) プロトコルのための 新しい鍵交換法を記述している. SSHのサーバとクライアントが Diffie-Hellman 鍵交換をするための新しい群を提案します. この提案された群は固定される必要はなく時間とともに変化できます. 1概要と原理 SSH [RFC4251] は, インターネットでの安全なリモートログインのための非常に一般的なプロトコルだ. 現在, SSHは "diffie-hellman-group1-sha1" 法 [RFC4253] を用いて最初の鍵交換をしている. この方法は, すべての操作を固定された群の上で実行するよう規定しています. Diffie-Hellman 鍵交換は, 一方の側だけでは決定できない共有の秘密を提供する. さらに, 共有の秘密は参加している当事者のみが分かる. SSHでは, 鍵交換は, ホスト認証を提供するホスト鍵で署名されている. Diffie-Hellman 鍵交換のセキュリティは, 離散対数問題 (DLP) が容易に解けないことに基づいている. 将来何年にも渡って SSHプロトコルが利用されることを期待しているので, 固定された群に対する広範囲の事前計算と群の上の離散対数を計算するより効率的なアルゴリズムが, SSH プロトコルのセキュリティの脅威になることを恐れている. Friedl, et al. Standards Track [Page 1] RFC 4419 SSH DH Group Exchange March 2006 新しい群を提案できると, 離散対数のより効率的な計算のために事前処理をする動機を減らすことができる. サーバはバックグラウンドで常に新しい群を計算できる. 2. Requirements Notation この文書でのキーワード "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", "OPTIONAL" は, [RFC-2119] で記述されているように解釈される. 3. Diffie-Hellman 群と鍵交換 サーバは, サーバが選択できる安全な素数のリストと対応する生成器を保持する. 素数 p が安全とは, p = 2q + 1 な q が素数の場合だ. バックグラウンドで新しい素数は生成できる. 生成器 g は生成される部分群のオーダーが小さい素数に因数分解できないように選ぶ必要がある. つまり p = 2q + 1 のとき, オーダーは q か p-1 のどちらかでなければならない. オーダーが p - 1 のとき, 指数は, pの法の範囲を均等に分布し小さいサブセットを巡回することがない, 可能なすべての公開値を生成する. このような生成器は "原始根" と呼ばれる （ｐが"安全"なときは容易に見つけられる). クライアントは, 適切なサイズを指定するサーバから法(modulus)を要求する. 次の記述では, C はクライアント, S はサーバ, 法 p は大きく安全な素数, g は GF(p)の部分群の生成器, min は クライアントが受容できる p のbitでの最小サイズ, n はクライアントがサーバから受け取りたい p の bitでの最小サイズ, max はクライアントが受容できるpのbitでの最大サイズ. V_S は S のバージョン文字列, V_C は C のバージョン文字列, K_S はホスト公開鍵, I_C は CのKEXINITメッセージ, I_S は SのKEXINITメッセージ (VS以降はこの部分が始まる前に交換されたもの)とする: 1C は S に "min || n || max" を送り, 群のサイズの最小受容値と希望値, 最大値をbitで示す. 2. S はクライアントの要求に一番一致する群を見つけ C に "p || g" を送る. 3. C は 1 < x < (p-1)/2 な乱数 x を生成する. e = g^x mod p を計算し "e" を S に送る. Friedl, et al. Standards Track [Page 2] RFC 4419 SSH DH Group Exchange March 2006 4. S は 0 < y < (p-1)/2 な乱数 y を生成し f = g^y mod p を計算する. S は "e" を受信する. K = e^y mod p と H = hash(V_C || V_S || I_C || I_S || K_S || min || n || max || p || g || e || f || K) (これらの要素はタイプに従ってエンコードされている. 以下を参照) を計算し, ホスト秘密鍵で H に署名し s を得る. S は "K_S || f || s" を C に送る. 署名の操作は2つめのハッシュ操作を伴なうかもしれない. 5. C は, K_S が本当に S のホスト鍵かを検証する(たとえば, 証明書や公開鍵を得られるローカルなデータベースを用いて). C は, 鍵を検証無しで受け入れることもできる; しかし, そうするとプロトコルを能動的な攻撃に対して安全ではなくしてしまう (しかし, 多くの環境で短い期間実際的な理由から望まれている). そして C は K = f^x mod p と H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)を計算し H に対する署名 s を検証する. サーバとクライアントは, 法の長さ k が1024 <= k <= 8192 である群をサポートする必要がある. min と max の推奨値はそれぞれ 1024 と 8192 だ. どちらの側も [1, p-1]の範囲にない e や f の値を送ったり受け入れたりしてはならない. この条件に違反したら, 鍵交換は失敗する. 限定攻撃(confinement attack) を防ぐため, 共有の秘密 K は 1 < K < p-1 のものだけ受け入れなければならない. サーバは, サーバが持っている群の中でクライアントが要求したサイズよりも大きいもののうちもっとも小さいサイズの群を返す必要がある. もしクライアントが要求するよりも大きな群をサーバが持っていなければ, 持っている一番大きな群を返す必要がある. すべての場合で, 少なくとも 1024 bit のサイズの群を返す必要がある. これは, 次のメッセージ群で実装される. 交換ハッシュを計算するハッシュ関数は, 方法の名前で定義される. これを HASH と呼ぶ. 署名に用いる公開鍵アルゴリズムは, KEXINIT メッセージで取り決める. まず, クライアントは以下を送る: byte SSH_MSG_KEY_DH_GEX_REQUEST uint32 min, minimal size in bits of an acceptable group uint32 n, preferred size in bits of the group the server will send uint32 max, maximal size in bits of an acceptable group Friedl, et al. Standards Track [Page 3] RFC 4419 SSH DH Group Exchange March 2006 サーバは以下で応答する: byte SSH_MSG_KEX_DH_GEX_GROUP mpint p, safe prime mpint g, generator for subgroup in GF(p) クライアントは以下で応答する: byte SSH_MSG_KEX_DH_GEX_INIT mpint e サーバは以下で応答する. byte SSH_MSG_KEX_DH_GEX_REPLY string server public host key and certificates (K_S) mpint f string signature of H ハッシュ H は, 次の連結に対する HASH の結果だ: string V_C, the client's version string (CR and NL excluded) string V_S, the server's version string (CR and NL excluded) string I_C, the payload of the client's SSH_MSG_KEXINIT string I_S, the payload of the server's SSH_MSG_KEXINIT string K_S, the host key uint32 min, minimal size in bits of an acceptable group uint32 n, preferred size in bits of the group the server will send uint32 max, maximal size in bits of an acceptable group mpint p, safe prime mpint g, generator for subgroup mpint e, exchange value sent by the client mpint f, exchange value sent by the server mpint K, the shared secret この値は交換ハッシュと呼ばれる. [RFC4253] により鍵交換を認証するのに用いられる. 4. 鍵交換法 この文書は 新しい2つの鍵交換法を定義する: "diffie-hellman-group-exchange-sha1" と "diffie-hellman-group-exchange-sha256" だ. Friedl, et al. Standards Track [Page 4] RFC 4419 SSH DH Group Exchange March 2006 4.1. diffie-hellman-group-exchange-sha1 "diffie-hellman-group-exchange-sha1" 法は, SHA-1 [FIPS-180-2] を HASH として用いる Diffie-Hellman 群と鍵交換を指定する. 4.2. diffie-hellman-group-exchange-sha256 "diffie-hellman-group-exchange-sha256" 法は, SHA-256 [FIPS-180-2] を HASH として用いる Diffie-Hellman 群と鍵交換を指定する. 鍵交換で利用されるハッシュ(この場合 SHA-256)は, 鍵導出疑似乱数関数(PRF)でも用いられなければならない. これは, [RFC4253]の「鍵交換からの出力」での要件によるものだ. 5. メッセージ番号のまとめ 次のメッセージ番号を, この文書で定義する. これらはこの文書で閉じた名前空間の中にあり, IANAによって割り当てられていない. #define SSH_MSG_KEX_DH_GEX_REQUEST_OLD 30 #define SSH_MSG_KEX_DH_GEX_REQUEST 34 #define SSH_MSG_KEX_DH_GEX_GROUP 31 #define SSH_MSG_KEX_DH_GEX_INIT 32 #define SSH_MSG_KEX_DH_GEX_REPLY 33 SSH_MSG_KEX_DH_GEX_REQUEST_OLD は 後方互換性のために用いられる. "min || n || max" を送る代わりに クライアントは "n" のみを送る. さらに, "min || n || max" の代わりに "n" のみを用いてハッシュが計算される. 30-49 の範囲の数は鍵交換特有のもので, 他の鍵交換法で再定義できる. 6. 実装上の注意 6.1. 生成器の選択 1つの有用なテクニックとして, 生成器を選択し法(modulus)の選択の篩をその生成器の素数に限する, というものがある. 2 p (mod 24) = 11 のとき. 5 p (mod 10) = 3 or 7 のとき. Friedl, et al. Standards Track [Page 5] RFC 4419 SSH DH Group Exchange March 2006 2と生成器として利用するのが推奨される. 乗算のパフォーマンスが良いからだ. これは, 原始根でない場合も有効だ. 可能な剰余の空間の半分をカバーするからだ. 6.2. プライベート指数 鍵交換のスピードを増すため, クライアントとサーバがそれぞれのプライベート指数のサイズを減らすことができる. プライベート指数は, 共有の秘密から生成される鍵の素材の少なくとも2倍の長さが必要だ. より詳細には, van Oorschot と Wiener の論文 [VAN-OORSCHOT] を参照せよ. 7. セキュリティの考察 このプロトコルは単純であることを目指しており, よく知られたプリミティブのみを利用している. コミュニティが受け入れやすくし実装を容易にしている. これにより, うまくいけばより安全なシステムを構成できる. 複数の法(moduli)を利用すると, 特定の攻撃者が法の交換の値の事前計算することを抑制し, 特定の法の分析に専念できなくさせる. ▽せきほうたい法として安全な素数だけを採用することは重要だ. そうすることで小さい素数に因数分解できないオーダーを持つ部分群を生成する生成器 g を見つけられる. つまり, p = 2q + 1 で, オーダーは q か p -1 のどちらかになる. オーダーが p - 1 のとき, 指数は, pの法の範囲を均等に分布し小さいサブセットを巡回することがない, 可能なすべての公開値を生成する. Van Oorshot と Wiener note は ランダムな素数法(modulus) p で小さいプライベート指数を使うと 離散対数の計算を簡単にできることを示した [VAN-OORSCHOT]. しかし, この問題は安全な素数には適用されないことを彼らは述べている. プライベート指数の最下位ビットは, 法が安全な素数このときに回復できる [MENEZES]. しかし, プライベート指数が十分大きければ問題ではない. これに関連して, Waldvogel と Massey は主張している : プライベート指数が{0,...,p-2}で独立に一様にランダムに選択されるなら, 鍵のエントロピーは最大値である lg(p-1)から2bit未満しか小さくならない [WALDVOGEL]. [RFC4251]のセキュリティの考察はこの鍵公開法にも適用される. Friedl, et al. Standards Track [Page 6] RFC 4419 SSH DH Group Exchange March 2006 8. 謝辞 The document is derived in part from "SSH Transport Layer Protocol" [RFC4253] by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne, and S. Lehtinen. Markku-Juhani Saarinen pointed out that the least significant bit of the private exponent can be recovered efficiently when using safe primes and a subgroup with an order divisible by two. Bodo Moeller suggested that the server send only one group, reducing the complexity of the implementation and the amount of data that needs to be exchanged between client and server. Friedl, et al. Standards Track [Page 7] RFC 4419 SSH DH Group Exchange March 2006 Appendix A：安全な素数の生成 "Handbook of Applied Cryptography" [MENEZES] は, k-bitの安全な素数の生成のために次のアルゴリズムを示している. pを法とする乗法群 (multiplicative group mod p) に対して2が生成器になるよう修正した. 1次の手順を実行: 1ランダムな (k-1)-bit の素数 q を選択. このとき q mod 12 = 5. 2. p := 2q + 1 を計算し, p が素数かテスト (たとえば除算の試行とRabin-Millerテストを用いて) 2. pが素数になるまで繰り返し. 実装がOpenSSLのライブラリを利用する場合, 1024-bit の安全な素数と 2 を生成器として持つ群は次のように作成できる: DH *d = NULL; d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); BN_print_fp(stdout, d->p); 2で生成された部分群のオーダーは q = p -1 だ. References Normative References [FIPS-180-2] National Institute of Standards and Technology (NIST), "Secure Hash Standard (SHS)", FIPS PUB 180-2, August 2002. [RFC4251] Ylonen, T. and C. Lonvick, "The Secure Shell (SSH) Protocol Architecture", RFC 4251, January 2006. [RFC4253] Lonvick, C., "The Secure Shell (SSH) Transport Layer Protocol", RFC 4253, January 2006. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. Informative References [MENEZES] Menezes, A., van Oorschot, P., and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, p. 537, 1996. Friedl, et al. Standards Track [Page 8] RFC 4419 SSH DH Group Exchange March 2006 [VAN-OORSCHOT] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key agreement with short exponents", Advances in Cryptology -EUROCRYPT'96, LNCS 1070, Springer-Verlag, pp. 332-343, 1996. [WALDVOGEL] Waldvogel, C. and J. Massey, "The probability distribution of the Diffie-Hellman key", Proceedings of AUSCRYPT 92, LNCS 718, Springer-Verlag, pp. 492-504, 1993. Authors' Addresses Markus Friedl EMail: markus@openbsd.org Niels Provos EMail: provos@citi.umich.edu William A. Simpson EMail: wsimpson@greendragon.com Friedl, et al. Standards Track [Page 9] RFC 4419 SSH DH Group Exchange March 2006 Full Copyright Statement Copyright (C) The Internet Society (2006). 訳者: 春山 征吾 . This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgement Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Friedl, et al. Standards Track [Page 10]