鍵共有プロトコル


鍵共有プロトコルとは?

鍵共有プロトコルとは、セッション鍵を共有するための2者間プロトコルである。

鍵共有プロトコルを実行する、2者 P1 と P2 は、

いくつかのメッセージを交換し、それら交換したメッセージをもとにそれぞれが計算を行い、ある同じビット列 k を出力する。
この共有したビット列 k をセッション鍵と呼ぶ。

セッション鍵 k を用いて、その後の P1 と P2 間の
  • 通信内容を秘匿したり(k を鍵としてブロック暗号+暗号利用モード)、
  • 通信内容を認証したりする(k を鍵としてMACを生成・検証)。

もちろん、鍵共有プロトコルには

秘匿性:

鍵共有プロトコルを実行する、2者P1 と P2 のやり取りするメッセージをすべて敵 A が覗き見しても、敵 A にはセッション鍵 k のどのような部分情報も得られない。
が必要である。



公開鍵暗号ベースの鍵共有プロトコル EB

公開鍵暗号 (G, E, D) を利用して、鍵共有プロトコル EB をつくることができる。

鍵共有プロトコル EB:

  1.   P2 は、鍵生成アルゴリズムGを実行して鍵ペア (e,d) ← G(n) を生成し、公開鍵 e のみを P1 に送る。
  2.  P1 は、ランダムな n ビットのビット列 k を生成し、それを鍵 e で暗号化して暗号文 c ← Ee(k) を作り、P2 に送る。 k を出力する。
  3.  P2 は、暗号文 c を復号して k ← Dd(c)を得て出力する。


敵 A が P1、P2間のメッセージ e と c を覗いても、公開鍵暗号の安全性より( c に暗号化されている)セッション鍵 k は分からない。

ただし、セッション鍵 k のどのような部分情報も敵 A に漏れないよう、強秘匿な公開鍵暗号を用いる。



RSA-PKCS #1 と Bleichenbacher 攻撃

RSA暗号に強秘匿性をもたせるために、SSL では RSA-PKCS #1 を用いている。
SSLの実装の仕方によっては、Bleichenbacher 攻撃が成り立つ。

blankimgプラグインエラー:ご指定のファイルがありません。アップロード済みのファイルを指定してください。
blankimgプラグインエラー:ご指定のファイルがありません。アップロード済みのファイルを指定してください。
blankimgプラグインエラー:ご指定のファイルがありません。アップロード済みのファイルを指定してください。

blankimgプラグインエラー:ご指定のファイルがありません。アップロード済みのファイルを指定してください。
blankimgプラグインエラー:ご指定のファイルがありません。アップロード済みのファイルを指定してください。






ディフィー・ヘルマン鍵共有プロトコル DH

p を十分大きな素数とし、g を、p を法とする位数が素数 q である整数(すなわち、g は q 乗すると初めてpを法として1となる)とする。


鍵共有プロトコル DH:

  1.  P1 は、1 以上 q 以下の乱数 x を選び、g の x 乗である X = gx mod p を計算し、P2 に送る。
  2.  P2 は、1 以上 q 以下の乱数 yを選び、g の y 乗である Y = gy mod p を計算し、P1 に送る。
  3.  P1 は、k = Yx mod p を計算し、出力する。
  4.  P2 は、k = Xy mod p を計算し、出力する。

ここで、
  • Yx = gxy = Xy
より、P1 と P2 は確かに同じ k を出力する。


数値例:
  • <p = 43, q = 7, g = 4>
g0 mod p = 1, g1 mod p = 4, g2 mod p = 16,
g3 mod p = 21, g4 mod p = 41, g5 mod p = 35,
g6 mod p = 11.

鍵共有プロトコル DH の実行例:

  1.  P1 は、1 以上 q=7 以下の乱数 x=3 を選び、g=4 の x=3 乗である X = 43 mod 43 = 21 を計算し、P2 に送る。
  2.  P2 は、1 以上 q=7 以下の乱数 y=5を選び、g=4 の y=5 乗である Y = 45 mod 43 = 35を計算し、P1 に送る。
  3.  P1 は、k = 353 mod 43 = 4 を計算し、出力する。
  4.  P2 は、k = 215 mod 43 = 4 を計算し、出力する。

  • 353 = (45)3 = (43)5 = 215 (mod 43).


ディフィー・ヘルマン鍵共有の秘匿性については、数論的な仮定が必要:

離散対数仮定:

1 以上 q 以下の範囲からランダムに a を選ぶとき、どのような効率的なアルゴリズムも、p, g, q, ga を与えられても、a は計算できない。

  • <p = 43, q = 7, g = 4>
4x mod 43 = 35 となる x は?


計算DH仮定:

1 以上 q 以下の範囲からランダムに a, b を選ぶとき、どのような効率的なアルゴリズムも、p, g, q および ga と gb を与えられても、gab は計算できない。

  • <p = 43, q = 7, g = 4>
43 mod 43 = 21, 45 mod 43 = 35  → 415 mod 43 = ?


判定DH仮定:

1 以上 q 以下の範囲からランダムに a, b, c を選ぶとき、どのような効率的なアルゴリズムも、p, g, q および ga と gb を与えられて、gab と gc を区別(することすら)できない。

  • <p = 43, q = 7, g = 4>
(21, 35, 4) OR (21, 35, 11) どちらが正しい?



判定DH 仮定のもとで、ディフィー・ヘルマン鍵共有(鍵共有プロトコル DH) は秘匿性を満たす。


他に、離散対数ベースの暗号技術として、エルガマル暗号シュノア署名が有名。





コンカレントな環境における鍵共有プロトコル

鍵共有プロトコルは、他のプロトコルやシステム(「親プロトコル」)で部品として用いられる。

親プロトコルは、同時に多数の鍵共有プロトコルを部品として実行することも珍しくない。このとき、敵はただメッセージを覗き見るだけとは限らず、
  • 同時に実行されている、ある鍵共有プロトコルの参加者として潜んでいたり、
  • すでに終了した過去の鍵共有プロトコルの、セッション鍵を入手していたり
することもある。(不注意な親プロトコルが使用済みのセッション鍵をばらしてしまうなど)。

このような、同時に複数の鍵共有プロトコルが実行されているような環境(コンカレントな環境)で、鍵共有プロトコルの秘匿性を考え直す必要がある。



コンカレントな環境における秘匿性:

コンカレントな実行環境、すなわち、
[設定]
  1.  鍵共有プロトコルは、同時に複数のコピーが(いくらかの文脈を共有した状態で)実行される、
  2.  しかも、敵 A 自身もそれらの任意の鍵共有プロトコルの実行に(正当な参加者としてあるいは誰かに成りすまして)参加できる、
  3.  さらに、敵 A はすでに終了した過去の任意の鍵共有プロトコルを選択し、そのセッション鍵を入手できる
環境において、
[条件]
  1.  鍵共有プロトコルの実行において、P1 と P2 さえ正しく正直に振舞えば、(陰日向で敵 A がどのように振舞おうとも)P1 と P2 の間で正しくセッション鍵が共有され、かつ
  2.  (敵 A の参加していない)鍵共有プロトコル実行の全てのメッセージを敵 A が覗き見しても、(設定 3 の手段を用いてセッション鍵を入手しない限り)敵 A にはセッション鍵 k のどのような部分情報もわからない、
を満たすとき、その鍵共有プロトコルは、コンカレントな環境において秘匿性をもつという。




プロトコル DH に対する中間者攻撃

鍵共有プロトコル DH はコンカレントな環境において秘匿性をもたない。実際、コンカレントな環境では、以下のような中間者攻撃が成立する。


  1.   P1 は正直に X (= gx) を計算し、P2 になりすました攻撃者 M に送る。
  2.  攻撃者 M は X' (= gx') を自身で計算し、P1 になりすまして P2 に送る。
  3.  P2 は正直に Y ( = gy) を計算し、P1 になりすました攻撃者 M に送る。
  4.  攻撃者 M は Y' ( = gy') を自身で計算し、P2 になりすまして P1 に送る。

以上の実行は、P1 と P2 の視点からは全く正常に見えている。ところが、
  • P1 は k1 = gx y' を、
  • P2 は k2 = gx' y を出力し、
この k1, k2 は異なるので、コンカレントな環境における秘匿性の条件1が破られている。さらに悪いことに攻撃者 M は上の k1 も k2 も知っている。





プロトコル EB に対する再送攻撃

鍵共有プロトコル EB もコンカレントな環境において秘匿性をもたない。実際、コンカレントな環境においては、以下のような再送攻撃が成立する。

ここでは、プロトコル EB において、P1 は予め P2 の公開鍵 e を入手しているとする。(したがって、プロトコル EB で送受信されるメッセージは、P1 から P2 へ送られる暗号文 c のみ。)


  1.  P1 と P2 は正直にプロトコル EBを実行する。このとき、P1 から P2 へ送られる暗号文 c を敵 R が入手する。
  2.  敵 R は、正当な送信者として、P2 との間でプロトコル EBを実行する。ただしこの際、上で入手した暗号文 c を P2 へ送る。
  3.  2 の R と P2 によるプロトコル EBの実行に対し、敵 R は設定3の手段を用いてそのセッション鍵 k を入手する。( k は c の復号文。)
  4.  敵 R は 1 で P1 と P2 が得たセッション鍵は k であることを知る。

つまり、敵 R は、覗き見したメッセージを自分自身のメッセージとして再送することで、コンカレントな環境における秘匿性の条件2を破ったわけである。





鍵共有プロトコルの強化

鍵共有プロトコルをコンカレントな環境に耐えられるよう、強化する。強化の方針は、以下の通り。

  • プロトコルの各メッセージにセッション識別子を含める。
プロトコル一つ一つの実行をセッションと呼ぶ。複数セッションに属するメッセージが混じってしまわないよう、各メッセージにセッション識別子を含める。

  • プロトコルの各メッセージに送信者識別子を含める。
異なる送信者が生成したメッセージが混じってしまわないよう、各メッセージに送信者識別子を含める。

  • プロトコルの各メッセージの送信に認証メカニズムを組み込む。
デジタル署名やMACを用いて、各メッセージの送信にチャレンジレスポンスに基づく認証メカニズムを組み込む。これにより、なりすましやメッセージの改ざんを防ぐ。




鍵共有プロトコル DH-SIG

記号:
  • 各パーティはデジタル署名使用できるものとし、パーティ Pi のメッセージ m に対する署名文を SIGi(m) で表す。
  • 各パーティ Piの識別子を(記号を節約して)Pi と書く。
  • セッション識別子を s とする。ここでは、セッション識別子 s は親プロトコルから与えられると考える。


鍵共有プロトコル DH-SIG:

  1.  P1 は、1 以上 q 以下の乱数 x を選び、g の x 乗である X = gx mod p を計算し、(P1,s,X) を P2 に送る。
  2.  P2 は、1 以上 q 以下の乱数 yを選び、g の y 乗である Y = gy mod p を計算し、(P2,s,Y,SIG2(P2,s,Y,X,P1)) を P1 に送る。
  3.  P1 は、署名文 SIG2(P2,s,Y,X,P1) の正しさを確認する。(もし正しくなければプロトコル実行を拒否。) さらに、(P1,s,SIG1(P1,s,X,Y,P2)) を P2 に送ると同時に、 k = Yx を計算し、 (s, k) を出力する。
  4.  P2 は、署名文 SIG1(P1,s,X,Y,P2) の正しさを確認する。(もし正しくなければプロトコル実行を拒否。) さらに、 k = Xy を計算し、(s, k) を出力する。



鍵共有プロトコル DH-SIG には、プロトコル SIGに通用した、中間者攻撃は成立しない。
プロトコル DH-SIG では、
  • メッセージが(ランダムチャレンジに対応する)署名文で守られている
おかげで、
  • 敵 M が P1 や P2 になりすましてメッセージを送ることができない
ためである。

例えば署名文 SIG2(P2,s,Y,X,P1) には送信者と受信者の識別子が含まれていることに注意する。






鍵共有プロトコル EB-SIG

部品としてディジタル署名のほかに、疑似ランダム関数 fκ(・) を用いる。擬似ランダム関数とは、
  • 鍵κを知らなければ、入力値-出力値ペアをいくつ見ても、ランダム関数と区別がつかない関数
をいう。


鍵共有プロトコル EB-SIG:

1.  P2 は、ランダムな n ビット列 N を生成し、メッセージ (P2, s, N) を P1 に送る。

2.  P1 は、ランダムな n ビット列 κ を生成し、鍵 e で暗号化して暗号文 c ← Ee(κ) を作り、メッセージ
  • (P1, s, c, SIG1(P1, s, c, N, P2))
を P2 に送るとともに、
  • k = fκ(P1,P2,s)
を出力する。

3.  P2 は、署名 SIG1 の正しさを確認し(正しくなければプロトコル実行を拒否。)、c を復号して κ← Dd(c) を得て、
  • k = fκ(P1,P2,s)
を出力する。



鍵共有プロトコル EB-SIG には、プロトコル EB に通用した再送攻撃は成立しない。

  • 敵 R が先と全く同じようにメッセージ (P1, s, c, SIG1)をまるごと再送しても、新しいランダムチャレンジ N に対応していないので署名が妥当でなくなる。

  • 敵R が 暗号文 c だけ再利用し、署名文は新しいランダムチャレンジ N に対応して自身で再計算して添付しても、セッション鍵 k = fκ(P1,P2,s)は、新しいセッション識別子 s (その他)にリンクしているので、元の値とは独立なランダムな値になる。























最終更新:2010年06月03日 13:14