q q 情報セキュリティ 第７回：２００７年６月１日（金） 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）（１） ここをクリックで ファイルを ダウンロード ここをクリックで MD5のハッシュ値 が入手できる

一方向ハッシュの利用例（MD5）（２） 確認方法（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では，暗号化も復号も署名も検証も「べき剰余」

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

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

署名文復元法（２） 数式を当てはめると 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))

認証子照合法（１） 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を改変

認証子照合法（２） 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 と１対１に対応する．すなわち，N×Nの各要素を順に漏れ なく列挙可能． そこで，N×Nの要素(a,b)を順に漏れなく取り出し， ビット列の系列のa番目の要素xおよびb番目の要素yに対して， x≠y かつ h(x)=h(y)であるかを評価すればよい． 計算できる？ 計算理論としては，これも帰納的可算． 実用上は，ビット列x,yをランダムに生成するほうが簡便．