2014年12月7日

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：問題制作者とのやりとり



というわけで、今回はflagのフォーマットが SECCON{〜} の形になっていると想定して進めます。
当初は全て8ビットバイトモードで記述されていると思って、8ビットバイトモードで求めていたのですが、うまくいかず...
というわけで、混合モードというものがあるそうで（初めて知った...
先頭の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コードが復元できます。

Time: 18:44 Tag:

0 件のコメント:

コメントを投稿

記事へのコメントはいつも確認している訳ではないので、お返事が遅れる場合があります。
ご質問やご意見は twitter@9SQ へお送り頂けると早くお返事できると思います。

登録: コメントの投稿 (Atom)