SECCON CTF 2017 「Qubic Rube」を解きました(WriteUp)
昨年のSECCON TOWERに続き,今年もSECCON CTFに参加しました.
wgg.hatenablog.jp
所属している2つの大学サークル(RCC , RiST)の両方でチームが作られていたのですが,僕はRiSTの方から参加しました.
QubicRube(Programming 300pt)
Qubic Rube
Please continue to solve Rubic's Cube and read QR code.
http://qubicrube.pwn.seccon.jp:33654/
今回解いた問題です
与えられたサイトにアクセスすると,各面がQRコードでできたルービックキューブが回転しています.
6面のうちいずれか一つのQRに次のキューブへのリンクが書かれています.
QRの一つに No ○/50 と書かれており,全部で50回キューブを解くとクリアらしいことがわかります.
初めはキューブが完成した状態なので,そのままQRコードリーダで読み込めるのですが,問題が進むにつれて,少し回された状態のキューブが表示され,そのままでは読み込めなくなっていきます.
ソースコードを確認したところ,Three.jsで描画されており,入力によってキューブを回転させるようなコードも記述されていなかったので,画像を加工してQRを復元する必要がありそうです.
フラグ取得へのアプローチ
昨年度は,可能な限りフラグ取得までを自動化しようとした結果,時間が足りず解けなかったので,今回は「人力で困難な部分だけを自動化する」ことを目指して進めました.
1問解く際の流れは以下のようになっています.
今回は,このうち1. 2. をプログラムによって自動で取得できるようにしました.
1.各面の画像を取得
ここは単純です.
Three.jsのコードで各面の画像を読み込んでいるので,そのURLを生成して画像をダウンロードするシェルスクリプトを作成しました.
例えば,2問目(http://qubicrube.pwn.seccon.jp:33654/02c286df1bbd7923d1f7)の場合
var texture1 = new loader.load( "/images/02c286df1bbd7923d1f7_R.png" ); var texture2 = new loader.load( "/images/02c286df1bbd7923d1f7_L.png" ); var texture3 = new loader.load( "/images/02c286df1bbd7923d1f7_U.png" ); var texture4 = new loader.load( "/images/02c286df1bbd7923d1f7_D.png" ); var texture5 = new loader.load( "/images/02c286df1bbd7923d1f7_F.png" ); var texture6 = new loader.load( "/images/02c286df1bbd7923d1f7_B.png" );
と書かれていたので, "/images/<問題のURL>_<向き>.png" を取得すれば良いことがわかります
作成したシェルスクリプトは以下になります
#!/bin/sh mkdir "${1}_${2}" cd ${1}_${2} for i in R L U D F B do wget qubicrube.pwn.seccon.jp:33654/images/${2}_${i}.png done
2.取得した画像を分割・回転,位置の入れ替えによってQRを復元する
ここがこの問題の最もメインとなる部分です.
僕は,趣味でルービックキューブを遊んでいた時期があったので,その知識が活かされました.
先に書いておきますが,僕は画像処理によってこの問題を解いたので「QRコードは右半分があれば復元できる」などの知識は持っていません.
復元の基本的な手法は「存在しうる全てのキューブの組み合わせに対して,QRとして成立しているか判定する」,いわゆる総当りてきなやり方で見つけました.
ルービックキューブの構造について
まずは,ルービックキューブの基本的な構造について確認しておきます.
ルービックキューブは基本的に3種類のキューブで構成されています
- コーナーキューブ (1面につき4個)
- サブキューブ (1面につき4個)
- センターキューブ (1面につき1個)
今回解くルービックキューブは「絵柄付きキューブ」のため,センターキューブの回転を考慮する必要があります.
www.macozy.com
また,4つのコーナーキューブのうち3つは正方形が書かれており,1つはそうでない右下に当たる部分で,これの検出が可能と推測したので更に判別するパターン数を減らすことが出来ます.
よって評価を行うパターン数は
右下以外のコーナーキューブの組み合わせ:3! x サブキューブの組み合わせ:4! x センターキューブの回転:4 = 576通り
この576通りの中で,QRコードとして成立するものが存在するはずで,それを見つけだします.
入力画像を調べる
各面の画像を確認すると,「246x246」で「82x82」毎に3分割されていることがわかります.これを利用して,コーナーキューブ,サブキューブ,センターキューブそれぞれの画像を抽出していきます.
右下コーナーの識別
左のキューブは,右下コーナーでない模様,
右のキューブは,右下コーナーになるべき模様です.
右下コーナーにならない場合,薄い青で塗った領域が全て黒になるので,それを利用して右下コーナーか判別しました
青枠部分に背景色が1点でも含まれていたらその時点で右下コーナー確定です.
完成!
これでシャッフルされたルービックキューブの画像から,それぞれのQRコードを復元する事が可能になりました.
あとは1問ずつ解いて次の問題に進んでいくだけです(めっちゃめんどくさかった
#SECCON
— WGG (@WGG_SH) 2017年12月10日
シャッフルされたルービックキューブを15秒弱で復元するプログラム作ってました() pic.twitter.com/UW0lJaS6GR
Flag
SECCON{Thanks to Denso Wave for inventing the QR code}
QRコードって,株式会社デンソーウェーブさんが考案したらしいです,知りませんでした.
おわりに
1年ぶりにSECCONのQRコード問題に挑みましたが,今年は無事に解くことが出来て良かったです.
正直QRコードはしばらく見たくないってぐらいに見飽きました...
ソースコードは下に貼ってあるので(参考になるかわかりませんが)そちらも見てみてください.
ソースコード
QR復元を行うプログラムをC++ (+ OpenCV), その他のつなぎをshで記述しました.
Win32とWSLを組み合わせて動かしているので,そのへんは環境に合わせて適当にしてください
書き殴ってバグがあったら微修正する形で進めていたので,かなり汚いどころか,理論的に間違っていた部分もあるので御了承
// source.cpp #include <opencv2\opencv.hpp> #include <vector> using namespace std; // using namespace cv; // 色リスト const int COLORS[6][3] = { {255,213,0}, // 黄色 {255,88,0}, // 橙 {0,81,186}, // 青 {0,158,96}, // 緑 {196,30,58}, // 赤 {255,255,255} // 白 }; // 画像の回転 // 90度単位で正確に回転するために実装 void imgRotate(cv::Mat& src, int rotate) { cv::Mat dst = src.clone(); for (int x = 0; x < 82; x++) { for (int y = 0; y < 82; y++) { switch (rotate) { case 0: dst.at<cv::Vec3b>(y, x) = src.at<cv::Vec3b>(y, x); break; case 1: dst.at<cv::Vec3b>(y, x) = src.at<cv::Vec3b>(81 - x, y); break; case 2: dst.at<cv::Vec3b>(y, x) = src.at<cv::Vec3b>(81 - y, 81 - x); break; case 3: dst.at<cv::Vec3b>(y, x) = src.at<cv::Vec3b>(x, 81 - y); break; default: break; } } } src = dst.clone(); } // QRを構成する9枚の画像を入れる struct QRData { cv::Mat qrImage; // 合成画像 cv::Mat cornerImage[3]; cv::Mat subImage[4]; cv::Mat centerImage; cv::Mat lowerRightImage; // QRが正しいか判定 bool checkCorrect() const { // 6x6 の正方形が形成できない箇所が存在すればはずれ for (int x = 24; x < 222; x += 6) { for (int y = 24; y < 222; y += 6) { bool flag = true; int col = this->qrImage.at<cv::Vec3b>(y, x)[1]; // 初めの色(緑要素)を取得 緑が0のマーカはない for (int x2 = 0; x2 < 6; x2++) { for (int y2 = 0; y2 < 6; y2++) { if (col != this->qrImage.at<cv::Vec3b>(y + y2, x + x2)[1])flag = false; } } if (flag == false)return false; } } return true; } // QRコード画像を生成 // 9枚の画像を結合する void generateQR() { cv::Mat hImage[3]; // 1段目 cv::hconcat(this->cornerImage[0], this->subImage[0], hImage[0]); cv::hconcat(hImage[0], this->cornerImage[1], hImage[0]); // 2段目 cv::hconcat(this->subImage[1], this->centerImage, hImage[1]); cv::hconcat(hImage[1], this->subImage[2], hImage[1]); // 3段目 cv::hconcat(this->cornerImage[2], this->subImage[3], hImage[2]); cv::hconcat(hImage[2], this->lowerRightImage, hImage[2]); // 縦結合 cv::vconcat(hImage[0], hImage[1], this->qrImage); cv::vconcat(this->qrImage, hImage[2], this->qrImage); } }; // 左上に回転されたコーナーキューブの画像を渡すと,右下に配置すべきか判別する bool checkLowerRight(cv::Mat& src) { for (int x = 0; x < 42; x++) { for (int y = 0; y < 6; y++) { cv::Vec3b col = src.at<cv::Vec3b>(y + 24, x + 24); if (!(col[0] == 0 && col[1] == 0 && col[2] == 0)) { return true; } } } return false; } int main(int argc, char* argv[]) { // cout << argc << endl; std::string directoryName = ""; std::string fileID = ""; int color = 0; if (argc == 4) { directoryName = std::string(argv[1]) + "_" + argv[2]; fileID = argv[2]; color = atoi(argv[3]); } else { // デバッグ用 directoryName = ""; fileID = ""; color = 0; } std::string directions[6] = { "R","L","U","D","F","B" }; // 面の名称 cv::Mat cornerImage[4]; // コーナーキューブ: 使うのは[0-2]のみ cv::Mat subImage[4]; // サブキューブ cv::Mat centerImage; // センターキューブ cv::Mat lowerRightImage; // 右下用 int cornerCount = 0; int subcount = 0; // 6枚の与えられた画像を読み込む for (int i = 0; i < 6; i++) { cv::Mat image= cv::imread(directoryName + "/" +fileID+"_" +directions[i] + ".png"); // それぞれの画像を9分割する for (int x = 0; x < 3; x++) { for (int y = 0; y < 3; y++) { cv::Mat cutImage(image, cv::Rect(x * 82, y * 82, 82, 82)); // 色を調べる int width = cutImage.cols; int height = cutImage.rows; bool isTargetColor = false; for (int x2 = 0; x2 < width; x2++) { for (int y2 = 0; y2 < height; y2++) { if (isTargetColor)goto LOOP_END; int b = cutImage.at<cv::Vec3b>(y2, x2)[0]; int g = cutImage.at<cv::Vec3b>(y2, x2)[1]; int r = cutImage.at<cv::Vec3b>(y2, x2)[2]; if (r == COLORS[color][0] && g == COLORS[color][1] && b == COLORS[color][2]) { // 目的の色 // cv::imwrite("result/" + directions[i] + "_" + std::to_string(x) + "_" + std::to_string(y) + ".png", cutImage); isTargetColor = true; } } } LOOP_END:; if (!isTargetColor)continue; // 検出色の場合,黒領域の位置からコーナー/サブ/センターを判断 // ミス:コーナー/サブ/センターの判別はx,yから可能 // 右下のコーナー特定にはこの部分は必要 std::vector<cv::Point2i> blackPointList; for (int x2 = 0; x2 < width; x2++) { for (int y2 = 0; y2 < height; y2++) { int b = cutImage.at<cv::Vec3b>(y2, x2)[0]; int g = cutImage.at<cv::Vec3b>(y2, x2)[1]; int r = cutImage.at<cv::Vec3b>(y2, x2)[2]; if (r == 0 && g == 0 && b == 0) { blackPointList.push_back(cv::Point2i(x2, y2)); } } } // 黒の抽出完了 cv::Point2i center; for (auto point : blackPointList) { center += point; } center.x/= blackPointList.size(); center.y /= blackPointList.size(); // string position = ""; bool isXShift = abs(center.x - 41) > 6; // 要調整 bool isYShift = abs(center.y - 41) > 6; // 要調整 if (isXShift&&isYShift) { // position = "コーナーキューブ"; cornerImage[cornerCount++] = cutImage.clone(); // 回転を取得 int rotate = 0; if (center.x - 41 > 0 && center.y - 41 > 0)rotate = 0; // 左上 if (center.x - 41 > 0 && center.y - 41 < 0)rotate = 3; // 右上 if (center.x - 41 < 0 && center.y - 41 > 0)rotate = 1; // 左下 if (center.x - 41 < 0 && center.y - 41 < 0)rotate = 2; // 右下 imgRotate(cornerImage[cornerCount - 1], 4-rotate); // cout << rotate << endl; // cv::imshow("", cornerImage[cornerCount - 1]); // waitKey(); // cv::imwrite("result/corner_" + std::to_string(cornerCount) + ".png", cornerImage[cornerCount - 1]); if (checkLowerRight(cornerImage[cornerCount - 1])) { // 右下に置くべき画像だった lowerRightImage = cornerImage[--cornerCount].clone(); } } else if (isXShift ^ isYShift) { // position = "サブキューブ"; subImage[subcount++] = cutImage.clone(); // 回転を取得 int rotate = 0; if (center.x - 41 > 5)rotate = 1; // 左 if (center.x - 41 < -5)rotate = 3; // 右 if (center.y - 41 > 5)rotate = 0; // 上 if (center.y - 41 < -5)rotate = 2; // 下 imgRotate(subImage[subcount - 1], rotate); // cv::imshow("", subImage[subcount - 1]); // waitKey(); // cout << rotate << endl; // cv::imwrite("result/sub_" + std::to_string(subcount) + ".png", subImage[subcount - 1]); } else { // position = "センターキューブ"; centerImage = cutImage.clone(); } // cout << "(" << directions[i] << "," << x << "," << y << ")" << "=" << center << position << endl; } } } // 必要な画像の抽出完了 // 正しいQRになるように回転する // コーナーキューブの配置組み合わせ int cornerRow[6][3] = { {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}, }; // サブキューブの配置組み合わせ int subRow[24][4] = { {0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}, {1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0}, {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0}, {3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0} }; // サブキューブの回転対応リスト int rot[4] = { 0,3,1,2 }; // それぞれの対応のキューブを生成 QRData* qrData = new QRData(); qrData->lowerRightImage = lowerRightImage.clone(); imgRotate(qrData->lowerRightImage, 2); for (int i = 0; i < 6; i++) { // 右下以外のコーナー組み合わせリスト for (int i2 = 0; i2 < 3; i2++) { qrData->cornerImage[i2] = cornerImage[cornerRow[i][i2]].clone(); imgRotate(qrData->cornerImage[i2], i2 == 2 ? 3 : i2); } for (int j = 0; j < 24; j++) { // サブキューブの組み合わせリスト for (int j2 = 0; j2 < 4; j2++) { qrData->subImage[j2] = subImage[subRow[j][j2]].clone(); imgRotate(qrData->subImage[j2],rot[j2]); } for (int k = 0; k < 4; k++) { // センターキューブの回転 qrData->centerImage = centerImage.clone(); imgRotate(qrData->centerImage, k); // 画像の完成 qrData->generateQR(); // cout << "(" << i << "," << j << "," << k << ")" << endl; //cv::imwrite(std::string("result/") + argv[1] + "/" + std::to_string(i) + "_" + std::to_string(j) + "_" + std::to_string(k) + "_" + std::to_string(color) + ".png", qrData->qrImage); // 画像が正しいQRか判定し,正しければ書き出し if (qrData->checkCorrect()) { // cout << "Correct!" << endl; cv::imwrite(std::string("result/") +argv[1]+"/"+ std::to_string(i) + "_" + std::to_string(j) + "_" + std::to_string(k)+"_" +std::to_string(color)+".png", qrData->qrImage); //cv::imwrite(std::string("result/") + std::to_string(21)+"/" + std::to_string(i) + "_" + std::to_string(j) + "_" + std::to_string(k) + ".png", qrData->qrImage); } } } } return 0; }
#!/bin/sh # detect.sh mkdir "${1}_${2}" cd ${1}_${2} for i in R L U D F B do wget qubicrube.pwn.seccon.jp:33654/images/${2}_${i}.png done cd ../ mkdir result/${1} for i in `seq 0 5` do wcmd qubicrube.exe ${1} ${2} ${i} done