定理(HMQV)の証明 - 暗号理論教室

---

定理(HMQV)の証明

HMQVプロトコルに対する、Canetti-Krawczykモデルにおける、任意のPPT攻撃者をMとおく。

Mが異なるピアが実行するセッションをテストセッションに選択するケース（他者との鍵共有）

Mが、ある異なるA, Bについて、テストセッションとして(A, B, X₀, Y₀)を選択し、そのセッションはセッション鍵

• K = H(v) （v = π(A, B, X₀, Y₀) ）

を出力したとする。v = π(A, B, X₀, Y₀) をテスト署名と呼ぶ。

• Mはセッションを暴露するとき、セッション鍵だけでなく、そのセッションの署名も受け取ると仮定してよい。
  • ※ Mにとってより有利な設定だから。

Hはランダムオラクルなので、MがH(v)を識別し得るのは、以下のいずれかのケースのみ：

• 署名偽造攻撃:
  • ある時点でMはオラクルHに テスト署名π(A, B, X₀, Y₀) を送る。
• 鍵反復攻撃:
  • Mは、テストセッションやそのマッチングセッションとは異なるセッションに、テストセッションと同じセッション鍵Kを生成させる。
  • （その後、そのセッションを暴露する。）

署名偽造攻撃の不可能性

Mを署名偽造攻撃に成功する任意の攻撃者とする。

• テストセッション(A, B, X₀, Y₀)は、その定義より、A内で完了している。
• テストセッションは未暴露でなければならないので、Aは（少なくともテストセッション完了までは）コラプトされていない。

よって、Aは実際にメッセージ(B, A, Y₀)を受け取っている。（ただし、Bがこのメッセージを作ったとは限らない。）

Aが受け取った、テストセッション内のY₀の出自は、以下の4通りのいずれか：

1. Y₀はB（内のある完了セッション）によっては生成されていない。
2. Y₀はB内のマッチングセッション(B,A,Y₀,X₀)によって生成された。
3. Y₀はB内の他者A*とのセッション(B,A*,Y₀,X*)によって生成された。（A*≠A）
4. Y₀はB内のAとの別セッション(B,A,Y₀,X*)によって生成された。（X*≠X₀）

ケース1またはケース2またはケース3が生じる場合

ケース1またはケース2またはケース3が生じる場合、Mを用いて以下のように双対XCR署名の偽造者Fを構成する（Mは各パーティを高々 m 回活性化するとする）:

偽造者F: X₀, Bを入力として、(A, a)を補助入力として、

• パーティP₁, ... , P_nを用意。
• i, j(≠i) ← [1..n], P_j(の公開鍵) = B, t ← [1..m]
  • （※ FはMがA=P_i内のt番目の(B=P_jとの)セッションをテストセッションに選択すると推測）
• B=P_j以外の秘密鍵と公開鍵を生成。ただし、P_iの鍵ペアは (A, a)。
• Mを起動：
  • Mの、B以外のパーティに対する要求は、そのパーティの秘密鍵を用いてオネストに対応する。
  • Mが、パーティBをメッセージ(B, P, X)で活性化したら、
    • (P,B)を署名オラクルBへ問い合わせ、双対XCR署名の一部Yを得て、Yを答える。
  • Mが、パーティB内のセッション(B, P, Y, X)に対し、セッション状態開示クエリまたはセッション出力クエリを発したら、
    • (P,B,Y,X)を署名オラクルBへ問い合わせ、双対XCR署名σを得て、σを答える。
      • ※ このとき、(P,Y) = (A, Y₀)となり、偽造ルールを違反してしまうことが心配。(Experiment ForgeDXCR 参照)
      • ※ ケース１⇒ Y₀はBによって生成されないので、Y=Y₀はネグリジブルな例外を除いてあり得ない。O.K.
      • ※ ケース２⇒ B内のマッチングセッションは本クエリの対象とならないので、Y=Y₀はネグリジブルな例外を除いてあり得ない。O.K.
      • ※ ケース３⇒ Y = Y₀とすると、P = A* ≠ A．O.K.
      • ※ ちなみに、ケース４⇒ X* = Xの可能性があり、(P,Y) = (A, Y₀)となり得る。N.G.
  • Mが、パーティA内の t 番目のセッションを活性化したら、
    • そのセッションのピアがBでないならば、アボートする。
    • else X₀を答える。
  • Mが、テストセッションとして(A,B,X₀,Y₀)を選択し、テスト署名π₀を出力したら、
    • (Y₀,A,B,π₀)を出力して、停止。

[偽造者Fの解析]:

• Fの、Mに対する推測『MがA=P_i内のt番目の(B=P_jとの)セッションをテストセッションに選択する』が当たっているとき、Fによるシミュレーションは完ぺき。
• 推測が当たる確率は 1/(n² m)。

よって、

• Pr[ Fが双対XCR署名の偽造に成功 ] ≧　1/(n² m) ・ Pr[ Mがケース1またはケース2またはケース3で署名偽造攻撃に成功 ].

したがって、Mがケース1またはケース2またはケース3で署名偽造攻撃に成功する確率はネグリジブルである。

ケース4が生じる場合

Mによる署名偽造攻撃において、テストセッション内のAが受け取ったY₀は、B内のAとの別セッション(B,A,Y₀,X*)によって生成された（X*≠X₀）とする。Mを用いて、双対XCR署名の偽造者F'を構成する（Mは各パーティを高々 m 回活性化するとする）。

• セッション(B,A,Y₀,X*)への暴露要求にどう対処するかがポイント。

偽造者F': X₀, Bを入力として、(A, a)を補助入力として、

• パーティP₁, ... , P_nを用意。
• i, j(≠i) ← [1..n], P_j(の公開鍵) = B,
• t, l(≠t) ← [1..m]
  • ※ FはMがA=P_i内のt番目の(B=P_jとの)セッションをテストセッションに選択し、
  • ※　Y₀は、B内のAとのl番目のセッションで生成すると推測。
• B=P_j以外の秘密鍵と公開鍵を生成。ただし、P_iの鍵ペアは (A, a)。
• Mを起動：以下を除いて、偽造者Fと同じように対応。
  • Mが、B内のl番目のセッションを活性化したら、
    • Y₀ ← <g> を返答する。
  • Mが、B内のl番目のセッション(B, A, Y₀, X*)に対し、セッション状態開示クエリまたはセッション出力クエリを発したら、
    • κ ← {0,1}^k を返答する。
      • ※ 偽造ルールに違反するため、このケースだけは、署名オラクルを使うことができない。
• Mが、テストセッションとして(A,B,X₀,Y₀)を選択し、テスト署名π₀を出力したら、
  • β ← {0,1}
    • β =^? 0 : (Y₀,A,B,π₀)を出力して、停止。
    • β =^? 1 :
      • κを返答する直前まで、巻き戻す。
      • v ← {MがオラクルHへ発したクエリー全体}, H(v)を返答する。
      • Mが、テストセッションとして(A,B,X₀,Y₀)を選択し、テスト署名π₀を出力したら、(Y₀,A,B,π₀)を出力して停止。

[偽造者F'の解析]:

• F'の推測i, j, t, lは確率1/(nm)²で当たる。以下、このケースに束縛。
• Mがl番目のセッション(B, A, Y₀, X*)について、その署名π*をオラクルHへ問い合わせないとき：
  • β=0のシミュレーションが完ぺき。
• Mがl番目のセッション(B, A, Y₀, X*)について、その署名π*をオラクルHへ問い合わせるとき：
  • β=1のシミュレーションがv=π*となる確率1/Qで完ぺき。（Q := Hへの問い合わせ総数）
• 以上より、ネグリジブルでない確率でF'はMを完全にシミュレートする。
• よって、双対XCR署名の安全性より、ケース4の偽造もできない。

鍵反復攻撃の不可能性

Mがテストセッションs=(A, B, X₀, Y₀)またはそのマッチングセッション(B, A, Y₀, X₀)とは異なるセッションs'=(A', B', X', Y')にテストセッションと同じセッション鍵を出力させるとする。フォーマルには、Mは出力として、セッションs'=(A', B', X', Y')を出力するとする。

一般性を失わす、

• Mはセッションs'に対してセッション出力クエリを発する （※ Mにとって、より有利な設定）
• π(A, B, X₀, Y₀) = π(A', B', X', Y')　（※ ランダムオラクルHの衝突困難性）

としてよい。

署名偽造攻撃の不可能性の節で構成した、偽造者F,F'が鍵反復攻撃の場合にも以下のように働く。

[ケース1または2または3]

• (X₀, B)を入力として、Fを実行する。
  • Mが（テストセッションの署名の代わりに）セッションIDとしてs'を出力したら、
  • Fの実行中、Mのセッションs'に対するセッション出力クエリに対して答えた署名π'を取り出し、出力する。

π'=πなので、これは双対XCR署名を破っている。

[ケース4]

• (X₀, B)を入力として、Fを実行する。
  • Mが（テストセッションの署名の代わりに）セッションIDとしてs'を出力したら、
    • s' = (B,A,Y₀,X*) ならばアボート。（※このセッションに対してだけは、F'は署名をちゃんと作っていない）
    • else Fの実行中、Mのセッションs'に対するセッション出力クエリに対して答えた署名π'を取り出し、出力する。

s' = (B,A,Y₀,X*)ならば、X≠X*より、ネグリジブルな例外を除いてπ(s') ≠ π(s)。
よって、アボートの確率はネグリジブルなので、ケース4でも双対XCR署名を破っている。

以上より、Mが鍵反復攻撃に成功する確率もネグリジブルである。

Mが同じピアが実行するセッションをテストセッションに選択するケース（自身との鍵共有、反射攻撃）

攻撃者Mがテストセッションとして同じピアBが実行するセッション(B, B, X₀, Y₀) を選択したとする。

• 双対XCR署名への帰着、すなわち偽造者Fの構成は同じ。
• ただし、先の定義では、双対XCR署名の安全性はB≠Aの場合のみ意味を持つので、その安全性を同一パーティBによる双対XCR署名DXCR(B,B,X₀,Y₀)に拡張することが必要。
  • A(=B)の秘密鍵が使えない点がB≠Aの場合と異なるところ。
  • しかし、署名対象メッセージは(B,B)と予めわかっている。

以下、DXCR(B,B,X₀,Y₀)を出力する偽造者Fを用いて、計算DH問題アルゴリズムCが構成できることをみる。

X₀ ≠ Y₀ のケース

アルゴリズムC: U=g^u, V=g^vを入力として、

• d₀ ← {0,1}^l
• B = V, X₀ = U/B^d0, G[X₀,B] = d₀.　（※ x₀ = u - bd₀ ）
• (B, X₀)を入力として、Fを起動する：
  • FがオラクルGへ問い合わせ(Y,m)を発したら、
    • G[Y,m]が未定義なら、e ← {0,1}^l, G[Y,m]=e
    • G[Y,m]を返答する。
  • Fが署名オラクルBへ問い合わせ (m,m') を発したら、
    • s ← Z_q, e ← {0,1}^l, Y = g^s / B^e
    • G[Y,m] = e とする。（ただし、G[Y,m]がすでに定義されていたらアボート。）
    • Yを返答し、FよりXを受け取って、d = G(X,m')についてσ = X^s B^sdを返す。
    • （※ (Y B^G(Y,m))^{x + db} = (Y B^e)^x+db = (g^s)^x+db = σ ）
• Fの出力を(Y₀, B, B, σ₀)とする。
  • （※ (Y₀, B)は、署名オラクルのシミュレーション時にCによって用いられておらず、かつFによりオラクルGへすでに問い合わされているとしてよい。）
• B, X₀を入力として、Fをもう一度起動する、ただし、
  • Fが(Y₀, B)をオラクルGへ問い合わせるまでは、先のFの実行と同一のランダムテープを用いて全く同様に処理する。
  • Fが(Y₀, B)をはじめてオラクルGへ問い合わせたら、以降、新しいランダムテープに切り替えて、
    • e' ← {0,1}^l, G[Y₀,B] = e' を返答する。
  • 後は新しいランダムテープを用いて先のFの実行と全く同様に処理する。
• Fの2回目の出力を(Y₀, B, B, σ₀')とする。
• e ≠ e' ならば、(σ₀ / σ'₀)^1/(e-e') を返す。ただし、

[アルゴリズムCの解析]:

• Fがネグリジブルでない成功確率をもつならば、2回とも偽造に成功する確率はネグリジブルでない。このとき、
  • (Y₀ B^e)^{(u-bd₀)+bd₀} = σ₀
  • (Y₀ B^e')^{(u-bd₀)+bd₀} = σ₀'
• これより、
  • B^u = (σ₀ / σ'₀)^1/(e-e').

X₀ = Y₀ のケース

• 上のCによる巻き戻しはうまくいかない。（d₀まで変わると困る。）
• しかし、このケースでは、セッション(B, B, X₀, X₀)はクリーン。すなわち、攻撃者Mはこのセッションを観察しているだけ。
• 以下のように、Mを用いてダイレクトに計算DHアルゴリズムを構成できる。

アルゴリズムC: U=g^uを入力として、

• g ← テストセッションを推測, b ← Z_q, B = g^b
• Mを起動。
  • Mがセッションgについて第1メッセージを要求したら、
    • (B, B, U)を返す。
  • Mがセッションgについて第2メッセージを要求したら、
    • (B, B, U)を返す。
• Mがセッションg=(B,B,U,U)の署名σ=g^(u+db)2を出力したら、（d=G(U,B))
  • σU^-2dbg^-(db)2 を返す。
  • ※ σ = g^{u2 + 2udb + (db)2} = g^u2 U^2db g^(db)2.

Q.E.D.
上へ

---