Q q 情報セキュリティ 第４回：２００７年５月１１日（金） q q.

Presentation on theme: "Q q 情報セキュリティ 第４回：２００７年５月１１日（金） q q."— Presentation transcript:

1 q q 情報セキュリティ 第４回：２００７年５月１１日（金） q q

2 本日学ぶこと 使い捨てパッド ＤＥＳ (Data Encryption Standard)
ＡＥＳ (Advanced Encryption Standard) ブロック暗号のモード 使い捨てパッドは無条件に安全だが，非実用的 対称暗号成功の秘訣は，排他的論理和（） DESのファイステル構造は，暗号化と復号が同じ構造 AESは，コンペ方式による標準化で選定された 対称暗号を使いたいなら，AES

3 （復習）暗号系 平文 平文 暗号化 暗号 化鍵 復号 鍵 復号 盗聴可能な 通信路 暗号文 暗号文

4 （復習）単一換字暗号 平文 平文 abc... WYH... 暗号化 暗号 化鍵 復号 鍵 復号 WYH... abc... 暗号文 暗号文

5 平文 平文 暗号文 暗号文 使い捨てパッド 暗号化 復号 暗号 化鍵 復号 鍵 11100 11100 10101 10101 01001

6 使い捨てパッドの暗号アルゴリズム 平文： M = m1m2m3… 鍵： K = k1k2k3…
暗号化： C = c1c2c3… ただし，ci = ki  mi ビット単位で，鍵と平文の排他的論理和を求める． 復号：M' = m'1m'2m'3 … ただし， m'i = ki  ci = ki  (ki  mi) = ki  ki  mi = (ki  ki)  mi = 0  mi = mi ビット単位で，鍵と暗号文の排他的論理和を求める． Vernamによって1917年に考案され，特許になった． 「バーナム暗号」とも呼ばれる． mi, ki, ci, m'iは 1ビット 送受信者の間で 共有しておく．

7 排他的論理和の性質 x  y = y  x x  x = 0 x  y  y = x x = y ⇒ x  z = y  z
z = x  y ⇒ x = z  y, y = x  z x y 1 x  y 排他的論理和の 真理値表 xを平文，yを鍵とみなすと， この式は，使い捨てパッドにおける 暗号化と復号の関係を表す．

8 使い捨てパッドは解読不可能 暗号文のみでは，同じ長さの任意のビット列が平文の候補となり，そこから平文を特定できない．
無条件に安全であり，情報理論的に解読不可能 （比較）実用化されている暗号アルゴリズムは，計算量的に解読不可能 既知平文攻撃や選択平文攻撃を用いれば，暗号化に使用したビット列を求めることができる． c = k  m ⇒ k = c  m しかしこれで求めた k は，(平文,暗号文)=(m,c)という暗号化の鍵としてしか使えない． k を知っても，それ以外の秘密通信の復号・解読には役に立たない．

9 暗号化鍵 復号鍵 鍵をどのようにして共有する？ 事前にビット列を共有しておき，暗号化・復号のたびに，使用したビット列に線を引いて消す．
暗号化する側がビット列を生成し，暗号文と別のルートで秘密に送る． 暗号化鍵 復号鍵

10 使い捨てパッドは非現実的 平文と同じ長さの鍵が必要 鍵の共有（配送）が難しい 鍵は「使い捨て」でなければならない
平文が1GBなら，鍵も1GB 鍵の共有（配送）が難しい 秘密の通信路があるのなら，そこにメッセージを送れば？ 鍵は「使い捨て」でなければならない 再利用すると，過去の通信内容が復号できてしまう． 鍵は真の乱数であり，かつ共有しなければならない 計算機が生成できるのは，擬似乱数か，再現性のない（物理ノイズによる）乱数のいずれか． 鍵は圧縮できない．

11 平文 暗号文 使い捨てパッドから学ぶこと 擬似乱数 排他的論理和は，「2度適用すると，元に戻る」ので，暗号化や復号の処理に適している． 暗号
ストリーム暗号 DES，AESなどの対称暗号でも活用 暗号 化鍵 擬似乱数 平文 暗号文

12 現代の対称暗号 DES (Data Encryption Standard)
１９７７年に連邦情報処理標準規格に採用された対称暗号 鍵長64bit，ブロック長64bit ファイステル構造により安全性を高める 「兵器」とみなされ，かつて輸出規制があった AES (Advanced Encryption Standard) Rijndaelともいう NISTが公募して２０００年に選定された対称暗号 鍵長128/192/256 bit，ブロック長128bit SPN構造により安全性と処理効率を実現 特許などの制限がなく無料で利用可能 「公募」の意味…安全性を評価したのは情報セキュリティの専門家 （安全なシステムを創る者は，自他の安全なシステムを検証する者でもある．）

13 ＤＥＳとＡＥＳに関わる組織と考案者 NSA NBS NIST Lucifer DES Rijndael AES IBM Daemen &
改組 米国 当局 修正 選定 選定 Lucifer DES Rijndael AES 暗号 方式 応募 応募 IBM （Feistel他） Daemen & Rijmen 考案者 ＮＳＡ：米国安全保障局，National Security Agency ＮＢＳ：米国商務省標準局，National Bureau of Standards ＮＩＳＴ：米国国立標準技術研究所

14 平文 鍵 暗号文 暗号文 平文 DESの概要 ラウンド１ サブ鍵１ ラウンド１６ ラウンド２ サブ鍵２ ラウンド２ ラウンド１６ サブ鍵１６
暗号化 復号 平文 鍵 暗号文 転置 転置 ラウンド１ サブ鍵１ ラウンド１６ ラウンド２ サブ鍵２ ラウンド２ ラウンド１６ サブ鍵１６ ラウンド１ 転置 転置 暗号文 平文

15 ファイステル構造（暗号化１） Li-1 ki Ri-1 f Li Ri Li = Ri-1
i 番目のラウンド（DESでは1≦i＜16） Li = Ri-1 Ri = Li-1  f (ki , Ri-1)

16 ファイステル構造（暗号化２） Li-1 ki Ri-1 f Li Ri Li = Li-1  f (ki , Ri-1)
最終ラウンド（DESではi=16） Li = Li-1  f (ki , Ri-1) Ri = Ri-1

17 Li-1 = Ri  f (ki , Li ) = Ri  f (ki , Ri-1)
ファイステル構造（復号１） Li Ri ki f Li-1 Ri-1 i 番目のラウンド（DESでは1≦i＜16） Ri-1 = Li Li-1 = Ri  f (ki , Li ) = Ri  f (ki , Ri-1)

18 DESとAESの安全性は？ DES AES 70～80年代は安全な対称暗号として使用されていた． 1993年，線形解読法が提案される．
1999年には22時間で解読（鍵発見）． 現在では使用は推奨されない． AES コンペ方式による標準化（専門家らによる十分な期間の検証）により安全性が認められた． 数学的構造を持つ（数式で記述できる）ことが安全性を脅かすかもしれない（ただし現時点で具体的な攻撃方法はない）． ラウンド数が少ない場合の解読の試みがなされている．

19 トリプルDES (3DES) DES-EDE3 DES-EDE2
鍵長は56×3=168bit（鍵空間は2168），ブロック長は64bit DES-EDE2 暗号アルゴリズムは，「鍵1でDES暗号化」して，「鍵2でDES復号」して，「鍵1でDES暗号化」 鍵長は56×2=112bit，ブロック長は64bit 長さは3倍だが，空間は3倍よりもうんと大きい

20 暗号アルゴリズム設計者の苦悩 暗号化や復号が高速にできると，解読も高速にできてしまうかもしれない．
処理速度が，暗号化＜復号というアルゴリズムは？ 圧縮ソフトウェアでは圧縮＜伸張のことが多い． 暗号化＜復号のアルゴリズムを考案すると，構造が複雑になり，思わぬところから欠陥が見つかるかもしれない．

21 ブロック暗号のモード 平文・暗号文のブロック化 複数ブロックの暗号化の方法 C0は初期ベクトル（盗聴されてもよい）
ブロック長のサイズで分割して，暗号アルゴリズムを適用する ブロック長に満たなければ，詰め物を加える（パディング） 複数ブロックの暗号化の方法 ECB (Electric CodeBook)モード…安全でない Ci = E(K, Mi) CBC (Cipher Block Chaining)モード…安全 Ci = E(K, (Ci-1 Mi)) C0は初期ベクトル（盗聴されてもよい） CTR (CounTeR)モード…安全 Ci = E(K, CTR + i)  Mi CTRは乱数（盗聴されてもよい） Ci, Mi, CTRは 1ブロック

22 ECBモードはなぜ安全でないか ECBモードのブロック暗号を盗聴していて，過去とまったく同じ（暗号化された）ブロックがくれば，この二つのブロックの平文は同じだと分かる． １パスワード＝１ブロックで暗号化して管理しているとき，暗号化ブロックを置き換えることで，他人のパスワードを改ざんし，成りすまして認証を受けることができてしまう．