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

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

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

バースデイパラドックスの 計算 n 個のバケツに q 個のボールを ランダムに入れる問題を考え る。 2 個以上のボールが少なくとも １つのバケツに入る確率を P coll とする。 P coll =1 － n(n-1)..(n-q+1)/n q ＞ 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 となる。 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× … … n 個のバケツ q 個のボール (1-e -x )/x は 単調減少 q=n 1/2 ∈ [1,(2n) 1/2 ] の時、 P coll ＞ q(q-1)/n× = (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

メッセージ長がｎの整数倍の 場合 １． メッセージ 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 )

関数 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 は衝 突困難」

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 の２進表現

SHA-1 （ Secure Hash Algorithm ） SHA-1 について 米国政府のシステム調達 基準で規定された衝突困 難なハッシュ関数 2 64 ビット未満の任意の メッセージを 160bit に圧 縮 固定長圧縮関数ｆを繰返 し利用する 関数 f は ビットの 入力を 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 = /2 =2 64 = (2 10 ) 6.4 =(10 3 ) 6.4 = GHz マシンが 1 クロックで１っの メッセージのハッシュ値を計算出来 ると仮定する。衝突ペアを確率 0.3 で 見つけるためには /10 9 x60x60x24x365 ≒ 10 7 年必要。

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 5A 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 のハッシュ 値

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