暗号の解読
暗号解読の分類
暗号文攻撃
暗号文しかわからない状態から鍵もしくは平文を求める。
既知平文攻撃
暗号文と平文を持っている状態から鍵を求める。
選択平文攻撃
自分で平文を選択して暗号化させることができる環境で鍵を求める。
暗号解読法
ブルートフォース(brute-force)攻撃
総当たり攻撃のこと。既知平文攻撃の一種。平均的には(鍵の全数×一回の復号化時間÷2)の時間があれば鍵を求めることができる。コンピュータの速度が上がるに従って総当たりにかかる時間も減り、相対的に暗号が弱くなっていくということになる。並列処理に向いており、もっとも原始的で一般的な解読方法。
差分解読法
選択平文攻撃の一種。複数の平文の差分とそれに対応する暗号文の差分を元に解読を行う。たとえば
DES
に対してこの方法を適用する場合、2の47乗個の平文と暗号文の組が必要となる。
線形解読法
選択平文攻撃の一種。暗号化のアルゴリズムを単純化し、鍵を予想する。
DES
の場合は、まず鍵の26bit分の候補を作成し、それぞれの候補に対して残りの30bitをブルートフォース攻撃する。平文と暗号文の組の数が2の43乗個の場合は10.6%の確率で、2の44乗個の場合は60.4%で、2の45乗個の場合は98.8%の確率で成功するということである。
timing attack
RSA
の秘密鍵をその処理時間で推測しようとする攻撃。考案者もインプリメントには成功していない。
対処法としては、処理後にウェイトを取って処理時間を一定にする方式と、まず乱数を掛け、その後その乱数の逆数を掛けることにより桁数を一定にする方式(blindingという)がある。
暗号システムへのアタック法
暗号を使ったシステムを破ろうとする場合に、必ずしも暗号を解読することだけがアタック法ではない。それよりもむしろ暗号以外の部分をアタックした方が効率的に暗号システムを破ることができる場合が多い。
人へのアタック
暗号システムには管理者がいるのが通常で、その人をアタックするという手段がある。ここで使われる手段は詐欺・脅迫等非学術的な手段である。当然、然るべきシステムではこのようなアタックにも耐えられなければならない。
極端な例としては、掃除夫を装って侵入し、付箋紙に書いてディスプレイに貼ってあるパスワードを盗み見る、といったことがあげられる。このようなアタックは「
ソーシャルエンジニアリング
」と呼ばれる。
実装のミスへのアタック
暗号解読トピック
にあるように、どんなに優れた暗号を使っていても、その実装の仕方が悪ければシステムは破られてしまう。特に鍵生成の部分についてこの問題が発生しやすいようである。いくらTriple-DESを使っていたとしても、鍵生成の乱数の種が時刻のみであれば、鍵を予測するのは非常に簡単なこととなってしまう。その他にも、生成した鍵が完全に消されずにメモリに残ってしまったり、ハードディスクにスワップアウトされたデータが消えきっていなかったりすることなども考えられる。微弱磁気を検査する装置を使えば、フォーマットされたディスクの内容を読むことも可能だという。
ハードウェアへのアタック
例えばICカードのタンパレジスタンス性を利用したシステムの場合、ICカードの中身を読み出すことがシステムを破ることにつながる場合がある。ICカードはあまりコストをかけられない場合が多く、内容を読み出すことが不可能ではない場合が多い。例えば大きな大学の施設を使えるような立場の人であれば、時間さえかければ中身を読むことは可能ということである。
それ以外にも、電磁波を検知することで数メートル離れた所からディスプレイに何が表示されているかを調べることができる装置(テンペストと呼ぶ)などもある。
暗号解読トピック
Netscape Commerce Serverの乱数生成に問題があり、暗号解読される
暗号自体が強くても実装がまずければ破られるという例。(
Netscape社の対応
)
RC4 40bitの鍵が破られる
RC4
がブルートフォース攻撃で破られたという報告。40bitなら総当たりでもどうにかなるという例。
RSA社主催の暗号解読コンテスト
でRC4 40bitが
3時間半で破られる
RSA DATA SECURITY CONFERENCEの開催に合わせてコンテストが開催され、大学生が大学のコンピュータを動員して3時間半で解読。平文は「40bitは使い物にならない」という意味の文だったということなので、恐らく輸出規制緩和を訴える出来レースだろう。
Copyright (C) Keiichiro Oguma / All rights reserved.