Re100 - Clifford

this challenge isn’t quite hard!

after a few look (with hexray x64 of course 😋), we can know how this program work

  • Input triangle of number
  • Check characteristic
  • Print flag, xor with input

example input

  • n=2

cliff_01.png

  • n=4

cliff_02.png

Check characteristic

  • Each number in triangle is integer and in bound [1, 3 * n * n - 3 * n + 1]
  • Each number is different

Consider A = Sum of row 0

  • Sum of each row (0 -> 2 * n - 1) = A (*)
  • Sum of each col (0 -> 2 * n - 1) = A
  • Sum of each diagonal (n) = A
  • array[0][0] + array[1][0] = 20 and array[0][0] = 9

From (*), we have an equation: (2 * n - 1) * A = sum(1, 2, .., 3 * n * n - 3 * n + 1)

there is only n = 3 and A = 38 satisfies this equation.

Our matrix become:

09 a1 a2 
11 a3 a4 a5
18 a6 a7 a8 a9
0 a10 a11 a12 a13 0
0 0 a14 a15 a16 0 0

And system of equation

09 + a1 + a2 = 38
11 + a3 + a4 + a5 = 38
18 + a6  +  a7 + a8  + a9 = 38
a10 + a11 + a12 + a13 = 38
a14 + a15 + a16 = 38

a1 + a3 + a6 + a10 = 38
a2 + a4 + a7 + a11 + a14 = 38
a5 + a8 + a12 + a15 = 38
a9 + a13 + a16 = 38

18 + a10 + a14 = 38
11 + a6 + a11 + a15 = 38
09 + a3 + a7 + a12 + a16 = 38
a1 + a4 + a8 + a13 = 38
a2 + a5 + a9 = 38

a(i) in [1, 19] and a(i) not in (9, 11, 18)

Aggh, simple enough, so we could use WolframAlpha with Mathematical or z3 SMT to solve this.

a1 = 14, a2 = 15, a3 = 6, a4 = 8,
a5 = 13, a6 = 1, a7 = 5, a8 = 4,
a9 = 10, a10 = 17, a11 = 7, a12 = 2,
a13 = 12, a14 = 3, a15 = 19, a16 = 16

Flagtoo_bad_this_took_20_years_to_find!!


Re200 - Jumble Mumble

Code logic below

  • Check argc == 2
  • Hex decode argv[1] to string S
  • Loop 0x80 round (i)
    • S = Wut(i, S)
    • S = Rot(S)
  • S == "The flag is *not* poop..."

Describle operation of 2 function Wut, Rot:

  • Consider aj is value of character at index j of string S
  • And S = a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 ...

With each 16 bytes block of S

jumble_00.png

Split into 4 DWORD number A, B, C, D which A = 0xa3a2a1a0, B = 0xa7a6a5a4, C = 0xa11a10a9a8, D = 0xa15a14a13a12

=> after Wut operation, (A B C D) becomes (D B' B C) with B' = F(i)(A, B, C, D)

Depend on i parameter of Function Wut. There are 4 state for F(i)

F1: X = ror((!B & D) | (B & C), 0x19) ^ A + B
F2: X = ror((!D & C) | (B & D), 0x19) ^ A + B
F3: X = ror(C ^ B ^ D, 0x19) ^ A + B
F4: X = ror((!D | B) ^ C, 0x19) ^ A + B

jumble_01.png

As you can see, it’s easy to restore A from B,C,D 😀

Similarly, Rot function logic

jumble_02.png

jumble_03.png

jumble_04.png

jumble_05.png

len = n * n = 4 * 4
divide S to n sub-string (length n): 
Sub[0]: a0 a1 a2 a3
Sub[1]: a4 a5 a6 a7
Sub[2]: a8 a9 a10 a11
Sub[3]: a12 a13 a14 a15
for i = 0 to n-1:
    new_Sub[i] = ""
    for j = 0 to n-1:
      new_Sub[i] += Sub[j][(n - 1) - i]
new_S = join(new_Sub)

new 4 sub-string: a3 a7 a11 a15, a2 a6 a10 a14, a1 a5 a9 a13, a0 a4 a8 a12
=> new S: a3 a7 a11 a15 a2 a6 a10 a14 a1 a5 a9 a13 a0 a4 a8 a12

Again, this function is reversable 😀

I’ve written a small script to solve (and note some test cases)

from struct import pack, unpack

# pha 4,3,2,1 4,3,2,1 x 16

c = "The flag is *not* poop, but you can try that anyway because you strings'd this binary and saw something that looked interesting and just had to try it..."
c = c + '\x00' * (256 - len(c))

def deROT(cc):
    #0123 4567 89ab cdef
    #37bf 26ae 159d 048c

    #76543210 d607f929 89abcdef fedcba98
    #1029ef98 32f9cdba 5407abdc 76d689fe
    l = len(cc)
    ll = int(l ** 0.5)
    
    new_cc = ''

    for i in range(ll):
        for j in range(ll):
            new_cc += cc[(ll - 1 - j) * ll + i]

    return new_cc

# https://www.falatic.com/index.php/108/python-and-bitwise-rotation
# Rotate left: 0b1001 --> 0b0011
rol = lambda val, r_bits, max_bits: \
    (val << r_bits%max_bits) & (2**max_bits-1) | \
    ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
 
# Rotate right: 0b1001 --> 0b1100
ror = lambda val, r_bits, max_bits: \
    ((val & (2**max_bits-1)) >> r_bits%max_bits) | \
    (val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))

def deWUT(cc, pha):
    #A B C D
    #D X B C
    #Pha 4: X = ror((!D | B) ^ C, 0x19) ^ A + B
    #Pha 3: X = ror(C ^ B ^ D, 0x19) ^ A + B
    #Pha 2: X = ror((!D & C) | (B & D), 0x19) ^ A + B
    #Pha 1: X = ror((!B & D) | (B & C), 0x19) ^ A + B

    new_cc = ""
    for i in range(len(cc) / 16):
        line = cc[i * 16:i * 16 + 16]
        D = unpack("<I", line[0:4])[0]
        X = unpack("<I", line[4:8])[0]
        B = unpack("<I", line[8:12])[0]
        C = unpack("<I", line[12:16])[0]

        #print hex(B), hex(C), hex(D)
        if pha == 1: Y = ((B ^ 0xffffffff) & D) | (B & C)
        if pha == 2: Y = ((D ^ 0xffffffff) & C) | (D & B)
        if pha == 3: Y = B ^ C ^ D
        if pha == 4: Y = ((D ^ 0xffffffff) | B) ^ C

        Y = ror(Y, 0x19, 32)
        A = X - B
        if (A < 0): A += 0x100000000
        A ^= Y
        new_line = pack("<IIII", A, B, C, D)
        new_cc += new_line
        
    return new_cc

#Pha 1: c = '76543210d607f92989abcdeffedcba98'.decode('hex')
#Tra ve 0123...
 
#Pha 2: c = '76aa32364e12c33e8985cd545da48832'.decode('hex')
#4f88b7ad 8985cd545da488....
 
#Pha 3: c = '76f532cb4458d1b3895dcd5cd3fd2a07'.decode('hex')
#f36ca93d 895dcd5cd3fd2a0776f532cb
 
#Pha 4: c = '76bd8925f511130d32b1cd9a88a47359'.decode('hex')
#02f96eb4 32b1cd9a88a4735976bd8925
 
#print deWUT(c,4).encode('hex')
 
#ROT: c = '250d9a598913cd73bd11b1a476f53288'.decode('hex')
#76bd8925f511130d32b1cd9a88a47359
#print deROT(c).encode('hex')
 
for i in range(8):
    for j in range(16):
        c = deROT(c)
        c = deWUT(c, 4-(i%4))
 
print "Input this for flag:", c.encode('hex')

Flage1607eb3c8fc42f8a8b0229bc49ae957


Re250 - CryptoServ

At first, it’s a normal socket program

netcat to server and send some crafts, I always get *invalid instruction*

Then, I disassemble the binary, we can see some interesting info

Strings:
    - Invalid instruction
    - Invalid opcode
    - Invalid instruction pointer
    - Invalid length
Function symbols:
    - resetvm
    - runvm

Yup, maybe it’s a virtual machine.

And no suprise, the vm logic like this (pseudocode)

int len_code, len_s
int initA, initB
char[0x800] vm_code
char[0x1000] s
 
recv(fd, &len_code, 8) #4 byte len_code, 4 byte len_s
recv(fd, &initA, 8) #4 byte initA, 4 byte initB
 
if len_code <= 0x100 && len_s <= 0x1000:
    recv(fd, vm_code, 8 * len_code)
    recv(fd, s, len_s)
    
    new_len = (len_s / 8 + 1) * 8
    ptr = malloc(new_len) #char*
    
    encipher(&len_code, ptr) #push address of len_code to get other variable in encipher func
    send(fd, ptr, new_len)
 
def encipher:
    v7 = initA
    v8 = initB
    for i in range(new_len / 8):
        v5 = (int)s[8 * i:8 * i + 4]
        v6 = (int)s[8 * i + 4:8 * i + 8]
        encipher_block(vm_code, len_code, v5, v6, v7, v8, masterKey, &ptr[8 * i])
        v7 = (int)ptr[8 * i:8 * i + 4]
        v8 = (int)ptr[8 * i + 4:8 * i + 8]
 
def encipher_block:
    reset_vm() #set register to 0
    vm[0] = v7
    vm[1] = v8
    vm[2] = v5
    vm[3] = v6
    vm[4, 5, 6, 7] = masterKey (16 bytes)
    
    #important function
    run_vm(vm_code, len_code)
    
    ptr[8 * i:8 * i + 4] = vm[0]
    ptr[8 * i + 4:8 * i + 8] = vm[1]

Because this is so clean and clear (no obfuscate as all), and hex-ray is so freaking good, I won’t talk too much about this step.

My code to generate pseudocode from vm_code (extracted from PCAP file based on recv/send function)

from struct import unpack
 
f = open('crypt_opcode.txt','rb').read()
 
def deVM(code):
    op0 = ord(code[0])
    op1 = ord(code[1])
    op2 = ord(code[2])
    op3 = ord(code[3])
    val = unpack("<I", code[4:8])[0]
    if op0 == 0: st = "vm[%d] = vm[%d]" % (op1, op2)
    if op0 == 1: st = "vm[%d] = %d" % (op1, val)
    if op0 == 2: st = "vm[%d] = vm[%d] + vm[%d]" % (op1, op2, op3)
    if op0 == 3: st = "vm[%d] = vm[%d] & vm[%d]" % (op1, op2, op3)
    if op0 == 4: st = "vm[%d] = vm[%d] | vm[%d]" % (op1, op2, op3)
    if op0 == 5: st = "vm[%d] = vm[%d] ^ vm[%d]" % (op1, op2, op3)
    if op0 == 6: st = "vm[%d] = ~vm[%d]" % (op1, op2)
    if op0 == 7: st = "vm[%d] = vm[%d] >> %d" % (op1, op2, val)
    if op0 == 8: st = "vm[%d] = vm[%d] << %d" % (op1, op2, val)
    if op0 == 9: st = "vm[%d] = vm[%d + vm[%d]]" % (op1, op2, op3)
    if op0 == 10: st = "if vm[%d] == vm[%d]: EIP = %d" % (op2, op3, val)
    if op0 == 11: st = "if vm[%d] < vm[%d]: EIP = %d" % (op2, op3, val)
    if op0 == 12: st = "return"
 
    #print "#", code.encode('hex'), op0, op1, op2, op3, val
    return st
 
for i in range(len(f) / 8):
    code = f[8 * i:8 * i + 8]
    print code.encode('hex'), deVM(code)

And the result of vm_code

vm[0] = vm[0] ^ vm[2]
vm[1] = vm[1] ^ vm[3]
vm[14] = 0x9E3779B9
vm[13] = 0
for vm[15] in range(64):
    vm[0] = vm[0] + ((vm[1] << 4) ^ (vm[1] >> 5) + vm[1]) ^ (vm[4 + (vm[13] & 3)] + vm[13])
    vm[13] = vm[13] + vm[14]
    vm[1] = vm[1] + ((vm[0] << 4) ^ (vm[0] >> 5) + vm[0]) ^ (vm[4 + ((vm[13] >> 11) & 3)] + vm[13])
return

What da ‘ncrypt! I had no idea 😅. Then I tried to google 0x9e3779b9, maybe this magic constant could help us.

http://programmers.stackexchange.com/questions/63595/0x9e3779b9-golden-number

So, it’s XTEA encrypt operation.

http://en.wikipedia.org/wiki/XTEA

We have cipher text and alogrithm, but no plaintext, no master-key (redacted 🙁). But we could generate cipher-text from plain-text via server.

I have so many stupid thoughts:

  • Break XTEA Alogrithm ?? No, this is reversing problem !
  • Chosen plain-text attack ? Not a single clue 🙁.
  • Recover key from cipher-text … “Stop plz!”

After stucked for 30 mins, I looked back to input and saw vm_code in PCAP. Why we need to send this code? It’s encrypt operation. How about vm_code for decryption?

Oh yeah, that is best way, and does not relate to crypto stuffs.

import socket

def send(s,m):
    print "[SEND]", m
    s.send(m)

def recv(s):
    t = s.recv(4096)
    print "[RECV]", t
    return t

def deXTEA(code):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('52.4.141.125', 4141))
   
    send(s, "\x27\x00\x00\x00\x08\x00\x00\x00")
    send(s, code)
    send(s, "010F000000000000010E0000B979379E060E0E0000000000010D0000406EDE8D0802000004000000070300000500000005020203000000000202020000000000010C00000300000007090D000B000000030B090C00000000090A040B00000000020A0A0D000000000502020A000000000602020000000000010800000100000002020208000000000201010200000000020D0D0E000000000108000001000000020D0D08000000000802010004000000070301000500000005020203000000000202020100000000010C000003000000030B0D0C00000000090A040B00000000020A0A0D000000000502020A0000000006020200000000000108000001000000020202080000000002000002000000000108000001000000020F0F080000000001080000400000000B000F08040000000C00000000000000".decode('hex'))
    send(s, "abcdefgh")

    t = recv(s)
    s.close()
    return t

def xor(s1, s2):
    st = ''
    for i in range(len(s1)):
        st += chr(ord(s1[i % len(s1)]) ^ ord(s2[i % len(s2)]))
    return st

z = open('crypto_output.txt','rb').read()
st = "AB 87 62 79 4F EF 7F 2D".replace(' ', '').decode('hex')
vv = ""
for i in range(len(z) / 8):
    cipher = z[8 * i:8 * i + 8]
    cipher = deXTEA(cipher)
    cipher = xor(cipher, st)
    vv += cipher
    st = z[8 * i:8 * i + 8]

print vv

'''
~~~~~~~~~~~~~~~~~~~~ RAD B) ~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~ Your flage is: ~~~~~~~~~~~~~~~~~~~~
~~~~~~~~ flag{g0t_a_pr0bl3m??_put_a_VM_0n_it!} ~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
'''

What an interesting challenge 😉

If you have any question or idea, plz comment below xD

Have fun, thank mate !