Qubic Rube writeup
この記事は
IQが1 Advent Calendar 2017 - Adventar
12日目の記事です。
12/9〜12/10のSECCONに出ていたらIQ1 っぽい問題(何)があったので解きました。IQ1 っぽくないpwnの問題は多分別の場所で書きます。
弊チームSSR_CTF_BUは国内22位(全体75位)だったので、国内決勝大会に出られそうです。めでたい。
各位のwriteupを見ていると正攻法でルービックキューブを解いた人はあんまりいなさそうですが、我々はばっちり正攻法でルービックキューブ解きました。辛かった。二度とやりたくねえ。
問題概要
Three.jsでQRコードが描かれたルービックキューブが回転しています。
ルービックキューブを解くと6枚のQRコードが発生し、そのうちの一枚に次のステージへのURLが入っているのでそれを50回やれ、という単純な問題です。
revフェーズ
チームメイトがデベロッパーツールでhttp://qubicrube.pwn.seccon.jp:33654/images/{stageid}_{face}.png で画像を持ってこれることを教えてくれました。なので、ここから画像を持ってくることにします。
ここでのfaceというのは面のことで、呼び方はここが詳しいです。
Up,Down,Right,Left,Back,Forwardでしょうか。
方針
方針は、
1.降ってくる画像からルービックキューブのキューブ文字列(UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBBみたいなの)に変換する
2.それをルービックキューブのライブラリに食わせ、解を得る
3.その解に基づき各マスを回転、移動させ、QRコードを復元する
の3段階で行きました。一番しんどいのは圧倒的に3です。
キューブ読み取り
画像処理にはおなじみのopenCVを使います。
方針としては、面を9分割して、ライブラリの要求する順番(U,R,F,D,L,Bの順)に文字として並べるという感じです。
まずダウンロードします。
namelist = ["U","D","L","R","F","B"] #02c286df1bbd7923d1f7 url_base = "http://qubicrube.pwn.seccon.jp:33654/images/"+stage+"_" for i in namelist: url = url_base+i+".png" name = url.split("/")[-1] print url,name urllib.urlretrieve(url,"{0}".format(name))
できました。
次に9分割します。
def getEachPanels(img): #https://github.com/muodov/kociemba #において、一面の画像を[1,2,3...9]の形で返します height, width, channels = img.shape hdiv3 = height/3 wdiv3 = width/3 ret = [] for j in range(3): for i in range(3): #sudo print j,i clp = img[j*wdiv3:(j+1)*wdiv3, i*hdiv3:(i+1)*hdiv3] ret.append(clp) return ret
できました。 ここで、imgはopencvの
img = cv2.imread(stage+"_{face}.png")
で読み取った結果です。 次に各マスの背景色を取得します。これは黒じゃないピクセルを一つ持ってくれば良いので、y=0のまま一行だけ見ました。結果はミスっていなかったのでOK。
#雑にy=0で横だけ見る、ダメならなおす def getBgColor(img): height, width, channels = img.shape for i in range(height): color = img[0, i] black = np.array([0,0,0]) if np.array_equal(black,color): continue else: return color
これで9分割したルービックキューブの1マス1マスの背景色が取ってこれるようになったので、キューブ文字列を作成できます。そこは各面に上記の関数を適用するだけなので省略します。
キューブを解く
得られたキューブ文字列をこれ
https://github.com/muodov/kociemba
に食わせて解を得ます。面倒なことはライブラリがやってくれます。
res = kociemba.solve(input_str)
解に基づいて画像を切り貼りする
ここからが本番です。
が、その前に各種機能を準備しておきます。必要なのは画像の回転と9分割した画像の結合です。
画像の回転は最初はアフィン変換を使っていたのですが、アフィン変換だと変更を繰り返していくと誤差がたまってひどいことになるので(下図)
正確に90の倍数度だけ回転するべく、90の倍数度だけ改めて以下の実装をしました。(アフィン変換のコードはどっかから持ってきた)
実は上記画像は中心の回転が正しくないのですが、それに関しては後述します。
def rotImg(img_src, deg): if deg == 90: ret = cv2.flip(img_src.swapaxes(1,0), 0) #print "ret",ret.shape ,"def",img_src.shape return ret if deg == -90: ret = cv2.flip(img_src.swapaxes(1,0), 1) return ret if deg == 180: ret = cv2.flip(img_src, 1) size = tuple([img_src.shape[1], img_src.shape[0]]) # 画像の中心位置(x, y) #center = tuple([int(size[0]/2), int(size[1]/2)]) center = tuple([size[0]/2, size[1]/2]) # 回転させたい角度（正の値は反時計回り） angle = deg # 拡大比率 scale = 1.0 # 回転変換行列の算出 rotation_matrix = cv2.getRotationMatrix2D(center, angle, scale) # アフィン変換 img_rot = cv2.warpAffine(img_src, rotation_matrix, size, flags=cv2.INTER_CUBIC) return img_rot
9分割した画像の結合は、numpyの結合でシュッとやりました。
def list2Img(v): #画像連結 #print v[0].shape, v[1].shape, v[2].shape r1 = np.concatenate((v[0],v[1],v[2]), axis=1) r2 = np.concatenate((v[3],v[4],v[5]), axis=1) r3 = np.concatenate((v[6],v[7],v[8]), axis=1) res = np.concatenate((r1,r2,r3), axis=0) return res
あとはチームメイトのルービックキューブのプロ氏(Aktzk)と頑張って各手続きを実装しました。
最初ここ
http://www.geocities.jp/russell_96owe/tyuutejunnkigou.html
の手続きを全部実装しようとしていたのですが(IQ1)アカテツくんの「6つだけ実装してあとはそれらの組み合わせで表現すればよくね？」の一言で実装量が1/3になりました。
(例えば、L'を実装したならばLはL'を3回、L2は2回やればよい。)
ルービックキューブとにらめっこして8時間くらい使いました。
頑張って実装した結果
def doProc(proc): global cube tmp = [] tmp2 = [] if proc == "L\'": #F左->U左 tmp = copy.deepcopy([cube["U"][0],cube["U"][3],cube["U"][6]]) cube["U"][0] = cube["F"][0] cube["U"][3] = cube["F"][3] cube["U"][6] = cube["F"][6] #U左->B右 tmp2 = copy.deepcopy([cube["B"][2],cube["B"][5],cube["B"][8]]) #0:x軸反転 1:y軸反転 -1:xy反転 cube["B"][2] = cv2.flip(tmp[2], -1) cube["B"][5] = cv2.flip(tmp[1], -1) cube["B"][8] = cv2.flip(tmp[0], -1) #B右->D左 tmp = copy.deepcopy([cube["D"][0],cube["D"][3],cube["D"][6]]) cube["D"][0] = cv2.flip(tmp2[2], -1) cube["D"][3] = cv2.flip(tmp2[1], -1) cube["D"][6] = cv2.flip(tmp2[0], -1) #D左->F左 cube["F"][0] = tmp[0] cube["F"][3] = tmp[1] cube["F"][6] = tmp[2] #左を回転 tmpimg = list2Img(cube["L"]) rotated = rotImg(tmpimg, 90) cube["L"] = getEachPanels(rotated) return if proc == "R\'": #U右->F右 tmp = copy.deepcopy([cube["F"][2],cube["F"][5],cube["F"][8]]) cube["F"][2] = cube["U"][2] cube["F"][5] = cube["U"][5] cube["F"][8] = cube["U"][8] #F右->D右 tmp2 = copy.deepcopy([cube["D"][2],cube["D"][5],cube["D"][8]]) cube["D"][2] = tmp[0] cube["D"][5] = tmp[1] cube["D"][8] = tmp[2] #D右->B左 tmp = copy.deepcopy([cube["B"][0],cube["B"][3],cube["B"][6]]) cube["B"][0] = cv2.flip(tmp2[2], -1) cube["B"][3] = cv2.flip(tmp2[1], -1) cube["B"][6] = cv2.flip(tmp2[0], -1) #B左->U右 cube["U"][2] = cv2.flip(tmp[2], -1) cube["U"][5] = cv2.flip(tmp[1], -1) cube["U"][8] = cv2.flip(tmp[0], -1) #右を回転 tmpimg = list2Img(cube["R"]) rotated = rotImg(tmpimg, 90) cube["R"] = getEachPanels(rotated) return if proc == "U\'": #F上->R上 tmp = copy.deepcopy([cube["R"][0],cube["R"][1],cube["R"][2]]) cube["R"][0] = cube["F"][0] cube["R"][1] = cube["F"][1] cube["R"][2] = cube["F"][2] #R上->B上 tmp2 = copy.deepcopy([cube["B"][0],cube["B"][1],cube["B"][2]]) cube["B"][0] = tmp[0] cube["B"][1] = tmp[1] cube["B"][2] = tmp[2] #B上->L上 tmp = copy.deepcopy([cube["L"][0],cube["L"][1],cube["L"][2]]) cube["L"][0] = tmp2[0] cube["L"][1] = tmp2[1] cube["L"][2] = tmp2[2] #L上->F上 cube["F"][0] = tmp[0] cube["F"][1] = tmp[1] cube["F"][2] = tmp[2] #上を回転 tmpimg = list2Img(cube["U"]) rotated = rotImg(tmpimg, 90) cube["U"] = getEachPanels(rotated) return if proc == "D\'": #F下->L下 tmp = copy.deepcopy([cube["L"][6],cube["L"][7],cube["L"][8]]) cube["L"][6] = cube["F"][6] cube["L"][7] = cube["F"][7] cube["L"][8] = cube["F"][8] #L下->B下 tmp2 = copy.deepcopy([cube["B"][6],cube["B"][7],cube["B"][8]]) cube["B"][6] = tmp[0] cube["B"][7] = tmp[1] cube["B"][8] = tmp[2] #B下->R下 tmp = copy.deepcopy([cube["R"][6],cube["R"][7],cube["R"][8]]) cube["R"][6] = tmp2[0] cube["R"][7] = tmp2[1] cube["R"][8] = tmp2[2] #R下->F下 cube["F"][6] = tmp[0] cube["F"][7] = tmp[1] cube["F"][8] = tmp[2] #下を回転 tmpimg = list2Img(cube["D"]) rotated = rotImg(tmpimg, 90) cube["D"] = getEachPanels(rotated) return if proc == "B\'": #L->U tmp = copy.deepcopy([cube["U"][0],cube["U"][1],cube["U"][2]]) cube["U"][2] = rotImg(cube["L"][0] , -90) cube["U"][1] = rotImg(cube["L"][3] , -90) cube["U"][0] = rotImg(cube["L"][6] , -90) #L->D tmp2 = copy.deepcopy([cube["R"][2],cube["R"][5],cube["R"][8]]) cube["R"][2] = rotImg( tmp[0] , -90) cube["R"][5] = rotImg( tmp[1] , -90) cube["R"][8] = rotImg( tmp[2] , -90) #R->D tmp = copy.deepcopy([cube["D"][6],cube["D"][7],cube["D"][8]]) cube["D"][8] = rotImg( tmp2[0], -90) cube["D"][7] = rotImg( tmp2[1], -90) cube["D"][6] = rotImg( tmp2[2], -90) #D->L cube["L"][0] = rotImg( tmp[0], -90) cube["L"][3] = rotImg( tmp[1], -90) cube["L"][6] = rotImg( tmp[2], -90) #Bを回転 tmpimg = list2Img(cube["B"]) rotated = rotImg(tmpimg, 90) cube["B"] = getEachPanels(rotated) return if proc == "F\'": #0:x軸反転 1:y軸反転 -1:xy反転 #U下->L右 tmp = copy.deepcopy([cube["L"][2],cube["L"][5],cube["L"][8]]) cube["L"][2] = rotImg(cube["U"][8], 90) cube["L"][5] = rotImg(cube["U"][7], 90) cube["L"][8] = rotImg(cube["U"][6], 90) #L右->D上 tmp2 = copy.deepcopy([cube["D"][0],cube["D"][1],cube["D"][2]]) cube["D"][0] = rotImg(tmp[0], 90) cube["D"][1] = rotImg(tmp[1], 90) cube["D"][2] = rotImg(tmp[2], 90) #D上->R左 tmp = copy.deepcopy([cube["R"][0],cube["R"][3],cube["R"][6]]) cube["R"][0] = rotImg(tmp2[2], 90) cube["R"][3] = rotImg(tmp2[1], 90) cube["R"][6] = rotImg(tmp2[0], 90) #R左->U下 cube["U"][6] = rotImg(tmp[0], 90) cube["U"][7] = rotImg(tmp[1], 90) cube["U"][8] = rotImg(tmp[2], 90) #Bを回転 tmpimg = list2Img(cube["F"]) rotated = rotImg(tmpimg, 90) cube["F"] = getEachPanels(rotated) return if len(proc) == 1: proc+="\'" doProc(proc) doProc(proc) doProc(proc) return if proc[1] == "2": doProc(proc[0]) doProc(proc[0]) return
デバッグ
ここまでのコードで回し始めると、13問目まで進んだところで進まなくなります。
出てくる画像を見ると、以下のように明らかに真ん中がおかしいので、真ん中の回転だけ4通り試すようにします。
それを修正してフラグが取れるコードは以下。
https://gist.github.com/ymduu/c122ba7a54f069902c76a10b983855aa
あとは50番目のQRコードに埋まっているフラグを取って終了
問題入力と結果を見てみます。
問題
結果
感慨深い。
SECCON{Thanks to Denso Wave for inventing the QR code}
ポエム
書く元気が消えた。なんなら書いたけど消したまである。CTFたのしい。
土日
消滅。
進捗
無い(理由:IQ1なので。)
明日のゼミ
誰がやるか決まっていない。クッソ怖い。IQ1なので進捗はない。
申し訳程度のIQ1ノルマを達成して終わりです。お粗末様でした。
