ForbiddenBITS CTF 2013 - smelf 200 - [Team xbios]

For this challenge we got a 64-bit stripped executable. The binary implements a crypter, our aim is to understand the crypter and decrypt the cipher text bytes in the binary. We reversed the binary and rewrote the code in python

0x400657: mov    eax,DWORD PTR [rbp-0x14] ; eax = i
0x40065a: cdqe   
0x40065c: add    rax,QWORD PTR [rbp-0x28] ; rax = i + *argv[1]
0x400660: movzx  eax,BYTE PTR [rax]
0x400663: mov    esi,eax    ; esi = *rax ; current byte
0x400665: mov    eax,DWORD PTR [rbp-0x14]
0x400668: cdqe   
0x40066a: add    rax,0x1       
0x40066e: add    rax,QWORD PTR [rbp-0x28] ; rax = (i+1) + *argv[1]
0x400672: movzx  eax,BYTE PTR [rax]   ; eax = *rax ; fetch the next byte
0x400675: mov    edx,eax    
0x400677: sar    dl,0x7     ; dl = dl/2^7 
0x40067a: shr    dl,0x6     ; dl = dl/2^6 ; this will 0 out register
0x40067d: add    eax,edx     
0x40067f: and    eax,0x3    ; eax = eax & 0x3
0x400682: sub    al,dl       
0x400684: movsx  eax,al     
0x400687: shl    eax,0x3    ; eax = eax * 2^3
0x40068a: mov    edx,DWORD PTR [rbp-0x2c]   
0x40068d: mov    edi,edx    ; edi = 0x12345678
0x40068f: mov    ecx,eax    
0x400691: shr    edi,cl     ; edi = edi/ 2 ^ cl
0x400693: mov    eax,edi    
0x400695: xor    eax,esi    ; eax = eax ^ esi

#!/usr/bin/env python
# crypt.py

import sys

# we should decrypt this string
crypt = [0x4c, 0x10, 0x49, 0x00, 0x24, 0x09, 0x49, 0x36, 0x09, 0x05, 0x1e, 0x26, 0x25, 0x4b, 0x00, 0x74, 0x65, 0x41, 0x00, 0x1e, 0x2a, 0x4b, 0x00, 0x1e, 0x2a, 0x4b, 0x4c, 0x48]

string = sys.argv[1]
key = 0x12345678
cipher = []

for i in range(len(string)-1):
    val = (ord(string[i+1]) & 0x3) * (2**3)
    edi = key / (2 ** val)
    eax = (edi ^ ord(string[i]) ) & 0xff
    cipher.append(hex(eax))

print cipher

We couldn't figure out an exact way to reverse the cipher text though. The algorithm uses (i)th and (i+1)th byte of plain text to calculate the (i)th cipher byte. So we generated a list of possible values for each byte position. Here is the python code:

#!/usr/bin/env python
# sol.py

# we should decrypt this string
crypt = [0x4c, 0x10, 0x49, 0x00, 0x24, 0x09, 0x49, 0x36, 0x09, 0x05, 0x1e, 0x26, 0x25, 0x4b, 0x00, 0x74, 0x65, 0x41, 0x00, 0x1e, 0x2a, 0x4b, 0x00, 0x1e, 0x2a, 0x4b, 0x4c, 0x48]

key = 0x12345678

for i in range(len(crypt)):
    print "#" * 20
    for j in range(32,127):
        pos = []
        for k in range(32,127):
            val = (k & 0x3) * (2**3)
            edi = key / (2 ** val)
            eax = (edi ^ j ) & 0xff
            if eax == crypt[i]:
                pos.append(k)
        if len(pos) > 0:
            print j,pos 

[ctf@renorobert Forbidden]# python sol.py
####################
52 [32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124]
94 [35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 123]
120 [34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126]
####################
36 [34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126]
70 [33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105, 109, 113, 117, 121, 125]
104 [32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124]
####################
49 [32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124]
91 [35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 123]
125 [34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126]
####################
52 [34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126]
86 [33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105, 109, 113, 117, 121, 125]
120 [32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124
==========================================================================================================

Then we used tree diagram to reach the flag. May not be the best solution but here is the approach:

[*] First element can be 52, 94 or 120
[*] Element 94 doesn't have an equivalent XOR 2nd byte ie. there is no 36,70,104. So 94 can be eleminated
[*] Element 52 maps to [36,104] and 120 maps to [70]. So 2 possible 1st byte values [52,120]
[*] Element 36 and 104 in 2nd byte position doesn't have an equivalent XOR byte ie. no 49,91 or 125. This leaves us with only one option [70], which is child of [120]
[*] Thus we have found the first two bytes as [120,70]

Entending this approach we found upto 26 bytes. Byte 27 was left with two options [52, 120] and byte 28 was left with 3 options [48,124] mapping to previous [52] and [90] mapping to [120]. These two bytes can be easily bruteforced or guessed.

This is wat we got from tree diagram [120 - 70 - 49 - 52 - 54 - 95 - 49 - 36 - 95 - 49 - 102 - 52 - 55 - 51 - 52 - 102 - 51 - 57 - 52 - 102 - 56 - 51 - 52 -102 - 56 - 51] . Final 2 bytes are [ 52 - 48]

Here is the final text we got xF146_1$_1f4734f394f834f8340. So the flag for the challenge is 1f4734f394f834f8340