他人の空似

2009 年 4 月 9 日

某東方二次製作ゲームの解析過程その2

Filed under: 解析 — 中の人 @ 12:12 PM

解析2:その他ファイルの取得

音楽ファイルとは別にもう一つファイルサイズが大きいファイルが存在します。
他にファイルサイズが大きいファイルが存在しない、exeファイル自体も非常に小さい、などからこれがその他の画像ファイルや効果音などなどを内部に保持していると見て間違いなさそうです。

とりあえず前回と同じようにバイナリエディタで開いてみることにします。
kaiseki4
なにやら凄い見覚えがある並び方をしているのが見て取れると思います。
どうやら音楽ファイルと同じ形式でファイルリストを保持しているようなので、試しに前回作ったツールで展開してみることにします。

予想通り展開できました、ですが展開できたファイルを開こうとしても開くことが出来ません。
試しに出来たファイルをバイナリエディタで開いてみると
kaiseki5
0x09に見える臼NGというのがpngの識別子です(正確にはその後の4byteも含みます)
他のファイルを開いても全て最初4byteがLZSSであることと、PNGの識別子が直接確認できることからなにかしら圧縮がかかっていると推測できますね。

ここでまず冒頭4byteに書かれているLZSSについて説明します。
(正式な仕様書の類を見たわけではなく全てコードを読んだ経験からきている知識のため、一部間違えている可能性があります)
軽く検索をかければ判ることですが、LZSSというのは有名な圧縮アルゴリズムの一種で
動的に辞書を作り、距離と長さをあらわすデータに遭遇したら辞書中の距離位置のデータを長さだけ取り出して展開先データとするものです。
(詳細についてここで詳しく述べることはありませんので自分で調べてください)
このアルゴリズム自体ポピュラーなもので、割と色々な実装が行われているためLZSSだとわかっただけでは具体的な展開方法まではわかりません。
そこでまず、バイナリから可能な限り情報を引き出すことにします。

第一に、このソフト上で実装されているLZSSはバイト単位で管理されていることがわかります。
通常であればビット単位で一致不一致を示すフラグ1bit、その後一致であれば距離と長さを表すデータ、不一致であれば元データ1byteという流れになるため
バイナリエディタ上で元データを一部でも読み取れるはずがありません。
なので、一致不一致を示すbit列はどこか一箇所にまとめてあるか、byte単位で表現されていると推測されます。

次に0x08番地に存在する0xFFについて、上の画像だけではわかりませんがほぼ全てのファイルにおいてそこが0xFFで固定でした。
また、png以外にもテキストファイルを含んでいたのですが、そのテキストファイルを見る限り0xFFのあと8byteは必ず元データがそのままという流れになっているようです。
さらに0x31~0x3A番地に注目してください、ここはおそらくtSoftwareという文字列が元データだと推測できますが、間に0xFFという余分な情報が挟まれているのがわかります。

まず0x39番地の余分な1byteはそのままつなげるだけで復元可能な点から、間の0xFFが距離と長さを示す情報以外のデータだと推測できます。
LZSSにおいて他に存在しうるデータといえば、辞書サイズか一致不一致フラグのみですが
辞書サイズがデータ上に点在している可能性は非常に低いため、この1byteが一致不一致フラグであると推測できます。

次に0xFFの後必ず元データが8byte並ぶことから8つ分の不一致をあらわす情報だと仮定することが出来ます。
それは0x08番地が固定である事からも読み取ることが可能で、辞書にデータが存在しない初期の状態では必ず不一致バイトが来ることが推測できるからです。

これらのことから、一致不一致フラグを8つまとめることでbit入出力を減らして効率化しているであろうことが推測できました。
(0x9Fの場合一致5不一致2一致1となるので、元データ5byte距離長さデータが2つ最後に元データ1byteとなります)
現時点では推測に推測を重ねる形ですが、試しにそうであると仮定して0xFF以外のフラグに遭遇するまで展開するコードを書いてみれば問題なく取れているが判ります。
また、0xFF以外のフラグに遭遇した後のデータを並べてみれば、その後2byte元データとは違うデータが混じっていることがわかりました。
これはやはり一致不一致フラグを8つまとめたものであり、さらに距離と長さを示す情報は2byteであろうことも推測できます。

この時点で一致フラグを無視し、不一致分だけ全て読み出すものを作りました。
png画像に用いてもいまいち結果がわかりませんが、テキストデータはNULL文字を含まない形に展開できたためここまでは推測が当たっていることが判ります。

次に必要になってくるのが辞書の作成方法と辞書サイズです。
辞書サイズは大きく分けて固定サイズ、ファイル内に保持している、ファイルサイズから算出の三方式があります。
ですが、ファイルサイズから算出であれば距離を表現するのに使うビット数が可変になるため現在のように2byte固定はありえません、なので算出では無いでしょう。
次にファイル内に保持している可能性として0x04番地の値が思い浮かびますが、必ずファイルサイズ以上の値を保持している、距離と長さを表現するバイト数は2byteであるため辞書サイズも最大で2byteである点からおそらくは違うでしょう。
というわけで、現在は固定サイズであると仮定して先に進みます。

細かい説明は省きますが、pngはフォーマットの使用上原則的に16byte目まで固定です。
(ほぼ確実に89 50 4E 47 0D 0A 1A 0A 00 00 00 0D 49 48 44 52となる)
なので2枚目の画像の0x11~0x13番地のFE ED F0の部分については展開後の様子が推測可能になります。

まず0x11番地の0xFEは一致不一致フラグで2進数に直すと11111110となるので0x12~0x13番地の2バイトが距離と長さを示す情報です。
次に展開先のデータですが、00 00 00 0Dで次の不一致データが0Dであるため00が3byte続く形に展開されると推測できます。
ですが、そこまでの12byteを見ても00が1byteも存在しません。

LZSSには良く使われる手法の一つに、事前に登場しやすいバイト列を辞書登録しておくことで圧縮効率を上げるというものがあります。
さらにその中で一番使われているのが辞書全体を00で埋めておくというもので
今回もその例であると推測可能です。
なので、既に辞書登録されているデータの前後どちらかとなるので登録済み12byte+長さ3byte分前の指定で15、もしくは直後指定で0だと仮定できます。
他にも辞書中を相対的に参照する距離ではなく絶対座標として参照する方式もありますが、現時点では推測不可能であるため無視することにします。

次に長さですが、使用するバイト数以下の長さでは置き換えても無駄であるため
基本的に置き換え必要バイト長+1が長さの最低値となります。
なので、長さ0をこの最低値として定義することで最低値分だけ長い一致まで表現することが可能になります。
(長さに1byte割り振った場合、そのままでは長さ255までしか格納できないが最低値を3と定義すると長さ258まで格納できる)
今回の場合は置き換えに2byte使用しているので、この手法が用いられていれば最低値3になります。
つまり今回は3byteなのでそのまま3か圧縮されて0だと仮定できます。

上記のことを踏まえてED F0の部分を眺めてみます。
まず、ビット列に戻すと1110 1101 1111 0000という並びになります。
この時点でまず1が出現する最多組み合わせである15 3よりも1が多い事に気づけます。
なので、距離か長さもしくは両方の推測が外れているとわかります。

現在考えられる可能性といえば、距離が相対ではなく絶対座標製である可能性です。
私自身理由が良くわかっていないのですが、絶対座標方式の場合辞書登録の始点が0x00番地からではないことが多いです。
なので、今回の例についても格納されているであろう数値が推測できません。
(それが目的の可能性もありますが、暗号化を目的としない圧縮アルゴリズムであるため可能性は低いと考えられます)

まず、効率化の観点から距離長>長さ長になることは確実なので、今回の例で言えば少なくとも距離長に10bitは割り振られていると考えられます。
それを踏まえてどちらか該当しないかと考えれば、辛うじて後半4byteが長さを表現しているのではないかと推測できます。
この時点で距離長が12bitと推測できるため、12bitで表現しうる最大値0xFFF+1=0x1000が辞書サイズであるという仮定も成り立ちます。
またbit入出力をなくすなど演算速度を重視していることから単純に2byte目の上位4bitを1byte目の前か後につなげる形だと思われるので0xFEDか0xEDFが距離であると考えられます。

もし距離が0xFEDであるならば、登録データ前を参照していた場合は0xFED+3で始点0xFF0、後を参照していた場合は0xFED-12で始点0xFE1。
0xEDFであれば前参照で0xEE2、後参照で0xED3。
現時点まで全ての推測が正しい場合はこの4パターンのどれかで展開できることになります。

ここまで来れば後は簡単で、実際に実装してみて4パターン全て試してみることにします。
格納されていたファイル自体多いので全て同じように調べて回ればどれか一つに絞り込めるかもしれませんが、実際検証した方が早いのでコードを組んでみることに。

結果としてみごと辞書始点0xFF0で展開に成功しました。


上の文章だけ読むと適当な推測を積み重ねていったら運良く正解にたどり着けただけのように思えるかもしれませんが、実際そのとおりです。
ただし上記の10倍程度は推測を重ね、その全てで失敗した結果この結論にたどり着いた形になります。

一例を挙げるならば、過去に登場していない0x00の3byteが圧縮されているという部分
ここで私は最初LZSSだけではなくランレングス圧縮も併用されており、距離と長さデータだと思っていた部分のうち1bitをフラグにして一部ランレングスとして機能しているのではないか?と考えました。
上記のとおりそんなことは無かったのですが、最初はそうとしか思えずランレングスの実装例をいくつもあさったものです。

結果として、本来であればデバッガーやメモリーエディターの力を借りておそらく3時間程度で済む解析に丸2日かけた計算になります。
やはりデバッガーは偉大だなと思いつつ、ランレングスやLZSSについてそれなりの知識を得られたので悪い試みではなかったと思っています。
もう一度やりたくはないですが……

ちなみに、今回と前回であげた例は非常に簡単な部類です。
本来であればバイナリエディタで見た時点でまっとうに意味を理解できる文字列が存在していること自体珍しく、デバッガーの力なしでは解析の足がかりにさえたどり着けないことも多いです。
最終的には上記と同じ道筋を辿るとはいえ、一般的な解析ではまず砂漠から一本の針を探すような途方もない作業が待っており、上記解析過程にたどり着いた時点で勝ちといっても過言ではありません。
そういう意味では、今回の記事は解析過程と銘打つには少々的外れな内容だったのかもしれませんね。

というわけで、解析過程の解説記事はこれで終了となります。
もしこのような奇特な記事を最後まで読んだ方がいるならありがとう、そしてお疲れ様でした。

2009 年 4 月 7 日

某東方二次製作ゲームの解析過程

Filed under: 解析 — 中の人 @ 10:39 AM

開発滞りまくってそろそろ罵声飛んできそうな状態ですが
火打石的依頼が舞い込んできたので、その過程を解説風に書いてみるテスト。

概要:とあるソフトの解析依頼
目的:ソフト内で使用されているデータの切り出し(可能であれば一般形式への変換も)
制限:ソフトの立ち上げ禁止

三つ目はWeb認証があるとかで、変なことされてネット対戦出来なくなると困るからだとか
起動もしないで解析とか無茶言うなって話ですが、考えてみれば地霊殿の解析はバイナリエディターだけだったなということで試しにやってみることに。


解析1:BGMファイルの取得

BGMというのはファイル容量が大きいためメモリー上に保持し辛く、遅延がダイレクトに影響を及ぼすため
大抵はその他ファイルとは別に展開が高速なフォーマットでアーカイブされていることが多いです。

今回のソフトもその例に漏れず、.musという判りやすい拡張子でどでかいファイルを保持していました。
本来ならこのファイルを撤去した上で起動し音がならないか試すのですが、今回は起動禁止なので音楽ファイルと決め打つことにします。

とりあえず先頭を少量切り出してきてバイナリエディタで開きます(容量が大きいため、そのままだと固まる)
するとこんな感じ(一部実際の内容から変えてあります)
kaiseki1
oggという音楽ファイルの拡張子が見えるので間違ってはいない様子。

おそらくは最初のPACKが識別子、その後80byte区切りでファイル情報らしきものが仕舞われているのが見て取れます。
問題はPACKから最初のファイル名までの4byteが一つ目の音楽ファイルに関する情報なのか、このファイル全体に関係する情報なのか判別付かない点ですが
二個目以降のファイル名の前4byteを見てみると数字の傾向が違うことが見て取れるので、今はとりあえずファイル全体に関連する情報だと思っておくことにします。

次にこの80byteが具体的にどういう構造をしているのか調べる作業に入ります。
まず膨大な0の山と、ファイル名~0で埋まっている部分を合計するとどれも64byteであることから
このフォーマットにおいてファイル名は64byteの決めうちであることが判ります。
残り16byteも断定したいところですが、今はまだどこで区切ればいいのかも判然としないので後回しにします。

ここで少し話がそれますが、一般にこういったアーカイブ形式の場合
ファイルリストと一緒にファイルの個数、もしくはファイルリストのサイズがついてくるか
ファイルリストがリスト構造になっており、終端まで辿ることで個数を判別できる仕様になっていることがほとんどです。

ですが、今はまだそれらしき情報を見つけていません、そこでこのファイルにいくつファイルが格納されているのか調べることにします。
その結果41個入っているらしいことが判りました。16進数になおすと0x29となります。
そう、先ほど後回しにしたPACKの後の4byteも同じく0x29でビンゴです。これがファイル個数だと思っていいでしょう。

念のためリスト構造の可能性を考えて内容不明の16byteから次のファイル名情報を指していそうな絶対or相対アドレスを探しますが見つかりません。
これはデータそのものに関するデータで、ファイルリスト自体に関連する情報ではないようです。

本来はここで16byteを全て切り出し1/2/4byteごとに区切ってみて特異点がないか探す作業になるのですが、流石に面倒くさいので別方向からアプローチすることにします。
kaiseki2

これは適当に手元にあったwavをoggエンコードした物をバイナリエディタで開いた画像です。
先頭4byteのOggSはoggフォーマットであることを示す識別子で、oggフォーマットのファイルであれば全て先頭4byteはこうなっています。
今回は既にファイル名からoggファイルが格納されていることはわかっているので、ためしにOggSで検索かけてみることにします、すると……
kaiseki3

見事にヒットしました、その後の流れを見比べてもoggの生データであると見て間違いなさそうです。
さらにこのoggファイルのアドレスをよく見ると面白いことがわかります。
一枚目の画像をよく見てください、二個目のファイル名の前8byteの所に0x00000D00と格納されているのが見て取れます。
試しにそのほかのファイル名の前8byteが指すアドレスの部分を見てみても全てOggSの識別子に行き当たります。
つまりこれがファイル格納位置だということですね。

残るはファイルサイズですが、ファイル位置がわかっているため次のファイル位置を元におおよそのサイズを割り出すことが出来ます。
今回の例で言えば二つ目のファイル位置が0x0005E700であるため、0x5E700-0xD00で0x5DA00以下であることがわかります。
ちょうど一つ目のファイル位置の次4byteに非常に近い数値が格納されているのがわかりますね。
念のため他のファイル情報も計算して見比べてみましたが全て非常に近い数値を取っていることがわかります。
つまり、これがファイルサイズということになります。

試しにバイナリエディタを使って手動で切り出してみましたが問題なく再生されました。
どうやらこれで問題ないようです、やったね!

ここまでをまとめると
4byte:PACK
4byte:格納されたファイル個数
ここからファイルリスト
64byte:ファイル名
8byte:不明
4byteファイル格納位置
4byte:ファイルサイズ
となります。

不明の8byteが気になりますが、自分にはわからなかったため気にしないことにします。
そんな適当でいいのかと思う人もいるかもしれませんが、解析の世界では割と普通。
判らないならとりあえず無視して、あとで食い違うことがあったらそのときに引っ張り出して繰ればいいのです。

ちなみに、上記の結果を基にした切り出しツールはCUIで余分な機能を色々つけても100行の1800文字で収まります。
下手をすればC言語始めて一週間の人でも書けちゃうレベル。

解析1と銘打ってあるとおりこのあと画像やら効果音も切り出していますが、そっちはまだ現在進行形なので終わった頃にでも

2009 年 4 月 6 日

解析に必要な才能って

Filed under: 未分類 — 中の人 @ 7:36 PM

理解する能力らしい。
確かにあるに越したことはないけど、必須と言うほどか?

自分は理解力無い方とは言わないまでも高くはないんで、
理解する能力が無くても、理解した知識があれば問題ないと思ってる。
だってDirectXの知識皆無のせいでDirectX関連の解析一切出来ないし。
クラスの内部表現はわかっていても、そこから実際の利用構図を思い描けないと無意味よねー

要するに、まったくのノーヒントで正解にたどり着ける能力なんぞ無くても、正解となりうる選択肢を全て知っていれば総当りで解けるよねって話。

理解力もしくは解読能力なんて必要ありません、その辺で売ってる参考書の類を全て諳んじられる程度に理解すれば問題など無いのです。
それを「知識だけの頭でっかちには無理だよ帰れ」なんていうほうが帰るべきだと思います、頭でっかちマンセー

リズムの乱れ

Filed under: 未分類 — 中の人 @ 7:19 PM

実家より戻って一週間、未だに毎日だらだらしてるだけで終わってます。
強いて言うなら食糧難で毎日おなかグーグー言わせている程度(自炊面倒だからって1日1食って話)
あぁ、あの充実したプログラで健康的な日々は何処に……

どうでもいいけど、絵や音楽を作れる人は凄い。
ここ一週間そういう凄い人にばかり遭遇する、マジ凄い。
どんな方向性であれセンス良い人が羨ましい。

自分もこう心に渦巻く衝動のようなものをストレートに表に出せる技術がほしい……

2009 年 4 月 2 日

エイプリルフール(一般)

Filed under: 未分類 — 中の人 @ 1:47 PM

自分の活動範囲内では去年えらい盛り上がり方をしたところばかりで、
今年も期待していたら全て肩透かしを食らった状況。

そのくせ知人友人からは細かい嘘に騙されまくり、笑う側ではなく笑われる側として一日を終えました、まる。

一応、マウスポインターを消してそっくりな画像を正反対の位置に表示するネタアプリは作っていたけど
当日になってから相手に起動してもらえなきゃ意味が無い、という壁に気づいて諦めました。
他にやりたいこともあったし……(東方版の方参照)

来年は去年みたいに一年越しのネタ*4とか豊作なエイプリルフール希望

エイプリルフール(東方ネタ)

Filed under: 東方 — 中の人 @ 1:38 PM

忘れてました、具体的には他人を騙すネタを。

即興で緋想天で未登場キャラの美鈴さんが実際に動いている動画作ったけど、流石に製作時間3時間の9秒動画では反応は微妙だった。
せめて一週間あれば……

話は変わって、星の話題。
上と同じく星の上で本来出ないはずのキャラ動かして本家キャラだと勘違いさせたやろうって嘘動画企画。
こっちは上よりさらに酷く、4/2の0:00始動というもはやエイプリルですらない企画。

ただ、こっちはそれなりに手が込んでいるので公開すればかなり釣れそうな気がする
(もうエイプリルも終わってるわけだし)
といっても、個人でやっている企画ではないため一般公開まで行かずに終わりそうな気もする。
動画自体はもう出来てて、身内では公開してるんだけどね。

« Newer Posts

Powered by WordPress