q q 情報セキュリティ 第８回：２００６年６月９日（金） q q

本日学ぶこと 鍵の利用と管理 鍵の分類，鍵の管理 乱数 公開鍵基盤（PKI) レポート課題２は，PPTとPDFで掲示します．

本日の授業で学ぶ語句 鍵，セッション鍵，マスタ鍵，CEK，KEK，鍵の生成・配送・更新・保存・暗号化・破棄 乱数，無作為性・予測不可能性・再現不可能性，擬似乱数，真の乱数，乱数生成器，種，内部状態 （公開鍵）証明書，認証局（CA），公開鍵基盤（PKI），リポジトリ，CRL，階層になった証明書，ルートCA， 鍵は平文と同じ価値を持つ． 擬似乱数生成器には最初に種を与える． PKIではCAによる（連鎖した）証明書が，鍵の正当性を保証する．

計算機の生成する乱数 線形合同法 メルセンヌ・ツイスタ（Mersenne Twister） /dev/random 古典的なアルゴリズム．randやrandom関数でも利用 予測可能．周期が小さく，質が悪い メルセンヌ・ツイスタ（Mersenne Twister） １９９０年代に開発されたアルゴリズム．フリー利用可 予測可能．周期が219937-1と大きい /dev/random UNIXの特殊ファイル 環境ノイズをもとに生成し，再現不可能 多ビット乱数を生成するには不向き

第２回レポート課題 次のいずれかの課題を実施すること 配点は１０点 提出方法 課題2a（調査課題） 課題2b（プログラミング課題） 両方を提出した人は，別個に採点して，高いほうをとる（ボーナスはつけない）． 個別の照会には応じない． 提出方法 メール：Subjectを「情報セキュリティレポート2a」または「情報セキュリティレポート2b」として，takehiko@sys.wakayama-u.ac. jpへ送信する．期限は「Fri, 23 Jun 2006 09:00:00 +0900」 紙は，第１回レポートと同じ要領で，６月２３日の授業開始時（９：１０～９：１５）に提出すること．

課題2a（１） 課題：日常生活におけるman-in-the-middle攻撃の実例を ３つ挙げよ． 提出要領 実例一つを１ページとして，本文は３ページとすること． 各ページの余白は５行以内とすること．（余白が多ければ減点） １ページ目の上部に，「情報セキュリティレポート2a」，学籍番号・氏名・提出年月日を記載すること．

課題2a（２） レポート作成の注意点 加点について 対象は計算機に関するものでも，そうでなくてもよい． man-in-the-middle攻撃の性質を理解した上で，その構図が成り立つ例を見つけること． 「事例の説明」と「考察（なぜそれがman-in-the-middle攻撃の実例なのか）」は，段落を分けて説明すること． 事例ごとに参考文献をつけること． 加点について 他の提出者が書いていない事例を取り上げていれば， １０点を超えない範囲で加点する．

課題2b（１） 課題：以下の仕様の一方向ハッシュ関数md5sに対して，衝突を見つけよ． md5sの仕様 入力：任意長のビット列b_in，出力ビット数p 出力：pビットのビット列b_out アルゴリズム: Step 1. ビット列b_inに対するMD5のハッシュ値（128ビット）を求め，b_tmpとする． Step 2. 1≦i≦pの各iに対して，次の処理を行う: b_tmpの第iビット，第i+pビット，第i+p*2ビット，…の排他的論理和を求め，それをb_outの第iビットの値とする． Step 3. b_outを出力して終了する．

課題2b（２） 解答要領 出力ビット数p=1,2,...,16のそれぞれに対して，衝突を求めよ． 解だけでなく，プログラム作成の方針（４００字程度）を記載し， ソースファイルを添付すること． プログラムの出力には，衝突する二つのビット列の２進表現と，そのハッシュ値を含んでいること． 実行環境（CPUの種類と速度，RAM容量，OSの種類，コンパイラの種類とバージョン）と実行時間を明記すること． プログラムに出力させるのでも，レポートに記載するのでもよい． 例：PentiumM 2.0GHz，1GB RAM，Gentoo Linux，GCC 3.3.6の環境で，p=16に対する衝突を発見するのに0.130秒を要した．

課題2b（３） プログラムファイル 6階演習室でLinuxでログインし，端末を立ち上げ，「~takehiko/secu2006/report2b/md5s_test」を実行すれば， いくつかのビット列とそのハッシュ値が表示される． 「~takehiko/secu2006/report2b/md5s_test 01000000」と 「echo -n ‘@’ | md5sum」の出力を比較すると， 同じハッシュ値になることが確認できる． コンパイル方法は，makeを自習し，同じディレクトリのMakefileを参照すること． これらのファイルをベースとするなら，適切に動作するmd5s_breaker.cを作って提出するだけでよい． 「cp –a ~takehiko/secu2006/report2b ~」などを実行して，自分の管理下にファイルをコピーしておくこと．

課題2b（４） その他の留意点 md5sの仕様を理解すれば，C以外の言語で実装してもよい． 出力ビット数pをもっと大きくしてもよい（出題者は，総当たり法をp=30まで試している）． 衝突を求めるための手法は，総当たり法でも，MD5に対する既存の衝突をp+1ビットの入力に適用するのでもよい． 乱数を使用する場合，再現可能（何回実行しても同じ出力）であること．現在時刻やプロセスIDなどを種としてはならない． 演習室で長時間計算をさせたまま，部屋を離れないこと．