勝手に転載しました。この情報の利用は自己責任でお願いします。

通勤ヒトフデのパスワード仕様概要

パスワードの例と解析手法

☆☆☆☆  始点 (1, 1) → 終点 (1, 2)
☆●□☆  ステップ数: 2
☆●□☆  難易度: 1
☆☆☆☆

上記のような一番簡単なステージのパスワード確認をすると、以下の15種類のパスワードのうちどれかがランダムで出てきます。

1929+ =V586 TP$43
1C2J2 1!JT9 HFV42
1F27H 48?XV WHPL0
1H2J! #H29N VH0$3
1J2J3 16?C2 XT3#2
1K2QT 1C9MQ QXN41
1L23= +-PT3 7#V42
N82+6 6C33- F8-50
N92+Q -F9W8 FJNT2
NC290 7MH6? 84$#3
NF2?? 060C! -3TH1
NH23L VF64P 1PP42
NJ2VP 2?9WT Q0T$1
NK2L6 4J=Y9 -?JJ3
NL2?9 7NQ=- JY$T1

こうやって並べてみると先頭の何文字かに規則性がありそうなのがわかります。同じ文字だったり続き文字だったり…。後半はバラバラですね。そこで先頭の情報を使ってそれ以降を暗号化していると推測できそうです (実際そうでした)。

ここで先ほどのステージの難易度を 1 から 2 に変えてみると、以下のようなパスワードになります (一例のみ)。

1N29+ =V586 TQ$43

先ほどの一番上のパスワードと比べてみると、文字列に少しだけ違いがあるのがわかります。この変わったところに難易度の情報が含まれていそうです。

このように情報を少しずつ変えて比較していき、提供側 (特にプログラマ) の視点に立ちながら推測と実験を繰り返すことで、データの配置場所と変換法則を導きだすのが基本的な解析手法になります。

解析成果

パスワード文字と32進数の対応
0: 00000 1: 00001 2: 00010 3: 00011 4: 00100 5: 00101 6: 00110 7: 00111
8: 01000 9: 01001 C: 01010 F: 01011 H: 01100 J: 01101 K: 01110 L: 01111
M: 10000 N: 10001 P: 10010 Q: 10011 T: 10100 V: 10101 W: 10110 X: 10111
Y: 11000 !: 11001 =: 11010 $: 11011 #: 11100 ?: 11101 -: 11110 +: 11111

はじめに取り組んだのがこれの作成。最初の試しに割り当ててみたものが、値の変動具合を色々調べた結果結局正解のようです。とても素直な数値で安心しました(^^

パスワード文字列をバイト列に

上記の対応表を元に、まずパスワード文字列をバイト列に変換します。色々試した結果、文字列を逆さまにして各文字に上記値を割り当て、後ろから 4bit ずつ並べていく方式がよさそうです。この変換をすると先ほどのパスワードが以下のようなバイト列になります (後述の CGI を使えば自動で変換できます)。

1929+ =V586 TP$43 →  12 98 4f 57 d2 8c 05 9b 9c  
1N29+ =V586 TQ$43 →  12 a8 4f 57 d2 8c 0d 9b 9c  

難易度を 1 から 2 にしたことで、2byte 目と 7byte 目に変化が現れました。色々試してみた結果、2byte 目にチェックデジットが、7byte 目に難易度が格納されていそうなことがわかりました。しかし残り14種類のパスワードの変化を見てみると、バイト単位では同じ箇所ですがビット単位では違う場所が変化しています。値自体も増えたり減ったりとマチマチです。

このことより、バイト単位である値との XOR 演算や循環ビットシフト演算をしているのだろうと推測します。これが一番の難関そうなのでおいておいて、とりあえず他の各バイトに格納されている情報も調査してみます。

ステージデータの各バイトの内容
0: 固定ヘッダ(0x1)、暗号キー(0x1-0xf)
1: チェックデジット
2: 始点X、始点Y
3: 終点X、終点Y
4: サイズX、サイズY
5: ステップ数
6: 難易度、ピース配置データ形式
7-: ピース配置データ

あらかじめどんなデータが含まれている「はず」か考えた上で、色々設定を変えながらデータサイズや変更箇所を調査したらこうなりました。

最初の固定ヘッダは特殊ピースを使っているパスワードでも固定なのですが、もしかしたらユーザが作ったパスワードという意味かも知れません (公式配布のものは 0x2 とか)。

ピース配置データはステージの外枠も含めた形で格納されているようです。要するに14×14のときに16×16=256のピースの情報が含まれていることになります。構成ピースが白黒ハードルのみの場合は1ピース1bit、その他の特殊ピースも入っている場合は1ピース3bit (2bitの場合もあるか?) のようです。この2つをピース配置データ形式の情報で区別しているんじゃないかと思っています。

→ ピース配置データ形式と呼んでいる値は難易度と OR して格納されているのですが、マルチやコテイを使ったときに0x8に、それ以外のときに0x0になるっぽいので、たぶん正解。でもあと4byte分フィールドが余ってるんだよなぁ (常に0x0?)。

このことより、ステージサイズが14x14のときに最大で 824bit=165文字のパスワードになる可能性がありそうです…(まだエディットが特殊ピース解放してないので未確認)。これじゃパスワード交換が気軽にできませんね…。

バイト列をステージデータに

ここまでの推測の積み重ねが正しいかどうかわかる、一番ドキドキする瞬間です。いろんなステージをバイト列変換して暗号法則を求めていくのですが、結論から言うと 3byte目以降 8byte ずつに以下のような演算を施していることがわかりました (例は暗号キーが 2 の場合)。

12 98 4f 57 d2 8c 05 9b 9c  
XOR   6d 73 e1 ac 05 8b 94 2f
SHIFT <7 <3 <0 <4 <5 <1 <6 <2
12 98 11 21 33 02 00 20 02

おー、なんか見慣れた数字が並んでる…! 推測があっていた部分もあるし間違っていた部分もありますが、この時点で超感動。これだから暗号解読はやめられません(^^

他のキーの場合もすべて求めましたが、この数値がどうやって決まっているかはよくわかりません。わかるのは 4bit 単位で重複がないことくらい。ある数値を元にランダムな並び替えをするアルゴリズムでも使っているのでしょうか。よくわからないので、今回は (8 + 8) * 15 個の数値を全部力技で手計算しました…(^^;

あとはこのステージデータを分解してエディットしたステージと同じものが生成できれば解析完了です。

ピースデータ

マルチピースやコテイピースを使っていないステージの場合

0: シロクロピース白 or ソトワク
1: シロクロピース黒 or ハードルピース

マルチピースやコテイピースを使っているステージの場合

000: シロクロピース白
001: シロクロピース黒
010: コテイピース白
011: コテイピース黒
100: マルチピース
110: 空きスペース or ソトワク
111: ハードルピース

コテイピースはどうせ横一直線しか配置できないんだから、16bit のデータとして別に格納するようにすれば マルチピースやコテイピースを使ったときのピースデータが 2bit で済むのに…、と思った次第です(^^

パスワード解析支援ツール

パスワードを暗号解除する前のバイト列に変換するCGIです。1行に1つのパスワードを書くと各行ごと変換してくれます。このバイト列群の変化具合を見て、値の格納場所と暗号方式を解読していきました。こういう解析作業では膨大な量のデータの比較が必要になるので、こんな感じにどばーっと並べられるようにしてあります。パスワード文字以外は計算しないので、全角で文字を書いておけば比較のメモに使えたりとなにげに便利です(^^

まだ最後の暗号化の部分が解析できていないのですが、このCGIをはじめとしたいくつかのお手製ツールを使ってシコシコ解析中です。ここまでくれば力技でもなんとかなりそうなので、完全解析も時間の問題だと思います、たぶん…。

→ 前述のようにほぼ解析終了しました。最後はやっぱり力技というか物量作戦になりました。あとは動作検証…。

参考 URL

Posted by ooba at 19:56