SubSubSub
โจทย์นี้เป็นข้อ SubSubSub จาก WAN LAI CTF เป็นโจทย์ reverse engineering ที่ให้ไฟล์ Windows executable มา 1 ไฟล์
ตอนรันโปรแกรม มันจะรอให้เรากรอก flag แบบนี้
Enter the flag:
ถ้าใส่ผิด โปรแกรมจะตอบว่า
Wrong!
แต่ถ้าใส่ถูก โปรแกรมจะตอบว่า
Correct! The flag is: <input>
เป้าหมายของโจทย์นี้ไม่ใช่การแก้ binary ให้พิมพ์ Correct! เฉย ๆ แต่ต้องเข้าใจกลไกตรวจ flag แล้วหาข้อมูลที่ถูกต้องจริง ๆ

เริ่มจากดูว่าไฟล์เป็นอะไร
อย่างแรกลองเปิดไฟล์ด้วย Detect It Easy จะเห็นว่าเป็นไฟล์ PE32 สำหรับ Windows แบบ 32-bit console program
จากข้อมูลเบื้องต้น ไฟล์ไม่ได้มี obfuscation ซับซ้อนมากเป็นพิเศษ

ขั้นต่อไปคือเอาไปเปิดใน Ghidra แล้วให้ Ghidra analyze ตามปกติ


หลังจากเปิดใน Ghidra แล้ว ให้ลองค้นหาข้อความที่น่าจะเกี่ยวกับการรับ flag เช่น
Enter the flag:
Wrong!
Correct! The flag is: %s
วิธีนี้ค่อนข้างตรงไปตรงมา เพราะข้อความพวกนี้มักถูกใช้อยู่ใกล้กับฟังก์ชันที่รับค่าและตรวจ flag

เมื่อดู xref ของข้อความเหล่านี้ จะเจอฟังก์ชันที่ Ghidra ตั้งชื่อให้อัตโนมัติว่า
FUN_00403b70
ฟังก์ชันนี้คือส่วนตรวจ flag หลักของโจทย์
ภาพรวมของ FUN_00403b70

undefined4 FUN_00403b70(void)
{
byte *pbVar1;
char *pcVar2;
char *pcVar3;
byte *pbVar4;
char *pcVar5;
byte *pbVar6;
char *pcVar7;
code *_File;
uint *puVar8;
char *pcVar9;
uint *puVar10;
uint *puVar11;
int iVar12;
int iVar13;
uint uVar14;
uint uVar15;
undefined4 *puVar16;
uint *local_114;
uint local_110 [64];
FUN_00401990();
puVar16 = (undefined4 *)&DAT_00407020;
for (iVar13 = 0xb; iVar13 != 0; iVar13 = iVar13 + -1) {
*puVar16 = 0;
puVar16 = puVar16 + 1;
}
*(undefined1 *)puVar16 = 0;
printf("Enter the flag: ");
_File = _iob_exref;
fflush((FILE *)(_iob_exref + 0x20));
local_114 = local_110;
pcVar9 = fgets((char *)local_114,0x100,(FILE *)_File);
puVar8 = local_114;
puVar11 = local_114;
if (pcVar9 != (char *)0x0) {
do {
puVar10 = puVar11;
puVar11 = puVar10 + 1;
uVar14 = *puVar10 + 0xfefefeff & ~*puVar10;
uVar15 = uVar14 & 0x80808080;
} while (uVar15 == 0);
if ((uVar14 & 0x8080) == 0) {
uVar15 = uVar15 >> 0x10;
puVar11 = (uint *)((int)puVar10 + 6);
}
pcVar9 = (char *)((int)puVar11 +
((-3 - (uint)CARRY1((byte)uVar15,(byte)uVar15)) - (int)local_114));
if (pcVar9 != (char *)0x0) {
if (*(char *)((int)local_110 + (int)(pcVar9 + -1)) == '\n') {
*(char *)((int)local_110 + (int)(pcVar9 + -1)) = '\0';
}
iVar13 = -1;
puVar11 = local_114;
do {
if (iVar13 == 0) break;
iVar13 = iVar13 + -1;
uVar14 = *puVar11;
puVar11 = (uint *)((int)puVar11 + 1);
} while ((char)uVar14 != '\0');
if (iVar13 == -0x2a) {
iVar13 = 0;
do {
iVar12 = iVar13 + 1;
(&DAT_00407020)[iVar13] = *(char *)((int)local_114 + iVar13);
iVar13 = iVar12;
} while (iVar12 != 0x28);
iVar13 = 0;
local_114 = (uint *)&DAT_00404020;
do {
pbVar1 = &DAT_00404060 + iVar13;
pcVar9 = &DAT_00407020 + iVar13;
pcVar2 = &DAT_00404061 + iVar13;
pcVar3 = &DAT_00404062 + iVar13;
pbVar4 = &DAT_00404064 + iVar13;
pcVar5 = &DAT_00404065 + iVar13;
pbVar6 = &DAT_00404068 + iVar13;
pcVar7 = &DAT_00404029 + iVar13;
iVar13 = iVar13 + 9;
do {
if ((((byte)((*pbVar1 | 1) * *pcVar9) != *(char *)local_114) ||
((byte)(*pcVar2 * *pcVar9 + (*pbVar4 | 1) * pcVar9[1]) !=
*(char *)((int)local_114 + 1))) ||
((byte)(*pcVar3 * *pcVar9 + *pcVar5 * pcVar9[1] + (*pbVar6 | 1) * pcVar9[2]) !=
*(char *)((int)local_114 + 2))) {
local_114 = (uint *)pcVar7;
puts("Wrong!");
return 0;
}
pcVar9 = pcVar9 + 3;
local_114 = (uint *)((int)local_114 + 3);
} while ((uint *)pcVar7 != local_114);
local_114 = (uint *)pcVar7;
if (iVar13 == 0x2d) {
printf("Correct! The flag is: %s\n",puVar8);
return 0;
}
} while( true );
}
}
puts("Wrong!");
}
return 1;
}
โค้ดที่ Ghidra decompile ออกมาอ่านยากพอสมควร เพราะเต็มไปด้วยชื่อตัวแปรอัตโนมัติจาก Ghidra เช่น pcVar9, pbVar1, local_114 และมีการคำนวณ pointer อยู่หลายจุด
แต่ถ้าแยกลำดับการทำงานของฟังก์ชัน จะได้ประมาณนี้
เรียก
FUN_00401990()ล้าง buffer ที่
DAT_00407020รับค่าจากผู้ใช้ด้วย
fgetsตัด newline
\nทิ้งถ้ามีเช็กว่าค่าที่กรอกต้องยาว 40 ตัวอักษร
คัดลอกค่าที่กรอก 40 byte ไปไว้ที่
DAT_00407020ตรวจข้อมูลด้วยสมการระดับ byte หรือ
mod 256ถ้าทุกเงื่อนไขผ่าน จึงพิมพ์
Correct!
พอเห็นลำดับการทำงานแบบนี้ โค้ดจะอ่านง่ายขึ้นมาก เพราะเรารู้แล้วว่าโจทย์นี้ไม่ได้ hash ค่าที่กรอกทั้งก้อน แต่ค่อย ๆ ตรวจข้อมูลเป็นชุดเล็ก ๆ
ก่อนจะเขียนสคริปต์แก้โจทย์ ให้แยกข้อมูลในฟังก์ชันตรวจ flag ออกเป็น 3 ส่วนก่อน คือค่าที่เรากรอก, ค่าที่โปรแกรมใช้เทียบผลลัพธ์, และค่าคงที่ที่ใช้คำนวณ
Buffer ที่ใช้ตรวจมี 45 byte
ช่วงต้นของฟังก์ชันมีโค้ดล้าง buffer ที่ DAT_00407020
puVar16 = (undefined4 *)&DAT_00407020;
for (iVar13 = 0xb; iVar13 != 0; iVar13 = iVar13 + -1) {
*puVar16 = 0;
puVar16 = puVar16 + 1;
}
*(undefined1 *)puVar16 = 0;
ตรงนี้คือการเติม 0 ลงใน buffer
จำนวนที่เคลียร์คือ
0xb รอบ * 4 byte = 44 byte
ตามด้วยอีก 1 byte
รวม = 45 byte
ดังนั้น DAT_00407020 คือ buffer สำหรับพักข้อมูล ขนาด 45 byte
ความยาว flag ต้องเป็น 40 ตัว
หลังจากรับค่าจากผู้ใช้ด้วย fgets แล้ว โปรแกรมจะตัด newline ออก จากนั้นเช็กความยาวของค่าที่กรอก
ในโค้ดที่ decompile ออกมา จะเห็นเงื่อนไขนี้
if (iVar13 == -0x2a) {
บรรทัดนี้อ่านยาก เพราะ Ghidra แปลงขั้นตอนการหา string length ออกมาเป็นลูปหน้าตาแปลก ๆ
แต่ถ้าไล่ค่าจริง ๆ จะได้ว่าเงื่อนไขนี้เทียบเท่ากับ
strlen(input) == 40
จากนั้นโปรแกรมคัดลอกค่าที่กรอก 40 byte เข้าไปใน DAT_00407020
iVar13 = 0;
do {
iVar12 = iVar13 + 1;
(&DAT_00407020)[iVar13] = *(char *)((int)local_114 + iVar13);
iVar13 = iVar12;
} while (iVar12 != 0x28);
ค่า 0x28 คือ 40
ดังนั้นก่อนเริ่มตรวจ สถานะของ buffer จะเป็นแบบนี้
byte 0..39 = ค่าที่เรากรอก
byte 40..44 = 0x00
นี่คือเหตุผลที่ flag จริงยาว 40 ตัวอักษร แต่ฟังก์ชันตรวจ flag ทำงานกับ buffer รวม 45 byte
จากโค้ด decompile ไปสู่ข้อมูลที่ต้องดึงออกมา
หลังจากรู้แล้วว่าโปรแกรมคัดลอกค่าที่กรอกไปไว้ที่ DAT_00407020 ขั้นต่อไปคือดูว่า ลูปตรวจ flag เอาค่านี้ไปเทียบกับอะไร
ในโค้ดที่ decompile ออกมา ช่วงตรวจ flag จะเห็น address สำคัญ 3 กลุ่ม
DAT_00407020 ใช้เก็บค่าที่เรากรอก
DAT_00404020 ถูกใช้เป็นค่าที่เอาไว้เทียบกับผลลัพธ์
DAT_00404060 ถูกใช้เป็นค่าคูณตอนคำนวณ
ตรงนี้เป็นจุดเริ่มของการตั้งชื่อในสคริปต์แก้โจทย์
DAT_00404020 -> exp
DAT_00404060 -> coeff
ตรงนี้ไม่ได้ตั้งชื่อตามความรู้สึก แต่ดูจากเส้นทางข้อมูลว่าแต่ละ address ถูกใช้ทำอะไรในเงื่อนไขตรวจ flag
ไล่ที่มาของแต่ละ address
DAT_00407020 คือ buffer เก็บค่าที่กรอก
ก่อนเข้าลูปตรวจ flag โปรแกรมคัดลอกค่าที่กรอก เข้า DAT_00407020
(&DAT_00407020)[iVar13] = *(char *)((int)local_114 + iVar13);
ดังนั้น DAT_00407020 คือ buffer ที่เก็บค่าหลังจากรับมาจากผู้ใช้
ต่อมาในลูปตรวจ flag มีบรรทัดนี้
pcVar9 = &DAT_00407020 + iVar13;
แปลว่า pcVar9 คือ pointer ที่ชี้ไปยังค่าที่ถูกคัดลอกไว้แล้ว
ถ้าตั้งชื่อให้อ่านง่ายขึ้น จะได้ว่า
x = pcVar9[0]
y = pcVar9[1]
z = pcVar9[2]
DAT_00404020 คือ ค่าผลลัพธ์ที่โปรแกรมใช้เทียบ
ก่อนเข้าลูปตรวจ โปรแกรมตั้งค่า local_114 ให้ชี้ไปที่ DAT_00404020
local_114 = (uint *)&DAT_00404020;
จากนั้นในเงื่อนไขตรวจ จะเห็นว่าค่าที่คำนวณจากข้อมูลที่กรอก ถูกนำไปเทียบกับค่าที่ local_114 ชี้อยู่
(byte)((*pbVar1 | 1) * *pcVar9) != *(char *)local_114
ฝั่งซ้ายคือค่าที่คำนวณจากข้อมูลที่กรอก
(byte)((*pbVar1 | 1) * *pcVar9)
ฝั่งขวาคือค่าคงที่ที่โปรแกรมคาดหวัง
*(char *)local_114
และเพราะ local_114 เริ่มจาก DAT_00404020 เราจึงสรุปได้ว่า
DAT_00404020 = ชุด byte สำหรับเทียบผลลัพธ์
ในสคริปต์แก้โจทย์จึงตั้งชื่อว่า
exp = [...]
exp ย่อมาจาก expected หรือค่าที่โปรแกรมคาดว่าจะได้
DAT_00404060 คือ ค่าสัมประสิทธิ์
ในลูปเดียวกัน โปรแกรมอ่านค่าจาก DAT_00404060 หลายตำแหน่ง
pbVar1 = &DAT_00404060 + iVar13;
pcVar2 = &DAT_00404061 + iVar13;
pcVar3 = &DAT_00404062 + iVar13;
pbVar4 = &DAT_00404064 + iVar13;
pcVar5 = &DAT_00404065 + iVar13;
pbVar6 = &DAT_00404068 + iVar13;
ถ้าเขียนใหม่ให้เห็น offset ชัด ๆ จะได้ว่าฟังก์ชันตรวจ flag ใช้ค่าจาก
DAT_00404060[i + 0]
DAT_00404060[i + 1]
DAT_00404060[i + 2]
DAT_00404060[i + 4]
DAT_00404060[i + 5]
DAT_00404060[i + 8]
ค่าเหล่านี้ถูกนำไปคูณกับ byte ของค่าที่กรอกในสมการ
ดังนั้น DAT_00404060 คือชุดค่าสัมประสิทธิ์ หรือค่าคงที่สำหรับคำนวณ
ในสคริปต์แก้โจทย์จึงตั้งชื่อว่า
coeff = [...]
ถึงตรงนี้เราจะรู้แล้วว่า array ในสคริปต์แก้โจทย์ต้องดึงมาจากสองตำแหน่งนี้
exp = byte ที่โปรแกรมเอาไว้เทียบกับผลลัพธ์
coeff = byte ที่โปรแกรมใช้เป็นตัวคูณค่าที่กรอก
สรุปคือ exp และ coeff ไม่ใช่ค่าที่สุ่มใส่ขึ้นมา แต่เป็น byte array ที่ดึงมาจาก .data ของ binary โดยอิงจากเส้นทางข้อมูลในฟังก์ชันตรวจ flag
ดึงค่า exp และ coeff จาก .data
เมื่อรู้แล้วว่า address แต่ละจุดมีหน้าที่อะไร ก็ดึง byte จาก binary ออกมาใช้ได้
exp มาจาก DAT_00404020 หรือ VA 0x00404020
coeff มาจาก DAT_00404060 หรือ VA 0x00404060
ค่า exp ที่ address 0x00404020 คือ
b5 c4 fb a4 0b 96 61 0a 41
02 f6 62 db 7e 6e d9 12 22
67 d6 b7 32 d6 05 e8 9d 94
ae b2 8f 6c 44 de c3 82 e9
9f 05 25 13 f8 4c 00 00 00
แปลงเป็น decimal ได้
exp = [
181, 196, 251, 164, 11, 150, 97, 10, 65,
2, 246, 98, 219, 126, 110, 217, 18, 34,
103, 214, 183, 50, 214, 5, 232, 157, 148,
174, 178, 143, 108, 68, 222, 195, 130, 233,
159, 5, 37, 19, 248, 76, 0, 0, 0
]
ค่า coeff ที่ address 0x00404060 คือ
d3 cb c8 ce 07 45 8c 97 29
29 1e a1 2f 9d c4 87 7d 3b
db 89 34 c0 c5 81 b0 62 c5
07 32 87 e2 df cd 6e d9 fd
cf 58 3c 0e 4d ce 8e a8 f9
แปลงเป็น decimal ได้
coeff = [
211, 203, 200, 206, 7, 69, 140, 151, 41,
41, 30, 161, 47, 157, 196, 135, 125, 59,
219, 137, 52, 192, 197, 129, 176, 98, 197,
7, 50, 135, 226, 223, 205, 110, 217, 253,
207, 88, 60, 14, 77, 206, 142, 168, 249
]
แกนของฟังก์ชันตรวจ flag: ตรวจทีละ 3 byte
โค้ดส่วนที่สำคัญที่สุดคือเงื่อนไขนี้
if ((((byte)((*pbVar1 | 1) * *pcVar9) != *(char *)local_114) ||
((byte)(*pcVar2 * *pcVar9 + (*pbVar4 | 1) * pcVar9[1]) !=
*(char *)((int)local_114 + 1))) ||
((byte)(*pcVar3 * *pcVar9 + *pcVar5 * pcVar9[1] + (*pbVar6 | 1) * pcVar9[2]) !=
*(char *)((int)local_114 + 2))) {
puts("Wrong!");
return 0;
}
ถ้าเปลี่ยนชื่อตัวแปรให้อ่านง่ายขึ้น
x = pcVar9[0]
y = pcVar9[1]
z = pcVar9[2]
และ
a = *pbVar1 | 1
b = *pcVar2
c = *pcVar3
d = *pbVar4 | 1
e = *pcVar5
f = *pbVar6 | 1
จะได้สมการ
out0 = (a*x) mod 256
out1 = (b*x + d*y) mod 256
out2 = (c*x + e*y + f*z) mod 256
ที่ต้องคิดแบบ mod 256 เพราะในโค้ดมีการ cast ผลลัพธ์เป็น byte
(byte)(...)
แปลว่าผลลัพธ์ถูกตัดเหลือ 8 bit เสมอ
โครงสร้าง block
ตัวแปร iVar13 เพิ่มทีละ 9
iVar13 = iVar13 + 9;
ดังนั้น ฟังก์ชันตรวจ flag แบ่งข้อมูลเป็น block ละ 9 byte
block 0: byte 0..8
block 1: byte 9..17
block 2: byte 18..26
block 3: byte 27..35
block 4: byte 36..44
รวมทั้งหมด 5 block หรือ 45 byte
แต่ภายในแต่ละ block โปรแกรมตรวจทีละ 3 byte
pcVar9 = pcVar9 + 3;
local_114 = (uint *)((int)local_114 + 3);
ดังนั้นใน 1 block จะตรวจ 3 รอบ รอบละ 3 byte
มองเป็นเมทริกซ์
สมการของค่าที่กรอกทีละ 3 byte
x, y, z
สามารถมองเป็นเมทริกซ์ ได้แบบนี้
[ out0 ] [ a 0 0 ] [ x ]
[ out1 ] = [ b d 0 ] [ y ] mod 256
[ out2 ] [ c e f ] [ z ]
เมทริกซ์นี้เป็น lower-triangular matrix
แปลว่าแต่ละแถวพึ่งพาข้อมูลแบบนี้
out0 ใช้แค่ x
out1 ใช้ x และ y
out2 ใช้ x, y และ z
ดังนั้นเราสามารถแก้ย้อนกลับได้ทีละตัว
x -> y -> z
ทำไมถึงย้อนกลับได้
ในโค้ดจะเห็นว่าค่าสัมประสิทธิ์บนแนวทแยงถูกบังคับให้เป็นเลขคี่ด้วย | 1
*pbVar1 | 1
*pbVar4 | 1
*pbVar6 | 1
ก็คือค่า
a, d, f
เมื่อคิดแบบ modulo 256 เลขคี่ทุกตัวจะมี modular inverse เพราะ gcd(odd, 256) = 1
ดังนั้นจึงแก้สมการย้อนกลับได้แบบนี้
x = out0 * inv(a) mod 256
y = (out1 - b*x) * inv(d) mod 256
z = (out2 - c*x - e*y) * inv(f) mod 256
นี่คือหัวใจของโจทย์นี้
ตัวอย่าง 3 byte แรก: ทำไมถึงได้ WAN
ลองเริ่มจากข้อมูลชุดแรกใน binary
ค่าสัมประสิทธิ์ 9 byte แรกจาก 0x00404060 คือ
d3 cb c8 ce 07 45 8c 97 29
ค่าที่ฟังก์ชันตรวจ flag ใช้จริงคือ
a = 0xd3 | 1 = 211
b = 0xcb = 203
c = 0xc8 = 200
d = 0x07 | 1 = 7
e = 0x45 = 69
f = 0x29 | 1 = 41
ส่วนค่าเทียบผลลัพธ์ 3 byte แรกจาก 0x00404020 คือ
b5 c4 fb
หรือ
out0 = 181
out1 = 196
out2 = 251
หา modular inverse ได้ว่า
inv(211) mod 256 = 91
inv(7) mod 256 = 183
inv(41) mod 256 = 25
แก้ตัวแรก
x = 181 * 91 mod 256
x = 87
ASCII 87 คือ
W
แก้ตัวที่สอง
y = (196 - 203*87) * 183 mod 256
y = 65
ASCII 65 คือ
A
แก้ตัวที่สาม
z = (251 - 200*87 - 69*65) * 25 mod 256
z = 78
ASCII 78 คือ
N
ดังนั้น 3 byte แรกที่ถอดกลับมาได้คือ
WAN
ผลลัพธ์ตรงนี้ช่วยยืนยันว่าแนวทางถูกต้อง เพราะ flag ของโจทย์นี้ขึ้นต้นด้วย WANLAI{...} อยู่แล้ว
WAN จึงยืนยันได้จากการแก้สมการย้อนกลับด้วย byte จริงที่อยู่ใน binary
สคริปต์แก้โจทย์
เมื่อเข้าใจสูตรแล้ว สคริปต์แก้โจทย์จะเขียนได้ตรง ๆ
exp = [
181, 196, 251, 164, 11, 150, 97, 10, 65,
2, 246, 98, 219, 126, 110, 217, 18, 34,
103, 214, 183, 50, 214, 5, 232, 157, 148,
174, 178, 143, 108, 68, 222, 195, 130, 233,
159, 5, 37, 19, 248, 76, 0, 0, 0
]
coeff = [
211, 203, 200, 206, 7, 69, 140, 151, 41,
41, 30, 161, 47, 157, 196, 135, 125, 59,
219, 137, 52, 192, 197, 129, 176, 98, 197,
7, 50, 135, 226, 223, 205, 110, 217, 253,
207, 88, 60, 14, 77, 206, 142, 168, 249
]
MOD = 256
out = []
for block in range(0, 45, 9):
a = coeff[block + 0] | 1
b = coeff[block + 1]
c = coeff[block + 2]
d = coeff[block + 4] | 1
e = coeff[block + 5]
f = coeff[block + 8] | 1
for j in range(0, 9, 3):
o0 = exp[block + j + 0]
o1 = exp[block + j + 1]
o2 = exp[block + j + 2]
x = (o0 * pow(a, -1, MOD)) % MOD
y = ((o1 - b * x) * pow(d, -1, MOD)) % MOD
z = ((o2 - c * x - e * y) * pow(f, -1, MOD)) % MOD
out.extend([x, y, z])
flag = bytes(out[:40]).decode()
print(flag)
ผลลัพธ์คือ
WANLAI{7f2b8c4a1d3e5f6098a7b2c4d6e8f1a3}
ที่ต้องใช้ out[:40] เพราะฟังก์ชันตรวจ flag ทำงานกับ buffer 45 byte ก็จริง แต่ค่าที่เรากรอกถูกบังคับให้ยาว 40 ตัวอักษร ส่วน 5 byte ท้ายเป็น 0x00 จาก buffer ที่ถูกเคลียร์ไว้ตั้งแต่แรก
ยืนยันผล
Correct! The flag is: WANLAI{7f2b8c4a1d3e5f6098a7b2c4d6e8f1a3}