ディフィー・ヘルマン鍵共有

ディフィー・ヘルマン鍵共有（ディフィー・ヘルマンかぎきょうゆう、Diffie–Hellman key exchange、DH）、あるいはディフィー・ヘルマン鍵交換（かぎこうかん）とは、事前の秘密の共有無しに、盗聴の可能性のある通信路を使って、暗号鍵の共有を可能にする、公開鍵暗号方式の暗号プロトコルである。この鍵は、共通鍵暗号の鍵として使用可能である。本ページでは有限体上の演算を利用したディフィー・ヘルマン鍵共有手法を扱う。有限体上のディフィー・ヘルマンの他には、楕円曲線上の演算を利用した楕円曲線ディフィー・ヘルマン鍵共有が広く使われている。

概要

1976年にスタンフォード大学の2名の研究員ホイットフィールド・ディフィーとマーティン・ヘルマンは、公開鍵暗号の概念を提案し、その具体的な方式の一つとして、ディフィー・ヘルマン鍵共有（DH鍵共有）プロトコルを提案した。この鍵共有方式は共通鍵暗号方式における鍵の受け渡しを安全に行うために提案された方式である。

このプロトコルは、通信を行いたい2者が各々公開鍵と秘密鍵（私有鍵ともいう）を用意し、公開鍵のみを相手に送信し、各自、自分の秘密鍵と受信した公開鍵から共通鍵を作成できる方法である。たとえ送受信されるデータ（すなわち、二人の公開鍵）を第三者がすべて盗聴していてもそれからでは（計算量的に）私有鍵も共通鍵も生成することができない所に特徴がある。

アメリカ合衆国とカナダで特許が取得された。両国でのアルゴリズムの特許期限は既に1997年 4月29日に切れたので、現在では誰でも自由に利用ができる。

プロトコルの内容

この方式は以下のように行われる。まず大きな素数 $p$ と、 $p-1$ を割り切る大きな素数 $q$ を用意する。また、 $g$ を $({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }$ の元であり、位数が $q$ である値とする。この $p,q,g$ の値は公開されているものとする^[1]。

いまアリスとボブが通信を行うとする。このときアリスとボブはお互い自分だけの知る秘密の値 a, b を選択する、この値は 0 以上 q−1 以下の中からランダムに選ぶ。（ここで、ゼロや小さな値（g^a < p となる a 等）を選択すると安全性が損なわれるが、そのような確率は無視できるほど小さい。）

アリスは以下の値 A を計算してそれをボブに送信する。

A=g^{a}{\bmod {p}}

ボブも同様に以下の値 B を計算してそれをアリスに送信する。

B=g^{b}{\bmod {p}}

アリスは自分だけの知る秘密の値 a とボブから送られてきて受信した値 B から以下の値を計算する。

K_{A}=B^{a}{\bmod {p}}

ボブも自分だけの知る秘密の値 b とアリスから送られてきて受信した値 A から以下の値を計算する。

K_{B}=A^{b}{\bmod {p}}

このときアリスとボブが計算した $K_{A}$ と $K_{B}$ は

K_{A}=K_{B}=g^{ab}{\bmod {p}}

となっていて一致するので、以後この値を共通鍵暗号方式の鍵 $K$ として使用する。

ここで第三者イブがこの二人の通信を傍受していて A と B の値を入手できたとしても、 $A=g^{a}{\bmod {p}}$ と $B=g^{b}{\bmod {p}}$ から $K=g^{ab}{\bmod {p}}$ を多項式時間で計算できる方法はいまのところ知られていないので、第三者イブが秘密の共通鍵 $K$ を生成することは困難である。このためアリスとボブが安全に通信を行うことが可能になる。

しかしながらたとえば、イブがボブになりすましをしていて、そうとは知らずに上記の手順でアリスが（相手がボブだと思ってだまされて）相互に通信をして共通鍵 $K$ を作ったとすると、それ以降のアリスからボブを相手として想定して送った $K$ を共通鍵として暗号化された通信の内容すべては，イブによって容易に内容が解読されてしまうことに注意が必要である。

なお、ディフィーとヘルマンによる最初の論文においては、 $g$ として $({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }$ の生成元を用いることが提案されているが、この場合、アリスが送った $A$ のルジャンドル記号を計算することによって、アリスの秘密情報 $a$ の最下位ビットが漏洩してしまう^[2]。

中間者攻撃

ディフィー・ヘルマン鍵共有自体は認証手段を提供するものではないため、単独では中間者攻撃に対して脆弱である。

ここではディフィー・ヘルマン鍵共有における中間者攻撃の具体的な手順について示す。

DNS偽装・ARPスプーフィング・その他の手段により攻撃者イブがこの二人の通信を中継して A と B の値を（本来の宛先には送らずに）盗み取ったとする。

このとき攻撃者イブはそれらに対して秘密の値 c と d を選択する。この値は a や b と同じ基準で選択される。

攻撃者イブは c を用いて次の値を計算して(アリスになりすまして)ボブに送信する。

A_{E}=g^{c}{\bmod {p}}

また d を用いて次の値を計算して（ボブになりすまして）アリスに送信する。

B_{E}=g^{d}{\bmod {p}}

ボブは自身の秘密の値 b と（アリスからだと思って，実際には攻撃者イブから）受信した値 $A_{E}$ から以下の値を計算する。

K_{BE}=A_{E}^{b}{\bmod {p}}

アリスは自身の秘密の値 a と（ボブからだと思って，実際には攻撃者イブから）受信した値 $B_{E}$ から以下の値を計算する。

K_{AE}=B_{E}^{a}{\bmod {p}}

攻撃者イブは自身の秘密の値 c と d と（中継せずに抜き取った）アリスからの値 A とボブからの値 B の値から以下の値をそれぞれ計算する。

K_{EAE}=A^{d}{\bmod {p}}

K_{EBE}=B^{c}{\bmod {p}}

このときアリスと（ボブになりすました）攻撃者イブの計算した $K_{AE}$ と $K_{EAE}$ の値，およびボブと（アリスになりすました）攻撃者イブの計算した $K_{BE}$ と $K_{EBE}$ の値は

K_{AE}=K_{EAE}=g^{ad}{\bmod {p}}

K_{BE}=K_{EBE}=g^{bc}{\bmod {p}}

になってそれぞれが一致する。

そうしてそれ以降の通信において攻撃者イブは，これら2つの値をそれぞれアリスおよびボブに対する共通鍵暗号方式の鍵として使用してアリスとボブの通信を中継し続けて、盗聴や改ざんを行うことができる。

公開鍵の選択

公開鍵は（何かしらの証明を付けた）静的なものであっても、一時的なもの（ephemeral、この場合特にDHEと略記される）であってもかまわない。一時的な鍵を使用した場合、鍵そのものには認証がないため、別な方法で認証を行うこととなる。もし認証がなければ、上述の通り中間者攻撃に対して脆弱となる。どちらか一方の鍵が静的なものであった場合、中間者攻撃を受けることはなくなるが、forward secrecyのような、その他の高度なセキュリティに与ることはできなくなる。静的な鍵を持つ側では、自身の秘密鍵漏洩を防ぐため、相手の公開鍵を確認して、安全な共通鍵生成関数を利用する必要がある。

共有した秘密をそのまま鍵として使うこともできなくはないが、ディフィー・ヘルマン鍵共有で生成したことによってできる弱いビットの影響を除去するため、秘密をハッシュに通すことが推奨される^[3]。

問題点

処理負荷

ディフィー・ヘルマン鍵共有は負荷のかかる処理であり、SSL/TLSに適用した場合では、通常のRSA暗号による鍵交換の場合と比較して、サーバのスループットが6分の1程度まで落ち込むという実験結果も存在する^[4]。

パラメータの設定ミス

これはディフィー・ヘルマン鍵共有のシステム自体に存在する問題ではないが、2013年の調査では、SSL/TLSでディフィー・ヘルマン鍵共有を有効としているサーバのうち、電子署名のビット数よりDHのビット数のほうが小さく、総当たり攻撃に対して弱くなってしまっているサーバが、実に80%以上の割合で存在していた^[5]。

Logjam 攻撃

原理上は解読がきわめて困難ではあるが、実装上の問題が存在する場合には解読が可能となる場合がある。

また原理上、使われている素数に対して十分な量の事前計算を行えば、その素数に対しては比較的短い時間で鍵を解読することができる ^[6]。2015年、このことを元にした論文が発表された^[7]。

この論文において、Alexaによるトップ100万HTTPSドメインの中で512ビット輸出版DHEを許可している 8.4% のうち 82% が、1024ビット非輸出版DHEでもトップドメイン全体の 17.9% がそれぞれ単一の素数を使い回しており、これらの素数に対して事前計算 (ある種の線形代数計算を含む) を行うことで多くのサーバーの通信に対して解読が行えることを指摘した。特に512ビットの素数に対して解読を実証し、数千コアと約8日の事前計算により、およそ70秒で解読ができることを示した^[7]。

さらに、サーバーが用いる素数についての離散対数問題をリアルタイムで解ける攻撃者が存在した場合には、たとえクライアント側が弱いDHEを許可していなくても偽のサーバーに接続させる中間者攻撃が成立し、例えばサーバー側が512ビットの輸出版DHEを許している場合には、輸出版DHEを許可していない新しいクライアントであっても通信をダウングレードさせることが可能であることを示した (Logjam 攻撃)^[7]。

同論文は1024ビットの非輸出版DHEについても、数億ドルのコストをかけて専用ハードウェアを構築した場合には、1つの素数に対して十分な線形代数計算を1年間で実行できる可能性があることを示唆している^[7]。

脚注

^ RFC 5114（Additional Diffie-Hellman Groups for Use with IETF Standards、2008年8月）や RFC 7919（Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS)、2016年8月）のように、広く公開されて用いられる (p,q,g) の組も存在する。
^ Dan, Boneh (1998), “The Decision Diflie-Hellman Problem”, Algorithmic Number Theory. ANTS 1998, LNCS 1423, https://doi.org/10.1007/BFb0054851 2021年12月24日閲覧。
^ Law, Laurie; Menezes, Alfred; Qu, Minghua; Solinas, Jerry; Vanstone, Scott (August 28, 1998). An Efficient Protocol for Authenticated Key Agreement. Certicom January 19, 2012閲覧。.
^ Symantec (2013)、pp.13-14。
^ Symantec (2013)、p.9。
^ Diffie, Whitfield; Oorschot, Paul C. Van; Wiener, Michael J. (1992-03-06), “Authentication and Authenticated Key Exchanges”, Designs, Codes and Cryptography 2017年12月24日閲覧。
^ ^a ^b ^c ^d Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew et al. (2015-10), Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice 2017年12月24日閲覧。

参考文献

W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol.IT-22, No.6, pp.644-654, Nov, 1976.
カナダの特許1,121,480
TLSにおけるForward Secrecyの利用に関する実証的研究調査 (PDF) シマンテック、2013年（2014年6月12日閲覧）。

外部リンク

RFC 2631: Diffie-Hellman Key Agreement Method
- Diffie-Hellman 鍵共有法（DH 法）

[1] RFC 5114（Additional Diffie-Hellman Groups for Use with IETF Standards、2008年8月）や RFC 7919（Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS)、2016年8月）のように、広く公開されて用いられる (p,q,g) の組も存在する。

[2] Dan, Boneh (1998), “The Decision Diflie-Hellman Problem”, Algorithmic Number Theory. ANTS 1998, LNCS 1423, https://doi.org/10.1007/BFb0054851 2021年12月24日閲覧。

[3] Law, Laurie; Menezes, Alfred; Qu, Minghua; Solinas, Jerry; Vanstone, Scott (August 28, 1998). An Efficient Protocol for Authenticated Key Agreement. Certicom January 19, 2012閲覧。.

[4] Symantec (2013)、pp.13-14。

[5] Symantec (2013)、p.9。

[6] Diffie, Whitfield; Oorschot, Paul C. Van; Wiener, Michael J. (1992-03-06), “Authentication and Authenticated Key Exchanges”, Designs, Codes and Cryptography 2017年12月24日閲覧。

[weakdh-7] Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew et al. (2015-10), Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice 2017年12月24日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

概要