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ちゃん先生)

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を貼っていくことにします。

New Style Collection / かごしまITフェスタ

告知しますと言いながら事後報告になってしまいましたが... 鹿児島市主催のかごしまITフェスタにて色々やったのでご報告。
#ファッションショーなのにダサい格好で登壇しているっていうツッコミは勘弁;;

今回は、鹿児島県内の女子大生によるファッションショー企画団体Lilyとコラボして、音と光のファッションショーというものに協力させていただきました。

モデルが何らかの決めポーズ的なものをすると、それに合わせて効果音が流れるというものを製作。
技術的には、Arduino Fioと加速度センサ(ADXL345)、XBee Pro(ZigBee)で体(主に腕)のモーションを取得して送信＆PCで受信、Processingで処理してモーション毎に音を鳴らすという仕組み。

コードに関しては色々と突貫で作ってる部分が多いので、時間が出来たら少し書き直して気が向いたら公開しようかなぁ...っと思っています。

Web系が大忙しで電子工作から離れつつある今日この頃...
そろそろニコ技にも進出したいところなので、ネタ探し中です。

Raspberry Piで秋月の無接点プッシュスイッチを使う

Web系のお仕事が山積みで、数ヶ月間更新出来ていませんでした;;
現在もガッツリ電子工作系に打ち込む時間が無いので、今回はベーシックな小ネタということで。

秋月電子で売ってる「無接点プッシュスイッチ（コード付）」を使う。
"機械的接点がない光学式の無接点プッシュスイッチです。デジタル出力型ＩＣセンサ内蔵でドライブ回路に直結可能。" という説明の通り、ICが載ってるので出てる線はVCC、GND、OUTの3本です。
添付されていた参考資料によると、スイッチを押すとOUTがGNDに落ちるようになっていたので配線は以下。

これに加えてLEDを1個追加したので、図には入れてませんが、GPIO 17(pin11)から1kΩの抵抗を介してLED、GND(pin6)というのを入れています。

プログラム(Python with RPi.GPIO)はこんな感じで。

import RPi.GPIO as GPIO

GPIO.setmode(GPIO.BCM)
GPIO.setup(4,GPIO.IN)
GPIO.setup(17,GPIO.OUT)

while True:
 if (GPIO.input(4)):
  GPIO.output(17,GPIO.LOW)
 else:
  GPIO.output(17,GPIO.HIGH)

ifとelseの中身を変えてあげれば何にでも使えますね。

もし、ボタンを押したらコマンドを叩く様にしたい場合は、

import RPi.GPIO as GPIO
import subprocess

GPIO.setmode(GPIO.BCM)
GPIO.setup(4,GPIO.IN)
GPIO.setup(17,GPIO.OUT)

while True:
 if (not GPIO.input(4)):
  subprocess.call("shutdown -h now", shell=True)

みたいな感じにしてあげれば良いかも。
#このままだとボタンを押していると連続して叩いてしまうので、一回だけ実行するようにする必要ありです。

追記：pushCheck = Falseとか定義して、以下みたいな感じにすればOK

while True:
 if (not GPIO.input(4) and not pushCheck):
  pushCheck = True
  print "Push!"
  GPIO.output(17,GPIO.HIGH)
 if (GPIO.input(4) and pushCheck):
  pushCheck = False
  GPIO.output(17,GPIO.LOW)

話は変わりますが、12/1に割と大きなネタがあるので、時期が近づいたら改めて告知します。

PICでBluetooth SPP - UARTコンバータ

BluetoothのSPPが使えるモジュール、技適マーク付きの物を買うと5000円以上したりします。
これを市販のUSBドングル型Bluetoothモジュールを使ってなんとかしようというネタ。

使うのはPIC24FJ64GB002というUSB OTGが使えるマイコンで、今のところ買えるのはRSやDigiKeyを除いて共立電子のみ。

回路はこんな感じでOK
USBコネクタ部分の配線がよく分からない順番になってますが、実際は
1 - VCC
2 - D- (図の茶色線)
3 - D+ (図の黄色線)
4 - GND
という感じでAメスコネクタと配線してください。

電圧は3.3V。
PicKit3から電源供給する際はプロジェクトのプロパティから電源供給をONに。(MPLAB X)
Arduinoのシールド化する際は3.3Vから引きます。
(本当はあんまり良くないけど)RX/TXは直でArduinoと接続しても問題なし。

実際に使う場合は、右上のFTDI breakooutが繋がってるRX、TX、GNDをUART通信したいデバイスに接続します。

Arduinoと接続してAndroidとSPPで通信している様子。
ここでは、ONと送るとArduinoの13番pinのLEDが点灯、OFFと送ると消灯というスケッチをArudinoに書き込んでいます。

PIC側のプログラムは、hrdakinori氏のPIC24F_btstackをベースに、UARTからの受信をBuetooth SPPに渡すコードを追加すればOKです。

具体的にはこんな感じで、まずbt_spp.cのbt_spp_recive_callbackを以下の様な感じに。

int bt_spp_recive_callback(uint16_t channel, uint8_t *packet, uint16_t size)
{
 packet[size] = 0;
        
        //SPP to UART
        UART2PrintString(packet);
        
 return 0;
}

更に、main.cのsw_processを以下の様な感じに。

static int sw_process(struct data_source *ds)
{
    if(IFS1bits.U2RXIF == 1){
 char text[100]={0};
        int i = 0;
        char c = 0;

        while(1){
            while(U2STAbits.URXDA) {
                c = U2RXREG;
                text[i] = c;
                i++;
            }
            if (c == '\n') break;
            else if(c == 0) break; // if UART no Connect, break while(1)
        }
        text[i] = 0; //

        //UART2PrintString(text); //debug and callback

        //Bluetooth Send
        bt_spp_send((uint8_t*)text,strlen(text));

        IFS1bits.U2RXIF = 0;

 if ( U2STAbits.OERR) {
  U2STAbits.OERR = 0;
 }
    }
 return 0;
}

あと、コンパイル時にundefined reference to packet_handlerが出るので、btstackのhci.c内のstatic void packet_handlerをvoid packet_handlerに変更します。

PICとのシリアル通信は57600bpsで、Bluetooth側は特に制約は無い(はず)。

こんな感じでSwitch Scienceさんのバニラシールドに載せてしまえば、Arduino UNOやMEGAのシールドとして普通に使えます。