WhiteHat Grand Prix 2018 – Quals Writeup

この大会は2018/8/18 11:00(JST)~2018/8/19 11:00(JST)に開催されました。
今回もチームで参戦。結果は460点で361チーム中45位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome(10)

URLのページにアクセスして、slackにログインすると、メッセージにフラグが書いてあった。
f:id:satou-y:20180822205321p:plain

WhiteHat{WelcometoGrandPrix2018}

misc02 (Misc)

isoファイルが添付されている。FTK Imagerで開く。
以下をエクスポートしてみる。

・/CDROM/ETC/MAIL/PRIVATE.ASC
・/CDROM/ETC/MAIL/ENCRYPT.PYC
・/MAILDIR/CUR/15334499.com

まずはENCRYPT.PYCをデコンパイルする。

# Embedded file name: ./encrypt.py
import struct
import sys
import base64
password_enc = 'JTd1XyoIbmc3PWhpOjhfVhsIbmcAAAAA'
if len(sys.argv) != 2:
    print 'Usage: %s data' % sys.argv[0]
    exit(0)
data = sys.argv[1]
padding = 4 - len(data) % 4
if padding != 0:
    data = data + '\x00' * padding
result = []
blocks = struct.unpack('I' * (len(data) / 4), data)
for block in blocks:
    result += [block ^ block >> 16]

output = ''
for block in result:
    output += struct.pack('I', block)

print base64.b64encode(output)

パスワードを復号してみる。

import struct
import base64

password_enc = 'JTd1XyoIbmc3PWhpOjhfVhsIbmcAAAAA'
enc = base64.b64decode(password_enc)

result = struct.unpack('I' * (len(enc) / 4), enc)
blocks = []
for res in result:
    blocks += [res ^ res >> 16]
data = ''
for block in blocks:
    data += struct.pack('I', block)

password = data.replace('\x00', '')
print password

パスワードは Phu_Dong_Thien_Vuong。
ASCファイルがあったこともあり、15334499.comのメールから添付ファイルSaintGiong.jpg.pgpを取り出す。これを復号する際にこのパスワードを使う。

$ gpg --import PRIVATE.ASC
gpg: 鍵4BA9AFA0: 秘密鍵をインポートしました
gpg: 鍵4BA9AFA0: 公開鍵"whitehat <whitehat@bkav.vn>"をインポートしました
gpg: 鍵4BA9AFA0:"whitehat <whitehat@bkav.vn>"変更なし
gpg: 処理数の合計: 2
gpg:               インポート: 1
gpg:              変更なし: 1
gpg:       秘密鍵の読み込み: 1
gpg:   秘密鍵のインポート: 1

$ gpg SaintGiong.jpg.pgp 

次のユーザの秘密鍵のロックを解除するには
パスフレーズがいります:"whitehat <whitehat@bkav.vn>"
512ビットELG-E鍵, ID F0EE4293作成日付は2018-08-05 (主鍵ID 4BA9AFA0)

gpg: *警告*: 暗号アルゴリズムCAST5は受取人の優先指定に入っていません
gpg: 512-ビットELG-E鍵, ID F0EE4293, 日付2018-08-05に暗号化されました
      "whitehat <whitehat@bkav.vn>"

SaintGiong.jpgが取り出せた。あとはヒントにもあったが、outguessで秘密情報を取り出す。

$ outguess -r SaintGiong.jpg secret.txt
Reading SaintGiong.jpg....
Extracting usable bits:   65209 bits
Steg retrieve: seed: 70, len: 3388
$ cat secret.txt
While the sixth Hung Vuong Dynasty, our country, then called Van Lang was under the menace of the An , situated in the North of Vietnam’s borders.
Hung Vuong King was very worried and assembled his court to prepare a plan of defense for the country. A mandarin of the civil service reminded the King that the original founding King of the country, Lac Long Quan  had instructed that if the country were ever to face danger, it should pray for his help.
In that situation, the King then invoked the spirit of the founding King. 
Three days later, a very old man appeared in the midst of a storm and said that he was Lac Long Quan himself. He prophesied that in three years the An from the North would try to invade the country; he advised that the King should send messengers all over the country to seek help from talented people, and that thereafter a general sent from heaven would come to save the country.
Event though three years later, indeed came the tempestuous foreign armies trying to take over the Southern Kingdom. At the capital city of Phong Chau, King Hung Vuong still remembered the instruction from Lac Long Quan.
However Even earlier than, at the village of Phu Dong, County of Vo Ninh, Province of Bac Ninh, a woman in her sixties reported she had seen footprints of a giant in the field. 
Amazed, she tried to fit her feet in the footprints and suddenly felt that she was overcome by an unusual feeling. 
Thereafter she became pregnant and delivered a boy whom she named Giong. Even at the age of three, Giong was not able to crawl, to roll over, or to say a single word.
Surprisingly, at the news of the messenger from the King, Giong suddenly sat up and spoke to his mother, asking her to invite the messenger over to their home. 
He then instructed the messenger to request the King to build a horse and a sword of iron for him so that he could go and chase the invaders away.
When the horse and sword were eventually brought to his home, Giong stood up on his feet, stretched his shoulders, became a giant of colossal proportions, and asked his mother for food and new clothing. 
She cooked many pots of rice for him but it was not enough for his appetite. The whole village brought over their whole supply of fabric and it was still not enough for his size.
Giong put his helmet on, carried his sword, jumped on the back of his horse and rode away, as fast as a hurricane. The iron horse suddenly spit fire, and brought Giong to the front line at the speed of lightning. The invaders saw Giong like a punishing angel overwhelming them. 
Their armies were incinerated by the flame thrown from the horse's mouth. Their generals were decapitated by Giong’s sword. When it finally broke because of so much use, Giong used the bamboo trees that he pulled up from the sides of the road and wiped away the enemies.
Afterwards, he left his armor on the mountain Soc (Soc Son) and both man and horse flew into the sky.
Legend holds that lakes in the area of mountain Soc were created from the footprints of Giong’s horse. At the site of the forest where he incinerated the enemy armies is now the Chay Village ("Chay" meaning burned).
In recognition of Giong's achievement, King Hung Vuong proclaimed him Phu Dong Thien Vuong (The Heaven Sent King of Phu Dong Village). For the people of his country, he is better known as Thanh Giong ("Saint" Giong)

フラグは含まれていないが、行頭をつなげるとWHITEHAT...となっている。つなげてもあまり意味のあるフレーズではないが、このままフラグのルールに従い、答えてみる。

WHITEHATSHWSGTALI

このsha1の結果をsubmitしたら通った。

$ echo -n WHITEHATSHWSGTALI | sha1sum
05cc532353023d5954da9507e189a55296f6db97  -
WhiteHat{05cc532353023d5954da9507e189a55296f6db97}

re06 (Rev)

$ file reverse.exe 
reverse.exe: PE32 executable (GUI) Intel 80386 Mono/.Net assembly, for MS Windows

ILSpyでデコンパイルすると、key(入力データ)を暗号化して比較していることがわかる。関係するコードは以下の部分。

public static string Enc(string s, int e, int n)
{
	int[] array = new int[s.Length];
	for (int i = 0; i < s.Length; i++)
	{
		array[i] = (int)s[i];
	}
	int[] array2 = new int[array.Length];
	for (int i = 0; i < array.Length; i++)
	{
		array2[i] = MainWindow.mod(array[i], e, n);
	}
	string text = "";
	for (int i = 0; i < array.Length; i++)
	{
		text += (char)array2[i];
	}
	return Convert.ToBase64String(Encoding.Unicode.GetBytes(text));
}

public static int mod(int m, int e, int n)
{
	int[] array = new int[100];
	int num = 0;
	do
	{
		array[num] = e % 2;
		num++;
		e /= 2;
	}
	while (e > 0);
	int num2 = 1;
	for (int i = num - 1; i >= 0; i--)
	{
		num2 = num2 * num2 % n;
		bool flag = array[i] == 1;
		if (flag)
		{
			num2 = num2 * m % n;
		}
	}
	return num2;
}

private void btn_check_Click(object sender, RoutedEventArgs e)
{
	string text = this.tb_key.Text;
	string a = MainWindow.Enc(text, 9157, 41117);
	bool flag = a == "iB6WcuCG3nq+fZkoGgneegMtA5SRRL9yH0vUeN56FgbikZFE1HhTM9R4tZPghhYGFgbUeHB4tEKRRNR4Ymu0OwljQwmRRNR4jWBweOKRRyCRRAljLGQ=";
	if (flag)
	{
		MessageBox.Show("Correct!! You found FLAG");
	}
	else
	{
		MessageBox.Show("Try again!");
	}
}

暗号化しているが先頭から一文字ずつ変換しているので、ブルートフォースで復号する。

import struct

def mod(m, e, n):
    array = []
    num = 0
    while e > 0:
        array.append(e % 2)
        num += 1
        e /= 2

    num2 = 1
    for i in range(num-1, -1, -1):
        num2 = num2 * num2 % n
        flag = (array[i] == 1)
        if flag:
            num2 = num2 * m % n

    return num2

enc = 'iB6WcuCG3nq+fZkoGgneegMtA5SRRL9yH0vUeN56FgbikZFE1HhTM9R4tZPghhYGFgbUeHB4tEKRRNR4Ymu0OwljQwmRRNR4jWBweOKRRyCRRAljLGQ='
enc = enc.decode('base64')

flag = ''
for i in range(0, len(enc), 2):
    for code in range(32, 127):
        enc_val = struct.unpack('H', enc[i:i+2])[0]
        if mod(code, 9157, 41117) == enc_val:
            flag += chr(code)
            break

print flag

復号結果は以下の通り。

WhiteHat{N3xT_t1m3_I_wi11_Us3_l4rg3_nUmb3r}
$ echo -n N3xT_t1m3_I_wi11_Us3_l4rg3_nUmb3r | sha1sum
be1f21d22d6ca5854be238772c7ac594eadc5ab0  -
WhiteHat{be1f21d22d6ca5854be238772c7ac594eadc5ab0}

misc04 (Misc)

$ nc misc04.grandprix.whitehatvn.com 1337
                   Wellcom to Friendly face challenge
According to experts, the formula for measuring the friendliness of a face is
    (lip point**nose point)**(eyes point**forehead point) mod Face_index
                              Now play!
------------------------------Stage 1--------------------------------------
Face_index: 4431737
Face           Lip point      Nose point     Eyes point     Forehead point 
:-)            596242442      481469043      970458274      32703946       
(';')          376021014      272175871      239425572      184621759      
(=^..^=)       485755959      459822117      70984484       6425194        
:)             977865016      739654486      296805231      562258274      
:-]            914395562      938717142      921361199      576965573      
:]             336429352      943961753      752611213      95370167       
:-3            165943262      966598407      516473754      772879133      
:3             889297404      23840982       606500337      736303577      
:->            541245039      283886587      250236527      771824867      
:>             636612689      936249233      319980673      338877742      
:-*            241647692      317174427      975314731      502081872      
:*             271638886      843604355      472679688      853083969      
(>_<)          633930454      209230772      52469366       895198448      
(>_<)>         995527139      208600614      858498435      577040482      
(';')          848596099      405700489      337685577      326163258      
(^_^;)         988185554      243044144      381916894      268647763      
(-_-;)         870125849      588116350      324643650      969271622      
(~_~;)         591753167      492749098      383987089      89199361       
(...;)         465374817      677444547      342357343      575883393      
(._.;)         525027485      646708335      571869565      488171404      
^_^;           95013153       882921976      251013374      223048438      
(#^.^#)        972541934      323081701      97697337       965645600      
(^^;)          168319131      893468036      677026321      667083111      
(-_-)zzz       460308725      713998921      157547765      873272113      
(^_-)          469080168      586577044      302298730      848820916      
((+_+))        310684442      806220740      489486988      730554133      
(+o+)          341931559      973851008      634295881      273149870      
^_^            435459073      803947061      403135837      249163168      
(^_^)/         817248024      461457840      122466022      287654650      
(=_=)          845486756      431899563      497453104      360016272      
(?_?)          347478160      220003849      28100026       958712334      
(^_^)          626921993      801762983      661020071      997855657      
(~o~)          225789800      631406677      535015751      189783066      
(~_~)          807938286      952126927      764786442      638732424      
o.O            871975848      257408524      426299419      59896758       
(o.o)          63223248       978835775      546529382      264433328      
oO             679254801      413413444      55017139       283662476      
<_<            736488270      359509676      929803086      369891930      
>_>            299626511      442201749      519739934      670684760      
<o?o>          674680095      856927711      496756490      81590770       
(>^.^)         780245547      254744992      229038267      629703628      
(^.^<)         405281708      687157157      353015431      755281648      
>,<            106378055      890404087      529192804      606538580      
;-(            513181644      459706648      529613032      931311838      
>:-(           587016768      782815123      713576827      321597509      
@(-_-)@        840506996      817976971      661753791      145890981      
@(^_^)@        863474035      182809717      514177192      793174325      
~O-O~          601211571      288325382      344765291      760697124      
:)]            991917239      864698356      68391752       351680770      
.-]            850742773      807690508      545894722      208852551      
.-)            455598369      432662165      229771808      821952329      
,-)            213887745      346518966      711375633      250280917      
':-(           385654334      97532947       860838537      433534132      
'-)            179269337      658324086      844837058      417744279      
:-D            466848302      21928777       173955338      339563435      
:=)            913770274      142738487      639227727      617937904      
:@             98765894       80122883       376496439      512041497      
<:-P           203112529      952067844      367806426      985693940      
:)>-           745938793      316337810      889074330      870349911      
:^)            78379055       630302543      166701512      857017312      
3:]            971098181      397257584      918930423      279788878      
(o^-^o)        914732303      267597906      802970827      263807313      
:-<            223587166      847745996      586708464      364485219      
:-[            88492755       312737068      227998177      147624657      
=:-)           234906718      528787599      937723179      306554978      
:-))           52586325       461817008      128874650      893917472      
<(-_-)>        760182940      838643548      569363638      165283155      
9_9            467028132      200982165      373411705      677154110      
=))            74217800       328284351      544357486      389014675      
7:)            902982576      879211080      828715890      606436127      
(<_>)          2776721        76548332       865922170      259242177      
:-(            329706650      201191399      779171278      178316061      
/:-)           703311712      629592477      807987564      737871016      
(-_-)          774112499      869284313      888552912      485637638      
:-*            680165343      32169796       588924131      455402899      
::=))          687239847      415460801      14828524       814673043      
o_o            849115553      951309125      769144825      682517755      
(*^_^*)        366967935      996883255      849091516      246423566      
(-::-)         64120405       829403093      668581993      835182060      
(^o^)          639633361      468110723      19523831       330311527      
:o)            803410338      522232647      772545391      737437770      
:|)            484447392      666349300      258910284      78499833       
:)             409969972      118803071      710326500      629936392      
:-)            420257921      758815700      702535489      591591244      
+:-)           507046230      974840616      136692833      433025097      
(:-)           931372485      303883708      928836052      845244431      
{:-)           414675990      737799366      915519879      946345418      
^&^            456715850      142166824      722043282      192560271      
=.=            854827506      962541908      219205017      564922319      
*~*            900518063      723307297      400360093      18021808       
(:>-<          409382634      372954587      455650500      452411178      
:-)---         765540422      292310472      220804776      20363262       
*-)            397286723      348184258      389371743      671368534      
>:*            456816308      557167076      448745985      898262835      
>.<            12017132       326539650      358099709      282393116      
:-@            20947658       86440236       159831491      77993591       
(:)-)          904767042      791772164      496897476      164869087      
::-)           483154180      173670907      43310880       167017739      
:-@            198644174      596224399      626716663      456640512      
@,.,@          935382486      691468677      584587520      179793294      
:-E            886076455      133288396      888456455      587622650      
:-[            833439341      164664199      751477298      722238083      
:-))           268158726      596277349      101793289      489763555      
:-[]           407141231      937381763      271820471      265582637      
:-)))          196127048      499086408      990692220      2709060        
(:-            530684193      355430256      33688527       743788259      
$_$            316493696      195845248      525788623      511389186      
(^:^)          644677468      362317579      479927686      853389642      
|___|          538871904      466692897      66164139       438963213      
:-)            7578352        593661332      991357690      997018911      
>O<            891811590      97984259       991030669      385697450      
:=)            252470814      906895930      98153725       829521427      
-:-)           901385711      643039757      71143493       147926124      
|:-)           695240184      778952493      491221544      894194207      
<(^.^<)        467571699      733944108      791210408      100078959      
<(*.*<)        679554586      373254869      810247219      294345618      
(*_*)          651786733      266904383      29442527       770000822      
._.            257615504      236664306      608767705      600223050      
@:-)           880803862      926737903      452048108      454010314      
<('.')>        733058449      892810814      773530725      528000556      
<('.'<)        579430788      304149147      577861147      583328793      
<(^.^)>        507019421      322208452      317046110      376912296      
<('.'<)        898401668      183862749      636714889      651053202      
:-*            590108193      139904728      644562260      706500409      
(:-*           514296447      200156909      401814197      105831470      
=^.^=          702596661      515873731      151349969      623222790      
<{::}>         478232622      936554793      478880525      609936656      
:-D            49331946       257073961      139570287      615626763      
:))            252760793      192745055      823359582      852633482      
:.-)           863450527      693239366      746928783      389664603      
(-:            835350723      340687976      181493414      47548225       
>;->           421466938      907922662      724741530      713999622      
:^o            259616359      79906074       328077364      655097082      
:-9            62427531       565086054      667084032      441954088      
So, what is the most friendly face?

(lip point**nose point)**(eyes point**forehead point) mod Face_index
をまともに計算すると時間がかかり終わらない。

中国人剰余定理などを使って、時間がかからない計算式に変える。

a = lip point
b = nose point
c = eyes point
d = forehead point
n = Face_index

pow(a ** b, c ** d, n)
= pow(pow(a, b, n), pow(c, d, phi), n)

nを素因数分解する必要あり。

phi = (p1-1) * (p2-1) * (p3-1) ...

あとはfriendlinessのポイントの高い顔文字とポイントを答えていく。

import socket
import re
from factordb.factordb import FactorDB

def get_friendliness(lip, nose, eyes, forehead, index, phi):
    return pow(pow(lip, nose, index), pow(eyes, forehead, phi), index)

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('misc04.grandprix.whitehatvn.com', 1337))

while True:
    data = recvuntil(s, 'So, what is the most friendly face?\n')
    print data

    pattern = 'Face_index\: (.+)'
    m = re.search(pattern, data)
    face_index = int(m.group(1))

    f = FactorDB(face_index)
    f.connect()
    elms = f.get_factor_list()
    dic_elms = {}
    for elm in elms:
        if elm not in dic_elms:
            dic_elms[elm] = 1
        else:
            dic_elms[elm] += 1

    phi = 1
    for elm in dic_elms:
        phi *= (elm - 1) * elm ** (dic_elms[elm] - 1)

    pattern = 'Forehead point \n(.+)\nSo, what'
    m = re.search(pattern, data, re.DOTALL)
    face_table = m.group(1).split('\n')

    faces_points = {}
    for line in face_table:
        face = line.split()[0]
        points = map(int, line.split()[1:])
        friendliness = get_friendliness(points[0], points[1],
            points[2], points[3], face_index, phi)
        faces_points[face] = friendliness

    best_face = max(faces_points, key=faces_points.get)
    print best_face
    s.sendall(best_face + '\n')
    data = s.recv(1024)
    print data

    best_point = faces_points[best_face]
    print best_point
    s.sendall(str(best_point) + '\n')
    data = s.recv(1024)
    print data
    if 'WhiteHat{' in data:
        break

5回正解すると、フラグが表示された。

WhiteHat{^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^}
$ echo -n "^.^_M4th_Math_Chin3se_Rema1nder_The0rem_&_Euler's_ThEorem_M@th_MAth_^/^" | sha1sum
883e8e59798f1884c3873ff5f47aaeea089097f9  -
WhiteHat{883e8e59798f1884c3873ff5f47aaeea089097f9}