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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

ディフィー・ヘルマン鍵共有(ディフィー・ヘルマンかぎきょうゆう、Diffie-Hellman key exchangeDH)、あるいはディフィー・ヘルマン鍵交換(かぎこうかん)とは、事前の秘密の共有無しに、盗聴の可能性のある通信路を使って、暗号鍵の共有を可能にする暗号プロトコルである。この鍵は、共通鍵暗号方式の鍵として使用可能である。

概要[編集]

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

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

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

プロトコルの内容[編集]

この方式は以下のように行われる。まず値の大きな素数 p を用意する。また g の生成とする。この gp は公開されているものとする[1]

いま X と Y が通信を行うとする。このとき X と Y はお互い秘密の値 a, b を選択する、この値は 0 以上 p-2 以下の中からランダムに選ぶ。(ここで、ゼロや小さな値(ga < p となる a 等)を選択すると安全性が損なわれるが、そのような確率は無視できるほど小さい。)

X は次の値 A を計算してこれを Y に送信する。

Y も同様に B を計算してこれを X に送信する。

X は自身の秘密の値 a と受信した B から以下の値を計算する。

Y も自身の秘密の値 b と受信した A から以下の値を計算する。

このとき X と Y が計算した K は共に

になっているため、以後この値を共通鍵暗号方式の鍵として使用する。

ここで第三者 Z がこの二人の通信を盗聴して AB を入手しても、 から 多項式時間で計算する方法は現在の所、存在しないので Z は鍵 K を生成することが困難である。このため X と Y が安全に通信を行うことが可能になる。

中間者攻撃[編集]

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

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

DNS偽装ARPスプーフィング・その他の手段により攻撃者 Z がこの二人の通信を中継して AB を入手したとする。

このとき Z はそれらに対して秘密の値 cd を選択する。この値は ab と同じ基準で選択される。

Z は c を用いて次の値を計算して Y に送信する。

また d を用いて計算して X に送信する。

Y は自身の秘密の値 b と受信した値から以下の値を計算する。

X は自身の秘密の値 a と受信した値から以下の値を計算する。

Z は自身の秘密の値 cd と受信した AB から以下の値を計算する。

このとき X と Y と Z が計算した K は共に

になっている。

以降の通信で Z はこれらの値を共通鍵暗号方式の鍵として使用して X と Y の通信を中継し、盗聴や改ざんを行う。

公開鍵の選択[編集]

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

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

問題点[編集]

処理負荷[編集]

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

パラメータの設定ミス[編集]

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

弱鍵の存在[編集]

原理上は解読がきわめて困難ではあるが、実装上の問題が存在する場合解読が容易である。実際に暗号化に使う大きな素数の生成過程に弱点があり、同じ素数を使ってしまう弱点があるという論文[5]が発表された。報道によれば数億ドルの専用機を作ると、1年に1つの1024ビットDH暗号が解読できるという[6]。最初の一つの解読で、世界中の2/3のVPNと1/4のSSHが解読できる。次の一つで世界中のトップ100万のHTTPS(セキュリティ)ウェブサイトが解読できるという[7]

筆者等[誰?]は512ビットで実証実験を行った。非輸出用版DHEでも輸出用DHEでも解読できた。2000コアを数時間使う等の準備期間を含んだ数週間の解読開発期間の後は、ワークステーション級のPCを使い平均[8]で70秒で解読できた。
DSAは基本的に安全だが、いくつかのサーバー[9]はある実装上のミスできわめて弱い鍵を持っている。例えばJavaのsun.security.provider 512-bitを使い、実装上のミスをした場合、290ビット分は無効となる。

脚注[編集]

  1. ^ RFC 3526(More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE)、2003年5月)のように、広く公開されて用いられる gp の組も存在する。
  2. ^ Law, Laurie; Menezes, Alfred; Qu, Minghua; Solinas, Jerry; Vanstone, Scott (August 28, 1998). An Efficient Protocol for Authenticated Key Agreement. Certicom. http://download.certicom.com/pdfs/corr98-05.pdf 2012年1月19日閲覧。. 
  3. ^ Symantec (2013)、pp.13-14。
  4. ^ Symantec (2013)、p.9。
  5. ^ Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice ACM Conference on Computer and Communications Security
  6. ^ 筆者等は数百億ドル以上の予算を持つNSAを想定している。
  7. ^ How the NSA broke encryption on trillions of secure connectionsBGR Oct 20, 2015
  8. ^ 正確には中間値。150秒では90%以上。
  9. ^ 彼らは5741個を発見した。

参考文献[編集]

関連項目[編集]