SECCON CTF 2014 online予選 QR400

前回の2013年で出た問題の逆(？)パターンでしたね。

問題：BBQR
Let's enjoy BBQR!

とりあえず、まずは問題の画像から読み解きます。
写っているマーカーと形式情報から、バージョン3のQRコードの左半分っぽいですね。

形式情報は全部残っていて、001011010001001と読めます。
誤り訂正レベル(Error Correction Level)：00
マスクパターン参照子(Mask Pattern)：101
誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)：1010001001

なので、訂正レベルH、マスクパターンは市松模様だと分かります。
バージョン3で訂正レベルHのQRコードは、データコード数26、エラー訂正コード数44、RSブロック数2です。

合成すると...

キレイにE1〜E44までのエラー訂正コードが残っています。
キレイにするとこんな感じかな？

左下図の赤がマスクパターン、右下図はパターンに従ってマスクしたところ。

このアンチマスクを合成して...

これを読んでいくと、下表のとおり。

以下のページを参照すると
http://www.swetake.com/qrcode/qr3.html

f(x)をg(x)で除算して... 排他的論理和を計算して... というのを26回ほど繰り返すと剰余R(x)が出てくるという感じだそうで。

データコードを係数とした多項式f(x)→これが分かるとflagが出てくる
エラー訂正コードの生成多項式g(x)→データコード数から算出可能
剰余R(x)→今回のQRコードで残っている部分

ここでタイムアップでした。

ここから先、解けたら追記していきます。
というより、このアプローチで正しいのかすら分かりません。
前回同様に人力解読に挑戦していますが、QRコードリーダのプログラムを上手く改良してエラー訂正コードのみからデータを取り出せるようにすることが出来るかもしれませんし...

※まだ解けてないので、上の画像(QRコードや表、剰余の式)は正しいと保証できませんのであしからず...

追記 2014/12/07 20:24：マスクパターンを掛け間違っていたので、画像を差し替えました

追記 2014/12/08 03:40：問題制作者とのやりとり

@9SQ ゼロ知識から本当に手計算で解く、って意味なら無理だと思う。フラグ形式がそうなってる、って情報は今だからわかることであって、もしかしたら別の情報も入ってたかもしれないし。リードソロモンの仕組みを確認したい、って意味なら止めない。かなり勉強になるはず。
— きくちゃん (@kikuchan98) 2014, 12月 7

手動解析、朝が来るまでに終わるのか pic.twitter.com/Xm4QGqzTBR
— けーいち (@9SQ) 2014, 12月 7

@9SQ あー、そういうアプローチかー。いいね。
— きくちゃん (@kikuchan98) 2014, 12月 7

というわけで、今回はflagのフォーマットが SECCON{〜} の形になっていると想定して進めます。
当初は全て8ビットバイトモードで記述されていると思って、8ビットバイトモードで求めていたのですが、うまくいかず...

@9SQ パンケーキの方と比べてみるとわかるけど、モードは混在できるのよ。
— きくちゃん (@kikuchan98) 2014, 12月 7

というわけで、混合モードというものがあるそうで（初めて知った...
先頭のSECCONは英数字モード、それ以降の{〜}を8ビットバイトモードであると仮定して...

英数字モード6文字=0010 000000110
SE=45*28+14=1274=10011111010
CC=45*12+12=552=01000101000
ON=45*24+23=1103=10001001111
ここまでで、4+9+11+11+11 = 46 bit

8ビットバイトモード18文字=0100 00010010
{=123=01111011
ここまでで、66 bit → 66/8 = 8.25 → D1〜D9の先頭2bitまで分かる

逆に終端は
}=125=01111101
ここまでで、202bitなので208bitになるように6bitを0で埋める

??011111 → D25
01000000 → D26

残り、D9後半6bit〜D25先頭2bitまでの合計128bit、16文字が不明。

αの指数と整数の対応表は http://www.swetake.com/qrcode/qr_table4.html を参照

でも、この手法だと8回目で計算できなくなる...


色々とアレだったので、改めて解法を別記事に書き直します...
(問題作成者からもアドバイスを頂いたので、それも含めて。)

以下おまけ。元々のD1〜D26。

これを当てはめて市松模様でマスクを掛けると以下のQRコードが復元できます。