無線 LAN 暗号化方式 WEP の秘密鍵を IP パケットから高速に導出する手法の実装と検証島根大学総合理工学部数理情報システム学科応用情報学講座田中研究室 S 前田恒太平成 26 年 2 月 3 日

Size: px

Start display at page:

Download "無線 LAN 暗号化方式 WEP の秘密鍵を IP パケットから高速に導出する手法の実装と検証島根大学総合理工学部数理情報システム学科応用情報学講座田中研究室 S 前田恒太平成 26 年 2 月 3 日"

ゆきひらえんの
5 years ago
Views:

1 無線 LAN 暗号化方式 WEP の秘密鍵を IP パケットから高速に導出する手法の実装と検証島根大学総合理工学部数理情報システム学科応用情報学講座田中研究室 S 前田恒太平成 26 年 2 月 3 日

2 目次目次... 1 第 1 章はじめに... 2 第 2 章 WEP 無線 LAN 無線 LAN のセキュリティプロトコル RC WEP WEP の脆弱性と従来の攻撃手法 FMS 攻撃 PTW 攻撃今回実装する攻撃手法第 3 章実装方法 Klein 攻撃 IP パケットを用いる上での問題点実装方法キーストリームの導出 WEP キー先頭 10 バイトの導出 WEP キー後尾 3 バイトの探索 WEP キー先頭 10 バイトの組み合わせの試行第 4 章検証結果と考察パケット数実行時間第 5 章今後の課題パケット収集と WEP キー解析を並行して実行するように改良複数の WEP キーに対して同様に導出が行えるかを検証試行回数を増加パケット数実行時間の定量的な評価謝辞引用参考文献

3 第 1 章はじめに近年無線 LAN の普及が進み一般家庭や企業のみならず公共施設や店舗など様々な場所で利用されるようになった無線 LAN はデータを電波で通信するため有線のそれよりも盗聴などの脅威が大きくなるそのためデータを暗号化し通信するセキュリティプロトコルの使用が必須であるセキュリティプロトコルの中の一つである WEP は今現在も多くの無線 LAN ルータに搭載され利用されているがこれに対してはすでに多数の攻撃手法が提案され実装されている [1][2][3] しかし今現在実装されている攻撃手法は条件が限られるもので解析が困難になるような状況をつくり出すだが WEP に対してはすでに IP パケットのみを用いて比較的少ないパケットで高速に WEP キーを導出するアルゴリズムが提案されている [4] そこで本研究ではこのアルゴリズムを実装し現実的な条件下で WEP キーが導出可能かどうかを導出にかかったパケット数および実行時間を計測し検証する 2

4 第 2 章 WEP 本章では無線 LAN セキュリティプロトコルである WEP とそのアルゴリズムに利用されているストリーム暗号 RC4 の概要及び WEP の脆弱性について述べる 2.1 無線 LAN 無線 LAN とは LAN と呼ばれる家庭内や施設内といった小さな規模で用いられるコンピュータネットワークのうち電波の送受信によって通信を行うものである単に無線 LAN と言った場合は IEEE 規格に準拠した機器で構成されるネットワークを指すことが多く本論文でもこの意味で用いる無線 LAN は通信ケーブルを物理的に接続する必要が無くスマートフォンやタブレット等の普及もあり一般家庭や企業のみならず公共施設や店舗など多くの場所で設置利用されている図 1: 無線 LAN 3

5 無線 LAN には通信ケーブルを物理的に接続し通信を行う有線 LAN と比べて以下のような特徴がある 1 通信ケーブルの接続が不要 2 通信速度安定性の面で劣る 3 強固なセキュリティプロトコルが必要 1のようなメリットがある反面 23のようなデメリットが存在する 2に関しては技術の進歩により有線 LAN と比べても見劣りしないレベルの品質が出るようになってきているが 3に関しては無線で通信を行う限り必ず必要な技術でありプロトコルの選択によってはセキュリティに重大な欠陥をもたらす場合がある 4

6 2.2 無線 LAN のセキュリティプロトコル無線 LAN 通信では傍受が極めて容易に行えるため送信されるパケットを暗号化し内容を知られないようにする必要があるその暗号化に利用されるのが各セキュリティプロトコルである図 2 セキュリティプロトコルこの無線 LAN のセキュリティプロトコルには様々なものがありその中の一つである WEP は今現在も多くの無線 LAN ルータに搭載され利用されている WEP の暗号化 / 復号化アルゴリズムには RC4 というストリーム暗号が用いられている以下それぞれの概要を述べる 5

2.3 RC4 RC4 とは 1987 年に Rivest によって提案されたストリーム暗号で SSL や WEP など広く利用されている [3] RC4 の内部状態は置換配列とそれに対する 2 つのポインタで構成されるなお各要素は 1 バイトの変数であるアルゴリズムは鍵スケジューリング部 KSA(Key Scheduling Algorithm) と擬似乱数生成部

7 2.3 RC4 RC4 とは 1987 年に Rivest によって提案されたストリーム暗号で SSL や WEP など広く利用されている [3] RC4 の内部状態は置換配列とそれに対する 2 つのポインタで構成されるなお各要素は 1 バイトの変数であるアルゴリズムは鍵スケジューリング部 KSA(Key Scheduling Algorithm) と擬似乱数生成部 PRGA(Pseudo Random Generation Algorithm) で構成される KSA では秘密鍵を用いて内部状態を撹拌し PRGA でその内部状態からキーストリームと呼ばれる擬似乱数列を生成する最後に平文とキーストリームの排他的論理和を取ることで暗号文を得る復号側でも同様に秘密鍵からキーストリームを生成し暗号文との排他的論理和を取ることで復号を行う図 3 RC4 6

8 KSA と PRGA のアルゴリズムの概要を以下に示す RC4 KSA: 1: For 2: 3: End for 4: 5: For 6: 7: 8: End for 図 4 KSA RC4 PRGA: 1: 2: 3: Loop 4: 5: 6: 7: 8: End loop 図 5 PRGA このように KSA PRGA はともに非常に簡潔な形で記述できるなお図中のは秘密鍵は出力するキーストリームである 7

2.4 WEP WEP とは有線同等機密 (Wired Equivalent Privacy) の略で IEEE 802.

9 2.4 WEP WEP とは有線同等機密 (Wired Equivalent Privacy) の略で IEEE b で規定されている無線 LAN セキュリティプロトコルである [5] 図 6 WEP 前述のようにその暗号化 / 復号化アルゴリズムには RC4 を用いるまた WEP には秘密鍵の長さが異なる 2 つの種類 WEP64 WEP128 が存在するが本研究ではより多く利用されている WEP128 を対象とする WEP ではパケット毎に異なる鍵 ( パケット鍵 ) を生成しこれを RC4 の秘密鍵として利用する具体的にはパケット鍵は 13 バイトの秘密鍵 (WEP キーと呼ぶ ) と 3 バイトの初期化ベクトルを用いて (1) という形でビット結合して生成するパケット鍵によって RC4 で暗号化された暗号化文は初期化ベクトルを付与して送信され受信側は受信したと WEP キーを用いてパケット鍵を生成し復号化を行う 8

10 図 7 WEP の暗号化図 8 WEP の復号化 9

2.7 WEP の脆弱性と従来の攻撃手法 WEP は提案されて以来様々な脆弱性を指摘されており多数の攻撃手法が提案実装されているがこの攻撃手法のうち多くは条件が限られてしまうもので解析が困難となる状況をつくりだすことができるものである以下に代表的な攻撃手法を 2 つあげる 2.7.1 FMS 攻撃代表的な攻撃手法に FMS 攻撃がある [1] FMS 攻撃は 2001 年に

11 2.7 WEP の脆弱性と従来の攻撃手法 WEP は提案されて以来様々な脆弱性を指摘されており多数の攻撃手法が提案実装されているがこの攻撃手法のうち多くは条件が限られてしまうもので解析が困難となる状況をつくりだすことができるものである以下に代表的な攻撃手法を 2 つあげる FMS 攻撃代表的な攻撃手法に FMS 攻撃がある [1] FMS 攻撃は 2001 年に Fluhrer らによって提案された初期化ベクトルの脆弱性を利用した攻撃手法である空間の中にはそのを利用してキーストリームを生成したとき観測したキーストリームの先頭に WEP キーの情報が大きく漏洩してしまうような値が存在しその値はと呼ばれている FMS 攻撃はこので暗号化されたパケットを大量に収集し解析することで WEP キーの導出を試みる手法である図 9 FMS 攻撃しかしこの手法はによって暗号化されたパケットのみに実行可能な攻撃手法であるためを有するパケットを大量に入手するまでに多くのパケットを観測し続ける必要があるまたを利用しないことによってこの攻撃に対して耐性を持たせることが可能である 10

2.7.2 PTW 攻撃次に代表的な攻撃手法として PTW 攻撃がある [2] PTW 攻撃は 2007 年に Tews らによって提案されたに依らず実行可能な攻撃手法である PTW 攻撃は Klein によって発表されたキーストリームから鍵を推定するという攻撃手法 (Klein 攻撃 )[3] を発展させたものである WEP キーの各バイトを並列に回復することが可能で

12 2.7.2 PTW 攻撃次に代表的な攻撃手法として PTW 攻撃がある [2] PTW 攻撃は 2007 年に Tews らによって提案されたに依らず実行可能な攻撃手法である PTW 攻撃は Klein によって発表されたキーストリームから鍵を推定するという攻撃手法 (Klein 攻撃 )[3] を発展させたものである WEP キーの各バイトを並列に回復することが可能で鍵導出を非常に高速に行える手法であるこの攻撃手法を実行する場合は平文の大部分が類推することができる ARP パケットを大量に収集し利用する図 10 PTW 攻撃実際には ARP パケットは通常の通信で用いられることは少なく大量のパケットを集めることは困難であるそのため ARP インジェクション攻撃 [6] という不正なアクセスをアクセスポイントに対して行い ARP パケットを強制的に送信させる必要があるしかし ARP インジェクションは容易に検知可能であるためこの不正アクセスを防ぐことで攻撃自体を防ぐことが可能である 11

13 2.8 今回実装する攻撃手法すでに WEP に関しては IP パケットのみを用いて比較的少ないパケットで高速に WEP キーを導出するアルゴリズムが寺村らによって提案されている [4] この攻撃手法は PTW 攻撃と同じく Klein 攻撃を発展させた攻撃手法であるが攻撃には ARP パケットではなく通常の通信で用いられる IP パケットを利用する通信を行う限り IP パケットの送受信は避けられず IP パケットのみを収集して攻撃を行うこの手法は防ぐことができない SSL と併用することや MAC アドレスフィルタリングを行うことで通信の盗聴や回線の不正利用を防ぐことはできるが WEP キー漏洩に対する根本解決にはならないしかし IP パケットは ARP パケットと違い 13,14 バイト目が固定ではなくまた容易に推定することも困難であるため後述する理由で PTW 攻撃で用いられる関数では WEP キーを導出することができない次章ではこのアルゴリズムの実際の実装方法をその問題に寺村らがどのように対処したかその手法とあわせて述べる 12

14 第 3 章実装方法本章では WEP キーを IP パケットから導出する手法 [4] の具体的な実装方法について述べる 3.1 Klein 攻撃 Klein は RC4 に対する解析を行い RC4 の内部状態とキーストリームとの間の相関を見つけそこからキーストリームから秘密鍵を確率的に導出する関数 (Klein 攻撃関数 ) を導いた [3] その式を以下に示すただしはパケット鍵はキーストリームは KSA の内部状態である (2) (3) この関数はという高い確率でパケット鍵の値と一致するとしているそのため多くのパケットを収集し投票を行うことで逐次的に鍵を導出することができる図 11 Klein 攻撃 13

15 3.2 IP パケットを用いる上での問題点 ARP パケットは先頭 15 バイトが容易に推測可能な固定値を取るためこの Klein 攻撃を用いれば逐次的にすべての WEP キーを導出する事ができる一方 IP パケットは 13,14 バイト目が固定ではなく推測も困難であるためこの手法ではキーストリームの 13,14 バイト目 ( ) が導出できずその結果パケット鍵の 14,15,16 バイト目つまりの値が導出できない図 12 IP パケットでのキーストリーム導出 14

16 この 3 バイト ( ) の全数探索を行えば WEP キー導出は可能であるが IP パケットの 15,16,18 バイト目が固定値であることを利用することでその問題を緩和することができる図 13 IP パケットの固定値及び推測可能値そのためにまず文献 [2] のアイディアを拡張して用いることで Klein 攻撃関数を以下の式に変形する (4) この式を用いることでの値を確率的に導出できるこの値を用いればの 2 バイトのみの全数探索で WEP キーを導出することができるようになる 15

17 3.3 実装方法本節ではプログラム全体の構成と各モジュールの具体的な動きについて述べる本プログラムの全体の構成は以下のようになっている図 14 本プログラムの全体の構成以下それぞれのモジュールの具体的な動きを示す 16

18 3.3.1 キーストリームの導出このモジュールでは IP パケットの固定あるいは推測可能値を用いてキーストリームの導出を行う図 15 キーストリームの導出キャプチャファイルの暗号化パケットと IP パケットの推測値との排他的論理和を取りキーストリームを取得するなお IP パケットの推測値の 13,14 バイト目はパケット長であるが WEP で暗号化を行った場合データ長は変わらないため取得したパケットの長さを取得することでそのまま値を利用できる最後にキーストリームの先頭に IV を付与してメモリに格納し終了する 17

19 3.3.2 WEP キー先頭 10 バイトの導出このモジュールではのモジュールで取得したキーストリームに対して (2) 式を適用し WEP キー先頭 10 バイトを投票で決定する (2) 図 16 WEP キー先頭 10 バイトの導出はじめにとしてすべてのキーストリームに対し (2) 式を計算するその結果適用したキーストリームの数だけキー候補が得られるためその中で最も多く出現したキーをとする同様の操作をが得られるまで逐次的に行う最後に投票テーブルの得票数の多い順にキーテーブルをソートして終了する 18

20 3.3.3 WEP キー後尾 3 バイトの探索このモジュールでは (4) 式を用いて後尾 3 バイトの和を導出しの全数探索を行いマッチングを試みるはじめに (4) 式をでそれぞれのキーストリームに対して適用しの値を計算し投票得票数一位の値をとする例えばで適用すると以下のようになるパケット鍵は 16 バイトであるためにはが適用されるがであるため両辺からを減ずることで以下の式になる同様にで適用する次にを用いての全数探索を行いマッチングを試みる ff ff ff 図 17 WEP キー後尾 3 バイトの探索マッチングが成功した場合その時の WEP キーを返して本プログラムは終了する最後までマッチングが成功しなかった場合はのモジュールを実行する 19

21 3.3.4 WEP キー先頭 10 バイトの組み合わせの試行このモジュールでは投票テーブルを用いて WEP キーの先頭 10 バイトを変更し再度のモジュールでマッチングを試みる得票率一位のキーとの得票数の差が小さいものから順にキーを変更しながらマッチングを行うなお Klein 攻撃は逐次的に値を求めているための変更によってに誤差が発生するがで発生した差をの値から減ずることで誤差を修正することができる ([4], p.168) 以下に実行例を示すキー候補 ( 得票数 ) 31(100) 32(50) 33(50) 41(100) 42(99) 43(97) 51(100) 52(50) 53(50) 61(100) 62(98) 63(50) 71(100) 72(50) 73(50) 81(100) 82(50) 83(50) 91(100) 92(50) 93(50) A1(100) A2(50) A3(50) B1(100) B2(50) B3(50) C1(100) C2(50) C3(50) 図 18 キーテーブル投票テーブルの例例として図 18 のようなキーテーブル投票テーブルが得られた場合を考える探索の前に探索したキーを記憶しておくためのという配列を生成し値をすべて 0 で初期化する最初に第一位との得票数差がと最も小さいのキーを変更するに変更が生じたための値を調整しこれを 1 回目のキーとするのキー候補をひとつ探索したためをインクリメントする ( ) 次に探索していないキーのうち第一位との得票数差が最も小さいものを探す今回の場合はでが最も小さいためこのキーを変更するに変更が生じたための値を調整し 2 回目のキーとする 20

22 またこれ以降はの値が 0 でないキー ( 探索したキー ) が存在するための変更はそのままに探索したことのあるすべてのキーをたどる今回はであるための値を変更するに変更が生じたための値を調整しこれを 3 回目のキーとする同様に操作を続けると次のような順でキーをたどることとなるなお 0 回目の部分は終了時点でのキーである (0 回目 ) A1 B1 C1 1 回目 A1 B1 C1 2 回目 A1 B1 C1 3 回目 A1 B1 C1 4 回目 A1 B1 C1 図 19 キー候補をたどる順の例 21

23 第 4 章検証結果と考察本章では本プログラムが現実的な条件下で WEP キーを導出可能であるかどうかその検証の結果を示すなお実験は以下の条件で行う 1 WEP キーは 2 タイムアウト時間を 30 秒に設定に固定現実的な条件下で導出可能かどうかの検証であるため検証用のパケットはプログラムで生成するのではなく実際にアクセスポイントを起動し通信を行うことで生成したい WEP キーを変更するとアクセスポイントの再起動や再接続などに時間がかかってしまうため 1の条件を指定する次に2についてだがまず WEP キーが見つからない場合のプログラム終了の制御に関しては以下の 2 つが考えられる試行する WEP キーの上限個数を設定する (KEY_LIMIT) タイムアウト時間を指定する (TIME_LIMIT) 本プログラムはどちらも指定することが可能だが今回はタイムアウト時間を 30 秒上限個数を無限大とした以上の条件で計 50 回の試行を行ったまた WEP キー解析には以下の PC を使用した OS Windows 7 Home Premium 32 bit (6.1, ビルド 7601) CPU Intel Core 2 Duo CPU E7500 (2.93GHz 2) メモリ 3072MB RAM 以下に検証の結果を示す 22

24 成功確率 4.1 パケット数本節では現実的に収集できる範囲のパケット数で WEP キー導出が可能かどうかを検証する実験結果のパケット数と成功確率の関係を以下のグラフに示す ,000 25,000 30,000 35,000 40,000 45,000 50,000 パケット数図 20 パケット数増加に伴う成功確率の変化今回実装した攻撃手法は所有者が対象のアクセスポイントを使って通信を行っている場合に送受信されるパケットを収集することではじめて攻撃を行うことができるつまりまったくそのアクセスポイントが使われていない場合この攻撃手法では WEP キーを導出することができないそのためあくまで対象アクセスポイントが利用されていることを前提で考察を行うパケット収集時間に関しては利用状況に応じてかなりばらつきが出るが例えば成功確率がほぼ 100% となるパケットについては早ければ数十秒から数分長くても 10 分程度の時間で収集可能であるつまり長くても 10 分程度あれば WEP キー導出ができると考える事ができる結果として対象アクセスポイントが利用されていることを前提とするならばこの手法は現実的に収集できる範囲のパケット数で WEP キーを導出可能であるといえる 23

25 実行時間 [ms] 4.2 実行時間本節ではパケット数増加に伴う実行時間の変化について考察するなお今回はタイムアウト時間を 30 秒と設定しており人が十分に待つことのできる時間であるため実行時間に関しては現実的な条件下という要件を満たしているものとする実験結果のパケット数と実行時間の関係を以下のグラフに示す中央値最小値 ,000 25,000 30,000 35,000 40,000 45,000 50,000 パケット数図 21 パケット数増加に伴う実行時間の変化タイムアウト時間を設ける必要があるため成功した試行のみのデータであり分母はパケット数によって異なるまた測定の結果外れ値が出たため平均値ではなく中央値を提示するパケット数が少ない段階では安定せず値が上下しているがパケット数が多くなると安定して速い速度で実行できている特にパケット数がを超えると最小値とほぼ同じ値が安定して出ていることから第一位のキーでマッチングが成功しのモジュールを実行せずに終了しているものと考えられるなおその場合はパケット数に比例した一定時間で完了する 24

26 第 5 章今後の課題本章では今回時間の都合上実装できなかった仕様や実施できなかった実験等について今後の課題として述べる 5.1 パケット収集と WEP キー解析を並行して実行するように改良パケットを収集しながら WEP キー解析を行うことができれば導出までの過程を単純化高速化することができる 5.2 複数の WEP キーに対して同様に導出が行えるかを検証 WEP キーを変更しての検証がほぼ行えていないため課題としてあげられるなお多数の WEP キーを設定して実験を行う場合プログラムで暗号化パケットを生成する方が効率的である 5.3 試行回数を増加試行回数が 50 回と少ないため大量の検証用パケットを入手し実験を行う必要があるその場合 5.2 と同様プログラムで暗号化パケットを生成する方法が効率的である 5.4 パケット数実行時間の定量的な評価現実的な条件下で導出が行えるという抽象的な評価しかできていないため統計の分野も踏まえて定量的な評価を行う必要がある 25

27 謝辞本研究を進めるにあたり最後まで熱心に御指導して頂きました田中章司郎教授には心より御礼申し上げます同研究室の皆様にも数々の御協力と御助言を頂きましたこと厚く御礼申し上げますなお本論文本研究で作成したプログラム及びデータ並びに関連する発表資料等の全ての知的財産権を本研究の指導教官の田中章司郎教授に譲渡致します 26

28 引用参考文献 [1] S. Fluhrer, I. Mntin, and A. Shamir, Weaknesses in the Key Scheduling Algorithm of RC4, SAC2001, Lecture Notes In Computer Science, Vol. 2259, pp.1-24, Springer-Verlag, [2] E. Tews, R. Weinmann, and A. Pyshkin, Breaking 104 bit WEP in less than 60 seconds, WISA2007, Lecture Notes in Computer Science, Vol.4867, pp , Springer-Verlag, [3] A. Klein, Attacks on the RC4 stream cipher, Designs, Codes and Cryptography, Vol.48, no.3, pp , Sep [4] R. Teramura, Y. Asakura, T. Ohigashi, H. Kuwakado, and M. Morii, Fast WEP-Key Recovery Attack Using Only Encrypted IP Packet, IEICE Trans. on Fundamentals of Electronics, Comm. And Computer Science, Vol. E93-A, no.1, pp , Jan [5] IEEE Computer Society, Wireless lan medium access control (MAC) and physical layer (PHY) specifications IEEE std , 1999 [6] The Aircrack-NG Team, Aircrack-ng 27

AirStationPro初期設定

AirStationPro初期設定 AirStationPro 初期設定 AirStationPro の検索 1. エアステーション設定ツール Ver.2 を立ち上げて次へをクリックする注 ) エアステーション設定ツール Ver.2 は製品に付属している CD からインストールするか http://buffalo.jp/do wnload/driver/lan/ai rnavilite.html にあるエアナビゲータライト Ver.12.71

無線 LAN 暗号化方式 WEP の秘密鍵を IP パケットから高速に導出する手法の実装と検証 島根大学総合理工学部数理 情報システム学科 応用情報学講座田中研究室 S 前田恒太 平成 26 年 2 月 3 日

無線 LAN 暗号化方式 WEP の秘密鍵を IP パケットから高速に導出する手法の実装と検証島根大学総合理工学部数理情報システム学科応用情報学講座田中研究室 S 前田恒太平成 26 年 2 月 3 日