HITCON CTF 2017 Quals

Loading the binary with IDA provides us:

Connecting to the service:

$ nc 13.112.220.64 9999
N: 104176920808444707134363566789644103637046138703732812593856489450966164422700871083271001476798525601830292237723021138499045286505397665962198734248957208942814238767855960753797521549548788530151996440657784060736603682776712677518537991291065233449586393186516770855075158900503486179189610821817031409223
e: 3
File list:
flag.txt
key.txt
run.sh
secret
secretfile.txt
Input filename(txt) :

At first i tried to factor N which give no promising result, after that @peter noticed the way server read filename can lead to buffer overflow that we can modify 2 bytes of e, after that we can re-read the flag file which will be encrypt using new e (let’s call it e'), if gcd(e, e')=1 we can recover the original message by extended gcd:

Final solution:

@mipu94 first working on this problem, dumped the seccomp part:

 0000: 0x20 0x00 0x00 0x00000000  A = sys_number
 0001: 0x15 0x01 0x00 0x00001337  if (A == 0x1337) goto 0003
 0002: 0x06 0x00 0x00 0x7fff0000  return ALLOW
 0003: 0x20 0x00 0x00 0x00000010  A = args[0]
 0004: 0x07 0x00 0x00 0x00000000  X = A
 0005: 0x54 0x00 0x00 0x0000ffff  A &= 0xffff
 0006: 0x02 0x00 0x00 0x00000003  mem[3] = A
 0007: 0x87 0x00 0x00 0x00000000  A = X
 0008: 0x74 0x00 0x00 0x00000010  A >>= 16
 0009: 0x02 0x00 0x00 0x00000002  mem[2] = A
 0010: 0x20 0x00 0x00 0x00000014  A = args[0] >> 32
 0011: 0x07 0x00 0x00 0x00000000  X = A
 0012: 0x54 0x00 0x00 0x0000ffff  A &= 0xffff
 0013: 0x02 0x00 0x00 0x00000001  mem[1] = A
 0014: 0x87 0x00 0x00 0x00000000  A = X
 0015: 0x74 0x00 0x00 0x00000010  A >>= 16
 0016: 0x02 0x00 0x00 0x00000000  mem[0] = A
 0017: 0x60 0x00 0x00 0x00000000  A = mem[0]
 0018: 0x15 0x00 0x01 0x00000000  if (A != 0) goto 0020
 0019: 0x00 0x00 0x00 0x00010000  A = 65536
 0020: 0x24 0x00 0x00 0x00006761  A *= 0x6761
 0021: 0x07 0x00 0x00 0x00000000  X = A
 0022: 0x34 0x00 0x00 0x00010001  A /= 0x10001
 0023: 0x24 0x00 0x00 0x00010001  A *= 0x10001
 0024: 0x84 0x00 0x00 0x00000000  A = -A
 0025: 0x0c 0x00 0x00 0x0000c450  A += X
 0026: 0x15 0x00 0x01 0x00010000  if (A != 65536) goto 0028
 0027: 0x00 0x00 0x00 0x00000000  A = 0
 0028: 0x02 0x00 0x00 0x00000000  mem[0] = A
 0029: 0x60 0x00 0x00 0x00000001  A = mem[1]
 0030: 0x04 0x00 0x00 0x00006c66  A += 0x6c66
 0031: 0x54 0x00 0x00 0x0000ffff  A &= 0xffff
 0032: 0x02 0x00 0x00 0x00000001  mem[1] = A
 0033: 0x60 0x00 0x00 0x00000002  A = mem[2]
 0034: 0x04 0x00 0x00 0x00005f65  A += 0x5f65
 0035: 0x54 0x00 0x00 0x0000ffff  A &= 0xffff
 0036: 0x02 0x00 0x00 0x00000002  mem[2] = A
 0037: 0x60 0x00 0x00 0x00000003  A = mem[3]
 0038: 0x15 0x00 0x01 0x00000000  if (A != 0) goto 0040
 0039: 0x00 0x00 0x00 0x00010000  A = 65536
 0040: 0x24 0x00 0x00 0x00006b61  A *= 0x6b61
 0041: 0x07 0x00 0x00 0x00000000  X = A
 0042: 0x34 0x00 0x00 0x00010001  A /= 0x10001
 0043: 0x24 0x00 0x00 0x00010001  A *= 0x10001
 0044: 0x84 0x00 0x00 0x00000000  A = -A
 0045: 0x0c 0x00 0x00 0x00001577  A += X
 0046: 0x15 0x00 0x01 0x00010000  if (A != 65536) goto 0048
 0047: 0x00 0x00 0x00 0x00000000  A = 0
 0048: 0x02 0x00 0x00 0x00000003  mem[3] = A
 0049: 0x60 0x00 0x00 0x00000000  A = mem[0]
 0050: 0x61 0x00 0x00 0x00000002  X = mem[2]
 0051: 0xac 0x00 0x00 0x0000340f  A ^= X
 0052: 0x02 0x00 0x00 0x00000004  mem[4] = A
 0053: 0x60 0x00 0x00 0x00000001  A = mem[1]
 0054: 0x61 0x00 0x00 0x00000003  X = mem[3]
 0055: 0xac 0x00 0x00 0x0000af9f  A ^= X
 0056: 0x02 0x00 0x00 0x00000005  mem[5] = A
 0057: 0x60 0x00 0x00 0x00000004  A = mem[4]
 0058: 0x15 0x00 0x01 0x00000000  if (A != 0) goto 0060
...
 4037: 0x0c 0x00 0x00 0x0000fc4b  A += X
 4038: 0x15 0x00 0x01 0x00010000  if (A != 65536) goto 4040
 4039: 0x00 0x00 0x00 0x00000000  A = 0
 4040: 0x02 0x00 0x00 0x00000003  mem[3] = A
 4041: 0x01 0x00 0x00 0x00001337  X = 4919
 4042: 0x60 0x00 0x00 0x00000003  A = mem[3]
 4043: 0xac 0x00 0x00 0x00008080  A ^= X
 4044: 0x15 0x01 0x00 0x00005d3e  if (A == 23870) goto 4046
 4045: 0x06 0x00 0x00 0x00000000  return KILL
 4046: 0x60 0x00 0x00 0x00000002  A = mem[2]
 4047: 0xac 0x00 0x00 0x000031c8  A ^= X
 4048: 0x15 0x01 0x00 0x0000d4d8  if (A == 54488) goto 4050
 4049: 0x06 0x00 0x00 0x00000000  return KILL
 4050: 0x60 0x00 0x00 0x00000001  A = mem[1]
 4051: 0xac 0x00 0x00 0x00000503  A ^= X
 4052: 0x15 0x01 0x00 0x000066c7  if (A == 26311) goto 4054
 4053: 0x06 0x00 0x00 0x00000000  return KILL
 4054: 0x60 0x00 0x00 0x00000000  A = mem[0]
 4055: 0xac 0x00 0x00 0x0000302c  A ^= X
 4056: 0x15 0x01 0x00 0x00009cef  if (A == 40175) goto 4058
 4057: 0x06 0x00 0x00 0x00000000  return KILL

Full dumped file here.

He tried to solve using z3 which seems practically impossible without optimizing.

After play a bit with the patterns in the dump, i notice some common patterns:

• swap pattern:

; SWAP($mem1, $mem2)
A = $mem1
X = $mem2
$mem1 = X
$mem2 = A

• xor pattern:

; $mem3 = $mem1 ^ $mem2
A = $mem1
X = $mem2
A ^= X
$mem3 = A

• add pattern:

; $mem3 = ($mem1 + $mem2) & 0xFFFF
A = $mem1
X = $mem2
A += X
A &= 0xffff
$mem3 = A

; $mem2 = ($mem1 + $num1) & 0xFFFF
A = $mem1
A += $num1
A &= 0xffff
$mem2 = A

• mod 0x10001 pattern:

; $mem2 = ((CHK0($mem1) * $num2) %0x10001) & 0xFFFF
A = $mem1
if (A != 0) goto $line1
A = 65536
A *= $num2
X = A
A /= 0x10001
A *= 0x10001
A = -A
A += X
if (A != 65536) goto $line2
A = 0
$mem2 = A

• check memory pattern:

; REQUIREMEM($num4, $num3, $num2, $num1, $num0)
X = $num0
A = mem[3]
A ^= X
if (A == $num1) goto $line1
return KILL
A = mem[2]
A ^= X
if (A == $num2) goto $line2
return KILL
A = mem[1]
A ^= X
if (A == $num3) goto $line3
return KILL
A = mem[0]
A ^= X
if (A == $num4) goto $line4
return KILL

• load argument pattern:

; LOADMEM($arg1)
A = $arg1
X = A
A &= 0xffff
mem[3] = A
A = X
A >>= 16
mem[2] = A
A = $arg1 >> 32
X = A
A &= 0xffff
mem[1] = A
A = X
A >>= 16
mem[0] = A

Using these pattern and after play some more we notice some more generic patterns:

; BLOCK($num1, $num2, $num3, $num4, $num5, $num6)
mem[0] = ((CHK0(mem[0]) * $num1) %0x10001) & 0xFFFF
mem[1] = (mem[1] + $num2) & 0xFFFF
mem[2] = (mem[2] + $num3) & 0xFFFF
mem[3] = ((CHK0(mem[3]) * $num4) %0x10001) & 0xFFFF
mem[4] = mem[0] ^ mem[2]
mem[5] = mem[1] ^ mem[3]
mem[4] = ((CHK0(mem[4]) * $num5) %0x10001) & 0xFFFF
mem[5] = (mem[4] + mem[5]) & 0xFFFF
mem[5] = ((CHK0(mem[5]) * $num6) %0x10001) & 0xFFFF
mem[4] = (mem[4] + mem[5]) & 0xFFFF
mem[0] = mem[0] ^ mem[5]
mem[1] = mem[1] ^ mem[4]
mem[2] = mem[2] ^ mem[5]
mem[3] = mem[3] ^ mem[4]

; INITIAL($num1, $num2, $num3, $num4)
mem[0] = ((CHK0(mem[0]) * $num1) %0x10001) & 0xFFFF
mem[1] = (mem[1] + $num2) & 0xFFFF
mem[2] = (mem[2] + $num3) & 0xFFFF
mem[3] = ((CHK0(mem[3]) * $num4) %0x10001) & 0xFFFF

Here’s the script to apply these patterns:

Which provided final block code:

A = sys_number
if (A == 0x1337) goto 0003
return ALLOW
LOADMEM(args[0])
BLOCK(0x6761, 0x6c66, 0x5f65, 0x6b61, 0x665f, 0x615f)
SWAP(mem[1], mem[2])
BLOCK(0x6d61, 0x5f49, 0xccbe, 0xcad6, 0xc2cc, 0xbec2)
SWAP(mem[1], mem[2])
BLOCK(0xbeda, 0xc2be, 0x92ce, 0xc2d8, 0xad85, 0x997d)
SWAP(mem[1], mem[2])
BLOCK(0x857d, 0xb585, 0x7d25, 0x9d85, 0xb199, 0x7d95)
SWAP(mem[1], mem[2])
BLOCK(0xfb0a, 0xfb6b, 0xafa, 0x4b3b, 0xb63, 0x32fb)
SWAP(mem[1], mem[2])
BLOCK(0x2b5b, 0xb32, 0xd615, 0xf496, 0x7616, 0xc665)
SWAP(mem[1], mem[2])
BLOCK(0xf656, 0xb616, 0x65f6, 0x15f6, 0x2cec, 0x2d8c)
SWAP(mem[1], mem[2])
BLOCK(0xcbec, 0xad6c, 0x2ccb, 0xec2b, 0xedac, 0x2be9)
INITIAL(0x1997, 0xd95a, 0xd859, 0x97d8)
REQUIREMEM(44702, 45409, 6003, 2695, 4919)
LOADMEM(args[1])
BLOCK(0x7665, 0x725f, 0x7972, 0x375f, 0x6e30, 0x5f65)
SWAP(mem[1], mem[2])
BLOCK(0x6d6f, 0x435f, 0xbef2, 0xe46e, 0xbedc, 0x60be)
SWAP(mem[1], mem[2])
BLOCK(0xcada, 0xde86, 0xbeec, 0xcae4, 0xdd7d, 0xb8c1)
SWAP(mem[1], mem[2])
BLOCK(0x7d95, 0xb5bd, 0xd7d, 0xd995, 0xc97d, 0xe5c8)
SWAP(mem[1], mem[2])
BLOCK(0x82fb, 0x2b6b, 0x7a1a, 0xfbb3, 0x2b92, 0xfbcb)
SWAP(mem[1], mem[2])
BLOCK(0x91ba, 0xfb71, 0xd6f4, 0x35f7, 0x6657, 0x25f7)
SWAP(mem[1], mem[2])
BLOCK(0x9723, 0x75f6, 0xe305, 0xf656, 0xeecc, 0xae4b)
SWAP(mem[1], mem[2])
BLOCK(0xef2e, 0x46eb, 0xedc6, 0xbec, 0xadad, 0xe86b)
INITIAL(0x97de, 0x5c8d, 0xd7db, 0x8c17)
REQUIREMEM(39867, 15917, 15970, 37882, 4919)
LOADMEM(args[2])
BLOCK(0x6e69, 0x6b78, 0x7866, 0x5f73, 0x6968, 0x745f)
SWAP(mem[1], mem[2])
BLOCK(0x6573, 0x7265, 0xf0f0, 0xccbe, 0xe6d2, 0xd0e8)
SWAP(mem[1], mem[2])
BLOCK(0xbeca, 0xe6e4, 0xcadc, 0xd2d6, 0x7dcd, 0xa5a1)
SWAP(mem[1], mem[2])
BLOCK(0xd17d, 0x95cd, 0xc995, 0xb9a5, 0xade1, 0xe199)
SWAP(mem[1], mem[2])
BLOCK(0x43a2, 0xfb2b, 0x9b93, 0x2b73, 0x4b5b, 0xc3c3)
SWAP(mem[1], mem[2])
BLOCK(0x32fb, 0x9b4b, 0x5737, 0x2656, 0xe696, 0xb787)
SWAP(mem[1], mem[2])
BLOCK(0x8665, 0xf736, 0x9687, 0x45f6, 0xadcd, 0x2d6f)
SWAP(mem[1], mem[2])
BLOCK(0xf0c, 0xcbee, 0x6d2d, 0xe8b, 0xecae, 0x6e4c)
INITIAL(0xde1e, 0x1997, 0xdcda, 0x5a1d)
REQUIREMEM(45968, 47503, 4914, 18106, 4919)
LOADMEM(args[3])
BLOCK(0x2173, 0x656c, 0x7572, 0x5f70, 0x6d6f, 0x6363)
SWAP(mem[1], mem[2])
BLOCK(0x6573, 0x5f67, 0xd8ea, 0xe4be, 0xe0da, 0xdec6)
SWAP(mem[1], mem[2])
BLOCK(0xc6ca, 0xe6be, 0xce42, 0xe6ca, 0x7dc1, 0xb5bd)
SWAP(mem[1], mem[2])
BLOCK(0x8d8d, 0x95cd, 0x7d9c, 0x85cd, 0x95b1, 0xd5c9)
SWAP(mem[1], mem[2])
BLOCK(0x7b1b, 0x1b2b, 0x9afb, 0x390b, 0x9b2b, 0x63ab)
SWAP(mem[1], mem[2])
BLOCK(0x92fb, 0x836b, 0x5735, 0xf672, 0x1736, 0x56c7)
SWAP(mem[1], mem[2])
BLOCK(0x5725, 0xf706, 0xd6f6, 0x3636, 0xe42e, 0x6cad)
SWAP(mem[1], mem[2])
BLOCK(0x8eae, 0x4bee, 0xdad, 0xec6c, 0x6cae, 0x6bec)
INITIAL(0x5b1d, 0x5c97, 0xdc1b, 0x5bd8)
REQUIREMEM(52416, 34922, 5033, 1967, 4919)
LOADMEM(args[4])
BLOCK(0x6761, 0x6c66, 0x5f65, 0x6b61, 0x665f, 0x615f)
SWAP(mem[1], mem[2])
BLOCK(0x6d61, 0x5f49, 0xccbe, 0xcad6, 0xc2cc, 0xbec2)
SWAP(mem[1], mem[2])
BLOCK(0xbeda, 0xc2be, 0x92ce, 0xc2d8, 0xad85, 0x997d)
SWAP(mem[1], mem[2])
BLOCK(0x857d, 0xb585, 0x7d25, 0x9d85, 0xb199, 0x7d95)
SWAP(mem[1], mem[2])
BLOCK(0xfb0a, 0xfb6b, 0xafa, 0x4b3b, 0xb63, 0x32fb)
SWAP(mem[1], mem[2])
BLOCK(0x2b5b, 0xb32, 0xd615, 0xf496, 0x7616, 0xc665)
SWAP(mem[1], mem[2])
BLOCK(0xf656, 0xb616, 0x65f6, 0x15f6, 0x2cec, 0x2d8c)
SWAP(mem[1], mem[2])
BLOCK(0xcbec, 0xad6c, 0x2ccb, 0xec2b, 0xedac, 0x2be9)
INITIAL(0x1997, 0xd95a, 0xd859, 0x97d8)
REQUIREMEM(40175, 26311, 54488, 23870, 4919)

Code for BLOCK operation:

The multiplication modulo operation can be reversed easily using exgcd, remain step to reverse is the xor with mem4 and mem5 variables, but luckily mem[0]^mem[2] is constant after that step, so we can reverse blocks directly:

After that the final reversing is very easy:

Output:

args[4]: 3399988180034215742
args[3]: 3399988403602744163
args[2]: 7310236399631692389
args[1]: 8391157515662226017
args[0]: 6878457303729123447
6878457303729123447
8391157515662226017
7310236399631692389
3399988403602744163
3399988180034215742

Easy life.

Provided python script is quite short:

Some summary:

• AES with CBC mode.
• Controllable IV on decryption.
• Non-randomized pad-length byte padding and un-checked un-padding.

So they matched for a padding-oracle attack.

First, we obtain the encrypted welcome message which provides us full information of that block’s encryption:

• Message welcome_txt: "Welcome!!" + "\x07"*7
• IV welcome_iv: first 16 bytes of E_welcome
• Ciphertext welcome_cip: remain 16 bytes of E_welcome

With these we can fully control the decrypted text of first block:

or

where

So to let the decrypt function to decrypt the first block into any plaintext just use IV xor P_0 xor P_target as the new IV.

So we can manage to run get-flag by that method and obtain the encrypted flag, which turned out to have 3 blocks.

The first block of flag starts with hitcon{ from the assert part in server code, which allow us to control first 7 bytes of the decrypted, which’s enough for the get-md5 command.

So for the first block, we can find each byte from 8^th character by enumerating its value. Assume we already found out a prefix p, we can use the known welcome encryption information to generate encrypted md5 hash of p+c for any char c, and then find c_flag by looking up p+c_flag using that encrypted md5 lookup table. But at first we have to find out the 16^th character of the first block so we can control the padding, which’s quite easy after we have all encrypted md5 hash of any single byte character S1: just enumerating the last byte c until we receive a hash that’s inside S1, at that time the decrypted block must be "get-md5" + (1 char) + (7 chars) + char(8), so the last byte is c xor 8.

For the second and third block, i used the part msg = recv_msg().strip() to solve each byte using md5 by controlling the padding value: if hash(s)=hash(s+c) then c must be a whitespace character.

Final solution below:

Main function’s code:

This’s a Rock-paper-scissors game which use 0,1,2 as the move values. It first require us to beat Slime bot and 10 Alpaca bots to obtain the first flag, and then 10 Nozomi and 100 randomly selected bots to obtain the second flag. We must send our AI as lua code once and every match will run without additional input.

All bot use pseudo random number generator to generate their moves, send last move to our ai and read our next move, then compare these moves to decide who wins, we will play 100 000 matches each game and required to win 90%, which’s 90 000 matches in order to win the game.

1. Slime bot: this’s the most simple bot, which generate next move as next_move = (last_move+1) mod 3.
2. Alpaca bot: this bot generate next move by using state transform formula number = last_user_move + number - 0x61C88647; which number is unsigned int and first generated using a true random generator, and then calculate its move as number mod 3.
3. Nozomi bot: this’s a more advanced bot which at first frightened me from understanding its state transform function (below), but after some google it’s turned out to be Park and Miller #2 RNG.

// decompiled code
tmp = 48271 * number * (unsigned __int128)0x200000005uLL >> 64;
number = 48271 * number - 0x7FFFFFFF * ((tmp + ((48271 * number - tmp) >> 1)) >> 30);
// Park and Miller #2 RNG
__uint64_t pm(__uint64_t x){
 return (x*48271)%0x7FFFFFFF;
}

First we need a way to detect the current bot we’re facing with, the easiest way is using game-counter variable but will lead into problem with 100 randomized game. We need to win 90 000 games, which mean we can lose 10 000 games, that’s a lot, so i spend 30 first moves to decide which’s the bot we’re facing:

1. Slime bot: Its formula is easy to verify, if all the first 30 moves are in the pattern 0,1,2,0,1,2,0,1,2… then that’s it.
2. Alpaca bot: At first i think this bot’s so easy, as 0x61C88647 mod 3 = 1 we just need to keep sending 1 as our move for the first 30 moves and then the number variable wont be changed. I was wrong. But luckily checking for number of unchanged moves is enough to verify this bot, which 50% of the moves must not be changed if we keep sending move 1.
3. Nozomi bot: Simple, if it isnt slime, and isnt alpaca, then that’s it.

Now’s the time for “AI”:

1. Slime bot: bot’s next move is (last_move+1)%3, easy.
2. Alpaca bot: due to the overflow problem, i thought this’s a RE problem first and move to other problems, but then @trichimtrich found out the problem. Subtracting number by 0x61C88647 frequency overflow the operation, which add into it a factor of 2^32 mod 3 = 1,  he completed solution for this bot and i ported to lua. Primary idea is that each time our predict move is different from the actual move, number must have been overflowed, we just need to keep a range that move the same speed as number to check for overflow and adjust the modulo value when our current predicted value is out or in of that range.
3. Nozomi bot: as the function is a PRNG which distributes sample equally within [0, 0x7FFFFFFF], we can somehow precompute a table of 2 000 000 samples which can be checked easily when number go into that table. I decided to use last 20 moves encoded in base 3 as key for the table. The probability that we failed to catch this table after 7000 moves is((0x7FFFFFFF-2000000)/0x7FFFFFFF)^7000 = 0.00147029, so our success rate is above 99%.

Final code that solved all these problems: