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

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

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

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

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

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

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

6 関数 H は衝突困難 （証明） 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(0 k ｏ x 1 )=f(0 k ｏ x’ 1 ) 。従って、 x 1 =x’ 1,..,x t =x’ t となり矛盾。 場合２： |x|≠|x’| （ |x|<|x’| とする） 場合１と同じ議論をすると、 f(0 k ｏ x 1 )=f(h’ u-1 ｏ x’ u ) となる。 0 k ≠h’ u-1 の場合ｆの衝突 ペアが 得られ矛盾。一方、 0 k =h’ u-1 の場合 f(z)=0 k となる z が得られ矛盾。 x’ に対応した変数に「 ’ 」を付 加 f ff f 0k0k x1x1 x2x2 x3x3 xtxt h1h1 h2h2 h t-1 htht f ff f 0k0k x’1x’1 x’2x’2 x’3x’3 x’tx’t h’1h’1 h’2h’2 h’ t-1 h’th’t メッセージ x メッセージ x’ 関数 H 定理： 「 f が衝突困難かつ f(z)=0 k となる z を求めることが困難」⇒「 H は衝 突困難」

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

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

9 SHA-1 (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 5A827999 if 0 ≦ t ≦ 19 6ED9EBA1 if 20 ≦ t ≦ 39 8F1BBCDC if 40 ≦ t ≦ 59 CA62C1D6 if 60 ≦ t ≦ 79 f t (B,C,D)= メッセージ Ｌの 2 進表現 1 0…0 L bit m bit64 bit M1M1 MnMn W0W0 W1W1 W 15 … 1 ワー ド (=32bit) 1 ブロック (=16 ワー ド ) K t = パディング ( ブロック境 界） +++++ H0H0 H1H1 H2H2 H3H3 H4H4 H0H0 H1H1 H2H2 H3H3 H4H4 K 0, W 0 K 1, W 1 K 79, W 79 MiMi M 1 から M n まで実行 W t =S 1 (W t-3 W t-8 W t-14 W t-16 ) 16 ≦ t ≦ 79 A B C D E + + + + KtKt WtWt ≪ 30 ≪5≪5 ftft ブロック M i のハッシュ 値 … … … 前のブロック M i-1 のハッシュ 値

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