# DiceCTF 2025 Quals
> Cảm ơn tất cả mọi người trong team vì đã tryhard tới phút cuối cùng. Shout out cho bạn web team mình vì bạn quỷ vl (đấm hẳn 4 challs web, how?).
## Rev/debugalyzer
Đề bài cho 2 files `dwarf` và `main`.
``` linux
~/currentCTF
❯ file dwarf
dwarf: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=ea8b6ed84558414de1165e3b6516d706cba825a0, for GNU/Linux 4.4.0, not stripped
~/currentCTF
❯ file main
main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=f89920a47f694838ae74c88db45a421949478a92, for GNU/Linux 4.4.0, with debug_info, not stripped
~/currentCTF
❯ ./main
debug me!
```
Bật IDA mở file `main` ra đọc thì thấy nó khá vô nghĩa, nên mình chuyển sang file `dwarf`.
Chạy thử:
``` linux
~/currentCTF
❯ ./dwarf
Usage: ./dwarf <elf-file>
~/currentCTF
❯ ./dwarf main
Processing...
Processing .debug_line unit: total_size=1690, header_size=64, instructions_length=1626
Flag is incorrect!
```
Mở IDA ra rev thì trong đó có một hàm khiến mình chú ý là `execute_dwarf_bytecode_v4`.
```c
int __fastcall execute_dwarf_bytecode_v4(__int64 a1, __int64 a2, __int64 a3, __int64 a4, unsigned __int8 a5)
{
__int64 v5; // rax
__int64 v7; // r13
unsigned __int8 v8; // al
__int64 v9; // r12
__int64 v10; // rbp
__int64 v11; // rdx
unsigned __int8 v12; // bl
char *v13; // rsi
unsigned __int64 v14; // rcx
int v15; // eax
const char *v16; // rax
__int64 v18; // rax
int v19; // eax
char v20; // si
char v21; // bp
int v22; // eax
__int64 v23; // rdx
char v24; // si
__int64 v25; // rcx
unsigned __int8 v26; // di
unsigned __int8 v27; // si
int v28; // eax
__int64 v29; // rdx
unsigned __int8 v30; // si
char v31; // al
unsigned __int64 v32; // [rsp+0h] [rbp-58h]
unsigned int check; // [rsp+8h] [rbp-50h]
__int64 v35; // [rsp+10h] [rbp-48h] BYREF
__int64 v36[8]; // [rsp+18h] [rbp-40h] BYREF
v36[0] = a1;
v35 = a2;
if ( !a2 )
{
check = 1;
goto LABEL_15;
}
v5 = a2;
check = 1;
while ( 1 )
{
v11 = v36[0];
v12 = *(_BYTE *)v36[0];
v13 = (char *)++v36[0];
v14 = v5 - 1;
v35 = v5 - 1;
if ( v12 )
{
if ( v12 < *(_BYTE *)(a3 + 3) )
{
switch ( v12 )
{
case 1u:
case 6u:
case 7u:
case 8u:
case 0xAu:
case 0xBu:
goto LABEL_9;
case 2u:
case 4u:
case 5u:
case 0xCu:
read_uleb128(v36, &v35);
break;
case 3u:
do
{
v31 = *v13++;
--v14;
}
while ( v31 < 0 && v14 );
v36[0] = (__int64)v13;
v35 = v14;
break;
case 9u:
if ( v14 > 1 )
{
v36[0] = v11 + 3;
v35 = v5 - 3;
}
break;
default:
printf("Opcode %d unimplemented\n", v12);
break;
}
}
goto LABEL_9;
}
v32 = read_uleb128(v36, &v35);
v7 = v35;
if ( !v35 )
goto LABEL_15;
v8 = *(_BYTE *)v36[0];
v9 = ++v36[0];
v10 = --v35;
if ( v8 == 81 )
{
v19 = read_uleb128(v36, &v35);
if ( !v35 )
goto LABEL_15;
v20 = *(_BYTE *)v36[0]++;
--v35;
flag[v19] = v20;
goto LABEL_9;
}
if ( v8 <= 0x51u )
break;
if ( v8 != 82 )
goto LABEL_34;
v15 = read_uleb128(v36, &v35);
if ( !v35 )
goto LABEL_15;
v21 = flag[v15];
v22 = read_uleb128(v36, &v35);
v23 = v35;
if ( !v35 )
goto LABEL_15;
v24 = flag[v22];
v25 = v36[0];
v26 = *(_BYTE *)v36[0];
--v35;
if ( v23 == 1 )
goto LABEL_15;
if ( v26 == 2 )
{
v12 = v24 * v21;
}
else if ( v26 > 2u )
{
v30 = v21 ^ v24;
if ( v26 == 3 )
v12 = v30;
}
else
{
v12 = v21 - v24;
v27 = v21 + v24;
if ( !v26 )
v12 = v27;
}
v36[0] += 2LL;
v28 = v36[0];
v29 = v23 - 2;
v35 = v29;
LOBYTE(v28) = v29 != 0;
LOBYTE(v29) = v12 != *(_BYTE *)(v25 + 1);
check &= v29 & v28 ^ 1;
LABEL_9:
v5 = v35;
if ( !v35 )
goto LABEL_15;
}
if ( v8 == 1 )
goto LABEL_9;
if ( v8 == 2 )
{
if ( v32 >= (unsigned __int64)a5 + 1 )
{
if ( a5 )
{
v18 = 0LL;
do
++v18;
while ( a5 != v18 );
}
else
{
v18 = 0LL;
}
v36[0] = v18 + v9;
v35 = v10 - v18;
}
goto LABEL_9;
}
LABEL_34:
printf("Extended opcode %d unimplemented\n", 0LL);
if ( v32 <= 1 )
goto LABEL_9;
while ( v10 )
{
if ( v10 - 1 == v7 - v32 )
{
v35 = v10 - 1;
v36[0] = v7 + v9 - v10;
goto LABEL_9;
}
--v10;
}
LABEL_15:
v16 = (const char *)select_str(incorrect_msg, correct_msg, check);
return puts(v16);
}
```
Tới khúc này thì thấy nó là 1 cái VM. Tới đây thì mình có hướng như này:
Đặt breakpoint để lấy giá trị của `v15`, `v22`, `v12` và `*(v25+1)`, từ đó mình sẽ biết nó lấy giá trị của flag ở đâu, và nó thực hiện phép tính gì với flag.
``` gdb
*R8 0x13
*R9 0x13
R10 0
R11 0x202
R12 0x55555555bb72 ◂— 0x520500f7011300
R13 0x579
R14 0x7fffffffd540 ◂— 0x10d0efb01
R15 0x555555556164 ◂— 0xfffff277fffff53c
*RBP 0x64
RSP 0x7fffffffd4a0 ◂— 5
*RIP 0x555555555518 (execute_dwarf_bytecode_v4+480) ◂— mov rdx, qword ptr [rsp + 0x10]
─────────────────────────────────────[ DISASM / x86-64 / set emulate on ]─────────────────────────────────────
0x5555555554fe <execute_dwarf_bytecode_v4+454> lea rdx, [rip + 0x2c3b] RDX => 0x555555558140 (flag) ◂— 'dice{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
0x555555555505 <execute_dwarf_bytecode_v4+461> movzx ebp, byte ptr [rdx + rax] EBP, [flag] => 0x64
0x555555555509 <execute_dwarf_bytecode_v4+465> lea rsi, [rsp + 0x10] RSI => 0x7fffffffd4b0 ◂— 0x577
0x55555555550e <execute_dwarf_bytecode_v4+470> lea rdi, [rsp + 0x18] RDI => 0x7fffffffd4b8 —▸ 0x55555555bb73 ◂— 0x1700520500f70113
0x555555555513 <execute_dwarf_bytecode_v4+475> call read_uleb128 <read_uleb128>
► 0x555555555518 <execute_dwarf_bytecode_v4+480> mov rdx, qword ptr [rsp + 0x10] RDX, [0x7fffffffd4b0] => 0x576
0x55555555551d <execute_dwarf_bytecode_v4+485> test rdx, rdx 0x576 & 0x576 EFLAGS => 0x202 [ cf pf af zf sf IF df of ]
0x555555555520 <execute_dwarf_bytecode_v4+488> je execute_dwarf_bytecode_v4+269 <execute_dwarf_bytecode_v4+269>
0x555555555526 <execute_dwarf_bytecode_v4+494> cdqe
0x555555555528 <execute_dwarf_bytecode_v4+496> lea rcx, [rip + 0x2c11] RCX => 0x555555558140 (flag) ◂— 'dice{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
0x55555555552f <execute_dwarf_bytecode_v4+503> movzx esi, byte ptr [rcx + rax] ESI, [flag+19] => 0x58
──────────────────────────────────────────────────[ STACK ]───────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd4a0 ◂— 5
01:0008│ 0x7fffffffd4a8 ◂— 0x8007fff00000001
02:0010│ rsi 0x7fffffffd4b0 ◂— 0x576
03:0018│ rdi 0x7fffffffd4b8 —▸ 0x55555555bb74 ◂— 0x11700520500f701
04:0020│ 0x7fffffffd4c0 ◂— 3
05:0028│ 0x7fffffffd4c8 ◂— 0x65a
06:0030│ 0x7fffffffd4d0 ◂— 0x40 /* '@' */
07:0038│ 0x7fffffffd4d8 —▸ 0x55555555ba50 ◂— 0x36000400000696
────────────────────────────────────────────────[ BACKTRACE ]─────────────────────────────────────────────────
► 0 0x555555555518 execute_dwarf_bytecode_v4+480
1 0x555555555a2f main+873
2 0x7ffff7da31ca __libc_start_call_main+122
3 0x7ffff7da328b __libc_start_main+139
4 0x5555555551a5 _start+37
──────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg>
```
Debug thử thì thấy flag nó mặc định luôn là:
``` gdb
pwndbg> x/s 0x555555558140
0x555555558140 <flag>: "dice{", 'X' <repeats 34 times>, "}"
```
Mình có thử mò ngồi thay đổi giá trị này, nhưng kết quả thì không khả quan lắm.
Quay lại vấn đề đặt breakpoint, thì mình viết script gdb thôi.
``` gdb
start main
breakrva 0x1A2A
breakrva 0x1439
breakrva 0x1518
breakrva 0x1576
while (1)
c
p/x $rax
c
p/x $rax
c
x/b $rcx + 1
p/x $bl
end
```
Ném log vào file output, xong rồi rev lại các phép tính.
``` python
#!/usr/bin/python3
from pwn import *
from z3 import *
data = open("output.txt", "r").read().split('\n')
start = 34
solver = Solver()
flag = b'dice{' + b'X' * 34 + b'}'
ans = list(b'dice{') + [0] * 34 + list(b'}')
for i in range(200):
a = data[start]
b = data[start + 3]
c = data[start + 6]
d = data[start + 7]
a = a[a.find('=') + 1:].strip()
b = b[b.find('=') + 1:].strip()
c = c[c.find(':') + 1:].strip()
d = d[d.find('=') + 1:].strip()
a = int(a, 16)
b = int(b, 16)
c = int(c, 16)
d = int(d, 16)
if (flag[a] + flag[b]) & 0xff == d:
if ans[b] == 0:
ans[b] = (c - ans[a]) & 0xff
elif ans[a] == 0:
ans[a] = (c - ans[b]) & 0xff
if (flag[a] ^ flag[b]) & 0xff == d and (a != 9 and b != 9) and (a != 18 and b != 18) and (a != 26 and b != 26) and (a != 29 and b != 29):
if ans[b] == 0:
ans[b] = (ans[a] ^ c) & 0xff
elif ans[a] == 0:
ans[a] = (c ^ ans[b]) & 0xff
if (flag[a] - flag[b]) & 0xff == d:
if ans[b] == 0:
ans[b] = (ans[a] - c) & 0xff
elif ans[a] == 0:
ans[a] = (c + ans[b]) & 0xff
if (flag[a] * flag[b]) & 0xff == d:
if ans[b] == 0:
for t in range(33, 127):
if (t * ans[a]) & 0xff == c:
ans[b] = t
break
elif ans[a] == 0:
for t in range(33, 127):
if (t * ans[b]) & 0xff == c:
ans[a] = t
break
start += 10
print(bytes(ans))
# dice{h1ghly_sp3c_c0mpl14nt_dw4rf_p4rs3r}
```
**Còn một vấn đề nữa mà script của mình gặp**: Vì mình không thể thay đổi xâu `flag` trên kia, nên `X - X = X ^ X` thì lúc đó rev nó sẽ bị sai. Đoạn này mình thực sự phải chỉnh script cho tới khi nào ra `flag`.
## Rev/ono
```linux
~/currentCTF 8m
❯ ./ono
oño? supershy
oño.
```
Hmm có vẻ đây là một bài flag checker, lets go mở IDA lên thôi nào.
Hàm `main`:
``` c++
__int64 __fastcall main(int a1, char **a2, char **a3)
{
size_t v3; // rax
__int64 v4; // rbx
__int64 v5; // rbp
char *v6; // rdi
__int64 v7; // rcx
int v8; // ebp
__int64 i; // rax
int v10; // edx
char *v12[2]; // [rsp+0h] [rbp-F8h] BYREF
char v13; // [rsp+17h] [rbp-E1h] BYREF
char v14; // [rsp+2Ch] [rbp-CCh] BYREF
char v15; // [rsp+41h] [rbp-B7h] BYREF
char v16[26]; // [rsp+56h] [rbp-A2h] BYREF
char *argv[4]; // [rsp+70h] [rbp-88h] BYREF
char s[8]; // [rsp+90h] [rbp-68h] BYREF
__int64 v19[12]; // [rsp+98h] [rbp-60h]
printf(format, a2, a3);
fflush(stdout);
fgets(s, 64, stdin);
v3 = strcspn(s, "\n");
s[v3] = 0;
if ( v3 == 32 )
{
v4 = *(_QWORD *)s;
argv[3] = 0LL;
argv[0] = &v13;
v5 = 0LL;
argv[1] = &v14;
argv[2] = &v15;
v12[0] = v16;
v12[1] = 0LL;
do
{
v6 = argv[v5];
v7 = v19[v5++];
snprintf(v6, 0x15uLL, "%llu", v7);
}
while ( v5 != 3 );
v8 = memfd_create(&unk_200F, 0LL);
for ( i = 0LL; i != 5429; ++i )
{
while ( 1 )
{
qword_4080[i] = v4 ^ (0x4C01DB400B0C9LL * qword_4080[i]);
v10 = 32;
do
{
v4 = __ROL8__((37 * v4) ^ (42424242 * v4), 7);
--v10;
}
while ( v10 );
if ( i )
break;
snprintf(v16, 0x1AuLL, aO, v4);
i = 1LL;
}
}
write(v8, qword_4080, 0xA9A8uLL);
fexecve(v8, argv, v12);
}
puts(::s);
return 1LL;
}
```
Vậy là flow nó như này:
- Check input có thỏa 32 kí tự không
- Xong r nó gán `v4 = 8 bytes đầu của flag` xong thực hiện 1 đống phép tính gì đó.
- Đồng thời nó cũng gọi `snprintf(v16, 0x1AuLL, "oño=%llu", v4);`. Đoạn này nó sẽ dùng để gán vào `envp (v12[0] = v16, v12[1] = 0)`.
- Xong rồi nó write data từ một cái mảng mà ta thực hiện các phép tính abcxyz gì đó vào `v8`, `write(v8, qword_4080, 0xA9A8uLL);`
- Cuối cùng thì nó gọi `fexecve(v8, argv, v12);`.
Ở đây thì mình đoán **8 bytes đầu** của **qword_4080** sau khi tính toán sẽ là header của một file ELF. Giờ viết script để tìm v4 thôi lets go.
``` python
#!/usr/bin/python3
from z3 import *
from pwn import *
a = 0x7F861CD6D160EBC3
header = u64(bytes.fromhex('7f45 4c46 0201 0100'))
v4 = BitVec('v4', 64)
solver = Solver()
solver.add(v4 ^ (0x4C01DB400B0C9 * a) == header)
if solver.check() == sat:
m = solver.model()
ans = m[v4].as_long()
print(hex(ans))
print(p64(ans))
```
``` linux
~/currentCTF 44s
❯ ./solve.py
0x77306e7b65636964
b'dice{n0w'
```
Vậy đây là 8 bytes đầu của flag, giờ mình dump memory ra một file bin xem nó sẽ `fexecve` cái gì.
Để dump memory ra thì ta xài lệnh này trong gdb:
``` linux
dump binary memory dump.bin 0x555555558080 0x555555558080+0xa9a8
```
``` gdb
pwndbg> breakrva 0x1223
Breakpoint 2 at 0x555555555223
pwndbg> c
Continuing.
oño? dice{n0waaaaaaaaaaaaaaaaaaaaaaaa
Breakpoint 2, 0x0000555555555223 in ?? ()
LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
─────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────
*RAX 0x1535
*RBX 0x3a789197de462f9f
*RCX 0x84721106af655b7d
*RDX 0xa9a8
*RDI 3
*RSI 0x555555558080 ◂— 0x10102464c457f
*R8 0x75
*R9 0
*R10 0
*R11 0
*R12 0x7fffffffd576 ◂— 0x3439383d6fb1c36f
*R13 0x7fffffffd590 —▸ 0x7fffffffd537 ◂— '7016996765293437281'
*R14 0x555555558080 ◂— 0x10102464c457f
*R15 0x7ffff7ffd000 (_rtld_global) —▸ 0x7ffff7ffe2e0 —▸ 0x555555554000 ◂— 0x10102464c457f
*RBP 3
*RSP 0x7fffffffd520 —▸ 0x7fffffffd576 ◂— 0x3439383d6fb1c36f
*RIP 0x555555555223 ◂— call 0x555555555050
──────────────────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]──────────────────────────────────────────────────────
► 0x555555555223 call write@plt <write@plt>
fd: 3 (/memfd:oño (deleted))
buf: 0x555555558080 ◂— 0x10102464c457f
n: 0xa9a8
0x555555555228 mov rdx, rsp
0x55555555522b mov rsi, r13
0x55555555522e mov edi, ebp
0x555555555230 call fexecve@plt <fexecve@plt>
0x555555555235 lea rdi, [rip + 0xdcd] RDI => 0x555555556009 ◂— 0xc36f002e6fb1c36f
0x55555555523c call puts@plt <puts@plt>
0x555555555241 push 1
0x555555555243 pop rax
0x555555555244 add rsp, 0xd0
0x55555555524b pop rbx
───────────────────────────────────────────────────────────────────[ STACK ]────────────────────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd520 —▸ 0x7fffffffd576 ◂— 0x3439383d6fb1c36f
01:0008│ 0x7fffffffd528 ◂— 0
02:0010│ 0x7fffffffd530 ◂— 0x3700000000000002
03:0018│ 0x7fffffffd538 ◂— '016996765293437281'
04:0020│ 0x7fffffffd540 ◂— '5293437281'
05:0028│ 0x7fffffffd548 ◂— 0x3631303700003138 /* '81' */
06:0030│ 0x7fffffffd550 ◂— '996765293437281'
07:0038│ 0x7fffffffd558 ◂— 0x31383237333433 /* '3437281' */
─────────────────────────────────────────────────────────────────[ BACKTRACE ]──────────────────────────────────────────────────────────────────
► 0 0x555555555223
1 0x7ffff7dc21ca __libc_start_call_main+122
2 0x7ffff7dc228b __libc_start_main+139
3 0x555555555281
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> x/s 0x555555558080
0x555555558080: "\177ELF\002\001\001"
pwndbg> dump binary memory ono_dump_1.bin 0x555555558080 0x555555558080+0xa9a8
```
``` linux
~/currentCTF 2m 35s
❯ file ono_dump_1.bin
ono_dump_1.bin: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, stripped
```
Mở `ono_dump_1.bin` ra xem thử:
Mình chú ý logic chính là đoạn này:
```c++
v8 = memfd_create(&unk_2006, 0LL);
v9 = (__int64 *)&unk_4060;
do
{
v10 = *v9;
v9 = (__int64 *)((char *)v9 + 1);
*(__int64 *)((char *)v9 - 1) = v5 * v10;
}
while ( v9 != (__int64 *)((char *)&unk_4060 + 28968) );
write(v8, &unk_4060, 0x7130uLL);
v11 = (__int64)*a3;
envp[0] = s;
envp[1] = 0LL;
__isoc99_sscanf(v11 + 5, "%llu", &v14);
v14 ^= v5;
snprintf(s, 0x1AuLL, format);
fexecve(v8, a2 + 1, envp);
```
Viết script để tìm tiếp thôi nhỉ:
``` python
#!/usr/bin/python3
from z3 import *
from pwn import *
x = u64(bytes.fromhex('E1 AF 4B DF 9D C6 25 C1'))
header = u64(bytes.fromhex('7f45 4c46 0201 0100'))
v4 = BitVec('v4', 64)
solver = Solver()
for i in range(8):
x *= v4
solver.add(x & 0xff == header & 0xff)
header >>= 8
x >>= 8
if solver.check() == sat:
m = solver.model()
ans = m[v4].as_long()
print(hex(ans))
print(p64(ans))
```
``` linux
~/currentCTF
❯ ./solve.py
0x30635f337233775f
b'_w3r3_c0'
```
Ra được 8 bytes tiếp theo của flag.
Dump memory các kiểu tiếp để xem nó `fexecve` cái gì tiếp thôi.
``` gdb
pwndbg> breakrva 0x1107
Breakpoint 2 at 0x555555555107
pwndbg> breakrva 0x1138
Breakpoint 3 at 0x555555555138
pwndbg> c
Continuing.
Breakpoint 2, 0x0000555555555107 in ?? ()
LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
─────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────
*RAX 0xf5b5e8549fa67db9
*RBX 0x7fffffffd728 —▸ 0x7fffffffd9a1 ◂— '/home/m1zuguchi/currentCTF/ono_dump_1.bin'
*RCX 0
*RDX 0x5cff9b68cc2
*RDI 0x7fffffffcf30 ◂— 0
*RSI 0x5cff9b68cc2
*R8 0x2f
*R9 0xffffffff
*R10 0xffffffffffffff88
*R11 0x7fffffffd3b0 ◂— 0xbaafbad8001
*R12 1
*R13 0x7fffffffd738 —▸ 0x7fffffffd9cb ◂— 'SHELL=/bin/bash'
*R14 0x555555556010 ◂— 0x756c6c25 /* '%llu' */
*R15 0x7ffff7ffd000 (_rtld_global) —▸ 0x7ffff7ffe2e0 —▸ 0x555555554000 ◂— 0x10102464c457f
*RBP 0x8000
*RSP 0x7fffffffd590 ◂— 0x5cff9b68cc2
*RIP 0x555555555107 ◂— cmp rdx, rax
──────────────────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]──────────────────────────────────────────────────────
► 0x555555555107 cmp rdx, rax 0x5cff9b68cc2 - 0xf5b5e8549fa67db9 EFLAGS => 0x217 [ CF PF AF zf sf IF df of ]
0x55555555510a ✔ jne 0x5555555551ab <0x5555555551ab>
↓
0x5555555551ab lea rdi, [rip + 0xe4e] RDI => 0x555555556000 ◂— 0xc36f002e6fb1c36f
0x5555555551b2 call puts@plt <puts@plt>
0x5555555551b7 push 1
0x5555555551b9 pop rax
0x5555555551ba add rsp, 0x48
0x5555555551be pop rbx
0x5555555551bf pop rbp
0x5555555551c0 pop r12
0x5555555551c2 pop r13
───────────────────────────────────────────────────────────────────[ STACK ]────────────────────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd590 ◂— 0x5cff9b68cc2
01:0008│ 0x7fffffffd598 —▸ 0x7fffffffd5c8 ◂— 0
02:0010│ 0x7fffffffd5a0 ◂— 0x6000000017
03:0018│ 0x7fffffffd5a8 ◂— 0
... ↓ 4 skipped
─────────────────────────────────────────────────────────────────[ BACKTRACE ]──────────────────────────────────────────────────────────────────
► 0 0x555555555107
1 0x7ffff7dc21ca __libc_start_call_main+122
2 0x7ffff7dc228b __libc_start_main+139
3 0x5555555551f1
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> set $rdx=0xf5b5e8549fa67db9
pwndbg> c
Continuing.
Breakpoint 3, 0x0000555555555138 in ?? ()
LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
─────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────
*RAX 0x555555558061 ◂— 0xb9c125c69ddf4baf
RBX 0x7fffffffd728 —▸ 0x7fffffffd9a1 ◂— '/home/m1zuguchi/currentCTF/ono_dump_1.bin'
*RCX 0xc125c69ddf4bafe1
*RDX 0x55555555f188 ◂— 0
*RDI 0x555555556006 ◂— 0xb1c36f006fb1c36f
*RSI 0x555555558060 ◂— 0xc125c69ddf4bafe1
R8 0x2f
R9 0xffffffff
*R10 0x7ffff7dad3d0 ◂— 0x110012000022e3
*R11 0x206
*R12 3
R13 0x7fffffffd738 —▸ 0x7fffffffd9cb ◂— 'SHELL=/bin/bash'
R14 0x555555556010 ◂— 0x756c6c25 /* '%llu' */
R15 0x7ffff7ffd000 (_rtld_global) —▸ 0x7ffff7ffe2e0 —▸ 0x555555554000 ◂— 0x10102464c457f
RBP 0x8000
RSP 0x7fffffffd590 ◂— 0x5cff9b68cc2
*RIP 0x555555555138 ◂— imul rcx, rbp
──────────────────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]──────────────────────────────────────────────────────
► 0x555555555138 imul rcx, rbp
0x55555555513c mov qword ptr [rax - 1], rcx [0x555555558060] => 0xe34eefa5d7f08000
0x555555555140 cmp rax, rdx 0x555555558061 - 0x55555555f188 EFLAGS => 0x293 [ CF pf AF zf SF IF df of ]
0x555555555143 ✔ jne 0x555555555132 <0x555555555132>
↓
0x555555555132 mov rcx, qword ptr [rax] RCX, [0x555555558061] => 0xb9e34eefa5d7f080
0x555555555135 inc rax RAX => 0x555555558062
0x555555555138 imul rcx, rbp
0x55555555513c mov qword ptr [rax - 1], rcx [0x555555558061] => 0xa777d2ebf8400000
0x555555555140 cmp rax, rdx 0x555555558062 - 0x55555555f188 EFLAGS => 0x293 [ CF pf AF zf SF IF df of ]
0x555555555143 ✔ jne 0x555555555132 <0x555555555132>
↓
0x555555555132 mov rcx, qword ptr [rax] RCX, [0x555555558062] => 0xc9a777d2ebf84000
───────────────────────────────────────────────────────────────────[ STACK ]────────────────────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd590 ◂— 0x5cff9b68cc2
01:0008│ 0x7fffffffd598 —▸ 0x7fffffffd5c8 ◂— 0
02:0010│ 0x7fffffffd5a0 ◂— 0x6000000017
03:0018│ 0x7fffffffd5a8 ◂— 0
... ↓ 4 skipped
─────────────────────────────────────────────────────────────────[ BACKTRACE ]──────────────────────────────────────────────────────────────────
► 0 0x555555555138
1 0x7ffff7dc21ca __libc_start_call_main+122
2 0x7ffff7dc228b __libc_start_main+139
3 0x5555555551f1
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> set $rbp=0x30635f337233775f
pwndbg> ni
0x000055555555513c in ?? ()
LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
─────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────
RAX 0x555555558061 ◂— 0xb9c125c69ddf4baf
RBX 0x7fffffffd728 —▸ 0x7fffffffd9a1 ◂— '/home/m1zuguchi/currentCTF/ono_dump_1.bin'
*RCX 0xe196d09b47aadb7f
RDX 0x55555555f188 ◂— 0
RDI 0x555555556006 ◂— 0xb1c36f006fb1c36f
RSI 0x555555558060 ◂— 0xc125c69ddf4bafe1
R8 0x2f
R9 0xffffffff
R10 0x7ffff7dad3d0 ◂— 0x110012000022e3
R11 0x206
R12 3
R13 0x7fffffffd738 —▸ 0x7fffffffd9cb ◂— 'SHELL=/bin/bash'
R14 0x555555556010 ◂— 0x756c6c25 /* '%llu' */
R15 0x7ffff7ffd000 (_rtld_global) —▸ 0x7ffff7ffe2e0 —▸ 0x555555554000 ◂— 0x10102464c457f
RBP 0x30635f337233775f ('_w3r3_c0')
RSP 0x7fffffffd590 ◂— 0x5cff9b68cc2
*RIP 0x55555555513c ◂— mov qword ptr [rax - 1], rcx
──────────────────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]──────────────────────────────────────────────────────
0x555555555140 cmp rax, rdx
0x555555555143 jne 0x555555555132 <0x555555555132>
0x555555555132 mov rcx, qword ptr [rax]
0x555555555135 inc rax
0x555555555138 imul rcx, rbp
► 0x55555555513c mov qword ptr [rax - 1], rcx [0x555555558060] => 0xe196d09b47aadb7f
0x555555555140 cmp rax, rdx 0x555555558061 - 0x55555555f188 EFLAGS => 0x293 [ CF pf AF zf SF IF df of ]
0x555555555143 ✔ jne 0x555555555132 <0x555555555132>
↓
0x555555555132 mov rcx, qword ptr [rax] RCX, [0x555555558061] => 0xb9e196d09b47aadb
0x555555555135 inc rax RAX => 0x555555558062
0x555555555138 imul rcx, rbp
───────────────────────────────────────────────────────────────────[ STACK ]────────────────────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd590 ◂— 0x5cff9b68cc2
01:0008│ 0x7fffffffd598 —▸ 0x7fffffffd5c8 ◂— 0
02:0010│ 0x7fffffffd5a0 ◂— 0x6000000017
03:0018│ 0x7fffffffd5a8 ◂— 0
... ↓ 4 skipped
─────────────────────────────────────────────────────────────────[ BACKTRACE ]──────────────────────────────────────────────────────────────────
► 0 0x55555555513c
1 0x7ffff7dc21ca __libc_start_call_main+122
2 0x7ffff7dc228b __libc_start_main+139
3 0x5555555551f1
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> info break
Num Type Disp Enb Address What
2 breakpoint keep y 0x0000555555555107
breakpoint already hit 1 time
3 breakpoint keep y 0x0000555555555138
breakpoint already hit 1 time
pwndbg> del 3
pwndbg> breakrva 0x1152
Breakpoint 4 at 0x555555555152
pwndbg> c
Continuing.
Breakpoint 4, 0x0000555555555152 in ?? ()
LEGEND: STACK | HEAP | CODE | DATA | WX | RODATA
─────────────────────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]─────────────────────────────────────────────
*RAX 0x55555555f188 ◂— 0
RBX 0x7fffffffd728 —▸ 0x7fffffffd9a1 ◂— '/home/m1zuguchi/currentCTF/ono_dump_1.bin'
*RCX 0
*RDX 0x7130
*RDI 3
RSI 0x555555558060 ◂— 0x10102464c457f
R8 0x2f
R9 0xffffffff
R10 0x7ffff7dad3d0 ◂— 0x110012000022e3
R11 0x206
R12 3
R13 0x7fffffffd738 —▸ 0x7fffffffd9cb ◂— 'SHELL=/bin/bash'
R14 0x555555556010 ◂— 0x756c6c25 /* '%llu' */
*R15 0x7fffffffd5b6 ◂— 0
RBP 0x30635f337233775f ('_w3r3_c0')
RSP 0x7fffffffd590 ◂— 0x5cff9b68cc2
*RIP 0x555555555152 ◂— call 0x555555555050
──────────────────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]──────────────────────────────────────────────────────
► 0x555555555152 call write@plt <write@plt>
fd: 3 (/memfd:oño (deleted))
buf: 0x555555558060 ◂— 0x10102464c457f
n: 0x7130
0x555555555157 mov rdi, qword ptr [r13]
0x55555555515b lea rdx, [rsp + 8]
0x555555555160 xor eax, eax EAX => 0
0x555555555162 mov rsi, r14
0x555555555165 mov qword ptr [rsp + 0x10], r15
0x55555555516a add rdi, 5
0x55555555516e and qword ptr [rsp + 0x18], 0
0x555555555174 call __isoc99_sscanf@plt <__isoc99_sscanf@plt>
0x555555555179 mov rcx, qword ptr [rsp + 8]
0x55555555517e mov rdi, r15
───────────────────────────────────────────────────────────────────[ STACK ]────────────────────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffd590 ◂— 0x5cff9b68cc2
01:0008│ 0x7fffffffd598 —▸ 0x7fffffffd5c8 ◂— 0
02:0010│ 0x7fffffffd5a0 ◂— 0x6000000017
03:0018│ 0x7fffffffd5a8 ◂— 0
... ↓ 4 skipped
─────────────────────────────────────────────────────────────────[ BACKTRACE ]──────────────────────────────────────────────────────────────────
► 0 0x555555555152
1 0x7ffff7dc21ca __libc_start_call_main+122
2 0x7ffff7dc228b __libc_start_main+139
3 0x5555555551f1
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> dump binary memory ono_dump_2.bin Quit
pwndbg> dump binary memory ono_dump_2.bin 0x555555558060 0x555555558060+0x7130
```
Mở IDA lên xem thử thui:
Có vẻ như lần này bài đã đụng đến cái `envp`, `*a3 + 5` là nó lấy số kiểu `llu` phía sau `oño=`, để biết số đó là gì thì ta check lại envp của 2 file trước đó.
**File1:**
**File2:**
Để lấy `envp` của file 1 thì ta debug, còn `envp` của file 2 là `envp của file 1 ^ flag của file 2`.
```python
#!/usr/bin/python3
from pwn import *
from z3 import *
from ctypes import *
chall1_envp = 8940005473485202353
chall2_ans = 3486735211078842207
header = b'\x7fELF\x02\x01\x01\x00'
ans = BitVec('ans', 64)
solver = Solver()
chall2_envp = chall2_ans ^ chall1_envp
print(hex(chall2_envp))
qword_4048 = 0x7E34413175C77CE8
qword_4050 = 0x0D4308F96CA525D5A
solver.add((ans % 0x539) != 800)
solver.add((qword_4048 + qword_4050 * ans) == chall2_envp)
if solver.check() == sat:
m = solver.model()
res = m[ans].as_long()
print(hex(res))
print(p64(res))
```
``` linux
~/currentCTF 11m 31s
❯ ./solve.py
0x4c7218afdb1154ee
0x31775f476e314b6f
b'oK1nG_w1'
```
Khúc này debug mình thấy vô IDA dump memory tiện hơn, đặt breakpoint ngay đoạn này sửa giá trị rồi dump là ok:
Script dump:
```IDA
auto fp, ea;
fp = fopen("dumped_3.bin", "wb");
for (ea = 0x556B2E57E060; ea < 0x556B2E57E060 + 0x38B8; ea++)
fputc(Byte(ea), fp);
```
Mở IDA ra xem thử thôi lets go, ở đây thì mình đã rev và rename rồi:
``` c++
__int64 __fastcall main(int a1, char **a2, char **a3)
{
int v3; // ecx
int v4; // r9d
unsigned __int64 v5; // r8
int v6; // esi
int v7; // eax
int v8; // r9d
void *v9; // r11
char *v10; // r9
char v11; // r10
int v13; // eax
int v14; // r10d
__int64 chall3_envp; // [rsp+8h] [rbp-30h] BYREF
__int64 chall3_flag; // [rsp+10h] [rbp-28h] BYREF
__int64 v17[4]; // [rsp+18h] [rbp-20h] BYREF
__isoc99_sscanf(*a3 + 5, "%llu", &chall3_envp);
__isoc99_sscanf(*a2, "%llu", &chall3_flag);
v3 = 0;
v4 = 0;
v5 = chall3_envp ^ chall3_flag;
v6 = 0;
chall3_flag ^= chall3_envp;
do
{
if ( ((v5 >> v3) & 1) == 0 )
{
++v4;
v6 = v3;
}
++v3;
}
while ( v3 != 64 );
v17[0] = 0LL;
if ( !v4 || (v7 = dfsBit(v5, v6, v17), v7 == v8) )
{
v9 = &unk_4060;
v10 = (char *)&unk_4060;
while ( 1 )
{
v11 = *v10;
v17[0] = 0LL;
if ( v11 )
{
if ( ((v5 >> ((unsigned __int8)v10 - (unsigned __int8)v9)) & 1) == 0 )
break;
v13 = dfsBit(v5, (int)v10 - (int)v9, v17);
if ( v13 != v14 )
break;
}
if ( ++v10 == (char *)&unk_4060 + 64 )
{
puts(win_message);
return 0LL;
}
}
}
puts(s);
return 1LL;
}
```
``` c++
__int64 __fastcall dfsBit(unsigned __int64 number, int bitPos, _QWORD *a3)
{
_DWORD *v3; // r12
unsigned int v5; // ebx
int v6; // edx
int v7; // eax
v3 = &unk_4040;
*a3 |= 1LL << bitPos;
v5 = 1;
do
{
v6 = bitPos / 8 + *v3;
v7 = bitPos % 8 + v3[1];
if ( (v7 | (unsigned int)v6) <= 7
&& (((unsigned __int8)(*a3 >> (v7 + 8 * (unsigned __int8)v6)) | (unsigned __int8)((number >> bitPos) ^ (number >> (v7 + 8 * (unsigned __int8)v6)))) & 1) == 0 )
{
v5 += dfsBit(number, v7 + 8 * v6, a3);
}
v3 += 2;
}
while ( (_DWORD *)((char *)&unk_4040 + 32) != v3 );
return v5;
}
```
Tóm tắt flow nó như này:
- Đem flag xor với envp
- Check xem các số 0 có liên thông với nhau khi duyệt **DFS** không (Nếu ở vị trí bit thứ i thì ta có thể duyệt sang bit thứ i - 1, i + 1, i - 8, i + 8 với điều kiện là 2 giá trị của bit bằng nhau).
- Xong rồi sẽ có một điều kiện để check bit thứ i xem có bật hay không, và số bit mà bit đó **DFS** tới thỏa điều kiện.
- Nếu thỏa tất cả điều kiện trên thì là flag.
Mình sẽ nói về cái điều kiện thứ 3 ở trên:
``` linux
[[19, 1], [33, 5], [39, 7], [42, 3], [45, 4], [52, 6], [58, 2]]
```
Nó yêu cầu tại vị trí thứ 19 (bit thứ 19 phải bật) DFS sẽ tới 1 đỉnh, 33 thì 5 đỉnh, và tương tự với các giá trị khác. Xong rồi các bit không bật thì phải liên thông với nhau. Điều thú vị ở đây là nghĩ đi nghĩ lại thì kiểu gì đây cũng là một bài **NP Hard** ???. Mình không giải nhiều bài **NP Hard** lắm nhưng ở đây mình biết được phần cuối flag kiểu gì cũng là `}`.
Đến đây thì mình sẽ không cố gắng giải một bài `NP Hard`, mà mình sẽ ngồi mò nó với những dữ liệu mà mình có (như là phần cuối là `}`, phần đầu là `t`).
Đến đây thì ngồi suy nghĩ các kiểu rồi, mình cũng không nhớ hết được mình đã nghĩ ra cái gì nên đây là script cho part cuối của flag:
``` c++
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int num, goal, cntVis[64], cur;
vector<int> vecVis[10];
bool vis[64], mp[64];
bool check(int x) {
return x >= 0 && x < 64;
}
void dfs(int u) {
if (mp[u]) {
return;
}
if (!vis[u]) {
return;
}
num++;
// cout << u << ' ';
mp[u] = 1;
for (int i = 0; i < 4; i++) {
int v = u + dx[i] * 8 + dy[i];
if (vis[v] && check(v)) {
dfs(v);
}
}
}
void dfs0(int u) {
if (mp[u]) {
return;
}
if (vis[u]) {
return;
}
num++;
// cout << u << ' ';
mp[u] = 1;
for (int i = 0; i < 4; i++) {
int v = u + dx[i] * 8 + dy[i];
if (!vis[v] && check(v)) {
dfs0(v);
}
}
}
int main() {
vector<pair<int, int>> dfsList;
dfsList.push_back({19, 1});
dfsList.push_back({33, 5});
dfsList.push_back({39, 7});
dfsList.push_back({42, 3});
dfsList.push_back({45, 4});
dfsList.push_back({52, 6});
dfsList.push_back({58, 2});
fill(vis, vis + 64, 0);
vis[63] = 1;
vis[62] = 1;
vis[61] = 1;
vis[60] = 1;
vis[55] = 1;
vis[52] = 1;
vis[57] = 1;
vis[58] = 1;
vis[45] = 1;
vis[37] = 1;
vis[29] = 1;
vis[21] = 1;
vis[43] = 1;
vis[42] = 1;
vis[35] = 1;
vis[39] = 1;
vis[31] = 1;
vis[23] = 1;
vis[15] = 1;
vis[7] = 1;
vis[6] = 1;
vis[5] = 1;
vis[33] = 1;
vis[25] = 1;
vis[17] = 1;
vis[9] = 1;
vis[10] = 1;
vis[19] = 1;
for (auto [i, cnt] : dfsList) {
num = 0;
fill(mp, mp + 64, 0);
dfs(i);
cout << i << ' ' << num << ' ' << cnt << "\n";
}
num = 0;
fill(mp, mp + 64, 0);
dfs0(59);
cout << num << ' ';
num = 0;
unsigned long long x = 0;
for (int i = 0; i < 64; i++) {
if (vis[i]) {
num++;
x |= (1ll << i);
}
}
cout << 64 - num << "\n";
cout << (x ^ 0x8bb15f9ec5f5ce94);
return 0;
}
```
Final flag:
```
dice{n0w_w3r3_c0oK1nG_w1tH_g4s!}
```
## misc/bcu-binding
Tải file về thì ta search thử 'dice{' để tìm flag và nó ra thật @@
Có vẻ như nó được giấu trong phần nền trắng để không thể nhìn thấy...
Flag: dice{r3ad1ng_th4_d0cs_71ccd}
## misc/dicecap
Đề cho ta 1 file pcap nên ta mở nó lên bằng wireshark và xem thử:
Thử tìm theo từ khóa thì ta ra được 2 kênh khả nghi chứa flag theo protocol FTP-DATA.
Export file ra thì ta được 1 file main theo định dạng ELF cùng 1 tệp zip cần mật khẩu mà trong đó chứa flag.txt có thể lấy flag.
File main được định dạng ELF nên ta mở IDA để đọc code của nó
Ở đây file main khởi tạo mật khẩu và nó có thể được dùng để giải nén file zip. Đọc rõ hơn:
1. Lấy thời gian hiện tại và làm tròn theo phút là được s
2. Lấy 5 ký tự đầu tiên của locale (dest)
3. Ghép username (v3)
4. Kết hợp tất cả thành mật khẩu (v6)
Đầu tiên, khi ta xem lại thì gói main nằm ở No.168 và khi tra lại thì ta lấy được thời gian v1 rồi sau đó tính theo công thức để lấy s.
```python!
v1 = 1743126530
s = v1 - v1 % 60
# 1743126480
```
Thứ hai về locate thì ta lấy mặc định là `en_US.UTF-8` nhưng chỉ lấy 5 kí tự đầu cho dest là: `en_US`
Cuối cùng, username ta sẽ có được bằng cách tìm kiếm những request được gửi lên thông qua gói tin mà ta có thể xem được và đây là kết quả:
```python=
# solution.py
v1 = 1743126530
s = v1 - v1 % 60
locale_str = "en_US"
username = "hacker"
password = f"{s}{locale_str}{username}"
print(password) #1743126480en_UShacker
```
Giải nén file zip và lấy flag thôi:
Flag: dice{5k1d_y0ur_w@y_t0_v1ct0ry_t0d4y!!!}
## crypto/vorpal-sword
```python=
# server.py
#!/usr/local/bin/python
import secrets
from Crypto.PublicKey import RSA
DEATH_CAUSES = [
"a fever",
"dysentery",
"measles",
"cholera",
"typhoid",
"exhaustion",
"a snakebite",
"a broken leg",
"a broken arm",
"drowning",
]
def run_ot(key, msg0, msg1):
"""
https://en.wikipedia.org/wiki/Oblivious_transfer#1–2_oblivious_transfer
"""
x0 = secrets.randbelow(key.n)
x1 = secrets.randbelow(key.n)
print(f"n: {key.n}")
print(f"e: {key.e}")
print(f"x0: {x0}")
print(f"x1: {x1}")
v = int(input("v: "))
assert 0 <= v < key.n, "invalid value"
k0 = pow(v - x0, key.d, key.n)
k1 = pow(v - x1, key.d, key.n)
m0 = int.from_bytes(msg0.encode(), "big")
m1 = int.from_bytes(msg1.encode(), "big")
c0 = (m0 + k0) % key.n
c1 = (m1 + k1) % key.n
print(f"c0: {c0}")
print(f"c1: {c1}")
if __name__ == "__main__":
with open("flag.txt") as f:
flag = f.read().strip()
print("=== CHOOSE YOUR OWN ADVENTURE: Vorpal Sword Edition ===")
print("you enter a cave.")
for _ in range(64):
print("the tunnel forks ahead. do you take the left or right path?")
key = RSA.generate(1024)
msgs = [None, None]
page = secrets.randbits(32)
live = f"you continue walking. turn to page {page}."
die = f"you die of {secrets.choice(DEATH_CAUSES)}."
msgs = (live, die) if secrets.randbits(1) else (die, live)
run_ot(key, *msgs)
page_guess = int(input("turn to page: "))
if page_guess != page:
exit()
print(f"you find a chest containing {flag}")
```
Theo thử thách, bài này nói về [1-2 oblivious transfer](https://en.wikipedia.org/wiki/Oblivious_transfer#1%E2%80%932_oblivious_transfer) nên mình cũng lên mạng tìm hiểu và đây là các bước mà giao thức này thực hiện:
1. Alice có tin nhắn $m_0, m_1$ và 1 cặp khóa RSA $(e, d, N)$. Bob biết được khóa công khai $(e, N)$ của Alice và muốn tin nhắn $m_c$ , với $c \in \{0, 1\}$.
2. Alice tạo ngẫu nhiên 2 số $x_0, x_1$ và gửi cho Bob.
3. Bob tạo ngẫu nhiên 1 số $k$ và gửi $v = b+k^e \mod N$ cho Alice.
4. Alice tính $k_0 = (v-x_0)^d\mod N$ và $k_1 = (v-x_1)^d\mod N$ rồi gửi $m_0'=m_0+k_0\mod N$ và $m_1'=m_1+k_1\mod N$ cho Bob.
5. Bob tính và lấy được $m_c=m_c'-k\mod N$ và không lấy được thông tin gì từ $m_{1-c}$
Đọc file server thì ta thấy là hàm `run_ot` đúng là đang thực hiện giống như 4 bước đầu trong giao thức trên. Và khi ta truy ngược lại thì ta cần biết được `page` mà được giấu trong tin nhắn `live`
```python=
live = f"you continue walking. turn to page {page}."
die = f"you die of {secrets.choice(DEATH_CAUSES)}."
msgs = (live, die) if secrets.randbits(1) else (die, live)
run_ot(key, *msgs)
page_guess = int(input("turn to page: "))
if page_guess != page:
exit()
```
Tuy nhiên vì `msgs` được random giữa `(live,die)` và `(die, live)`, cùng với việc ta phải nhập đúng `page` trong 64 lần liên tiếp thì rõ ràng việc làm như Bob là lấy được 1 trong 2 tin nhắn không khả thi. Vì xác suất trúng được hết chỉ là $\dfrac{1}{2^{64}}$.
Vì ta đã biết được list của các `DEATH_CAUSES` nên ta cũng có thể tính được hết tất cả các `die` của chall, tức là ta có thể phân biệt được đâu là `live` và đâu là `die`.
Nhận thấy, ta đã biết $c_0, c_1$, 1 trong hai giá trị $m_0, m_1$ thì việc tìm ra được giá trị còn lại phải dựa vào 1 biểu thức tuyến tính giữa 4 biến này xảy ra.
Nói rõ hơn:
$$
c_0\equiv m_0+k_0\mod n
$$
$$
c_1\equiv m_1+k_1\mod n
$$
$$
\Leftrightarrow a c_0 -bc_1\equiv am_0-bm_1 +(ak_0 -bk_1)\mod n \ \ \ \ \ (*)
$$
Có nghĩa là ta phải tìm v làm sao mà $ak_0-bk_1 \equiv 0 \mod n$, với a,b bất kỳ
Điều này tương đương với: $(v-x_0)^d\equiv k(v-x_1)^d \mod n$
$$
\Leftrightarrow (v-x_0)^{de}\equiv k^e(v-x_1)^{de}\mod n
$$
Chọn v có điều kiện $\gcd(v-x_0, n) = 1$ và sử dụng định lý Euler cùng $de\equiv 1\mod \phi(n)$
$$
\Leftrightarrow v-x_0\equiv k^e(v-x_1)\mod n
$$
$$
\Leftrightarrow (k^e - 1)(v-x_1)\equiv x_1-x_0\mod n
$$
Thử $k=1,-1$ đều không thỏa nên ta thử $k = 2$
Lúc này, $k^e-1=2^{65537}-1$ là 1 số Mersenne nên các ước nguyên tố của nó có [tính chất](https://vi.wikipedia.org/wiki/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_Mersenne#C%C3%A1c_%C4%91%E1%BB%8Bnh_l%C3%BD_v%E1%BB%81_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_Mersenne): Nếu q là một số nguyên tố của 1 số Mersenne: $q\equiv 1\mod 65537, q\equiv \pm1\mod 8$
Mặt khác, $n$ là một số nguyên tố 1024 bit nằm trong khoảng $2^{1023}$ đến $2^{1024}-1$ và là rất lớn so với ước nguyên tố điển hình của $2^{65537}-1$. Hơn nữa, theo [Định lý số nguyên tố](https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91) thì có thể có khoảng $\dfrac{2^{1023}}{ln(2^{1023})} \approx \dfrac{2^{1023}}{709}$ số nguyên tố 1024 bit. Do đó với 1 số nguyên tố 1024 bit ngẫu nhiên, gần như chắc chắn là số đó không có khả năng là ước của $2^{65537}-1$
Vì vậy, $\gcd(k^e-1,n)=1$ tương đương với tồn tại nghịch đảo modulo n của $2^{65537}-1$
$$
\Leftrightarrow v-x_1\equiv (k^e - 1)^{-1}(x_1-x_0)\mod n
$$
$$
\Leftrightarrow v\equiv (k^e - 1)^{-1}(x_1-x_0) + x_1\mod n
$$
```python=
e = 65537
k = 2**e - 1
def sol_v(n, k, x0, x1):
d = inverse(k, n)
return (x1 + d*(x1-x0)) % n
```
Bây giờ trở lại với $(*)$ thì ta được biểu thức tuyến tính sau:
$$
\Leftrightarrow c_0 -2c_1\equiv m_0-2m_1\mod n \ \ \ \ \ (**)
$$
Lúc này, ta chia 2 trường hợp rõ ràng:
1. nếu `page` nằm trong `live` của $m_0$:
$$
(**)\Leftrightarrow m_0\equiv c_0 -2c_1+2m_1\mod n
$$
```python=
def case_m0(n, c0, c1, lst):
page = -1
for i in lst:
k = (c0 - 2*c1 + 2*i) % n
try:
res = long_to_bytes(k)
except ValueError:
continue
if res.startswith(b"you continue walking. turn to page "):
page = res[35:-1]
if page.isdigit():
break
return page
```
2. nếu `page` nằm trong `live` của $m_1$:
$$
(**)\Leftrightarrow m_1\equiv (m_0-c_0+2c_1)\times 2^{-1}\mod n
$$
```python=
def case_m1(n, c0, c1, lst):
page = -1
inv = inverse(2, n)
for j in lst:
k = (j - c0 + 2*c1)*inv % n
try:
res = long_to_bytes(k)
except ValueError:
continue
if res.startswith(b"you continue walking. turn to page "):
page = res[35:-1]
if page.isdigit():
break
return page
```
Đến đây rồi thì, ta brute-force hết cái list của `die` thì ta sẽ biết được trường hợp nào là thỏa và tìm được `page`. Remote tới server và nhận flag thôi :333
```python=
# solution.py
from pwn import *
from Crypto.Util.number import *
import sys
sys.set_int_max_str_digits(0)
DEATH_CAUSES = [
'a fever',
'dysentery',
'measles',
'cholera',
'typhoid',
'exhaustion',
'a snakebite',
'a broken leg',
'a broken arm',
'drowning',
]
lst = []
for i in DEATH_CAUSES:
die = f'you die of {i}.'
s = int.from_bytes(die.encode(), 'big')
lst.append(s)
def rev_data():
return int(io.recvline().strip().decode())
def take_data1():
io.recvuntil("n: ")
n = rev_data()
io.recvuntil("x0: ")
x0 = rev_data()
io.recvuntil("x1: ")
x1 = rev_data()
return n, x0, x1
e = 65537
k = 2**e - 1
def sol_v(n, k, x0, x1):
d = inverse(k, n)
return (x1 + d*(x1-x0)) % n
def take_data2():
io.recvuntil("c0: ")
c0 = rev_data()
io.recvuntil("c1: ")
c1 = rev_data()
return c0, c1
def case_m0(n, c0, c1, lst):
page = -1
for i in lst:
k = (c0 - 2*c1 + 2*i) % n
try:
res = long_to_bytes(k)
except ValueError:
continue
if res.startswith(b"you continue walking. turn to page "):
page = res[35:-1]
if page.isdigit():
break
return page
def case_m1(n, c0, c1, lst):
page = -1
inv = inverse(2, n)
for j in lst:
k = (j - c0 + 2*c1)*inv % n
try:
res = long_to_bytes(k)
except ValueError:
continue
if res.startswith(b"you continue walking. turn to page "):
page = res[35:-1]
if page.isdigit():
break
return page
io = remote("dicec.tf", 31001)
for _ in range(64):
n, x0, x1 = take_data1()
v = sol_v(n, k, x0, x1)
io.recvuntil("v: ")
io.sendline(str(v))
c0, c1 = take_data2()
page = case_m0(n, c0, c1, lst)
if page == -1:
page = case_m1(n, c0, c1, lst)
io.recvuntil("turn to page: ")
io.sendline(page)
data = io.recvall()
print(data)
io.close()
```
Flag: dice{gl3am1ng_g0ld_doubl00n}
{%hackmd j1OspBFEQaSWOBxLkcN4xA %}
Sign in with Wallet
Connect another wallet