気合いで読むQRコード入門

この記事はKCS Advent Calendar 16日目の記事です。

概要

以前参加したSquareCTFでQRコードに関する問題が出たのでその解説をしていこうと思います。この問題に取り組むとQRコードの仕組みが大枠理解でき、カメラがなくてもQRコードを読めるようになります！（ホンマか！？）
別にCTFに参加したことがなくても聞いたことがなくても解けるレベルの問題なので興味のある方は記事を読む前に挑戦してみると面白いかもしれません。あと入門と書いてありますが続きはないです。

挑戦する方向けに、CTFでは回答さえ合っていれば良く、そのプロセスは問われないのでどう解いても構いません。QRの仕様についてはググったりしてもらっても全然大丈夫です。うまく復元できると、とある文字列が手に入るはずです（この大会では"FLAG"という文字列が含まれることがわかっています）。

問題のリンク

SquareCTF2018 C3 shredded
squarectf.com

解説

配布されたファイルを解凍すると27個の細長い画像ファイルが手に入ります。これが問題のタイトルからもわかるように、縦に分割されたQRコードです。

　　　　　　　　　　　　

↑こんなのが27枚

なんとなーくこれらをつなぎ合わせればQRコードになりそうなのが推測できますね！（？）

復元するに当たってQRコードの仕組みを大枠知っておく必要がありそうです。僕は以下のサイトを参考にしました。
(1)http://eleclog.quitsq.com/2014/01/seccon-ctf-2013-online-forensics-400.html
(2)http://www.swetake.com/qrcode/qr1.html
(3)http://nlab.itmedia.co.jp/nl/articles/1801/31/news008.html

QRコードにも色々種類があるらしい。まずバージョンですが、配布された画像を何枚か観察すると、縦は２１マスであることから今回はバージョン１のようです。そうなると27枚の画像のうちの真っ白の6枚は画像の両端になることがわかります。このようにまずは位置が確定できるものを探しましょう。バージョン１の場合は以下の画像の位置は固定なようです。

（画像は(2)のリンクより)

また上の画像の水色の部分に誤り訂正レベルやマスクパターンの情報が入るようです。これらは二箇所に同じ情報が同じ順番に15マスに渡って格納されます。以下の画像は今回の問題とは少し違うフォーマットですが、水色の部分の構造は同じです。

(画像は(3)のリンクより）

これらの情報を元に画像を埋めて行くと1,2,5,6,7,8,9,14,15,21列目が確定します。1列目や7列目は比較的確定するのが簡単ですが、5,9,15,21列目などは2対の15マスの形式情報が一致することを利用して絞っていきます。残りの画像のそれぞれの行の特徴から組み合わせを推測すると、3,4行目が2つ、16,20行目が2つ、17,18,19行目が3つ、10~13列目は7行目が白黒交互になることから、10,12行目で、11,13行目でそれぞれ2つとなりました。この時点で2x2x2x2x3!の96通りまで絞ることができました。

QRのルールを用いて絞って行くのはここまでが限界です（多分）。なのでここからは生のQRコードを読んで行きましょう笑。

QRコードの読み方は右下から２列に渡ってジグザグに読んで行きます。言葉だと伝わりにくいので、図を見てもらいましょう。

(画像は(3)のリンクより)

20列目になりうる画像は2つに絞れているので確定している21列目と合わせて見ましょう。

①　　　　　　　　　　②
　　　　　　　　　

しかしQRコードはこのままだと読むことができません。先ほどのリンクを読んでいただければわかるのですが、QRコードにはマスクがかかっています。そのマスクを解かなければいくら気合いがあっても読むことができません。しかもマスクにも何種類かあるらしい。。。

(画像は(1)のリンクより)

今回はラッキーなことに先程までの手順で絞れている画像からマスクパターンがわかります。この問題では(i+j)%3=0のところにマスクがかけられているようです。この式は一番左上の座標を(0,0)、右下を(20,20)とした時のi行目、j列目の座標(i,j)についての式です。上だと21列目と書いていたところは(i,21)ではなく(i,20)となることに注意してください。例えば(19,20)の座標は(19+20)%3=0を満たすので、1(黒)でxorします。

さてゴリゴリ読んで行きましょう。

①の画像は000001010100100010100100で②の画像は010000010100110011110000なのがわかります。これに先ほどのマスクをかけます。20,21行目にかけるマスクは011000011000011000011000であるので、

①
    000001010100100010100100
xor 011000011000011000011000 <-mask
-------------------------------------
    011001001100111010111100

②
    010000010100110011110000
xor 011000011000011000011000 <-mask
-------------------------------------
    001000001100101011101000

得られたbit列を精査して行きます。QRコードでは最初の4bitはモードを表します。数字モードなら0001、英数字モードなら0010、8bitモードなら0100、漢字モードなら1000です。①は0110、②は0010なので①の可能性が絶たれたと同時に今回は英数字モードであることがわかります。②と特定できましたが、他の列も特定するためにまだゴリゴリデコードして行きます。4bit以降に続くbitにはデータの文字数の情報が入っています。英数字モードだとこれを9bitで表すそうです。②の5bit目以降を見ると000011001であり、これを10進数に直すと25です。つまりデータ総数は25文字であることがわかります。おお！徐々に読めてきていますねぇ。感動します。

この文字数に続くbitから生のデータです。英数字モードでは11bit区切りでデータが格納されています。20,21行目の残りのbitも11bitなのでデコードして行きましょう。英数字モードではデータの格納がかなり特殊で、11bitのデータに2文字の情報が入っています。11bitのデータを10進数に直して、それを45で割った商が1文字目、余りが2文字目という構造をしています。8bitモードだと普通のasciiに準拠しているのですが、英数字モードは特殊な変換が必要なのですね。以下のリンクのテーブルを参照してデコードしましょう。

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

今回の続きは01011101000なので、10進数に直すと744です。744=16*45+24で、テーブルで16と24のところを引くと、出てくる2文字”GO”であることがわかります。
おおお！QRコードをカメラなしで読めています！ゾクゾクしますね！この調子です！

続く18,19行目も上記同様にゴリゴリ読んでください（書くの疲れた）。18,19行目になりうるのは3つに絞られているので、6通りの組み合わせをそれぞれデコードすると"GO"に続く文字であることから、どれが正しいかわかると思います。

これで16,18,19,20行目が特定できたので、あとは2x2x2の８通りに持ち込むことができました。まだまだゴリ押ししても構いませんが、これくらいに絞れたら全通り試せる数字になってきたので僕は全通り試して、実際にカメラに読み込ませました(←!?)。解ければいいんですよ解ければね。

ということで以下が修復されたQRコードです！！

お疲れ様でした〜。