The Success of the Qiangwang Cup
After the last failed experience, I expected the upcoming Qiangwang Cup Youth CTF to be much more straightforward, but reality proved otherwise.
Below is the write-up in the order I solved the problems (this time, I was the only one to solve them, not bad!):
1. Check-in
Opening the exe immediately revealed the flag (super happy to get the first blood):
flag{鲸鱼带你进入鲸奇世界}
2. Lihua's for
Step 1: Unpacking:
Step 2: Open the 64-bit IDA and locate the main function
int __cdecl main(int argc, const char **argv, const char **envp)
{
char flag[42]; // [rsp+20h] [rbp-60h] BYREF
int a[42]; // [rsp+50h] [rbp-30h] BYREF
int b[42]; // [rsp+100h] [rbp+80h]
int i_0; // [rsp+1B4h] [rbp+134h]
int i; // [rsp+1B8h] [rbp+138h]
int good; // [rsp+1BCh] [rbp+13Ch]
_main();
qmemcpy(a, &unk_403040, sizeof(a));
puts("input flag");
scanf("%s", flag);
puts(flag);
for ( i = 0; i <= 41; ++i )
b[i] = i ^ flag[i];
for ( i_0 = 0; i_0 <= 41; ++i_0 )
{
if ( a[i_0] != b[i_0] )
{
good = 0;
break;
}
good = 1;
}
if ( good == 1 )
printf("good~");
else
printf("error!");
return 0;
}
It can be observed that the program works by XOR-ing each user input flag[i] with i and then comparing it to a[i].
Step 3: Simply dump the values of a[i] and write an exploit to recover the flag.
(Another quick reverse-engineering check-in problem solved.)
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[] =
{
0x66, 0x00, 0x00, 0x00, 0x6D, 0x00, 0x00, 0x00, 0x63, 0x00,
0x00, 0x00, 0x64, 0x00, 0x00, 0x00, 0x7F, 0x00, 0x00, 0x00,
0x64, 0x00, 0x00, 0x00, 0x32, 0x00, 0x00, 0x00, 0x36, 0x00,
0x00, 0x00, 0x6A, 0x00, 0x00, 0x00, 0x6C, 0x00, 0x00, 0x00,
0x3E, 0x00, 0x00, 0x00, 0x3D, 0x00, 0x00, 0x00, 0x39, 0x00,
0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x6F, 0x00, 0x00, 0x00,
0x3A, 0x00, 0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x77, 0x00,
0x00, 0x00, 0x3F, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00,
0x25, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x22, 0x00,
0x00, 0x00, 0x3A, 0x00, 0x00, 0x00, 0x7A, 0x00, 0x00, 0x00,
0x2E, 0x00, 0x00, 0x00, 0x78, 0x00, 0x00, 0x00, 0x7A, 0x00,
0x00, 0x00, 0x31, 0x00, 0x00, 0x00, 0x2F, 0x00, 0x00, 0x00,
0x29, 0x00, 0x00, 0x00, 0x29, 0x00, 0x00, 0x00, 0x16, 0x00,
0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x44, 0x00, 0x00, 0x00,
0x45, 0x00, 0x00, 0x00, 0x12, 0x00, 0x00, 0x00, 0x47, 0x00,
0x00, 0x00, 0x47, 0x00, 0x00, 0x00, 0x41, 0x00, 0x00, 0x00,
0x1A, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
int main()
{
for(int i=0;i<42;i++)
{
for(int t=1;t<255;t++)
{
if((i^t)==a[i*4])
{cout<<char(t);break;}
}
}
return 0;
}
flag{a41be465-a50f-4124-b7ba-2766aff6baf2}
3. Crypto2
Given that:
n1=20663949646446787716947370247427064802032290773674573417491154934657966734874241036307633567695175131014840617208051931753476223149652427133485160771068994073566431652969243962290116898345337189704974833817335135391974497754670322430159624252007005736522065638860351992074099453212550475552692645688800084354832716662142860413158369020005830095049988807931794736876563293916525328174812726514626029103506607813186690909585870115364600969148482617083817273910020722354923244093624032174432568413187131385994452769295894606345768596899824635672699945050103814681553981019917552667794514804359500108947102234376726009329
n2=23260834024376640092536888922041147168387702014814910549469730354688848760379274203088716649609675449936234732528778557041701524981200368996310064584479657042098426164366286670115392015865853892816983885530312074073396422301009513106258655315791720535737587913264728919869055970993613641008348186263870234072422880033882864603438907070864271470483691729705421547143623305055532339107777314310976947392833395180922324243244784018964736826235018388498516438612962123562977736924674510730898077787055367234786519915374446506561992135856904927351307275140543635152771670410211235702283822782412971646092584646758107766061
c1=20522772249591436865905796103232542494211695376973377722875606678999899690405480809231671346489821878050354380591999935960795888483664473952207298504196203830543208477229162177648586683957831016664569242538775928728009699300145355818417233892295367828930893733774091897666206696635744262884229680137381841581000794056156842812583057103472764486608022028638288161256424936523444974815727764620634174112474612238992061186937613171878635903455700636894570504376153482600057655480654731180740098435209814585459376319844315388048636156465832997913885636776523217188604040216732137108997444787157007665652718553013424347649
c2=18715009944766815149492560645051626329204114049927707292306481018724323433701970253541495090244787378826569549885480491764057526828531429033378143426272248940256432423939977805246742287886281853484696625486522535042794403288199393432900065504766428665320682811338887618389589263597065738414638013423594446322359052784842619755053094028050245325637698678444632860097510081832077842610716042473697478416213915805481704537884611126069907812621750817901278803326304784057145916721693930579344441283586458621033705530309835431139751025999089707480829034535026967779441379062426254038310930863215188888662357133997908688736
e=65537
Upon inspection, n1 and n2 are not coprime. You can refer to this method use a common factor attack to perform the decryption.
import gmpy2
from Crypto.Util.number import long_to_bytes
c1 = ...
c2 = ...
n1 = ...
n2 = ...
e = 65537
p12 = gmpy2.gcd(n1, n2)
assert (p12 != 1)
q1 = n1 / p12
q2 = n2 / p12
d1 = gmpy2.invert(e, (p12 - 1) * (q1 - 1))
d2 = gmpy2.invert(e, (p12 - 1) * (q2 - 1))
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
print long_to_bytes(m1)+long_to_bytes(m2)
flag{afb1e6f2-9acb-efde-ad7c-246a99d8f1fd}
4. Jigsaw Puzzle
I could maybe write a script to solve this challenge, but I couldn't, so I had to visually inspect the unusual images and piece them together into a single image: (edited using PowerPoint)
At this point, I was stuck, but my rank was around 30+, just a few spots away from the offline cutoff. And I happened to be blocked on a misc problem that seemed solvable:
So I reached out to that student from Anhui (I met him this March—after a summer of practice, he had improved a lot) to do a write-up trade. I gave him the solution for a reverse challenge, and he gave me the write-up for this problem.
I submitted flag{Hamsters_are_so_cute}, but it was incorrect. Considering that there was no closing brace immediately after cute, it suggested that some punctuation might be occupying that space. Easily overlooked punctuation includes '!' and '|', because they could be confused with the braces and cause a wrong submission. By adding 1–5 '!' or '|' after cute, I finally got the correct flag:
flag{Hamsters_are_so_cute!!!}
Who would have thought of that!!!
5. Crypto1
With only 20 minutes left before the competition ended, I was sitting at rk22. Based on the pattern from the last contest, the final ranking would surely drop quickly, so I had to AC one more problem to secure my spot in the onsite competition.
So we have:
n=96722669749951212913756678234358651184134068407812470434435916603156818917545841439779031943800634250032106764154804309935557678512858630048212204696471487762160744924838010746445510979202735123140536599975731157563069594497905809587369126155476201977830809090473053692189364335223367147692962090288185113654598050169422517553085833257142179937154768657039042632343562454149914801329414293361879935460883633117988279426277638667508115319494914342600199690237441851088350726869553691992122821267990343643644523989413546160765907845604067031798179773495433134648132709349683621175243064236059479837244518879574919017301667066698329442453248971033564328161407342561250703168154214939772631586519304164853651
c1=66738113223447221430009739914948303261002811553064307532926788024694319846909340806982708347904688420671656410554852340732395818007063648478593071665936277836988050526188064146099581039172667768507259894363266310279948729552649788129953872816024709989260060633285022337107662251504618369065597018450927041881262189584381809106166042131798086882746986243210896131714227544235843922107304728228549916171484199199612243776469423359120753888158616202476325705252715374109256790899923317253605743212561589807498078080069511918514647943399566630574192829185904868376879831247378819590121286186417825591746918495311372015707767009078229770450338244309693800180936418605756818618708750868807720566288044943952844
c2=88330949146651042517337653740810385187361689012501792799900873279978736035790659211001047937337215121948527017022967642906632732136313750277237761910710915459733551421653259986088596828049455592613225962133163865584111828012197112528645520371075411167515961263199635568730334149461654340122507778194391601956023625429418297129608911450200836427221311442323768087256798964844787274408624548839536279704401007441198390922847003287643673183230633728790263593607595427088882078742699027563601046309308221108391158848644822374865676056755011459026909057983805069264236657111115914570543103494726584296335044897998794251877515750910330960179539465060133592380802344398038815679281272098815068185059127533110716
e1=49
e2=35
It's clearly a common modulus attack scenario, but e1 and e2 are not coprime; their greatest common divisor is 7.
Here, we need to divide e1 and e2 both by 7, turning m into
. At this point, a low exponent attack can be applied. The problem's code is as follows:
# py2 sameNAttack.py
import primefac
from Crypto.Util.number import long_to_bytes
n=...
e1=...
e2=...
c1=...
c2=...
def same_n_attack(n,e1,e2,c1,c2):
def egcd(a,b):
x, lastX = 0, 1
y, lastY = 1, 0
while (b != 0):
q = a // b
a, b = b, a % b
x, lastX = lastX - q * x, x
y, lastY = lastY - q * y, y
return (lastX, lastY)
s = egcd(e1,e2)
s1 = s[0]
s2 = s[1]
if s1 < 0:
s1 = -s1
c1 = primefac.modinv(c1, n)
if c1 < 0:
c1 += n
elif s2 < 0:
s2 = -s2
c2 = primefac.modinv(c2, n)
if c2 < 0:
c2 += n
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
i = 0
while 1:
if gmpy2.iroot(m + i * n, 7)[1] == True:
print(long_to_bytes(gmpy2.iroot(m + i * n, 7)[0]))
break
i += 1
return flag
c = res = str(hex(same_n_attack(n,e1,e2,c1,c2)))[2:-128]
print res
flag = ''
for i in range(0,len(res),2):
ch = res[i]+res[i+1]
flag += chr(int(ch,16))
print flag
flag{8ac9f9e3-82ba-ff7e-ac7b-235a02d891ef}
6. result
Who knew there was more than one backdoor deals, and the further down the ranks you went, the faster the drop (so intense). With just 30 seconds left before the competition ended, my rank fell from rk24 to rk25, and I missed the chance to enter the onsite competition (which is fine anyway—I wouldn't know what to do there, just sit and brood).
But man, this ranking curve is just crazy.
I wish someone had been disqualified earlier.
7. will be updated after re2 and misc2
8. (updated on 10/2)
Wow, I actually made it to the onsite competition.
I originally thought it was because some people didn't submit their wp or got caught doing backdoor deals, and were disqualified. It turns out that the scores for ranks 23–26 were all the same, so we all advanced.
The competition took place from October 16 to 17, which conveniently allowed me to skip the big dorm performance for the dorm cultural festival—what a relief!