情報セキュリティ　 第９回 ハッシュ関数.

Presentation on theme: "情報セキュリティ　 第９回 ハッシュ関数."— Presentation transcript:

1 情報セキュリティ　 第９回 ハッシュ関数

2 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄
セキュリティに対する脅威　　　　脅かされる特性　　　　　暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 （情報が書き換えられる） 正真性 一方向ハッシュ関数 なりすまし （正しい送信者のふりをする） 認証 メッセージ認証コード 否認 （後から私じゃないと言う） 否認不可能性 デジタル署名

3 ハッシュ関数 ハッシュ関数 衝突困難なハッシュ関数H 固定長圧縮関数 鳩ノ巣原理
長いメッセージを短いビット（ハッシュ値）に圧縮する関数。 ハッシュ値は固定長。 衝突困難なハッシュ関数H ハッシュ値が一致するxとx’の対(つまり、H(x)=H(x’)を満たすxとx’)を効率よく見つけることが困難なハッシュ関数。 固定長圧縮関数 ある固定長のメッセージをハッシュ値に変換する関数。 長いメッセージのハッシュ値を求めるためには、固定長圧縮関数を繰返し適用する。 鳩ノ巣原理 n+1羽の鳩がn個の巣に入る時、2羽以上の鳩が入る巣が少なくとも一つ存在する。 バースデイパラドックス 鳩ノ巣原理により、366人集まると誕生日が一致するペアが必ず存在する。 20人集まった場合、誕生日が一致するペアが存在する確率は約0.3である（意外に多い） 。 多項式時間で解けるアルゴリズム

4 バースデイパラドックスの計算 n個のバケツにq個のボールをランダムに入れる問題を考える。
n=365の時、n1/2≑19 n個のバケツにq個のボールをランダムに入れる問題を考える。 2個以上のボールが少なくとも１つのバケツに入る確率をPcollとする。 Pcoll=1－n(n-1)..(n-q+1)/nq ＞1－e-1/n ( q-1) =1－e-q(q-1)/2n 1≦q≦(2n)1/2の場合を考える。 x=q(q-1)/2nは、0≦x＜1となる。 　　Pcoll ＞1－e-x=x(1-e-x)/x ＞x(1-e-1) = q(q-1)/n×(1-e-1)/2 = q(q-1)/n× q=n1/2∈[1,(2n)1/2]の時、 Pcoll ＞ q(q-1)/n× = (1-n-1/2) 大きなnに対して、 Pcoll＞0.3 ハッシュ値がkビットの場合、2k/2回ハッシュ値を計算する と確率0.3で衝突が起きる。 e-x>1-x q個のボール … (1-e-x)/xは単調減少 … n個のバケツ

5 ハッシュ関数の利用例 ブロックチェーン : : : ブロック10 ブロック11 ブロック12 ブロックヘッダ ブロックヘッダ ブロックヘッダ
マイニングとは、ブロックヘッダのハッシュ値がある値以下になるナンスを見付ること ブロックヘッダ ブロックヘッダ ブロックヘッダ 前のブロックの ヘッダのハッシュ値 前のブロックの ヘッダのハッシュ値 前のブロックの ヘッダのハッシュ値 マークル・ルート マークル・ルート マークル・ルート ナンス ナンス ナンス トランザクション1 トランザクション1 トランザクション1 トランザクション2 トランザクション2 トランザクション2 : : : トランザクション8 トランザクション8 トランザクション8 ブロック10 ブロック11 ブロック12

6 ハッシュ関数の利用例 マークル・ルート : ブロックヘッダ ナンス マークル・ルート ハッシュ001 ハッシュ002 マークル・ルート
前のブロックの ヘッダのハッシュ値 ハッシュ001 ハッシュ002 マークル・ルート ナンス ハッシュ01 ハッシュ02 ハッシュ03 ハッシュ04 トランザクション1 ハッシュ1 ハッシュ2 ハッシュ3 ハッシュ4 ハッシュ5 ハッシュ6 ハッシュ7 ハッシュ8 トランザクション2 : トランザクション8 トランザクション1 トランザクション2 トランザクション3 トランザクション4 トランザクション5 トランザクション6 トランザクション7 トランザクション8

7 MD(Merkle-Damgard)変換
任意に長いメッセージをハッシュ値に圧縮するハッシュ関数を構成する一つの方法。 衝突困難な関数ｆを繰返し使う。 関数ｆはk+nビットのメッセージをkビットのハッシュ値に圧縮する。 メッセージ長がｎの整数倍の場合 １．メッセージxをｎビット毎に分割する。 x=x１ｏx2ｏ..ｏxｔ 　　|x１|=|x2|=..=|xt|=n ２．最初の関数ｆのハッシュ値h1は： 　　h1=f(0kｏx1) ３．i=2,..,tに対し、hi=f(hi-1ｏxi) ４．関数Hのハッシュ値H(x)は、H(x)=hｔ ｏはビット列の連結 |x|はxの長さ メッセージ x1 x2 x3 xt ハッシュ値 関数H f f f f ht 0k h1 h2 ht-1 h1=f(0kｏx1) ht=f(ht-1ｏxt)

8 関数Hは衝突困難 定理： 「fが衝突困難かつf(z)=0kとなるzを求めることが困難」⇒「Hは衝突困難」 x1 x2 x3 xt
（証明）　H(x)=H(x’)となる対xとx’ （x≠x’）が見つかったと仮定する。 場合１：　|x|=|x’| 　hｔ=h’ｔより、f(hｔ-1ｏxｔ)=f(h’ｔ-1ｏx’ｔ)。fは衝突困難より、 hｔ-1=h’ｔ-1かつxｔ=x’ｔである。 　hｔ-1=h’ｔ-1より、f(hｔ-2ｏxｔ-1)=f(h’ｔ-2ｏx’ｔ-1)。 fは衝突困難より、 hｔ-2=h’ｔ-2かつxｔ-1=x’ｔ-1である。 　同じ議論を繰返し、最後にf(0kｏx1)=f(0kｏx’1)。従って、 x1=x’1,..,xt=x’tとなり矛盾。 場合２：　|x|≠|x’|　（|x|<|x’|とする） 　場合１と同じ議論をすると、f(0kｏx1)=f(h’u-1ｏx’u)となる。0k≠h’u-1の場合ｆの衝突ペアが 　得られ矛盾。一方、0k=h’u-1の場合 f(z)=0kとなるzが得られ矛盾。 x’に対応した変数に「’」を付加 x1 x2 x3 xt メッセージx 関数H 0k f f f f ht h1 h2 ht-1 メッセージx’ x’1 x’2 x’3 x’t 関数H 0k f f f f h’t h’1 h’2 h’t-1

9 MD変換の一般形 メッセージ長がｎの整数倍でない場合 （主変換） １．h1=f(0k+1ｏy1) 定理： 「fが衝突困難」⇒「Hは衝突困難」
（予備変換） １．メッセージxをｎ-1ビット毎に分割 x=x１ｏx2ｏ..ｏxt 　　|x１|=|x2|=..=|xt-1|=n-1, |xt|=n-1-d ２．y1=x1,..,yt-1=xt-1, yt=xtｏ0d ３．yt+1をdの２進表現とする （主変換） １．h1=f(0k+1ｏy1) ３．i=2,..,t+1に対し、hi=f(hi-1ｏ1ｏyi) ４．関数Hのハッシュ値H(x)はH(x)=hｔ+1 定理： 「fが衝突困難」⇒「Hは衝突困難」 　x1 　x2 　x3 　　xt メッセージ dの２進表現 0ｏx1 1ｏx2 1ｏx3 1ｏxtｏ0d 1ｏyt+1 関数H ハッシュ値 f f f f f 0k ht+1 h1 h2 ht-1 ht

10 SHA-1（Secure Hash Algorithm）
米国政府のシステム調達基準で規定された衝突困難なハッシュ関数 264ビット未満の任意のメッセージを160bitに圧縮 固定長圧縮関数ｆを繰返し利用する 関数fは ビットの入力を160ビットに圧縮する 前身のMD4、MD5（k=128bit)は衝突ペアが既知 表記法 １．１ワード＝３２ビット ２．１ブロック＝１６ワード ３．∧：論理積、∨：論理和、￢：ビット反転、　 　　 ：排他的論理和 ４．ワードX,Yに対して、 X+Yは、 X+Y mod 232 ５．Sn(X)：nビット左巡回シフトSn(X)=(X≪n)∨(X≫32-n) 衝突ペアを確率0.3で見つけるハッシュ値の計算回数2160/2=280= (210)8=(103)8=1024 デジタル署名で使用 2128/2=264= (210)6.4=(103)6.4=1019.2 nビット巡回シフト 1GHzマシンが1クロックで１っのメッセージのハッシュ値を計算出来ると仮定する。衝突ペアを確率0.3で見つけるためには1024/109x60x60x24x365≒107年必要。

11 SHA-1 ft(B,C,D)= … メッセージ … 0…0 … M1 Mn … Kt = A B C D E H0 H1 H2 H3 H4
パディング(ブロック境界） ft(B,C,D)= L bit m bit 64 bit … (B∧C)∨((￢B)∧D) if 0≦t≦19 B C D if 20≦t≦39 (B∧C)∨(B∧D)∨(C∧D) if 40≦t≦59 B C D if 60≦t≦79 5A if 0≦t≦19 6ED9EBA1 if 20≦t≦39 8F1BBCDC if 40≦t≦59 CA62C1D6 if 60≦t≦79 メッセージ … 1 0…0 Ｌの2進表現 … M1 Mn … 1ワード (=32bit) 1ブロック (=16ワード) W0 W1 W15 Kt = A B C D E H0 H1 H2 H3 H4 前のブロックMi-1のハッシュ値 Mi M1からMn まで実行 ≪5 + K0, W0 ft + K1, W1 ≪30 + Kt K79, W79 Wt + Wt=S1(Wt Wt Wt Wt-16) 16≦t≦79 + + + + + A B C D E H0 H1 H2 H3 H4 ブロックMiのハッシュ値

12 2回目小テスト（理解度確認試験）について 実施日：第１０回講義の日 成績評価に関係する。 持ち込み可 試験内容
教科書または、パワーポイント参照可。 試験内容 第１回～９回講義内容