Monday, March 18, 2013

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

2 comments :

  1. Nice way to solve it. You could have solved it in a deterministic way by starting from the last character. Every character is encrypted by using an algorithm that depends on the following character. The second character is sar'd, shr'd etc. and then a final value is used to shift right 0x12345678 of bytes and finally the lowest byte of that is used as the xor key of the first character. So if we know what the second character is, we can can get the previous character. Luckily if you look at the ciphertext, it ends with 0x0, and the only way to get 0 in the algorithm is if the input byte is 0. So we know the last character, we can then get the second to last character etc. I have written this assembly code solve it.
    Note that decrypting this way yields the key in reverse order so we just need to reverse it.
    http://pastebin.com/408ENEvQ
    I hope this helps

    ReplyDelete
    Replies
    1. Hey nice solution :) When I inspected the memory, this is how it looked like
      (gdb) x/36bx 0x601030
      0x601030: 0x4c 0x10 0x49 0x00 0x24 0x09 0x49 0x36
      0x601038: 0x09 0x05 0x1e 0x26 0x25 0x4b 0x00 0x74
      0x601040: 0x65 0x41 0x00 0x1e 0x2a 0x4b 0x00 0x1e
      0x601048: 0x2a 0x4b 0x4c 0x48 0x00 0x00 0x00 0x00
      0x601050: 0x78 0x56 0x34 0x12

      My interpretation was, there is 28 bytes of cipher text, followed by a NULL and then the key value of 0x12345678. For 28 bytes of cipher text, we need 29 bytes of plain text. I guess your technique is based on the fact that string is terminated by NUL, so the 29th byte of plain text will be a NUL byte. So we can compute the plain text in reverse, using the 29th byte as NUL. Nice :) tried it out in python http://pastebin.com/EpDp5LYg. Good way to take advantage of NUL. Thanks for the input

      Delete