[-]=======================================================================[-] Wizard Bible vol.35 (2007,8,14) [-]=======================================================================[-] x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第0章:目次 --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○第1章: マニアックJavaプログラミング第6回: 〜 Javaでメタプログラミング 〜 金床 著 ○第2章: Windowsシステムプログラミング Part1 〜イントロダクション〜 Kenji Aiko 著 ○第3章: Quick Beのメモリーリーク修正&Vista対応パッチの作成 Will 著 ○第4章: 基礎暗号学講座 〜 第11回 〜 IPUSIRON 著 ○第5章: お知らせ ○第6章: 著者プロフィール x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第1章: マニアックJavaプログラミング第6回: 〜 Javaでメタプログラミング 〜 --- 著者:金床 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに  アプリケーション内で動的にコードを生成し、さらにそれを実行したい場合が ある。このようにプログラムが動的にプログラムを生成し実行するようにプログ ラムをプログラムすることをメタプログラミングとよぶ。 ■0x02.) コードの生成  さてメタプログラミングは「コードの生成」と「コードの実行」から成り立つ わけだが、「コードの生成」は単なる文字列処理である。例えば次の例は立派に コードを生成している。 ----- System.out.println( "System.out.println( \"hoge\" )" ); -----  うわ、ただ文字列を出力するだけなのにSystem.outとか打つのって鬱じゃね? しかもダブルクオートをエスケープしたりして超読みにくくね?ヒアドキュメン ト無いとかありえなくね?Javaちょっとダサくね?いやむしろかなりダサくね?  などとちょっとでも思ったキミはボクとはトモダチになれないと思うので、次 の記事に飛んでくだちい。  ということで「コードの生成」は普段プログラマーが自分で打ち込んでいるソ ースコードをプログラム自体に出力させるだけなので、用途によって適切なルー チンを組むだけで完成する。ここでは特に難しいことはない。 ■0x03.) コードの実行  問題は生成したコードの実行なのである。  …は?  …つか、eval呼ぶだけじゃね?まさかJavaにはeval無いとか?ちょwwwそれって ありえなくね?  などと少しでも脳裏をかすめたキミはCIAに洗脳されているか、あるいは脳内麻 薬の出過ぎでオーバードーズ気味になっていると思われるので、今すぐ水分をた っぷりとって休養すること。  そんなわけでJavaにはevalがない(涙)ので、動的にコードを実行するには一 工夫必要となる。というか実行の前にコンパイルしなくてはならない。今回は隠 れAPIとして一部のマニアに知られている、Javaソースコードのコンパイル機能を 利用してみることにする。 ■0x04.) tools.jar  SunのJDKをダウンロードして使用している場合には、libの下にtools.jarとい うファイルがあるはずだ。これはJavaのソースファイルをコンパイルするコマン ドであるjavacから使われるものである。これを勝手に自分のJavaアプリ内から呼 んでしまうのだ。  コンパイルで必要になるのはtools.jarの中に格納されているcom.sun.tools.j avac.Mainというクラスである。このクラスのcompileというメソッド(そのまん まの名前である)を呼び出すことでJavaのソースコードがコンパイルされ、クラ スファイルが生成される。  もちろんRuntime.execなどを使ってjavacコマンドを別のプロセスとして立ち上 げる方法でもコンパイルはできるのだが、このクラスを直接呼び出すことでパフ ォーマンス的に有利となる(javacコマンドはJVMを起動するため、実際のコンパ イルよりも前の処理でたくさんのCPUサイクルを消費する)。 ■0x05.) javaShell  それではJavaアプリ内部で動的にソースコードをコンパイルすることにより、 インタラクティブにJavaのコードを実行する、いわばJavaのシェルのようなアプ リケーションを作ってみることにする。ソースコードは次のURLからダウンロード できる。 http://src.jumperz.net/javaShell.java  このアプリケーションを開始すると、標準入力からJavaソースコードの入力を 行うことができるようになる。空行を打ち込むとそこまでに入力したJavaソース コードが内部でコンパイルされて実行される。  例えば画面に「patch Kenji」と出力するためには次のようにする。 ----- [anvil@supernova ~]# java javaShell ← javaShellを起動 System.out.println( "patch Kenji" ); ← Javaのソースコードを打ち込む                    ← 空行を打ち込む patch Kenji              ←コードが実行される -----  複数行に渡ってソースコードを打ち込むこともできる。例えば「1234+2222」を 計算したい場合には次のようにする。 ----- int a = 1234; int b = 2222; System.out.println( a + b ); 3456  ←コードが実行される -----  このプロセスを好きなだけ繰り返すことができる。シェルから抜けるには「qu it」あるいは「exit」と打ち込む。 ■0x06.) ソースコード解説  それではお待ちかねのソースコード解説である。 ----- String javaHome = System.getProperty( "java.home" ); -----  まず環境変数java.homeを取得し、現在実行中のJREのホームディレクトリを取 得する。 ----- File tools = new File( javaHome + "/../lib/tools.jar" ); if( !tools.exists() ) { System.out.println( "tools.jar not found." ); return; } -----  JDKがインストールされている場合には、tools.jarはJREのひとつ上の階層のl ibディレクトリ以下にある。このファイルが見つからない場合にはjavaShellは動 作しないので、エラーメッセージを出力して終了する。 ----- String classStr = "public class otf { public String toString() { try { CODE } catch( Throwable e ) { e.printStackTrace(); } return \"\"; } }"; -----  この文字列は動的に生成されるクラスファイルの元になる文字列である。整形 すると次のようになる。 ----- public class otf { //----------------------------- public String toString() { try { CODE } catch( Throwable e ) { e.printStackTrace(); } return ""; } //----------------------------- } -----  「CODE」の部分にユーザが入力したコードが挿入され、実行されることになる。 toStringを利用しているのは単なる手抜きである(これがなぜ手抜きになるのか については後ほど触れる)。  続いてユーザからの入力を逐次受け取るためのループが開始される。while周辺 についてはお決まりなので説明は省略する。 ----- if( line == null || line.equalsIgnoreCase( "quit" ) || line.equalsIgnoreCase( "exit" ) ) { break; } -----  これによりユーザが「quit」あるいは「exit」を入力した場合(あるいは標準 入力が閉じられた場合)にループから抜けることになる。 ----- else if( line.equals( "" ) ) { exec( classStr, buf.toString() ); buf = new StringBuffer(); } -----  ユーザが空行を入力した場合、クラスファイルの元となる文字列classStrと、 その時点までに入力されたJavaソースコードを保持しているインスタンスのbufを 文字列型に変換したものをexec関数に渡す。  exec関数内ではいよいよJavaの動的コンパイルと実行が行われる。 ----- //Generate java source String className = "otf_" + System.currentTimeMillis(); String javaFileName = className + ".java"; classStr = replaceAll( classStr, "CODE", userStr ); classStr = replaceAll( classStr, "public class otf", "public class " + className ); saveStringToFile( classStr, javaFileName ); -----  動的に生成したクラスは毎回使い捨てる。そのため毎回別のクラス名が必要と なる。ここでは現在時刻をミリ秒単位で取得しそれを使ってクラス名を決定する。 例えばクラス名は「otf_118663679990」のようになる。ちなみに「otf」はオンザ フライ、つまりフライの上にのっているマヨネーズなどのことを指している。マ ヨネーズは油の固まりなので、メタボなキミは食べちゃダメだぞ。  replaceAllというのはただの文字列置換関数である。つまり「CODE」の部分を 「System.out.println( "patch Kenji" );」のようなユーザが入力したソースコ ードに、そしてクラス名の部分を「public class otf」から「public class otf _118663679990」のように変換している。変換後の文字列は正しいファイル名で (つまりotf_118663679990.javaのようにクラス名と対応したファイル名で)保存 する。  続いてコンパイルを行う。tools.jarは通常はJREからは見えない位置にあるた め、自動的にクラスのロードを行うことができない。そこでローカルなクラスロ ーダを作成する。クラスファイルが格納されているjarファイル(tools.jarのこ と)はわかっているので、file:のURLを与えてURLClassLoaderを作成する。 ----- String javaHome = System.getProperty( "java.home" ); File tools = new File( javaHome + "/../lib/tools.jar" ); String toolsFileName = tools.getCanonicalPath(); URL toolsURL = new URL( "file:" + toolsFileName ); URLClassLoader cl = new URLClassLoader( new URL[]{ toolsURL } ); -----  そして目的であるMainクラスをロードする。 ----- Class javac = cl.loadClass( "com.sun.tools.javac.Main" ); -----  実はソースコード中に ----- com.sun.tools.javac.Main javac = ... -----  とするコーディングも可能なのだが、この場合にはjavaShell.javaのコンパイ ルの際にクラスパスとしてtools.jarを与える必要がある。これは面倒なので、今 回はリフレクションを用いている。これにより「javac javaShell.java」だけで コンパイルすることが可能となっている。  リフレクションを用いているため、Mainクラスのcompileメソッドの呼び出しは 次のようにMethodクラスを用いて行う。 ----- Method m = javac.getDeclaredMethod( "compile", new Class[]{ String[].class } ); String[] args = new String[]{ javaFileName }; Object result = m.invoke( null, new Object[]{ args } ); -----  これによってコンパイルが開始される。エラーがある場合にはエラー出力にエ ラーメッセージなどが出力される。コンパイルが成功した場合には0が返される。 ----- if( resultInt != 0 ) { System.out.println( "Compilation error." ); return; } -----  コンパイルがエラーになった場合にはコードを実行せず、関数を抜ける。  コンパイルが成功した場合には、次のように動的に生成したクラス(「otf_11 8663679990.class」など)をロードし、newInstanceを使ってインスタンスを生成 する。 ----- //Execute Class otfClass = cl.loadClass( className ); Object o = otfClass.newInstance(); -----  コードを実行するためにただ単にtoStringを呼び出す。toStringはObjectクラ スに備わっているものなので、ここではリフレクションなどのややこしい手間を かけずに動的に生成されたクラスのメソッドを実行することができる。非常にひ ねくれた形のポリモーフィズムの利用だと言えるだろう。 ----- o.toString(); -----  言うまでもないがこのコードはネタなので、会社で書かないようにしていただ きたい(コンストラクタでもできる気がするが、試していない)。ソースコード の解説は以上である。 ■0x07.) まとめ  今回はjavacが使っている隠れAPIを使い、さらにクラスを使い捨てることでJa vaで動的にソースコードを扱う例について説明をおこなった。実際の開発でも( デザインパターンの)Factoryメソッドなどと組み合わせることで面白いことがで きるだろう。  筆者は実際にこのテクニックを使い、設定ファイルの記述にそのままJavaを使 うということをやっている。これによって設定ファイル中でif文などによる条件 分岐などが非常に簡単に記述できるようになった。  ちなみにJavaでのメタプログラミングに興味のある人はjavassistを試してみる ことをおすすめする。こちらはかなり洗練されたインターフェースで動的にクラ スの中身を書き換えることができる面白いライブラリだ。使い捨てではできない こともこちらでは可能となるだろう。  また、さらに深く潜りたいキミはJavaバイトコードを勉強するとよいだろう( 筆者はめんどくさいので勉強してません…スマン○(自主規制)) x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第2章: Windowsシステムプログラミング Part1 〜イントロダクション〜 --- 著者:Kenji Aiko x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに  このテキストは、Windowsシステムに関するプログラミングを中心に記述してい る。他プロセスへのコード注入、APIフック、サービス制御マネージャ、カーネル レベルプログラミング、任意のコードの隠蔽などを中心に解説している。 ■0x02.) 任意のコードを別のプロセスへ注入する方法  http://www.codeproject.com/threads/winspy.asp  上記のサイトには「任意のコードを別のプロセスへ注入する方法」として、3つ の手法が紹介されている。 1.SetWindowsHookExを用いてグローバルフックし他プロセスへDLLをマッピング 2.CreateRemoteThreadとLoadLibraryを使い他プロセスへDLLをマッピング 3.CreateRemoteThreadとWriteProcessMemoryを使い他プロセスへコードを注入  1と2に関しては、任意のコードをDLLとして用意し、そのDLLを他プロセスへマ ッピングすることにより、目的を実現している。3に関しては、DLLとしては用意 せず、他のプロセスにコードを割り込ませるためのメモリ領域を確保させ、その 領域に、こちらが用意したコードを注入し実行させることにより、目的を実現し ている。  2に関しては「常駐プログラム隠蔽テクニック」にて、3に関しては「KeyLogge rとプロセス隠蔽についてのまとめ」にて詳細を紹介している。  常駐プログラム隠蔽テクニック  http://ruffnex.oc.to/kenji/text/dll_inj/  KeyLoggerとプロセス隠蔽についてのまとめ  http://ruffnex.oc.to/kenji/thekeylogger/keyLoggerTH.cpp ■0x03.) APIフックからのアプローチ  任意のコードを別のプロセスへ注入するテクニックは、IAT書き換えによるAPI フックのテクニックと似ている。APIフックにも様々なアプローチが存在するが、 SetWindowsHookExを用いて他のプロセスへDLLをマッピングさせ、そのDLL内部で フック処理(IATを書き換える処理)を実行することで、APIの監視を実現するテ クニックがある。これについては、Jeffrey Richter氏の著書「Advanced Window s」にて、詳細に記述されている(ただし「Advanced Windows」に書かれているテ クニックは、Windows 2000までを対象としているため、XP以降では少々プログラ ムを変更する必要があるかもしれない)。  また、私も「Windows API Hooking Tutorial」にて簡単な解説をしている。  Windows API Hooking Tutorial  http://ruffnex.oc.to/kenji/text/api_hook/  「プロセスを隠蔽する」という目的においても、APIフックはなかなかの効果を 発揮する。例えば、ネイティブAPIであるNtQuerySystemInformationをフックする ことで、任意のプロセスを隠蔽できる。実証コードは以下。  http://ruffnex.oc.to/kenji/win/HideProcess.zip  このテクニックを使えば、タスクマネージャやプロセス列挙APIからは完全に隠 れる。ただし、SetWindowsHookExを用いたAPIフックを使っているため、全プロセ スにDLLが注入されている。つまり、どんなDLLを利用しているのかを調べれば簡 単に特定できる。デバッガを起動し、現在起動中の適当なプログラムにアタッチ してインポートしているDLLを調べれば、APIフックを行っているコード(DLL)を 発見できる。  NtQuerySystemInformationをフックしてプロセスを隠蔽するというアプローチ を、カーネルモードで実装することもできる。カーネルモードでのAPIフックは、 ユーザモードとは違ったテクニックが必要となるが、カーネルモード(ドライバ) でNtQuerySystemInformationをフックし、任意のプロセスを隠蔽すれば、DLLを使 用していない以上、ユーザランドから、隠蔽を行っているプログラムを特定する のは困難になる。  ドライバからのプロセス隠蔽については、私のブログにて、sp氏がコメントし てくれた。sp氏が書いた実証コードは以下。  http://sp-.up.seesaa.net/image/Mizinger_SRC.zip  これはとても面白いコードである。  ぜひとも一度読んでみてほしい(sp氏thax!)。 ■0x04.) サービスプロセス  プロセスを隠すという意味では、サービスプロセスとして登録するのもひとつ の方法かもしれない。Windows 9x系ならば、以下のコードで、プロセスをサービ スプロセスとして登録できる。 ----- Windows 9x系でのサービス登録 HMODULE hKernel32 = GetModuleHandle(_T("kernel32")); typedef DWORD (WINAPI *REGISTERSERVICEPROCESS)(DWORD, DWORD); REGISTERSERVICEPROCESS RSProcess = (REGISTERSERVICEPROCESS) GetProcAddress(hKernel32, "RegisterServiceProcess"); if( ! RSProcess ) return(-1); RSProcess(NULL, 1); -----  Windows 2000以降では、サービス制御マネージャを使うことで、サービス登録 ができる。サービス制御マネージャについては、常岡伸二氏の著書「スタンダー ド Visual C++」にその詳細が書かれている。  Windows 9x系でのサービス登録については以下のサイトが参考になるだろう。  http://www7a.biglobe.ne.jp/~tsuneoka/win32sub/8.html  サービスプロセスとして稼動させたら、少なくともタスクマネージャからは見 えなくなる。しかし、サービス自体は、Windowsが提供しているインターフェース であるため、それほどテクニカルではない。あくまでも方法のひとつということ だ。 ■0x05.) カーネルレベルからのアプローチ  「任意のコードを隠す」ということに重点を置けば、ドライバを作成した方が よい。ユーザモードで動作するプログラムは、すべて「プロセス」という形でOS から完全に管理されるため、隠すためには、サービスとして動作させるか、コー ドを他のプロセスへ入れるしかない。しかし、カーネルレベルならば、その制限 はかなり緩くなるため、また、違ったアプローチを取れる。  カーネルモジュールを参照するには、「Device Tree」や「WinObj」また「Ice Sword」といったソフトが必要だが、少なくとも一般的に使用されているWindows に、これらのソフトがインストールされているとは思えない。それだけでも隠蔽 するという意味では、ポイントが高い。しかし、なるべくならこれらのツールで も確認できない方がよいだろう。そのために、カーネルレベルでの隠蔽工作が必 要となる。  もっとも有名なテクニックは、カーネル内に存在するモジュールリストの読み 飛ばしだ。カーネル空間には、現在動作中のドライバの数だけ、モジュールのエ ントリ情報が存在する。エントリとは、モジュールの情報が格納される領域のこ とで、例えば、読み込んだドライバのファイル名や、ファイルパス、それに読み 込んだ先のメモリアドレスなどが記憶される。  ドライバが読み込まれるごとに、その読み込まれたドライバのモジュール情報 が、エントリとして追加され、逆に、ドライバがメモリから解放されたら、エン トリも削除される。そして、エントリ情報は、Windowsが一括管理しやすいよう、 連結リスト構造になっている。  モジュールエントリには、次のエントリへのアドレス(Flink)と、前のエント リへのアドレス(Blink)が記されており、DriverEntry関数の引数として渡され るDRIVER_OBJECT構造体から、自分自身のエントリアドレスが取得できる。つまり、 自分のエントリを出発点として、これらを左右に辿ることで、すべてのエントリ を参照できる。  この連結リストの中から、任意のドライバプログラムのエントリを外せば、そ のドライバプログラムに対して、システムからアクセスできなくなる。  この方法により、「IceSword」からの閲覧を拒否できる。  エントリ情報を格納すべき構造体を次に示す。ちなみに、モジュールのエント リ情報は非公開のものであり、マイクロソフトから正式な定義を提示されたわけ ではないため、内容に差異があるかもしれない。 ----- typedef struct _module_entry { LIST_ENTRY list; // モジュールリスト DWORD unknown1[4]; DWORD base; DWORD driver_start; DWORD unknown2; UNICODE_STRING path; // システムファイルパス UNICODE_STRING name; // ドライバ名 } MODULE_ENTRY, *PMODULE_ENTRY; -----  最初のLIST_ENTRY構造体内部にて、左右のエントリのアドレスが格納されてる。 また、システムファイルのパスとドライバ名もある。他の部分は推測だが、読み 込まれたメモリのベースアドレスやエントリポイントなどの領域もあると考えら れる。  ただし、重要なことは、このエントリ情報の内容ではなく、エントリそのもの を書き換えること。自身のエントリから、左右のエントリを書き換え、自身を隠 すコードを考える。 ----- driverData = *((MODULE_ENTRY **)((DWORD)pDriverObject + 20)); if(driverData != NULL){ *((PDWORD)driverData->list.Blink) = (DWORD) driverData->list.Flink; driverData->list.Flink->Blink = driverData->list.Blink; } -----  最初に、自身のエントリのアドレスを、DRIVER_OBJECT(pDriverObject)から もらい、そのエントリアドレスをdriverDataとする。そして、まずは自身のエン トリのLIST_ENTRYを参照し、その「Flink(次)のアドレス」を、自身の「Blink (前)が指す先」に代入する。これで、自分の前のエントリは、自分の先のエン トリを指すことになる。次に、自分の先のエントリのBlink(前)の値を、自分の 前のエントリの値に変更する。これで、連結エントリから自分が排除されたこと になる。  これにより、この連結エントリを辿ることでカーネルモジュールを参照する手 法をとっているプログラムからは、自身を隠蔽できる。 参考:Phrack 62(http://www.trust-us.ch/phrack/show.php@p=62&a=12) ■0x06.) 非公開APIからのアプローチ  非公開APIであるZwSetSystemInformationを使えば、ドライバプログラムをいと も簡単に隠蔽できる。  ZwSetSystemInformationは、ntdll.dll内に存在するが、マイクロソフトからの 正式なドキュメントが存在しないため、非公開APIとなっている。よって、使用す るためには引数や戻り値を推測するしかないが、デバッガで関数内を追っていけ ば、ある程度は使い方を理解できる。  このAPIはなかなか優秀で、大抵のカーネルモジュール列挙プログラムから、そ の存在を知られることなく動作させることができる。私が確認した限りでは、「 Device Tree」と「WinObj」では見ることができなかった。  このAPIの実証コードは以下に公開されている。  http://www.rit.edu/~jrk9185/rootkit/3/ ■0x07.) さいごに  ここで紹介したテクニックは、どれも数年前までは、ユニークで興味深いもの だったが、現在では、当たり前に知っておかなければならないものばかりになっ てしまった。少なくともWindowsシステムに精通している人間ならば、ほとんど知 っている情報だったと思う。  今回はイントロダクションとして、当たり前のテクニックを紹介するだけに留 まったが、今後はこれらの技術を元に、もう少し進んだテクニックの解析へ進め ていきたいと思う。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第3章: Quick Beのメモリーリーク修正&Vista対応パッチの作成 --- 著者:Will x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに  今回はブログで少し書いたQuick Beのメモリーリークについて詳しくとまでは いきませんが、その修正方法について書いてみました。Vistaでなくてもエラーの 検出はできるのですが、Vistaの方がわかりやすいということで今回についてはV ista環境を想定しています。  なお、必要な物として以下のソフトウェアが必要です。OllyDbgについてはすで に日本語化済みとして話しを進めます。 ・OllyDbg http://www.ollydbg.de/ ・Quick Be Build 011 http://cowscorpion.com/file/QuickBe.html ■0x02.) Quick Beとは  krackをしている人ならば知らない人はいないと思いますが、Quick Beはいわゆ る、日本ではバイナリエディタ、海外ではhexadecimal editorなどと呼ばれてい るソフトウェアです。 ■0x03.) なぜ修正するのか?  Windows Vista上でQuick Beを動作させた場合「パッチファイル実行」の「書き 換えるファイルが存在するフォルダ」を選択すると落ちてしまいます。他のWind owsでは落ちはしませんが、以下の様なログを残します。 ----- メッセージ=デバッグ文字列: Invalid Address specified to RtlFreeHeap( 130000, 7d08e150 ) -----  というわけで自分で修正してみましょう。 ■0x04.) 修正 (注意)以下の作業はVistaで行います。  まず、OllyDbgでQuick Beを開き、実行させます。そしてフォルダを選択すると ntdllの中で一時停止し、さらに進めると終了してしまいます。というわけで再ス タートし、トレース実行を行います。再びフォルダを選択し、停止したところで ラントレースを見ます。  ntdllに入る前に実行されたのが、次の命令だとわかります。 ----- 0040E185 FF15 30564100 CALL NEAR DWORD PTR DS:[<&ole32.CoTaskMe>; ole32.CoTaskMemFree -----  この関数が原因なのです。  そして、これのどこが駄目なのかというとその前のPUSH EAXです。本来ならば SHBrowseForFolderの戻り値を引数にして呼び出す必要があるのですが、SHGetPa thFromIDListを呼び出す前に戻り値を退避させていないので、その戻り値で上書 きされています。というわけで修正したいのですが、かなり詰まっています。空 いてる所にジャンプしてから修正するのがいいかも知れませんが、今回はパッチ 数を減らす方向で修正しましょう。  そういう訳でエラー処理の ----- TEST EAX,EAX JE 0040E9AF ----- を消して使うことにします。  上記のコードを ----- MOV DWORD PTR SS:[ESP+14],EAX ----- に変更します。  後はファイルに保存するだけです。  以上でQuick Beの修正は終わりです。 ■0x05.) 駄文  時間はあるけどネタがないということで、再度しょぼい文章を書かしていただ きましたw。今度出す時はもう少しましなことを書きたいと思います。と思い続 けて最早不可能だと気づきました。  ではでは。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第4章: 基礎暗号学講座 〜 第11回 〜 --- 著者:IPUSIRON x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに  今までのWBではElGamal暗号(WB32)やRSA暗号(WB34)について解説しました。 こうした暗号における鍵生成アルゴリズム・暗号化アルゴリズム・復号アルゴリ ズムなどでは、「乱数を選択」「modの計算」「巨大な数の累乗計算」などといっ た暗号特有のアルゴリズムが行われていた。こうした暗号特有のアルゴリズムを 素朴に実装しようとすると効率が悪いことがある。場合によっては、暗号の安全 性さえも揺るがしてしまうことになってしまう。こうした問題に対して、効率の よいアルゴリズムがすでに数学ライブラリに収録されていたりする。実際に暗号 を実装するときには、そうしたライブラリ内の関数を利用すればよいだろう。こ こではアルゴリズムの動きをトレースすることによって、より数学的理解を深め ることを目的とする。  「暗号化・復号に必要な数学的作業」と「それに使われるアルゴリズム」の対 応表を次に示す。 --------------------------------------------------------------------- | 目的 | アルゴリズム | |----------------------------------------+--------------------------| | a,bの最大公約数GCD(a,b)を求める | ユークリッドの互除法 | | ax+by=GCD(a,b)を満たす(a,b)を求める | 拡張ユークリッドの互除法 | | ay≡1 (mod n)を満たす乗法逆元yを求める | 今回解説予定 | | 原始元の生成・判定 | 次回解説予定 | | 安全な乱数の生成 | 擬似乱数生成器(PRG) | | べき乗計算 | 今回解説予定 | | 素数の生成・判定 | Miller-Rabin法 | | 連立合同方程式を解く | 中国人剰余定理(CRT) | | ハッシュ値の計算 | ハッシュ関数 | ---------------------------------------------------------------------  今回の記事では「乗法逆元を求めるアルゴリズム」と「べき乗計算のアルゴリ ズム」について解説する。 ■0x02.) 乗法逆元を求めるアルゴリズム  乗法逆元を求める前に、いつも乗法逆元が存在するかどうかが心配である。こ の心配事を解決するために、いくつか数学的事実を見ていく必要がある。  まず、乗法逆元が存在する条件として、次の数学的事実がある。 [定理]35.1 「ay≡1 (mod N)を満たすyが存在する」⇔「GCD(N,a)=1」  合同式や最大公約数について忘れてしまった方はきちんと復習しておいて欲し いが、ここでは簡単に⇔の左右の意味について解説しておく。左辺は「ay-1がNの 倍数となるyが存在する」という意味である。即ち「ayをNで割った余りが1となる ようなyが存在する」という意味である。一方、右辺は「Nとaの最大公約数は1」 という意味である。即ち「Nとaは互いに素」という意味である。  次に「⇔」という記号(同値記号)の意味は、「左辺が成り立つならば、右辺 が成り立つ」かつ「右辺が成り立つならば、左辺が成り立つ」ということである。  よって、定理の全体的な意味は「ayをNで割った余りが1となるようなyが存在す るときは、Nとaが互いに素であるときに限る」ということになる。  実際に数値例で確認してみる。N=10,a=7で考える。この2つは互いに素である。 このとき、7y≡1 (mod 10)を満たすyが存在するだろうか。ここでは、素朴に総当 りでyに値を入力してみる。 ・y=1のとき、(左辺)=7×1=7≠1=(右辺) ・y=2のとき、(左辺)=7×2=14≡4 (mod 10)≠1=(右辺) ・y=3のとき、(左辺)=7×3=21≡1 (mod 10)=(右辺) ←一致している! ・y=4のとき、(左辺)=7×4=28≡8 (mod 10)≠1=(右辺) ・y=5のとき、(左辺)=7×5=35≡5 (mod 10)≠1=(右辺) ・y=6のとき、(左辺)=7×6=42≡2 (mod 10)≠1=(右辺) ・y=7のとき、(左辺)=7×7=49≡9 (mod 10)≠1=(右辺) ・y=8のとき、(左辺)=7×8=56≡6 (mod 10)≠1=(右辺) ・y=9のとき、(左辺)=7×9=14≡4 (mod 10)≠1=(右辺) ・y=10のとき、(左辺)=7×10=70≡0 (mod 10)≠1=(右辺)  y=3のときに、左辺と右辺が一致することが確認できた。つまり、答えはy=3で ある。  この定理が一般的で成り立つことを証明しておく。アルゴリズムだけに興味の ある方は証明は軽く読み流してもらって構わない。 [証明] 「GCD(N,a)=1」 ⇔「∃x,y∈Z;Nx+ay=1」 ⇔「ay≡1 (mod N)」 □  [定理]35.1より、N=p(素数)のときには、ゼロを除くすべての要素に対して乗 法逆元が存在することがわかる。このことは、mod pの世界のいては、加算・減算 ・乗算に加えて除算さえも自由に行えるということである。このように四則演算 が自由に行える世界を体と呼ぶ。  この事実はとても重要である。そのため、暗号の世界では、しばしばmod pの世 界で考えることが多い。  最後にきちんと定理としてまとめておこう。証明は明らかなので省略する。 [定理]35.2 pが素数とする。このとき、任意のa∈{1,…,p-1}に対して、乗法逆元a^(-1) mod pが存在する。  以上の2つの定理より、mod pの世界を持ち出せば、最初の心配事は払拭するこ とがわかる。それでは乗法逆元を求めるアルゴリズムを紹介する。アルゴリズム なのでまず入出力を明確にしておく。 ・入力:整数a,N(ただしN>0) ・出力:整数a^(-1) mod N or「逆元は存在しない」というメッセージ  アルゴリズムのコードは次の通りである(行列の形で書ければ見た目はすっき りする)。floor(・)は引数を小数点切り捨てする関数とする。 ----- d0←a, x0←1 d1←N, x1←0 while(d1≠0){ d0←d1, x0←x1 d1←d0-floor(d0/d1)×d1, x1←x0-floor(d0/d1)×x1 } if d0=1 then return a^(-1)=x0 mod N else return 「逆元は存在しない」 ----- ■0x03.) べき乗計算のアルゴリズム  べき乗計算とは、「a,xが与えられたときにy=a^xを求める」計算である。累乗 に相当するxが大きければ大きいほど、必要な掛け算が膨大になってしまう。素朴 にやろうとすると(x-1)回の計算が必要である。例えば、3^5を素朴にべき乗計 算すると、3×3×3×3×3を計算する。×の個数が4回(=5-1)なので、4回の掛 け算が必要ということである。暗号で使われている世界ではxが200桁ぐらいにな ってしまうので、この素朴な計算では時間がかかりすぎる。  計算量の説明をすると、x-1≒2^κが成り立つので、指数時間がかかってしまう。 これでは多項式時間の計算しかできないアルゴリズムでは歯が立たない。つまり 素朴な計算では効率が悪すぎるということである。  そこで、y=a^x mod Nを効率よく計算する方法を考える必要がある。  まず数値例から考えていく。3^20を計算したいとする。素朴な方法で計算する と、19回の乗算をすることになる。ところが、3^20は次のように計算することも できる。 ((((3^2)^2)×3)^2)^2  2乗しているところで乗算は1回(2^3は3×3だから)、「×」のところで乗算は 1回とカウントできるので、この計算ではたった5回で計算できてしまう。  このような展開の計算と同様なことがアルゴリズムでも実現できる。アルゴリ ズムで考えると初期段階などの処理が必要なので、5回ではなく7回の乗算が必要 となる。それでも素朴な方法による19回の乗算よりははるかに効率がよい。それ ではアルゴリズムの基本的な考え方について解説する。  まず、modの世界ではなく、普通にy=a^xを計算したいとする(a,xは正の整数)。 このとき次のように処理していく。 [Ⅰ]yに対して、y←1と初期値を代入する。 [Ⅱ]xの2進ビットパターンを上位ビットから1ビットずつ見ていき、各ビットに対 して次の処理を実行する。  (2.1)まずyを2乗する。即ちy←y×y  (2.2)そのビットが1ならば、さらにxを掛ける。即ちy←y×x  この処理で、y=3^20を計算してみる(a=3,x=30)。 [Ⅰ]y=1 [Ⅱ]20の2進数は10100である。  [1]一番左のビット1に対して、   (2.1)y=y×y=1×1=1 ←(=3^0)   (2.2)y=y×a=1×3=3 ←(=3^1)  [2]左から2番目のビット0に対して、   (2.1)y=y×y=3×3=9 ←(=3^2)  [3]左から3番目のビット1に対して、   (2.1)y=y×y=9×9=81 ←(=3^4)   (2.2)y=y×a=81×3=243 ←(=3^5)  [4]左から4番目のビット0に対して、   (2.1)y=y×y=243×243=59,049 ←(=3^10)  [5]左から5番目のビット0に対して、   (2.1)y=y×y=59,049×59,049=3,486,784,401 ←(=3^20)  「×」は合計7回登場していることがわかる(括弧の数と対応)。例えば、2進 ビットパターンが最大5桁の場合は最悪でも10回の乗算で済むということがわかる。 なぜならば11111のときは、[Ⅱ]のすべての場合において2回の乗算を計算するか らである。  計算量での考察もしておく。y=a^xは素朴な計算の計算量はO(x)であるが、上記 の方法ではO(log(x))で済む。  mod Nの世界で考えるときは、掛け算をする度にmod Nで考える。つまり、「y= 3^20 mod 13」を計算するときは次のようになる(a=3,x=30,N=13)。 [Ⅰ]y=1 [Ⅱ]20の2進数は10100である。  [1]一番左のビット1に対して、   (2.1)y=y×y=1×1=1 ←(=3^0)   (2.2)y=y×a=1×3=3 ←(=3^1)  [2]左から2番目のビット0に対して、   (2.1)y=y×y=3×3=9 ←(=3^2)  [3]左から3番目のビット1に対して、   (2.1)y=y×y=9×9=81≡3 mod 13 ←(=3^4)   (2.2)y=y×a=3×3=9 ←(=3^5)  [4]左から4番目のビット0に対して、   (2.1)y=y×y=9×9=81≡3 mod 13 ←(=3^10)  [5]左から5番目のビット0に対して、   (2.1)y=y×y=3×3=9 ←(=3^20)  さらに、使用変数を減らす方法を次に示す。x_(k-1)=1と仮定する。 [Ⅰ]まずy=aとおく。 [Ⅱ]次に、xの2進ビットパターン(x_(k-1),x_(k-2),…,x0)を上位ビットから1ビ ットずつ見ていき、各ビットに対して次の処理を実行する。i=k-2から0まで次を 繰り返す。  (2.1)y←y×y mod N  (2.2)そのビットx_iが1ならば、さらにaを掛ける。即ちy←y×a mod N  こうすることで使用する変数がyのみで済む。  これで本題の乗法逆元を求めるアルゴリズムを紹介する準備ができた。アルゴ リズムなのでまず入出力を明確にしておく。 ・入力:整数a,x,N(ただしN>0) ・出力:整数y=a^x mod N  アルゴリズムのコードは次の通りである。 ----- x_(k-1)←1 y←a i←k-2 while(i≧0){ y←y×y mod N if(x_i==1) y←y×a mod N i=i-1 } ----- ■0x04.) 終わりに  今回紹介したような(もっと効率がよいかもしれない)アルゴリズムは数論用 のライブラリであるNTL(http://www.shoup.net/ntl/)に収録されている。興味 のある方はNTLの関数を読んでみて欲しい。  次回は引き続き暗号特有のアルゴリズムである「原始元の生成・判定のアルゴ リズム」を紹介する予定である。原始元の生成は鍵生成アルゴリズムで度々必要 となる。原始元は興味深い性質をたくさん持っているので、そうした数学的事実 も一緒に紹介していければと思っている。  では、また来月会いましょう。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第5章: お知らせ --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○Wizard Bible(http://wizardbible.org/)では随時、執筆ライターを募集して います。  扱う内容のテーマは広義での「under ground」です。例えばハッキングからサ リンガスの合成法などと幅広い内容を考えています。また特殊な職業や趣味を持 った方のレクチャーなども含まれます。  一回きりでも構いません。また必ず毎回連載する義務もありませんので、でき る範囲で構いません。気軽に声をかけてください。 ○Kenji AikoさんがQ&Aを作ってくれました。初めて参加する人でもわかりやすく 書かれていますので、参考にしてください。 http://wizardbible.org/wbQandA.html ○Wizard Bibleに参加希望の方は気軽にメール(ipusiron@gmail.com)ください。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第6章: 著者プロフィール --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■金床 ●Job: プログラマー ●Web: http://guardian.jumperz.net/, http://www.jumperz.net/ ●Mail: anvil@jumperz.net ●Comment:  ようやく某書籍が発売されました。お買いあげくださった方、本当にありがと うございます。また、当初の締め切りを半年以上過ぎたのになまあたたかく見守 ってくれたデータハウス社長とまどさんに感謝します。ちなみにサポートページ はhttp://www.jumperz.net/was.jspです。36万文字くらい書いたのでしばらく文 章はいいやって感じで、原稿依頼を片っ端から蹴ってます(;´Д`)スイマセン  反動でコード書きまくりな今日この頃 やはりコード書きは楽しいのぅ。  そういえばハカージャパンに筆者のインタビューが掲載されました。なんか、 ウニュンさんの次のページなんですよこれが。緊張します。ていうかウニソさんとかルミソさ んとかVladさんとかはるかさんとか漏れ的伝説級な人たちと同じ扱いなんですよ。 すごいですもうこれはひとことでは言い表せないですチェケラッチョ。でまたインタビュ ーの内容が面白いんですよ。ウニンさんは「低レイヤーからはじめるといい」とか書 いてあって「今のひとはいきなりWindowsだから、ある意味不幸」みたいなこと書 いてあって、それなんて漏れ?って感じw。いきなり「コンピュータ=ウィンドウ システム」からスタートしちゃうと、「低レイヤー」が何なのかがいまいちイメ ージできないのが辛いです。当時ケンジタソのアセンブリ言語の教科書とかがあ ったらなぁ…。 ●Anti-DNS Pinningとか  最近Anti-DNS Pinning攻撃は「DNS Rebinding」とよばれるようになってきまし た。これはなかなかよいネーミングだと思います。で、なんかスタンフォード大学の論 文に漏れのサイトがワルモノとして登場してるようです(;´Д`) http://crypto.stanford.edu/dns/  こいつら論文書いてる途中漏れに質問メール送ってきたくせに(しかも答えたら返 事なしw)人をブラクハト呼ばわりとは。なかなかにファッキンシットでございますね。 ●今興味あるモノ  最近Javaにはまってます。は?…っつかもまいずっと前からJavaって言ってる じゃん!って感じですが、最近さらにはまってます。特にJNIに一度手を出してか らはJavaとC言語がかなりシームレスであることに気がついて可能性が広がった感 じ。んで追い打ちをかけるかのようにJavaは6からほとんどオープンソースになっ てるんですね。ソースコードが誰でもhttp://download.java.net/jdk6/から、ダ ウンロードできるようになってます。Javaのクラスライブラリはもちろん、その 下でどのような実装が行われているか(つまりSocketクラスが実際にWindowsやS olarisやLinuxでどのようにWinsockの関数やシステムコールを呼び出しているの か)まで読めるので、超面白いです。Sunなどにいる一流のエンジニアのコードはきれい で刺激的。ということで時代はJava。今までもJava。そしてこれからもJava。 ■Kenji Aiko ●Job: kernel hacker ●Web: http://ruffnex.oc.to/kenji/ ●Mail: kenji@ruffnex.oc.to ●Team(Group): N/A ●今興味あるモノ:Windows Vista  「Windows Vista」買いました(^^;。そもそも僕は、Vistaには興味がなかった のですが、たまたま友達に誘われてパソコンショップに行ったら、なんかVistaと かがあって、なんか触ってみたら、結構良さそうだなぁという感じで、なんか、 もう…、うん…(ぉぃ。 しかし、Vistaは、何をするにもいちいちダイアログが 出現するし、IE7では表示されないWebサイトがいくつかあるし、WinDDKはVista版 じゃないとインストールできないし(当たり前?)、慣れるまでは本当にいろい ろと大変そうだなぁと思っています。  ただ、Vistaでデバドラ関連をやりたかったので、その辺りを調べるのが結構楽 しい今日この頃。いつかVistaネタで何か書きたいっす。 ■Will ●Job:Student ●Web:http://d.hatena.ne.jp/Will_net/ ●Mail:will_net@hotmail.co.jp ●Team(Group): N/A ●今興味あるモノ  あると言えばあるし、ないと言えばないw  気の向くままに色々やってます。 ■IPUSIRON ●Job: student ●Web: http://akademeia.info ●Mail: ipusiron@gmail.com ●Team(Group): N/A ●今興味あるモノ:  今現在ではありませんが、つい先日「ひぐらしのなく頃に」にはまっていまし た。元々存在は知っていて、アニメ版は一部DVDで観ていたのですが、ゲームの方 ははるかに面白かったです。ビジュアルノベル(ほとんど小説みたいなもの)な ので、すぐに終えることができると始める前は思っていましたが、甘かったです。 1話終えるのに6時間以上かかるので、夜に始めるといつの間にか朝になっている ということもたびたびでした。解・礼を合わせて50時間以上かかったと思います。 しかしながら、それでもやってよかったと感じました。このゲームを通すことで、 色々考えさせられることもありました。そういう意味で、自分の人生に影響を与 えるような存在となりました。