allways r0ops

This challenge was quite hard for the points given. Anyway, the “reversing” is easy enough.

First off the program accepts a network connection and reads up to 0x1000 bytes to a global buffer. Then it copies 0x1000 random looking bytes from one global buffer to another. I have no idea what this step is for; an attempt at obfuscation maybe?

Lastly rdi is loaded with the address of the received data, rsi with the address of an uninitialized global buffer, and rsp with an address in the middle of the random looking bytes. Upon return from the program will then of course jump to the first address stored here.

As it turns out that address contains a jump to a short code sequence which ends in a ret, which of course means that the program jumps to the next address in the “stack”:

1 0x0dead1f4: jmp     2 ;; 0x0dead1f8
2 0x0dead1f6: or      esi, esi ;; probably just for alignment
3 0x0dead1f8: pop     rcx
4 0x0dead1f8: retn

Looking at a few more gadgets on the “stack” I see the pattern that they all start with a short jump and end with a return.

So I write an IDA script to extract the “real” program:

 1 from idaapi import *
 2 from idautils import *
 3 from idc import *
 4 import sys, os
 5 
 6 # IDA does something to fd 1 and 2
 7 def info(s):
 8     os.write(42, '%s\n' % s)
 9 
10 rsp = 0xe0b08a0
11 program = []
12 while True:
13     addr = Qword(rsp)
14     line = '0x%08x -> ' % rsp
15     rsp += 8
16     # Looks like all gadgets start on a jump
17     jmp = DecodeInstruction(addr)
18     # Not a pointer: The "stack" is probably exhausted
19     if jmp is None:
20         break
21     assert jmp.get_canon_mnem() == 'jmp'
22     addr = jmp.Op1.addr
23     while True:
24         size = MakeCode(addr)
25         assert size > 0
26         mnem = GetMnem(addr)
27         line += '0x%08x: %s' % (addr, GetDisasm(addr))
28         if   mnem == 'retn':
29             break
30         elif mnem == 'pop':
31             line += ' ;; %d' % Qword(rsp)
32             rsp += 8
33         addr += size
34         program.append(line)
35         line = ' ' * 14
36 
37 info('\n'.join(program))
38 
39 exit()

And run it:

  1 $ idaq64 -Sdecode.py -B r0ops 42>&1
  2 0x0e0b08a0 -> 0x0dead1f8: pop     rcx ;; = 0x8
  3 0x0e0b08b0 -> 0x0dead275: pop     r9 ;; = 0x1337deadbeef0095
  4 0x0e0b08c0 -> 0x0dead127: mov     rax, [rdi]
  5 0x0e0b08c8 -> 0x0dead0f1: add     rsi, 8
  6 0x0e0b08d0 -> 0x0dead208: mov     [rsi], rax
  7 0x0e0b08d8 -> 0x0dead26b: mov     r8, [rsi]
  8 0x0e0b08e0 -> 0x0dead0fc: sub     rsi, 8
  9 0x0e0b08e8 -> 0x0dead107: add     rdi, 8
 10 0x0e0b08f0 -> 0x0dead0f1: add     rsi, 8
 11 0x0e0b08f8 -> 0x0dead27e: mov     [rsi], r9
 12 0x0e0b0900 -> 0x0dead212: mov     rax, [rsi]
 13 0x0e0b0908 -> 0x0dead0fc: sub     rsi, 8
 14 0x0e0b0910 -> 0x0dead1f0: pop     rbx ;; = 0xcafe
 15 0x0e0b0920 -> 0x0dead145: imul    rax, rbx
 16 0x0e0b0928 -> 0x0dead0f1: add     rsi, 8
 17 0x0e0b0930 -> 0x0dead208: mov     [rsi], rax
 18 0x0e0b0938 -> 0x0dead288: mov     r9, [rsi]
 19 0x0e0b0940 -> 0x0dead0fc: sub     rsi, 8
 20 0x0e0b0948 -> 0x0dead0f1: add     rsi, 8
 21 0x0e0b0950 -> 0x0dead27e: mov     [rsi], r9
 22 0x0e0b0958 -> 0x0dead212: mov     rax, [rsi]
 23 0x0e0b0960 -> 0x0dead0fc: sub     rsi, 8
 24 0x0e0b0968 -> 0x0dead1f0: pop     rbx ;; = 0xbeef
 25 0x0e0b0978 -> 0x0dead131: add     rax, rbx
 26 0x0e0b0980 -> 0x0dead0f1: add     rsi, 8
 27 0x0e0b0988 -> 0x0dead208: mov     [rsi], rax
 28 0x0e0b0990 -> 0x0dead288: mov     r9, [rsi]
 29 0x0e0b0998 -> 0x0dead0fc: sub     rsi, 8
 30 0x0e0b09a0 -> 0x0dead2cc: pop     r12 ;; = 0x1
 31 0x0e0b09b0 -> 0x0dead292: pop     r10 ;; = 0x3419
 32 0x0e0b09c0 -> 0x0dead1e8: pop     rax ;; = 0x0
 33 0x0e0b09d0 -> 0x0dead1f0: pop     rbx ;; = 0x0
 34 0x0e0b09e0 -> 0x0dead200: pop     rdx ;; = 0x1d8
 35 0x0e0b09f0 -> 0x0dead19f: cmp     rax, rbx
 36               0x0dead1a2: jnz     short near ptr unk_DEAD1A7
 37               0x0dead1a4: add     rsp, rdx
 38 0x0e0b09f8 -> 0x0dead0f1: add     rsi, 8
 39 0x0e0b0a00 -> 0x0dead29b: mov     [rsi], r10
 40 0x0e0b0a08 -> 0x0dead2c2: mov     r11, [rsi]
 41 0x0e0b0a10 -> 0x0dead0fc: sub     rsi, 8
 42 0x0e0b0a18 -> 0x0dead0f1: add     rsi, 8
 43 0x0e0b0a20 -> 0x0dead2b8: mov     [rsi], r11
 44 0x0e0b0a28 -> 0x0dead212: mov     rax, [rsi]
 45 0x0e0b0a30 -> 0x0dead0fc: sub     rsi, 8
 46 0x0e0b0a38 -> 0x0dead1f0: pop     rbx ;; = 0x1
 47 0x0e0b0a48 -> 0x0dead177: and     rax, rbx
 48 0x0e0b0a50 -> 0x0dead0f1: add     rsi, 8
 49 0x0e0b0a58 -> 0x0dead208: mov     [rsi], rax
 50 0x0e0b0a60 -> 0x0dead2c2: mov     r11, [rsi]
 51 0x0e0b0a68 -> 0x0dead0fc: sub     rsi, 8
 52 0x0e0b0a70 -> 0x0dead0f1: add     rsi, 8
 53 0x0e0b0a78 -> 0x0dead2b8: mov     [rsi], r11
 54 0x0e0b0a80 -> 0x0dead212: mov     rax, [rsi]
 55 0x0e0b0a88 -> 0x0dead0fc: sub     rsi, 8
 56 0x0e0b0a90 -> 0x0dead1f0: pop     rbx ;; = 0x1
 57 0x0e0b0aa0 -> 0x0dead200: pop     rdx ;; = 0x68
 58 0x0e0b0ab0 -> 0x0dead1ae: cmp     rax, rbx
 59               0x0dead1b1: jz      short near ptr unk_DEAD1B6
 60               0x0dead1b3: add     rsp, rdx
 61 0x0e0b0ab8 -> 0x0dead0f1: add     rsi, 8
 62 0x0e0b0ac0 -> 0x0dead2d5: mov     [rsi], r12
 63 0x0e0b0ac8 -> 0x0dead212: mov     rax, [rsi]
 64 0x0e0b0ad0 -> 0x0dead0fc: sub     rsi, 8
 65 0x0e0b0ad8 -> 0x0dead0f1: add     rsi, 8
 66 0x0e0b0ae0 -> 0x0dead261: mov     [rsi], r8
 67 0x0e0b0ae8 -> 0x0dead226: mov     rbx, [rsi]
 68 0x0e0b0af0 -> 0x0dead0fc: sub     rsi, 8
 69 0x0e0b0af8 -> 0x0dead145: imul    rax, rbx
 70 0x0e0b0b00 -> 0x0dead0f1: add     rsi, 8
 71 0x0e0b0b08 -> 0x0dead208: mov     [rsi], rax
 72 0x0e0b0b10 -> 0x0dead2df: mov     r12, [rsi]
 73 0x0e0b0b18 -> 0x0dead0fc: sub     rsi, 8
 74 0x0e0b0b20 -> 0x0dead0f1: add     rsi, 8
 75 0x0e0b0b28 -> 0x0dead261: mov     [rsi], r8
 76 0x0e0b0b30 -> 0x0dead212: mov     rax, [rsi]
 77 0x0e0b0b38 -> 0x0dead0fc: sub     rsi, 8
 78 0x0e0b0b40 -> 0x0dead0f1: add     rsi, 8
 79 0x0e0b0b48 -> 0x0dead261: mov     [rsi], r8
 80 0x0e0b0b50 -> 0x0dead226: mov     rbx, [rsi]
 81 0x0e0b0b58 -> 0x0dead0fc: sub     rsi, 8
 82 0x0e0b0b60 -> 0x0dead145: imul    rax, rbx
 83 0x0e0b0b68 -> 0x0dead0f1: add     rsi, 8
 84 0x0e0b0b70 -> 0x0dead208: mov     [rsi], rax
 85 0x0e0b0b78 -> 0x0dead26b: mov     r8, [rsi]
 86 0x0e0b0b80 -> 0x0dead0fc: sub     rsi, 8
 87 0x0e0b0b88 -> 0x0dead0f1: add     rsi, 8
 88 0x0e0b0b90 -> 0x0dead29b: mov     [rsi], r10
 89 0x0e0b0b98 -> 0x0dead212: mov     rax, [rsi]
 90 0x0e0b0ba0 -> 0x0dead0fc: sub     rsi, 8
 91 0x0e0b0ba8 -> 0x0dead195: shr     rax, 1
 92 0x0e0b0bb0 -> 0x0dead0f1: add     rsi, 8
 93 0x0e0b0bb8 -> 0x0dead208: mov     [rsi], rax
 94 0x0e0b0bc0 -> 0x0dead2a5: mov     r10, [rsi]
 95 0x0e0b0bc8 -> 0x0dead0fc: sub     rsi, 8
 96 0x0e0b0bd0 -> 0x0dead0f1: add     rsi, 8
 97 0x0e0b0bd8 -> 0x0dead29b: mov     [rsi], r10
 98 0x0e0b0be0 -> 0x0dead212: mov     rax, [rsi]
 99 0x0e0b0be8 -> 0x0dead0fc: sub     rsi, 8
100 0x0e0b0bf0 -> 0x0dead1f0: pop     rbx ;; = 0x0
101 0x0e0b0c00 -> 0x0dead200: pop     rdx ;; = 0xfffffffffffffde0
102 0x0e0b0c10 -> 0x0dead1ae: cmp     rax, rbx
103               0x0dead1b1: jz      short locret_DEAD1B6
104               0x0dead1b3: add     rsp, rdx
105 0x0e0b0c18 -> 0x0dead0f1: add     rsi, 8
106 0x0e0b0c20 -> 0x0dead2d5: mov     [rsi], r12
107 0x0e0b0c28 -> 0x0dead212: mov     rax, [rsi]
108 0x0e0b0c30 -> 0x0dead0fc: sub     rsi, 8
109 0x0e0b0c38 -> 0x0dead0f1: add     rsi, 8
110 0x0e0b0c40 -> 0x0dead27e: mov     [rsi], r9
111 0x0e0b0c48 -> 0x0dead226: mov     rbx, [rsi]
112 0x0e0b0c50 -> 0x0dead0fc: sub     rsi, 8
113 0x0e0b0c58 -> 0x0dead200: pop     rdx ;; = 0x20
114 0x0e0b0c68 -> 0x0dead1ae: cmp     rax, rbx
115               0x0dead1b1: jz      short locret_DEAD1B6
116               0x0dead1b3: add     rsp, rdx
117 0x0e0b0c70 -> 0x0dead200: pop     rdx ;; = 0xfffffffffffffc38
118 0x0e0b0c80 -> 0x0dead1df: loop    near ptr unk_DEAD1DB
119 0x0e0b0c88 -> 0x0dead340: sub     rsp, 10h
120               0x0dead344: mov     edi, 0DEAD544h
121               0x0dead349: call    near ptr _puts
122               0x0dead34e: mov     edi, 0DEAD54Eh
123               0x0dead353: mov     eax, 0
124               0x0dead358: call    near ptr _printf
125               0x0dead35d: mov     dword ptr [rbp-4], 0
126               0x0dead364: jmp     short near ptr unk_DEAD38B
127               0x0dead366: mov     eax, [rbp-4]
128               0x0dead369: cdqe
129               0x0dead36b: mov     rax, ds:qword_E0B10C0[rax*8]
130               0x0dead373: mov     eax, eax
131               0x0dead375: mov     rsi, rax
132               0x0dead378: mov     edi, 0DEAD55Dh
133               0x0dead37d: mov     eax, 0
134               0x0dead382: call    near ptr _printf
135               0x0dead387: add     dword ptr [rbp-4], 1
136               0x0dead38b: cmp     dword ptr [rbp-4], 7
137               0x0dead38f: jle     short loc_DEAD366
138               0x0dead391: mov     edi, 0DEAD564h
139               0x0dead396: call    near ptr _puts
140               0x0dead39b: mov     eax, 0
141               0x0dead3a0: call    near ptr unk_DEAD3AF
142               0x0dead3a5: leave
143 0x0e0b0c90 -> 0x0dead3b3: sub     rsp, 10h
144               0x0dead3b7: mov     edx, 0
145               0x0dead3bc: mov     esi, 0
146               0x0dead3c1: mov     edi, 3
147               0x0dead3c6: call    near ptr _accept
148               0x0dead3cb: mov     [rbp-4], eax
149               0x0dead3ce: mov     eax, [rbp-4]
150               0x0dead3d1: mov     ecx, 0
151               0x0dead3d6: mov     edx, 1000h
152               0x0dead3db: mov     esi, 0E0B10C0h
153               0x0dead3e0: mov     edi, eax
154               0x0dead3e2: call    near ptr _recv
155               0x0dead3e7: mov     eax, [rbp-4]
156               0x0dead3ea: mov     edi, eax
157               0x0dead3ec: mov     eax, 0
158               0x0dead3f1: call    near ptr _close
159               0x0dead3f6: mov     edx, 0E0AF0A0h
160               0x0dead3fb: mov     esi, 0E0B00A0h
161               0x0dead400: mov     eax, 200h
162               0x0dead405: mov     rdi, rdx
163               0x0dead408: mov     rcx, rax
164               0x0dead40b: rep movsq
165               0x0dead40e: mov     eax, 0E0B10C0h
166               0x0dead413: mov     rdi, rax
167               0x0dead416: mov     eax, 0E0B20C0h
168               0x0dead41b: mov     rsi, rax
169               0x0dead41e: mov     eax, 0E0AF8A0h
170               0x0dead423: mov     rsp, rax

There are four conditional jumps in there. They all jump past the next instruction and directly to the retn. In all four cases the following instruction adds to rsp which is effectively a jump in the stack-program.

Looking at the stack-program I notice that

  1. It looks like it is “compiled” from some higher-level language (add rsi/sub rsi -instructions?)

  2. The last two gadgets are huge; they are probably “real” functions. The second one (the pointer at 0x0e0bc90) is just back in the accept-loop, so the first one (pointer at 0x0ebc88) is probably a win-function.

First I group the program by which instructions I guess belong to the same higher-level language operation:

  1     pop     rcx ;; = 0x8
  2     pop     r9  ;; = 0x1337deadbeef0095
  3 
  4     mov     rax, [rdi]
  5     add     rsi, 8
  6     mov     [rsi], rax
  7     mov     r8, [rsi]
  8     sub     rsi, 8
  9 
 10     add     rdi, 8
 11 
 12     add     rsi, 8
 13     mov     [rsi], r9
 14     mov     rax, [rsi]
 15     sub     rsi, 8
 16 
 17     pop     rbx ;; = 0xcafe
 18     imul    rax, rbx
 19 
 20     add     rsi, 8
 21     mov     [rsi], rax
 22     mov     r9, [rsi]
 23     sub     rsi, 8
 24 
 25     add     rsi, 8
 26     mov     [rsi], r9
 27     mov     rax, [rsi]
 28     sub     rsi, 8
 29 
 30     pop     rbx ;; = 0xbeef
 31     add     rax, rbx
 32 
 33     add     rsi, 8
 34     mov     [rsi], rax
 35     mov     r9, [rsi]
 36     sub     rsi, 8
 37 
 38     pop     r12 ;; = 0x1
 39     pop     r10 ;; = 0x3419
 40     pop     rax ;; = 0x0
 41     pop     rbx ;; = 0x0
 42 
 43     pop     rdx ;; = 0x1d8
 44     cmp     rax, rbx
 45     jnz     short near ptr unk_DEAD1A7
 46     add     rsp, rdx
 47 
 48     add     rsi, 8
 49     mov     [rsi], r10
 50     mov     r11, [rsi]
 51     sub     rsi, 8
 52 
 53     add     rsi, 8
 54     mov     [rsi], r11
 55     mov     rax, [rsi]
 56     sub     rsi, 8
 57 
 58     pop     rbx ;; = 0x1
 59     and     rax, rbx
 60 
 61     add     rsi, 8
 62     mov     [rsi], rax
 63     mov     r11, [rsi]
 64     sub     rsi, 8
 65 
 66     add     rsi, 8
 67     mov     [rsi], r11
 68     mov     rax, [rsi]
 69     sub     rsi, 8
 70 
 71     pop     rbx ;; = 0x1
 72 
 73     pop     rdx ;; = 0x68
 74     cmp     rax, rbx
 75     jz      short near ptr unk_DEAD1B6
 76     add     rsp, rdx
 77 
 78     add     rsi, 8
 79     mov     [rsi], r12
 80     mov     rax, [rsi]
 81     sub     rsi, 8
 82 
 83     add     rsi, 8
 84     mov     [rsi], r8
 85     mov     rbx, [rsi]
 86     sub     rsi, 8
 87 
 88     imul    rax, rbx
 89 
 90     add     rsi, 8
 91     mov     [rsi], rax
 92     mov     r12, [rsi]
 93     sub     rsi, 8
 94 
 95     add     rsi, 8
 96     mov     [rsi], r8
 97     mov     rax, [rsi]
 98     sub     rsi, 8
 99 
100     add     rsi, 8
101     mov     [rsi], r8
102     mov     rbx, [rsi]
103     sub     rsi, 8
104 
105     imul    rax, rbx
106 
107     add     rsi, 8
108     mov     [rsi], rax
109     mov     r8, [rsi]
110     sub     rsi, 8
111 
112     add     rsi, 8
113     mov     [rsi], r10
114     mov     rax, [rsi]
115     sub     rsi, 8
116 
117     shr     rax, 1
118 
119     add     rsi, 8
120     mov     [rsi], rax
121     mov     r10, [rsi]
122     sub     rsi, 8
123 
124     add     rsi, 8
125     mov     [rsi], r10
126     mov     rax, [rsi]
127     sub     rsi, 8
128 
129     pop     rbx ;; = 0x0
130     pop     rdx ;; = 0xfffffffffffffde0
131 
132     cmp     rax, rbx
133     jz      short locret_DEAD1B6
134     add     rsp, rdx
135 
136     add     rsi, 8
137     mov     [rsi], r12
138     mov     rax, [rsi]
139     sub     rsi, 8
140 
141     add     rsi, 8
142     mov     [rsi], r9
143     mov     rbx, [rsi]
144     sub     rsi, 8
145 
146     pop     rdx ;; = 0x20
147 
148     cmp     rax, rbx
149     jz      short locret_DEAD1B6
150     add     rsp, rdx
151 
152     pop     rdx ;; = 0xfffffffffffffc38
153     loop    near ptr unk_DEAD1DB
154 WIN:
155     ...
156 EXIT:
157     ...

Points of interest:

Rewriting register assignment, jumps and inserting labels gives:

 1     rcx <- 8
 2     r9  <- 0x1337deadbeef0095
 3 START:
 4     rax <- get_next_input_qword
 5     r8  <- rax
 6 
 7     rax <- r9
 8     rbx <- 0xcafe
 9     rax <- rax * rbx
10     r9  <- rax
11 
12     rax <- r9
13     rbx <- 0xbeef
14     rax <- rax + rbx
15     r9  <- rax
16 
17     r12 <- 1
18     r10 <- 0x3419
19 
20     rax <- 0
21     rbx <- 0
22     goto LBL3 if rax == rbx
23 
24 LBL1:
25     r11 <- r10
26 
27     rax <- r11
28     rbx <- 1
29     rax <- rax & rbx
30     r11 <- rax
31 
32     rax <- r11
33     rbx <- 1
34     goto LBL2 if rax <> rbx
35 
36     rax <- r12
37     rbx <- r8
38     rax <- rax * rbx
39     r12 <- rax
40 
41 LBL2:
42     rax <- r8
43     rbx <- r8
44     rax <- rax * rbx
45     r8  <- rax
46 
47     rax <- r10
48     rax <- rax >> 1
49     r10 <- rax
50 
51 LBL3:
52     rax <- r10
53     rbx <- 0
54     goto LBL1 if rax <> rbx
55 
56     rax <- r12
57     rbx <- r9
58     goto EXIT if rax <> rbx
59 
60     loop START
61 WIN:
62     ...
63 EXIT:
64     ...

Aha, rax and rbx are only used as temporary variables (notice that the compiler completely breaks character in the right-shift operation where 1 is used directly rather than being loaded into rbx).

Getting rid of rax and rbx:

 1     rcx <- 8
 2     r9  <- 0x1337deadbeef0095
 3 START:
 4     r8  <- get_next_input_qword
 5 
 6     r9  <- r9 * 0xcafe
 7     r9  <- r9 + 0xbeef
 8 
 9     r12 <- 1
10     r10 <- 0x3419
11     goto LBL3
12 
13 LBL1:
14     r11 <- r10
15     r11 <- r11 & 1
16     goto LBL2 if r11 <> 1
17     r12 <- r12 * r8
18 
19 LBL2:
20     r8  <- r8 * r8
21     r10 <- r10 >> 1
22 
23 LBL3:
24     goto LBL1 if r10 <> 0
25 
26     goto EXIT if r12 <> r9
27 
28     loop START
29 WIN:
30     ...
31 EXIT:
32     ...

One final rewrite (even though I’m sure you have it figured out):

 1 r9  <- 0x1337deadbeef0095
 2 run 8 times {
 3   r8  <- get_next_input_qword
 4   r9  <- r9 * 0xcafe + 0xbeef
 5   r12 <- 1
 6   r10 <- 13337
 7   while (r10) {
 8     if (r10 & 1) {
 9       r12 <- r12 * r8
10     }
11     r8  <- r8 * r8
12     r10 <- r10 / 2
13   }
14   if (r9 != r12) {
15     exit();
16   }
17 }
18 win();

This code computes a series as:

\[ x_0 = \tt{0x1337deadbeef0095} \\ x_n = x_{n-1} \cdot \tt{0xcafe} + \tt{0xbeef} \]

Split the input into qwords, \(y_1, ..., y_8\). For each \(y_i\) exponentiation by squaring is used to compute \(y_{i}^{13337}\).

If \(y_{i}^{13337} = x_i\) for \(i = 1, ..., 8\) the win-function is called. Easy-peasy.

Team member kriztw solved this part:

Because register values wrap around, computation effectively happens modulo \(2^{64}\).

By Euler’s theorem we have that \(a^{\phi(n)} \equiv 1 \mod n\), so if we can find \(d \equiv 13337^{-1} \mod \phi(n)\) we will have \(x_{i}^{d} = (y_{i}^{13337})^d = y_{i}^{13337 \cdot d} = y_{i}^1 = y_i\).

Every odd number is relatively prime to \(2^{64}\) so \(\phi(2^{64})\) is \(2^{63}\). And here’s the program:

 1 import gmpy
 2 
 3 N = 2**64
 4 
 5 xs = [0x1337deadbeef0095]
 6 for _ in range(8):
 7     xs.append((xs[-1] * 0xcafe + 0xbeef) % N)
 8 
 9 d = gmpy.invert(13337, 2**63)
10 for x in xs[1:]:
11     y = pow(x, d, N)
12     assert pow(y, 13337, N) == x
13     print y

Flag: 0ctf{c97155a5e288fa45f926b1058e4e0385d6ccde8513002885dc67948524bcbc85}


(To top)

Comments