Q q 情報セキュリティ 第7回:2007年6月1日(金) q q.

Slides:



Advertisements
Similar presentations
情報セキュリティ 第9回 ハッシュ関数. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをす る) 否認 (後から私じゃないと言 う) 共通鍵暗号 公開鍵暗号.
Advertisements

情報セキュリティ 第3回 現代暗号の基礎数理. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号.
効率的に計算可能な 加法的誤りの訂正可能性 安永 憲司 九州先端科学技術研究所 SITA 2012 @ 別府湾ロイヤルホテル
情報セキュリティ 第12回 公開鍵暗号基盤. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをす る) 否認 (後から私じゃないと言 う) 共通鍵暗号 公開鍵暗号.
電子社会設計論 第12回 Electronic social design theory 中 貴俊.
0章 数学基礎.
メール暗号化:秘密鍵・公開鍵の作成  作業手順 Windows メール(Vista).
駒澤大学 経営学部 情報セキュリティ B 公開鍵暗号による 認証つきの秘匿通信 ―― 鍵に注目して ――
情報工学科 06A2055 平塚 翔太 Hiratsuka Shota
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
IaaS 仮想マシン(VM)をネットワーク経由で提供 負荷に応じてVM数や性能を変更できる ハードウェアの導入・管理・維持コストの削減
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
黒澤 馨 (茨城大学) 情報セキュリティ特論(6) 黒澤 馨 (茨城大学) 2017/3/13 confidential.
「コンピュータと情報システム」 07章 インターネットとセキュリティ
「まめだくん Ver.1.0」 特徴と利用方法.
第2章 第1節 情報通信の仕組み 4 暗号技術と情報の保護 5 コンピュータとネットワークの管理
Q q 情報セキュリティ 第3回:2007年4月27日(金) q q.
数 学 の か た ち 第3講 暗号を作ろう 早苗 雅史 数学とソフトウエア
黒澤 馨 (茨城大学) 情報セキュリティ特論(7) 黒澤 馨 (茨城大学)
暗号技術 ~公開鍵暗号方式の仕組み~ (3週目)
第8章 Web技術とセキュリティ   岡本 好未.
第10回 情報セキュリティ 伊藤 高廣 計算機リテラシーM 第10回 情報セキュリティ 伊藤 高廣
黒澤 馨 (茨城大学) 情報セキュリティ特論(5) 黒澤 馨 (茨城大学)
Q q 情報セキュリティ 第3回:2005年4月28日(金) q q.
Q q 情報セキュリティ 第3回:2005年4月22日(金) q q.
数学のかたち 暗号を作ろう Masashi Sanae.
Q q 情報セキュリティ 第5回:2005年5月13日(金) q q.
Q q 情報セキュリティ 第14回:2005年7月15日(金) q q.
Q q 情報セキュリティ 第8回:2006年6月9日(金) q q.
Q q 情報セキュリティ 第4回:2007年5月11日(金) q q.
共通暗号方式 共通のキーで暗号化/復号化する方法 例) パスワードつきのZIPを送信して、後からパスワードを送る方法 A さん B さん
情報セキュリティ  第4回 メッセージ認証コード.
第二章 インターネットで やり取りする情報を守る
PGP インターネットで 広く使われている暗号技術
実用的暗号通信ソフトウェア 「まめだくん」の開発 Shiota Laboratory
情報セキュリティ  第11回 デジタル署名.
Linux リテラシ 2006 第5回 SSH と SCP CIS RAT.
情報セキュリティ  第8回 RSA暗号.
2章 暗号技術 FM15002 友池 絲子.
武藤研究室セキュリティー藩暗号犯メンバー 環境情報学部4年 櫻井 環境情報学部3年 秋本 環境情報学部3年 堀田 環境情報学部2年 卯野木
Q q 情報セキュリティ 第11回:2004年6月18日(金) q q.
5.RSA暗号 素因数分解の困難性を利用した暗号.
Q q 情報セキュリティ 第8回:2005年6月3日(金) q q.
Q q 情報セキュリティ 第7回:2006年6月2日(金) q q.
暗号技術 ~暗号技術の基本原理~ (1週目) 情報工学科  04A1004 石川 真悟.
Q q 情報セキュリティ 第6回:2007年5月25日(金) q q.
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
Q q 情報セキュリティ 第4回:2005年5月12日(金) q q.
コミュニケーションと ネットワークを探索する
Q q 情報セキュリティ 第9回:2006年6月16日(金) q q.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
「情報セキュリティ論」 2-4 公開鍵暗号の原理とRSA暗号
Q q 情報セキュリティ 第9回:2007年6月15日(金) q q.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号,量子コンピュータ
Q q 情報セキュリティ 第5回:2006年5月19日(金) q q.
Q q 情報セキュリティ 第12回:2004年6月25日(金) の補足 q q.
Q q 情報セキュリティ 2006年6月30日(金) 第2回レポート課題の解説 q q.
ネット時代のセキュリティ3(暗号化) 2SK 情報機器工学.
黒澤 馨 (茨城大学) 情報セキュリティ特論(8) 黒澤 馨 (茨城大学)
Q q 情報セキュリティ 第6回:2005年5月26日(金) q q.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
暗号技術・セキュリティ 情報工学科  04A1004 石川 真悟.
電子投票班 (電子オークション班) 後藤研究室 大木島 航.
データの改竄を防ぐ仕組み 2002/9/12 牧之内研究室「インターネット実習」Webページ
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
情報処理Ⅱ 2005年11月25日(金).
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
CSS符号を用いた量子鍵配送の安全性についての解析
2012年度 情報数理 ~ ハミング距離 ~.
Presentation transcript:

q q 情報セキュリティ 第7回:2007年6月1日(金) q q

本日学ぶこと メッセージ認証 一方向ハッシュ関数,メッセージ認証コード,ディジタル署名は改竄を検出できる. ディジタル署名(デジタル署名) いずれも,完全性に関する技術 一方向ハッシュ関数,メッセージ認証コード,ディジタル署名は改竄を検出できる. メッセージ認証コードは,鍵を共有する当事者間で(のみ) メッセージの完全性を検証できる. ディジタル署名は第三者による検証ができる.

なりすまし・偽造(復習) 送信 受信 敵 完全性を脅かす なりすましにはユーザ認証,偽造にはメッセージ認証

改ざん(復習) 送信 受信 敵 完全性を脅かす man-in-the-middle攻撃,中間者攻撃ともいう

リプレイ攻撃(復習) 送信 受信 敵 完全性を脅かす

機密性・完全性と暗号技術 完全性 (正真性) 機密性 アルゴリズム秘匿 による暗号 鍵なし 一方向ハッシュ関数 共通鍵 対称暗号 メッセージ認証コード 非対称鍵 公開鍵暗号 ディジタル署名

一方向ハッシュ関数(one-way hash function)とは メッセージからハッシュ値と呼ばれる情報を作る操作・関数 メッセージとそのハッシュ値が与えられれば,そのいずれかが改ざんされていないことを確認できる. ハッシュ値について 指紋(fingerprint),サマリ(summary)などとも呼ばれる. 一般に,関数ごとに固定長で,メッセージに比べて小さい. 「8文字のパスワード」も,「1GBのファイル」も, SHA-1のハッシュ値はそれぞれ160ビット 具体的な一方向ハッシュ関数 MD5, SHA-1, SHA-256, SHA-512など

一方向ハッシュ関数の数学的準備 表記 メッセージとハッシュ値について h : ハッシュ関数 m, n, x : メッセージ(ハッシュ関数の入力) h(m), h(n), h(x) : ハッシュ値(ハッシュ関数の出力) メッセージとハッシュ値について メッセージ空間は一般に無限集合 ハッシュ値空間は有限集合 SHA1なら,160ビットのビット列なので, ハッシュ値空間の大きさは 2160

一方向性とは 任意のメッセージmに対してh(m)を計算するのは容易であるが,任意に与えられたh(m)から,mを求めることができない. 集合 Hm={x | h(x)=h(m)} を求めることは原理的に可能であるが,無限集合かもしれないし,mそのものを求めることは不可能.Hmの要素を一つ求めることは,弱衝突耐性に関する話. Hm= {x | h(x)=h(m)} メッセージ 空間 m hとh(m)によって決まる集合 ハッシュ値 空間 h(m)

一方向ハッシュの利用例(MD5)(1) ここをクリックで ファイルを ダウンロード ここをクリックで MD5のハッシュ値 が入手できる

一方向ハッシュの利用例(MD5)(2) 確認方法(LinuxまたはCygwin) httpd-2.2.2.tar.gz をダウンロードし,適当なディレクトリに置く. 端末(シェル)を起動し,上記のディレクトリに移動する. 「md5sum httpd-2.2.2.tar.gz」を実行すると,ハッシュ値として,32文字(128ビット)の16進文字列が出力される. ブラウザで[MD5]をクリックして,ハッシュ値を比較する. 同じならば,誤りなく送信できたと推定できる. 異なっていれば,ダウンロードに失敗した恐れがあり,最初からやり直す. この方法でファイルの完全性を確認できるが,改ざんされている可能性は否定できない. 途中で悪意のある者が,http-2.2.2.tar.gzとハッシュ値の両方を他のデータに取り替えているかもしれない!

弱衝突耐性とは 与えられたh(m)から,h(m)=h(n)を満たすメッセージnを求めることができない. m=nか否かは問わない. 原理的に求めることができるので,実用上は「計算量的に困難」であることを示せばよい.

弱衝突耐性を破る攻撃 参考:『暗号技術入門―秘密の国のアリス』 pp.184-186 Hm= {x | h(x)=h(m)} メッセージ 空間 一億円契約書 (マロリー作成,たくさん) マロリーが目標とする 一億円契約書 n ハッシュ値 空間 h(m)=h(n) 参考:『暗号技術入門―秘密の国のアリス』 pp.184-186

強衝突耐性とは m≠nかつh(m)=h(n)を満たすメッセージm,nを求めることができない. hが単射 ⇔ Hm={m} 通常使う一方向ハッシュ関数では,メッセージ空間(の部分集合)はハッシュ値空間よりも大きいので,単射とならない. 破れる? ハッシュ値空間のサイズMに対して,   個のメッセージを生成し,ハッシュ値を求めると,その中の一組が同じハッシュ値になる確率が1/2を超える.(誕生日攻撃) SHA-1なら,(2160)1/2 = 280個.それでも非現実的.

強衝突耐性を破る攻撃 参考:『暗号技術入門―秘密の国のアリス』 pp.186-188 百万円契約書 (マロリー作成,たくさん) 一億円契約書 (マロリー作成,たくさん) メッセージ 空間 m,n:マロリーが目標と する契約書 ハッシュ値 空間 h(m)=h(n) 参考:『暗号技術入門―秘密の国のアリス』 pp.186-188

メッセージ認証コード MAC (Message Authentication Code) 作成の流れ 作成者 検証者 MacintoshやMACアドレスとは別物 作成の流れ 作成者 メッセージ メッセージ 認証コード MAC値’ 鍵 鍵 等しい? メッセージ メッセージ 認証コード MAC値 検証者 MAC値を復号して メッセージを得る ことはない

メッセージ認証コードは脚光を浴びない できること 第三者証明と否認ができない ある鍵を用いてメッセージとそのMAC値のペアを作成したことを,共有する鍵を持つ人の間で,確認(保証)すること. 「そのペアの所有者は,適切な鍵を持っている」は保証できない.リプレイ攻撃の可能性があるため. 第三者証明と否認ができない 元のメッセージとそのMAC値を持っていても,鍵がなければ,それが適切なペアか判断できない. AliceとBobのみが共有する情報を使って,Aliceがメッセージ認証コードを作ったとしても,Aliceは後で「私は作っていない(Bobが作った)」と主張できてしまう.

公開鍵暗号とディジタル署名の数式表現 RSA暗号方式 RSAディジタル署名方式 RSAでは,暗号化も復号も署名も検証も「べき剰余」 暗号化:C = Encrypt(pub, M) = ME mod N 復号:M = Decrypt(pri, C) = CD mod N RSAディジタル署名方式 署名:S = Sign(pri, M) = MD mod N 検証:M = Verify(pub, S) = SE mod N RSAでは,暗号化も復号も署名も検証も「べき剰余」

ディジタル署名をどう活用する? 復元の結果,意味のあるメッセージが得られたら,この署名文は適切な鍵で署名されたと判断する. ⇒ 署名文復元法 「意味のある」の判定が容易でないことも. 復元の結果と,公開もしくは送信されたメッセージとを照合し,同じ内容ならば,この署名文は適切な鍵で署名されたと判断する. ⇒ 認証子照合法 メッセージは意味のない(ランダムな)値でもよい. 「署名文の送信者はプライベート鍵(秘密鍵)を所有している」と考えてはいけない. リプレイ攻撃の可能性あり!

プライベート鍵で署名した署名文は 対応する公開鍵でのみ正しく検証できる 署名文復元法(1) プライベート鍵で署名した署名文は 対応する公開鍵でのみ正しく検証できる (署名文の検証) (ディジタル署名) (署名文の作成) メッセージ 公開鍵で 復元 署名文 プライベート 鍵で署名 メッセージ 公開鍵 公開鍵ペア プライベート 鍵 図の出典:『暗号技術入門―秘密の国のアリス』 p.214を改変

署名文復元法(2) 数式を当てはめると M' Verify S Sign M pub pri S = Sign(pri, M) (署名文の検証) (ディジタル署名) (署名文の作成) M' Verify S Sign M pub 公開鍵ペア pri S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M))

認証子照合法(1) M M pri S S pub M' = M? M' S = Sign(pri, M) 等しくなかったら, 適切なプライベート鍵で署名されていない 通信路中で 改竄が起こった pri Sign S S pub Verify M' = M? M' S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M)) 図の出典:『暗号技術入門―秘密の国のアリス』 p.217を改変

認証子照合法(2) M M S pri pub S M' M' = h(M)? 等しくなかったら, h h Sign 適切なプライベート鍵で署名されていない 通信路中で 改竄が起こった 前ページのSよりも 格段にサイズが小さい h h h(M) S h(M) pri Sign pub Verify M' = h(M)? S M' S = Sign(pri, h(M)) M' = Verify(pub, S) = Verify(pub, Sign(pri, h(M))) 図の出典:『暗号技術入門―秘密の国のアリス』 p.219を改変

リプレイ攻撃対策は? シーケンス番号 タイムスタンプ(timestamp) ノンス(nonce) メッセージに通し番号を埋め込む. メッセージに時刻情報(作成時刻または期限の時刻)を埋め込む. ノンス(nonce) セッションごとに異なるランダムな値を生成し,埋め込む.

「原理的に可能」とは? 知ってほしいこと 無限集合といっても,一般にその各要素は,有限の長さで記述できる 解を求めることが「原理的に可能」な実例 「原理的に可能」と言うときはたいてい,「現実的には困難」と続く.

0, 1, 00, 01, 10, 11, 100, 101, … ビット列が無限集合であるとは とビット列を並べることで 1ビット 2ビット 3ビット とビット列を並べることで 重複なくビット列を列挙できる. この系列のx番目のビット列を求めることができる. ビット列mが,この系列の何番目にあるかを求めることも できる. この系列はいくらでも書くことができる. ⇒ 無限集合 しかしこの系列に出現するどの要素も,長さ有限のビット列 である.

一方向性・弱衝突耐性の破り方 入力: ハッシュ関数h,ハッシュ値M = h(m) 出力: 集合 {x | h(x) = M},またはその要素の一つ 方針 ビット列の(無限)系列の各要素を小さいものから順に取り出し(xとする),h(x) を求め,それが M と等しいか判定する. 等しければ,その x を出力する.(一つだけでいいなら,ここで終了) 計算できる? 計算理論では,「帰納的可算」と呼ばれる(ただし「帰納的」ではない). 一方向ハッシュ関数では,終了するまでの時間はハッシュ値空間に比例するので,この空間を大きくすればよい.

強衝突耐性の破り方 入力: ハッシュ関数h 出力: 集合 {(x,y) | x≠y, h(x)=h(y)},またはその要素の一つ 方針 自然数の集合をNと書くとき,N×N = {(a,b) | a∈N, b∈N} は N と1対1に対応する.すなわち,N×Nの各要素を順に漏れ なく列挙可能. そこで,N×Nの要素(a,b)を順に漏れなく取り出し, ビット列の系列のa番目の要素xおよびb番目の要素yに対して, x≠y かつ h(x)=h(y)であるかを評価すればよい. 計算できる? 計算理論としては,これも帰納的可算. 実用上は,ビット列x,yをランダムに生成するほうが簡便.