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