Pages

2014年1月27日

SECCON CTF 2013 online予選 forensics 400

SECCON CTF 2013 オンライン予選のフォレンジックス400点の解法です。
競技中は解けませんでしたので、終わってからじっくり解いてみました。

問題:QRコードの断片を読み取れ
富士山麓で焼け落ちたQRコードの断片が発見された。 損傷が激しい。内容を復元することはできるだろうか?
qr-photo.jpg

QRコードの仕様について詳しく知らなかったので、調べました。
http://ja.wikipedia.org/wiki/QR%E3%82%B3%E3%83%BC%E3%83%89

・バージョンがある(1〜40)
誤り訂正レベルがある(L,M,Q,H)
・モードがある(数字、 英数字、8ビットバイト、漢字)
・どのモードを使っているかを表すモード指示子がある
・文字列/データの長さを表す文字数指示子がある
・QRコードは読み取り精度を高めるためにマスク処理が行われている
・どのようなマスクが掛かっているかを表すマスクパターン参照子がある

Wikipedia英語版では図解で説明されていました。
http://en.wikipedia.org/wiki/QR_code


QRコードの3つの角に付いてるマーカー、そのうち左側のマーカーの周りには、誤り訂正レベル(Error Correction Level)、マスクパターン参照子(Mask Pattern)、誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)が配置されています。
残る1つ、右上のマーカーの下には、この訂正ビットの下8ビットが配置されています。

ここまでで分かったことは...
QRコードにはマスクが掛かっているが、どのマスクパターンが掛かっているかはマスクパターン参照子が無いと分からない。
→でも、写真のQRコードには左半分が無いから、マスクパターンの種類は分からない。
→ついでに誤り訂正レベルも分からない。

ここで、英語版Wikipediaにある次の画像に注目しました。
誤り訂正レベルHでバージョン3のQRコードのコード配置の説明画像です。


とりあえず、これに写真のQRコードを合成してみよう...


なんと、ドットのサイズも配置もバッチリじゃないですか...
どうやら、写真に写っているのはバージョン3らしく、誤り訂正レベルHのQRコードと仮定すればデータ領域は全部残っているとみることが出来そうです。
誤り訂正はできませんが、この部分が読み取れれば何とかなりそう。
しかし、マスクが被さっているので、このまま読んでも意味が通じません。
→なんとかしてマスクパターンが知りたい
→右上のマーカーの下(上図の赤い部分)に付いている訂正ビットの下位8bitは分かる!

左が上位ビットらしいので、これを読むと、下位8bitは10001001と分かります。

http://www.swetake.com/qrcode/qr5.html
http://www.swetake.com/qrcode/qr6.html

↑こちらのサイトによれば、誤り訂正レベル(Error Correction Level)、マスクパターン参照子(Mask Pattern)、誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)を形式情報と呼び、15bitで表現されるようです。
15bitのうち、最初の5ビット(誤り訂正レベル2bit+マスクパターン参照子3bit)をBCH符号化したものが10bitの訂正ビットで、最初の5bitとBCH符号化した10bitを引っ付けた15bitを更に101010000010010とXORしたものがQRコードに刻まれるとのこと。

ここで、誤り訂正レベルをH(上位2bitが10)と仮定すると、マスクパターンは全てで8種類なので...
10000、10001、10010、10011、10100、10101、10110、10111をBCH符号化して求めた10bitの訂正ビットをそれぞれに付け、これをXORしたものの下位8bitが10001001であるものがあれば、マスクパターンを特定することができます。


というわけで、計算すると下位8bitが一致するのはマスクパターン参照子000となります。
写真QRコードと判明した形式情報からQRコードを描くと、以下になります。
(まだリーダーなどでは読み込めません)


マスクパターン参照子000のマスクは(i+j) mod 2 = 0なので、マスクは市松模様のようになります。
もう一度マスクを掛ければ元に戻るので、上記のQRコードのマーカーと形式情報を除外した場所を市松模様状にマスクを掛け、先ほどのコード配置図を合成すると、以下のようになります。


D1からD26まで、ビット配置の規則に従って読んでいくと、


http://www.swetake.com/qrcode/qr2.html

↑こちらサイトによれば、最初の4bitはモード指示子で、この場合は0010なので英数字モード、次の9bitが文字数指示子で000100011なので10進数にすると35文字ということになります。
それ以降は11bitずつ区切れば良いそうで、区切った11bitを10進数に変換すると以下の通り。
(35文字なので、最後の1文字だけ上位6bitを読んで10進数に変換)


この10進数の値は英数字2文字分で、1文字目のコードに45掛けた数値と2文字目のコードの和になっているとのこと。
(文字コード対応表は下記)


という訳で、全てのパターンを計算しました。安定のC(白目

#include <stdio.h>

int main(void) {
 int i,j;
 for(i=0;i<=44;i++){
  for(j=0;j<=44;j++){
   printf("45*%d+%d=%d\n",i,j,45*i+j);
  }
 }
 return 0;
}

実行結果は下記
http://ideone.com/phmtrx

必ず一意の数値になるので、10進数に直した数字で一覧を検索すると下記のように対応します。


並べると「CONGRATS. FLAG IS VIVA REED-SOLOMON」で、Keyは「VIVA REED-SOLOMON」となります。

おまけ:完全復元したQRコード
感想:QRコードを学べる良い機会になりました!
(もう二度とQRコード印刷した紙を燃やしたりしないでください >Kちゃん先生)

2014年1月26日

SECCON CTF 2013 online予選

感想:難しかった

解けたのはforensics100と300だけ、あとはcrypt100の法則に気がついた(ソルバー書いたのは後輩)のとforensics200の仕様を発見した(スクリプト書いて回したのは後輩)くらいしか貢献できませんでした...

とりあえずforensics300だけメモしておきます。(追記:最下部にWriteUpへのリンクをまとめました)

問題:ログインパスワードを解明せよ
調査対象パソコンのユーザー名Forensicsのパスワードが不明な状態です。 システムの電源を落とす前に、win32ddにより、メモリ全体のイメージファイル(RAW形式)が取得されています。 このイメージファイルを解析し、ユーザー Forensics のWindowsへのログオンパスワードが何かを特定してください。
メモリをダンプした対象システムは Windows 7, x86(32bit)です。
Memorydump2.rar

参考にしたのは
http://cyberarms.wordpress.com/2011/11/04/memory-forensics-how-to-pull-passwords-from-a-memory-dump/

Volatility 2.3.1 Standaloneを使いました。
https://code.google.com/p/volatility/downloads/list

Windows 7 x86とのことなので、

C:\Users\keiichiro\Desktop>volatility hivelist -f Memorydump2.bin --profile=Win7SP0x86
Volatility Foundation Volatility Framework 2.3.1
Virtual    Physical   Name
---------- ---------- ----
0x9ff5a3c0 0x37fbb3c0 \SystemRoot\System32\Config\SECURITY
0x9ffc03a0 0x30e243a0 \SystemRoot\System32\Config\SAM
0x8f60c568 0x04bbc568 [no name]
0x8f61c008 0x005d2008 \REGISTRY\MACHINE\SYSTEM
0x8f6448d8 0x04b3c8d8 \REGISTRY\MACHINE\HARDWARE
0x90659650 0x199c0650 \??\C:\Windows\ServiceProfiles\NetworkService\NTUSER.DAT
0x906d8008 0x13200008 \??\C:\Windows\ServiceProfiles\LocalService\NTUSER.DAT
0x93cf5008 0x38814008 \Device\HarddiskVolume1\Boot\BCD
0x93d479d0 0x388c19d0 \SystemRoot\System32\Config\SOFTWARE
0x989bc008 0x37920008 \SystemRoot\System32\Config\DEFAULT
0x9e6e69d0 0x005469d0 \??\C:\Users\forensics\ntuser.dat
0x9efe5650 0x028aa650 \??\C:\Users\forensics\AppData\Local\Microsoft\Windows\UsrClass.dat

SAMとSYSTEMの番地が分かったので、これを使って

C:\Users\keiichiro\Desktop>volatility hashdump -f Memorydump2.bin --profile=Win7SP0x86 -y 0x8f61c008 -s 0x9ffc03a0 > passhashs.txt

Administrator:500:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
Guest:501:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
forensics:1000:aad3b435b51404eeaad3b435b51404ee:98ffdb1b29e7c88954326cd4011141d8:::

ophcrackにrainbow table(vista_free)を読ませてpasshashs.txtを投入すると3秒くらいで出ました。


最後はforensicsの500をいじってましたが、500点問題となるとうまくはいかないもんですね...

追記:以下に参考になるWrite-upを貼っていくことにします。