q q 情報セキュリティ第７回：２００６年６月２日（金） q q 本日学ぶこと  メッセージ認証 q q q q 一方向ハッシュ関数メッセージ認証コードディジタル署名（デジタル署名）いずれも，正真性・完全性に関する技術 2 本日の授業で学ぶ語句       一方向ハッシュ関数，指紋，完全性，ハッシュ値，衝突，弱衝突耐性，強衝突耐性，一方向性，メッセージダイジェスト， MD5，SHA-1，誕生日攻撃メッセージ認証コード（MAC），なりすまし，HMAC ディジタル署名，署名と検証，署名文復号法，認証子照合法，第三者検証，否認防止一方向ハッシュ関数，メッセージ認証コード，ディジタル署名は改竄を検出できる．メッセージ認証コードは，鍵を共有する当事者間で（のみ）メッセージの完全性を検証できる．ディジタル署名は第三者による検証ができる． 3 機密性・正真性と暗号技術機密性正真性（完全性）鍵なしアルゴリズム秘匿による暗号一方向ハッシュ関数共通鍵対称暗号メッセージ認証コード非対称鍵公開鍵暗号ディジタル署名 4 一方向ハッシュ関数：準備  表記 q q q  h : ハッシュ関数 m, n, x : メッセージ（ハッシュ関数の入力） h(m), h(n), h(x) : ハッシュ値（ハッシュ関数の出力）メッセージとハッシュ値について q q メッセージ空間は一般に無限集合ハッシュ値空間は有限集合  ビット長を固定とすることが多い  SHA1なら，160ビットのビット列なので，ハッシュ値空間の大きさは 2160 5 一方向性とは  任意のメッセージmに対してh(m)を計算するのは容易であるが，任意に与えられたh(m)から，mを求めることができない． q 集合 Hm={x | h(x)=h(m)} を求めることは原理的に可能であるが，無限集合かもしれないし，mそのものを求めることは不可能． Hmの要素を一つ求めることは，弱衝突耐性に関する話．メッセージ空間 Hm= {x | h(x)=h(m)} m hとh(m)によって決まる集合ハッシュ値空間 h(m) 6 弱衝突耐性とは  与えられたh(m)から，h(m)=h(n)を満たすメッセージnを求めることができない． q q m=nか否かは問わない．原理的に求めることができるので，実用上は「計算量的に困難」であることを示せばよい． 7 弱衝突耐性を破る攻撃（教科書pp.184-186） Hm= {x | h(x)=h(m)} m:百万円契約書（アリス作成）メッセージ空間一億円契約書（マロリー作成，たくさん）マロリーが目標とする一億円契約書 n ハッシュ値空間 h(m)=h(n) 8 強衝突耐性とは  m≠nかつh(m)=h(n)を満たすメッセージm,nを求めることができない． q hが単射でなければ，原理的に求めることができるので，実用上は「計算量的に困難」であることを示せばよい．  hが単射 ⇔ Hm={m}  通常使う一方向ハッシュ関数では，メッセージ空間（の部分集合）はハッシュ値空間よりも大きいので，単射とならない． 9 強衝突耐性を破る攻撃（教科書pp.186-188）メッセージ空間百万円契約書（マロリー作成，たくさん）一億円契約書（マロリー作成，たくさん） m,n：マロリーが目標とする契約書ハッシュ値空間 h(m)=h(n) 10 一方向ハッシュの利用例（MD5）（１）ここをクリックでファイルをダウンロードここをクリックで MD5のハッシュ値が入手できる 11 一方向ハッシュの利用例（MD5）（２）  確認方法（LinuxまたはCygwin） 1. httpd-2.2.2.tar.gz をダウンロードし，適当なディレクトリに置く． 2. 端末（シェル）を起動し，上記のディレクトリに移動する． 3. 「md5sum httpd-2.2.2.tar.gz」を実行すると，ハッシュ値として， 32文字（128ビット）の16進文字列が出力される． 4. ブラウザで[MD5]をクリックして，ハッシュ値を比較する．  同じならば，誤りなく送信できたと推定できる．  異なっていれば，ダウンロードに失敗した恐れがあり，最初からやり直す．  この方法でファイルの完全性を確認できるが，改竄されている可能性は否定できない． q man-in-the-middle攻撃により，http-2.2.2.tar.gzとハッシュ値の両方を他のデータに取り替えているかもしれない！ 12 公開鍵暗号とディジタル署名の数式表現  RSA暗号方式 q q  RSAディジタル署名方式 q q  暗号化：C = Enc(pub, M) = ME mod N 復号：M = Dec(pri, C) = CD mod N 署名：S = Sign(pri, M) = MD mod N 検証：M = Ver(pub, S) = SE mod N RSAでは，暗号化も復号も署名も検証も「べき剰余」 q ElGamalなど，他の暗号アルゴリズムでは必ずしも成立しない． 13 ディジタル署名の方法１（１）  署名文復元法教科書Fig.9-2（p.214）の，より適切な図プライベート鍵で署名した署名文は対応する公開鍵でのみ正しく検証できるメッセージ（署名文の検証）（ディジタル署名）（署名文の作成）公開鍵で復元署名文プライベート鍵で署名公開鍵公開鍵ペアメッセージプライベート鍵 14 ディジタル署名の方法１（２）  教科書Fig.9-2（p.214）に数式を当てはめる M' （署名文の検証）（ディジタル署名）（署名文の作成） Verify S Sign pub 公開鍵ペア M pri S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M)) 15 ディジタル署名をどう活用する？   復元の結果，意味のあるメッセージが得られたら，この署名文は適切な鍵で署名されたと判断する． ⇒ 署名文復元法復元の結果と，公開もしくは送信されたメッセージとを照合し，同じ内容ならば，この署名文は適切な鍵で署名されたと判断する． ⇒ 認証子照合法 q  認証子照合法では，メッセージはランダムな値でもよい．「署名文の送信者はプライベート鍵（秘密鍵）を所有している」と考えてはいけない． q 再生攻撃の可能性あり！ 16 ディジタル署名の方法２  認証子照合法教科書Fig.9-5（p.217）に数式を当てはめる M pri M 等しくなかったら， Sign  S S  pub Verify M'   適切なプライベート鍵で署名されていない通信路中で改竄が起こった M' = M? S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M)) 17 ディジタル署名の方法３  これも，認証子照合法教科書Fig.9-6（p.219）に数式を当てはめる M M h h 等しくなかったら，  S h(M) h(M)  pri Sign S   pub Verify M' 適切なプライベート鍵で署名されていない通信路中で改竄が起こった M' = h(M)? S = Sign(pri, h(M)) M' = Verify(pub, S) = Verify(pub, Sign(pri, h(M))) 18 以下余談  知ってほしいこと q q 無限集合といっても，一般にその各要素は「有限の長さで記述できる」こと解を求めることが「原理的に可能」な実例  「原理的に可能」と言うときはたいてい，「現実的には困難」と続く． 19 ビット列が無限集合であるとは 0, 1, 00, 01, 10, 11, 100, 101, … 1ビット 2ビット 3ビット … とビット列を並べることで q q q 重複なくビット列を列挙できる．  この系列のx番目のビット列を求めることができる．  ビット列mが，この系列の何番目にあるかを求めることもできる．この系列はいくらでも書くことができる． ⇒ 無限集合しかしこの系列に出現するどの要素も，長さ有限のビット列である． 20 一方向性・弱衝突耐性の破り方    入力：ハッシュ関数h，ハッシュ値M = h(m) 出力：集合 {x | h(x) = M}，またはその要素の一つ方針 q q  ビット列の（無限）系列の各要素を小さいものから順に取り出し（xとする），h(x) を求め，それが M と等しいか判定する．等しければ，その x を出力する．（一つだけでいいなら，ここで終了）計算できる？ q q 計算理論では，「帰納的可算」と呼ばれる（ただし「帰納的」ではない）．一方向ハッシュ関数では，終了するまでの時間はハッシュ値空間に比例するので，この空間を大きくすればよい． 21 強衝突耐性の破り方    入力：ハッシュ関数h 出力：集合 {(x,y) | x≠y, h(x)=h(y)}，またはその要素の一つ方針 q q  自然数の集合を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)であるかを評価すればよい．計算できる？ q q 計算理論としては，これも帰納的可算．実用上は，ビット列x,yをランダムに生成するほうが簡便． 22