複数回通信可能なChaffing and Winnowingのテーブルによる可視化 東京大学理科一類2年 田中 香津生
概要 複数回通信可能なChaffing and Winnowingを実現するテーブルの作成 Flashを用いたデモ実装
インデックス Chaffing and Winnowingの概要 Chaffing and Winnowingを複数回利用へ拡張 デモの仕様、目的 デモ実演
Chaffing and Winnowing[1] 1998年に発表。 方法[2] 送りたいメッセージのほかにダミーとなるメッセージをそれぞれタグ(Authentication Code)をつけて送る。(Chaffing) 事前に認証鍵を共有することでタグによって受信者のみが正しいメッセージを見分けられる。(Winnowing) 特徴 平文のまま通信ができるため暗号化が必要ない
Chaffing and Winnowingの例1 “Hi, Bob” , A1 Alice Bob “Hi, Larry” , A2 ←Chaff packet “Hi, Bob”,A1 Winnowing “Hi, Larry”,A2 Charles ? “Hi, Bob” ,A1 “Hi, Larry”,A2 Perfect-Security:認証鍵を持たない第3者が盗聴できない
Chaffing and Winnowingの例2 “Hi, Bob” , A1 Alice Bob “Hi, Larry” , A2 ←Chaff packet “Hi, Bob”,A1 Winnowing “Hi,Eve” ,A3 “Hi, Larry”,A2 Charles Non-Malleability:別のメッセージに対する正しいタグを生成できない
複数回通信への拡張[3] 2007年5月発表 一つの認証鍵で複数回の通信の安全性を保証することを数学的に証明
複数回通信の実装 複数回通信は可能か? 07年の論文には、理論上可能であることしか示されていない 実際に動くプログラムとしてデモで実装 ・デモ・・・安全性の検証(攻撃者のプログラム) ・安全か ・正しく動くか 検証
C&W Multiple Useのデモの構成 Authentication Code(Ak) 1 2 0,1 2,3 4,5 2,4 0,5 1,3 3,5 1,4 0,2 1 2 plain text 2 1 Secret key=1 Alice Bob (0,2) (0,1) デモの説明、 (1,2) (1,1) (2,2) (2,1) ? Charles ? Secret Key =1 or 3 (1,2) Secret Key =0~5 Secret Key =1 ! (2,1)
デモの内容 テーブルの仕組み(セキュアなテーブル) テーブルの仕組み(セキュアでないテーブル) 攻撃者プログラム(セキュアなテーブル) メッセージ空間が4におけるテーブルの仕組み、認証鍵を生成する仕組み テーブルの仕組み(セキュアでないテーブル) セキュアでないテーブルにおける認証鍵生成の矛盾 攻撃者プログラム(セキュアなテーブル) 今回作成したテーブル生成プログラムにおける通信を盗聴するプログラム 攻撃者プログラム(セキュアでないテーブル) セキュアでないテーブルによる通信を盗聴するプログラム
結論 テーブルを使用することでChaffing and Winnowingは実装可能。 適切なテーブルを用意すれば安全なChaffing and Winnowigの通信が可能。 本来見えない暗号方式の仕組みの視覚化は難しい。
参考文献 [1] R. Rivest, “Chaffing and winnowing: confidentiality without encryption,” http://theory.lcs.mit.edu/~rivest/publications.html [2] G. Hanaoka, Y. Hanaoka, M. Hagiwara, H. Watanabe and H. Imai, “Unconditionally secure Chaffing-and-Winnowing: A Relationship Between Encryption and Authentication,” Proc. of AAECC’06, LNCS 3857, Springer-Verlag, pp.154-162, 2006. [3] Wataru Kitada, Goichiro Hanaoka, Kanta Matsuura, Hideki Imai, “Unconditionally Secure Chaffing-and-Winnowing for Multiple Use”, International Conference on Information Theoretic Security, 2007. [4] A. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal 28, pp. 656–715, 1949.