情報セキュリティ 第 13 回 2011 年 7 月 15 日 ( 金 ) 1/31
本日学ぶこと 暗号プロトコル プロトコルの諸概念 鍵配布プロトコル ( およびその攻撃 ) Diffie-Hellman 鍵交換 ( およびその攻撃 ) ゼロ知識対話証明,Feige-Fiat-Shamir 認証プロトコル 2
プロトコルとは (1) 2 者以上の参加者が関係し, ある課題を達成するための一連の手順のこと. 一連の手順 ( シーケンス ) 前のステップが終わっていないのに次のステップを始めてはならない. 2 者以上の参加者が関係 ケーキを焼く はプロトコルではないが, だれかに食べてもらう まで含めればプロトコルになる. ある課題を達成 これがなければ時間の無駄 参考 : 暗号技術大全 (Bruce Schneier 著, 山形浩生監訳 )p.23 3
プロトコルとは (2) アルゴリズムも, 複数の計算機で実行するなら プロトコル と言える 分散コンピューティング 暗号化した通信に限らず, 暗号技術 ( 素因数分解問題や離散対数問題の困難性なども ) を用いた通信の手順を 暗号プロトコル という. ハッシュ値の照合や, ディジタル署名も, 暗号プロトコルになり得る. PKIにおける鍵の入手,SSL/TLSやSSHのハンドシェイクプロトコルも該当する. 4
プロトコルの設計 実行 適切なプロトコルは, デッドロックなどの通信上の障害を起こさない. 双方が相手の受信待ち状態になってはいけない! 安全な暗号プロトコルは, 悪意のある送信を何らかの方法で検出する. 適切な情報を持たない者を誤って認証してはいけない! 5
暗号プロトコルの具体例 鍵配布センターを利用したセッション鍵共有 Diffie-Hellman 鍵交換 Feige-Fiat-Shamir の認証プロトコル 6
対称暗号をどう使う?( 復習 ) 仮定 : 使用する対称暗号は安全 ( 解読できない ) 対称暗号は, 暗号化の鍵 = 復号の鍵 鍵はいくつ必要? n 人ならそれぞれ n-1 個, 全体で n(n-1)/2 個 7
鍵配布センター 鍵配布センターを設置し, 各利用者は, ここと鍵を共有する. 鍵の数は,n 人ならそれぞれ 1 個, 全体で n 個 鍵配布センターは, 不正や鍵の漏洩などをしないものとする. 信頼される第三者 (Trusted Third Party) である. 利用者の中には, 他人の秘密情報を知りたい 悪者 がいるかもしれない. 利用者間の通信には, その場限りの鍵 ( セッション鍵 ) を生成して使ってもらう. セッション鍵は, 乱数を用いて生成し, 各利用者の鍵や, これまで生成したセッション鍵に依存しないものにする. でも, どうすればセッション鍵を当事者間 ( のみ ) で共有できる? 8
準備 (1): 実行環境 k(a) k(b) k(m) 鍵配布センター Trent k(a) Alice Bob k(b) Mallory k(m) 悪者 9
準備 (2): 暗号化と復号の記法 鍵 y 平文 x 暗号化 暗号文 e(y,x) 暗号文 e(y,x) 鍵 y 復号 平文 x 10
セッション鍵の配布案 Trent (i) a, b (ii) e(k(a),r) (iii) e(k(b),r) Alice (iv) e(r,c) Bob r: セッション鍵 ( 実行のたびに値が変わる ) c:alice が Bob に送りたい内容 暗号技術入門 秘密の国のアリス pp.109-110 11
配布案は安全か? 目標 :Mallory が,Alice になりすまして Bob と通信できるための情報 ( セッション鍵 r) を獲得すること Alice に扮する Mallory r r Bob 12
中間者攻撃 カレーライスください ハヤシライスお願いします 客 ( 悪意ある ) ウエイター 料理人 カレーライスどうぞ ハヤシライスできたよ Mallory がこの方法で盗聴とメッセージの改竄が行えるなら, 目標を達成できてしまう. 13
配布案に対する中間者攻撃 Trent (iii) e(k(m),r1) (iv) e(k(a),r1) (ii) m, a M (vi) m, b M (vii) e(k(m),r2) (viii) e(k(b),r2) (i) a, b (v) e(k(a),r1) (ix) e(k(b),r2) Alice (x) e(r1,c) M (xi) e(r2,c) Bob セッション鍵 r1 は,Alice と Mallory が共有する. セッション鍵 r2 は,Bob と Mallory が共有する. 14
Diffie-Hellman 鍵交換 Diffie と Hellman が 1976 年に考案した, 二者間で秘密の数値を共有するプロトコル RSA 暗号アルゴリズムの発表 (1978 年 ) よりも早い 鍵交換 と書かれるが, 鍵そのものは交換しない. 鍵の手掛かりとなる情報を交換することで, 鍵 ( 秘密の数値 ) を求めている. 頭文字をとって DH, DH 方式 などとも呼ばれる. 15
Diffie-Hellman 鍵交換の処理と通信 Alice g a % p Bob g b % p 公開値の計算 公開値の交換 公開値の計算 乱数 a 乱数 b 共有鍵の計算 共有鍵の計算 g ab % p 共有する値 g ab % p 新版暗号技術入門 秘密の国のアリス p.281 を改変 16
Diffie-Hellman 鍵交換の数学的背景 公開情報 : 素数 p, 生成元 g Aliceが秘密に持つ情報 :a Bobが秘密に持つ情報 :b Alice Bob:g a % p Bob Alice:g b % p Aliceの鍵生成 :(g b % p) a % p = g ab % p Bobの鍵生成 :(g a % p) b % p = g ab % p gはpに依存する. gは必ずしも素数ではない. Alice と Bob の処理は, 乱数生成 べき剰余のみなので, 高速 p,g,g a % p,g b % p を盗聴しても, そこから a や b を効率よく得ることはできないので, 安全であると言える. 17
離散対数問題 ( 一部復習 ) 入力 : 素数 p, 生成元 g, 正整数 y 出力 : y = g z % p を満たす整数 z ( ただし 1 z<p) 総当り法で解を見つけるのは, 多項式時間アルゴリズムではない. z=1,2,... と解の候補を試すと, 解が出るまでのべき剰余計算回数の期待値は, おおよそ p/2. すなわち p に比例する. 離散対数問題の入力サイズは,p のビット長 p log 2 p によって決まる. よって, 時間計算量は O(p) = O(2 p ) であり, 多項式時間ではない. g が p の生成元である の必要十分条件 g % p,g 2 % p,,g p-2 % p がどれも異なる. g % p,g 2 % p,,g p-2 % p がいずれも 1 ではない. p-1 の素因数であるすべて q に対して,g (p-1)/q % p 1 18
ここでも中間者攻撃 カレーライスください ハヤシライスお願いします 客 ( 悪意ある ) ウエイター 料理人 カレーライスどうぞ ハヤシライスできたよ Diffie-Hellman 鍵交換は中間者攻撃に対する脆弱性を有する 19
Diffie-Hellman 鍵交換に中間者攻撃を適用すると (1) Alice Mallory Bob g a % p 公開値の交換 g m % p 公開値の交換 g b % p 公開値の計算 公開値の計算 公開値の計算 乱数 a 乱数 m 乱数 b 共有鍵の計算 共有鍵の計算 共有鍵の計算 g am % p 共有 g am % p g bm % p 共有 g bm % p 20
Diffie-Hellman 鍵交換に中間者攻撃を適用すると (2) 公開情報 : 素数 p, 生成元 g Alice,Bob,Malloryが秘密に持つ情報 :a, b, m [Alice] g a % p [Mallory] g m % p [Bob] [Bob] g b % p [Mallory] g m % p [Alice] Aliceの鍵生成 :(g m % p) a % p = g am % p Bobの鍵生成 :(g m % p) b % p = g bm % p Malloryの鍵生成 1:(g a % p) m % p = g am % p Malloryの鍵生成 2:(g b % p) m % p = g bm % p 21
Diffie-Hellman 鍵交換に中間者攻撃を適用すると (3) Alice と Mallory は g am % p を共有し, Bob と Mallory は g bm % p を共有する. Alice と Bob の間では情報を共有していないが, Alice は,Bob と g am % p を共有していると思っている. Alice が,g am % p を鍵として暗号文を作り,Bob に送ったら, Mallory はそれを受け取って g am % p で復号し, g bm % p で暗号化したものを Bob に渡す. Alice と Bob の間で秘密にしたい通信内容が,Mallory にも知れてしまう! α E(g am %p,α) E(g bm %p,α) α Alice Mallory Bob α 22
Diffie-Hellman 鍵交換の補足 実用化されている Diffie-Hellman 鍵交換に基づく情報共有法 では, 中間者攻撃の問題に対応している. 23
Feige-Fiat-Shamir の認証プロトコル FFS 方式 Fiat-Shamir 方式 などとも呼ばれる 秘密の情報を持っていれば, プロトコルの実行により間違いなく認証者はそれを確認できる. 秘密の情報は認証者にも知られない ゼロ知識対話証明 (Zero-Knowledge Interactive Proof,ZKIP) 秘密の情報を持っていない者が, なりすましてプロトコルを実行しても, 成功する確率はせいぜい 1/2 繰り返し実行すると, 成功率は指数的に小さくなる. 処理速度は RSA よりも非常に速い. Prover ( 証明者 ) ユーザ情報を入力 OK/NG Verifier ( 認証者 ) 24
FFS プロトコルの前提 事前に生成しておく情報 2 つの大きな素数 p,q を非公開とし,n pq を公開 証明者は整数 s (1 s<n) を秘密情報として持つ 整数 v s 2 % n も公開する 計算の困難さ 素因数分解は困難 大きな整数 m と整数 a (1 a<m) が与えられたときに, b 2 % m = a を満たす b (m を法とする a の平方根 ) を求めるのは m が素数ならば容易 ( 効率のよいアルゴリズムが存在する ) m が合成数ならば容易ではない 25
FFS プロトコル ( 図 ) n, s n, v(=s 2 ) 証明者 x r 2 % n 認証者 r をランダムに選ぶ e {0,1} e をランダムに選ぶ y を計算する y r s e % n y 2 = x v e? 26
FFS プロトコル ( 記述 ) Step 1: 証明者は乱数 r を生成し,x r 2 % nを計算して,x を認証者に送る. Step 2: 認証者は e {0,1} をランダムに選び, 証明者に送る. Step 3: 証明者は y r s e % n を計算して認証者に送る. e=0 y r % n e=1 y rs % n Step 4: 認証者は y 2 % n = x v e % n が成り立つか確かめ, 成り立たなければ認証しない. e=0 y 2 % n = r 2 % n? e=1 y 2 % n = r 2 s 2 % n = (r 2 % n)(s 2 % n) % n? 成り立てば, 認証者が納得いくまで Step1~4 を行う. 27
なぜ FFS プロトコルでうまくいく? 攻撃者の目標 : 整数 s を持たないが, 証明者になりすまして認証者から認証されること 攻撃者があらかじめ x と y の組を生成しておけば? y をランダムに生成してから,x y v -1 % n を作ると, e=1 のときは成功するが, e=0 のときは失敗する (n を法とする x の平方根は求められない ). 攻撃者が過去に盗聴した情報を送れば ( リプレイ攻撃 )? 以前の通信と e が異なっていれば失敗する. すべての (x,e,y) を保存するのが現実的に難しくなるよう, p,q の大きさを決めればよい. 28
暗号プロトコルの安全性 暗号プロトコルを形式的に記述し, その枠組みのもとで安全性を検証すること ( 形式的手法 ) が広く研究されてきた. 暗号プロトコルの仕様 形式的記述論理モデル項書換え系オートマトンなど 安全である 安全でない ある枠組みのもとで, 安全性が証明可能な (provably secure) 暗号プロトコルを設計するという研究もある. 29
暗号プロトコル : おわりに 基礎となる暗号技術が安全であっても, それを用いた暗号プロトコルが安全であるとは限らない. 暗号プロトコルに限らず, 多数の人が関わるシステムを設計するときは 実行環境には誰がいて, それぞれ何ができて何ができず, 何をしたいかを明確にする. うまくいく 根拠を明確にする. 悪意のある者や何らかのトラブルも考慮に入れ, それでも安全な環境を維持できるようにする. 30
本日のまとめアンケート 本日の授業の中で, 印象に残った言葉を 3 つ選び, メモに記入して提出しなさい. 31E