WGGの活動log

都内でゲーム開発だったりVRだったりをしてるかもしれないエンジニアです. WGGは「ワグ」と読みます

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コードでできたルービックキューブが回転しています.
f:id:wgg00sh:20171210130851p:plain




6面のうちいずれか一つのQRに次のキューブへのリンクが書かれています.
QRの一つに No ○/50 と書かれており,全部で50回キューブを解くとクリアらしいことがわかります.
初めはキューブが完成した状態なので,そのままQRコードリーダで読み込めるのですが,問題が進むにつれて,少し回された状態のキューブが表示され,そのままでは読み込めなくなっていきます.

f:id:wgg00sh:20171210131120p:plain

ソースコードを確認したところ,Three.jsで描画されており,入力によってキューブを回転させるようなコードも記述されていなかったので,画像を加工してQRを復元する必要がありそうです.

フラグ取得へのアプローチ

昨年度は,可能な限りフラグ取得までを自動化しようとした結果,時間が足りず解けなかったので,今回は「人力で困難な部分だけを自動化する」ことを目指して進めました.

1問解く際の流れは以下のようになっています.

  1. 各面の画像を取得
  2. 取得した画像を分割・回転,位置の入れ替えによってQRを復元する
  3. 復元したQRを読み込み,次の問題へのリンクを取得する

今回は,このうち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コードとして成立するものが存在するはずで,それを見つけだします.

入力画像を調べる

f:id:wgg00sh:20171210140725p:plain
各面の画像を確認すると,「246x246」で「82x82」毎に3分割されていることがわかります.これを利用して,コーナーキューブ,サブキューブ,センターキューブそれぞれの画像を抽出していきます.

右下コーナーの識別

f:id:wgg00sh:20171210144342p:plain

左のキューブは,右下コーナーでない模様,
右のキューブは,右下コーナーになるべき模様です.

右下コーナーにならない場合,薄い青で塗った領域が全て黒になるので,それを利用して右下コーナーか判別しました
青枠部分に背景色が1点でも含まれていたらその時点で右下コーナー確定です.

QRコードとして成立するものの識別

ここまでで,先に上げた576通りを作るための画像の分別が完了しました.
ここからは,実際に576通りのQRコード(仮)の画像を作成して,その全てに対して本当にQRコードなのか調べていきます
f:id:wgg00sh:20171210144935p:plain
このようにQRコードっぽい画像が576枚生成されます.

画像サイズから見る不適切なQRの識別方法

合成したQR画像は,元の各面画像と同じ「246x246」です.
画像を拡大して見たところ,QRの各ビットは「6x6」の正方形で描画されています.
しかし,分割された画像は「82x82」で6の倍数では無いため,不適切な結合をしている場合「つなぎ目が正方形で無くなる」可能性が高いという特徴があります.

f:id:wgg00sh:20171210145817p:plain

正しく復元ができている場合,そのようなつなぎ目は発生しないため,6x6正方形以外の黒領域が出来ているQRコードを全て除外します.
今回の50問では,これによって不適切なQRコードが残ることは一度もありませんでした.

f:id:wgg00sh:20171210150014p:plain

完成!

これでシャッフルされたルービックキューブの画像から,それぞれのQRコードを復元する事が可能になりました.
あとは1問ずつ解いて次の問題に進んでいくだけです(めっちゃめんどくさかった

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