]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/mla/asis19.md
ilm0 - added spent hours and fixed formatting
[pub/jan/ctf-seminar.git] / writeups / mla / asis19.md
1 # ASIS Cyber Security Contest '19
2
3 ## Close Primes
4
5     The people who can do you the most damage are the ones who are closest to you.  
6     "close" means q = next_prime(p)
7     nc 76.74.177.206 3371
8
9 The hint `close means q = next_prime(p\)` was released at a later time and I only found out about that hint after the challenge ended.
10 Upon connecting to the host we get a challenge in the form of `Please submit a printable string X, such that sha256(X)[-6:] = 95b3ff and len(X) = 27`.
11 That appears to be the same prove-of-work task that is used in the "Yet funny" challenge, for which the source code is given.
12 The hash can be one of `md5, sha1, sha224, sha256, sha384, sha512` and the length is between `10 and 40`. 
13 Once the PoW has been solved, we are presented with the following task:
14
15     hi all! We are looking for two large close 512-bit primes p and q such that q > p, and √q - √p ≥ 0.000000000000000000000000000000000000000000000000000000000000000000000000016
16         Can you find such primes? √ means sqrt, try your best and send to us the first prime p.
17         Options:
18                 [S]end prime p
19                 [Q]uit!
20                 
21 ### Attempt
22
23 I first wrote a python script to solve the PoW part. 
24
25 ```python
26 from pwn import *
27 import itertools
28 from time import sleep
29 from random import choice
30 from string import *
31 import pwnlib.util.hashes
32
33 host='76.74.177.206'
34 port=3371
35
36 def parse(line):
37         hash = line[46:line.index('(')]
38         mindex = line.index('] = ')
39         match = line[mindex+4:mindex+10]
40         length = int(line[-3:-1])
41         return (hash, match, length)
42
43 def reconnectTillMd5():
44         while True:
45                 r = remote(host, port)
46                 line = r.recvline().decode()
47                 (h, m, l) = parse(line)
48                 if h == 'md5':
49                         print(line)
50                         return (r,h,m,l)
51                 else:
52                         r.close()
53                         sleep(0.5)
54
55 def bruteforce_rand(match, length, hashfunc):
56     l = len(match)
57     count = 1
58     while True:
59         c = ''.join(choice(ascii_letters + digits) for i in range(length))
60         h = hashfunc(c.encode())
61         if h[-l:] == match:
62             print('match found: {} = h({})'.format(h, c))
63             return c
64         if count % 1000000 == 0:
65             print('tried {} * 10^6 hashes'.format(count/1000000))
66             print('{} = h({})'.format(h, c))
67         count+=1
68
69 def bruteforce_seq(match, length, hashfunc):
70     l = len(match)
71     count = 1
72     for c in itertools.product(ascii_letters+digits, repeat = length):
73         c = ''.join(c)
74         h = hashfunc(c.encode())
75         if h[-l:] == match:
76             print('match found: {} = h({})'.format(h, c))
77             return c
78         if count % 1000000 == 0:
79             print('tried {} * 10^6 hashes'.format(count/1000000))
80             print('{} = h({})'.format(h, c))
81         count+=1
82
83 def main():
84     (r, h, m, l) = reconnectTillMd5()
85     c = bruteforce_seq(m,l)
86     r.sendline(c)
87     txt = r.recvall()
88     print(txt)
89
90 if __name__ == '__main__':
91     #h = md5sumhex
92     #l = 10
93     #plain = 'aaaanaaaaa' #''.join(choice(ascii_letters+digits) for i in range(l))
94     #hash = h(plain.encode())
95     #match = hash[-6:]
96     #print('{} characters long ending with {}'.format(l, match))
97     #c = bruteforce_seq(match, l, h)
98     main() 
99 ```
100 The code connects to the server using the pwntools tubes module, gets the PoW challenge and tries to bruteforce the correct hash. Here I had some problems, because I would often get a timeout before the script could find a correct value. I first thought the problem is that I ran the code in a VM, but running the code directly did not improve the performance. Because I did not want to use a different language because pwntools is so convenient and I did not know (or want to) if multithreading / starting multiple processes would help much I just reconnected till to the host till I got a md5 hash, for which the script got an solution most of the time. Then I received the real challenge as shown above. The challange can be run offline, which is nice. To find primes I used the gmpy2 library, which also has a function `next_prime(q)`, which conveniently finds the next prime `p` such that `p > q`. The code:
101 ```python
102 from Crypto.Util.number import *
103 import gmpy2
104
105 def main():
106         c = 0
107         start=time.time()
108         dif = 0.000000000000000000000000000000000000000000000000000000000000000000000000016
109         while True:
110                 p = getPrime(512)
111                 q = gmpy2.next_prime(p)
112                 if (gmpy2.sqrt(q) - gmpy2.sqrt(p)) >= dif:
113                         print('found: ', p, q)
114                         return (p,q)
115                 if time.time() - start > 15:
116                         print('{}: {} tested'.format(time.time()-start, c))
117                         start = time.time()
118                 c +=1
119
120 if __name__ == '__main__':
121         p,q = main()
122         print('(p,q) = ({},{})'.format(p,q))
123 ```
124 I ran that code for about an hour and in the meantime looked another challenge. Unfortunately, the code did not work / return a result. 
125
126 ## Problems of my code
127 After the CTF was over, I looked at the writeup from [here][1] to find out why my code did not work.
128 The code above cannot find a solution because I did not set the precision of the [reals / the mpfr module][2]. 
129 That can be done with `gmpy2.get_context().precision = 1024`. If we do not set the `precision` to a sufficiently high number, the `sqrt` calculations - `gmpy2.sqrt(q)` and `gmpy2.sqrt(p)` - return the same value because the numbers are so huge. As an example:
130 ```python
131 >>> p = getPrime(512)
132 >>> p
133 11631779155100729962586087103617610994659776213061220305417026036717218640211672664963542324251964649791603386004740049118812343848359731655073667497316291
134 >>> gmpy2.sqrt(p)
135 mpfr('1.0785072626135037e+77')
136 >>> gmpy2.sqrt(p-999999999999999999999999999999)
137 mpfr('1.0785072626135037e+77')
138 ```
139 Therefore, the difference between the two square roots is always 0 and my loop never terminates.
140
141 Performance-wise, I am sure there are some possible improvements ;).
142
143
144 [1]: https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/close_primes
145 [2]: https://gmpy2.readthedocs.io/en/latest/mpfr.html#contexts
146
147
148 ## Serifin (crypto)
149     A sincere gift for cryptographers, enjoy solving it!
150
151 We got an archive with the following files:
152 + output.txt
153 + serifin.py
154
155 output.txt contains two large numbers, `c and n`:
156
157     c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
158     n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
159
160 serifin.py contains code that encodes the flag by performing `c = encrypt(flag, n)`. It seems we have to reverse engineer the code and somehow calculate the flag given the two values `c,n` from the output.txt file.
161
162 ### Attempt
163 First I looked at the source code: two prime numbers p and q are generated but with some condition
164     
165     p%9 = 1, q%9 = 1, p%27 > 1, q%27 > 1 and q = next_prime(fun(p))
166
167 Then, the flag is encoded with `c = flag^3 mod n` with `n=p*q`.
168 Essentially we have to solve the congruence  `f³ = c mod n` with c and n given.
169 First, I tried solving this with z3 and the python bindings for it. Unfortunately, that didn't work.
170 I then took a closer look at the serifin function and found that it basically calculates the partial sum of the geometric series `a + a/l + a/l² + a/l³ + ..`, but with the caveat that if the difference between the current and last term is smaller than `0.0001`, the function stops. Maybe that information can be used to factor `n` into `p and q`.
171
172 I then spent a long time reading up about modular arithmetic and RSA.
173 Apparently, the solution has something to do with the [Chinese Remainder Theorem][1], because I found and [stackexchange entry][2]. I spent some more time reading up on the CRT but unfortunately did not learn how to solve the problem.
174
175 [1]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
176 [2]: https://math.stackexchange.com/questions/2689987/solving-cubic-congruence
177
178
179
180 ## Securealloc (Warm-up, pwn)
181     
182 ### Description
183     The key to success in the battlefield is always the secure allocation of resuorces!
184     nc 76.74.177.238 9001
185     
186 Archive with
187 + libc.so.6
188 + libsalloc.so
189 + securalloc.elf
190
191 We are given a binary and a library together an specific version of libc. The binary runs on a remote host and takes input on port 9001. Upon connecting to the host/port we are given a menu with the following options:
192  1. Create      - asks for size, allocates memory of given size
193  2. Edit                - write to the allocated memory
194  3. Show                - print content of memory
195  4. Delete      - free the memory
196   
197 ![menu.png][menu]
198
199 From that, I concluded the challenge has something to do with heap exploitation.
200
201 ### Attempt
202 I am not that familiar with binary exploitation, I never did a heap overflow challenge and only some basic stack overflow exploits, so I did not know what to expect.
203 First of all, I just played around with the binary and tried some unusual inputs to maybe produce an error, e.g. edit before create and writing more than the specified size. Both of these attempts resulted in an error, see the images below. The error `*** heap smashing detected ***: ...` was new to me, I knew that gcc prints a stack smashing error but I`ve never heard of this one. I googled the error message but did not get any results so I assumed it is a custom error message. 
204
205 ![segfault.png][segfault]
206 ![heapsmash.png][heapsmash]
207  
208 Next, loaded the binaries into ghidra to disassamble/decompile them and look at the code. I pretty quickly found the main function, then inspected the code some more and did some variable and function renaming.
209 The main function (see below) does some initialisation and then prints the menu, takes the user input and performs some action based on it in an infinite loop.  
210
211 ```c
212 void main(void)
213 {
214   int extraout_EAX;
215   init_stuff();
216   do {
217     print_menu();
218     if (extraout_EAX == 2) {
219       edit();
220     }
221     else {
222       if (extraout_EAX < 3) {
223         if (extraout_EAX == 1) {
224           create();
225         }
226         else {
227 LAB_00100dad:
228           puts("Invalid option");
229         }
230       }
231       else {
232         if (extraout_EAX == 3) {
233           show();
234         }
235         else {
236           if (extraout_EAX != 4) goto LAB_00100dad;
237           delete();
238         }
239       }
240     }
241     __heap_chk_fail(DAT_00302050_pointer_to_memory);
242   } while( true );
243 }
244 ``` 
245 To get the input from the user, the functions `userInput()` resp.`readInput(..)`are used. I took a closer look at these function because I already knew there was some kind of overflow in the  code due to the errors from before. Indeed, in `readInput` (see below) there is an infinite loop that uses `read(..)` to get the user input and store it in the give buffer. The loop does not check the buffer size and only terminates after a `\n` is encountered.
246 ```c
247 char * readInput(char *param_1)
248 {
249   ssize_t sVar1;
250   char *buffer;
251   buffer = param_1;
252   while( true ) {
253     sVar1 = read(0,buffer,1);
254     if (sVar1 == 0) {
255                     /* WARNING: Subroutine does not return */
256       exit(1);
257     }
258     if (*buffer == '\n') break;
259     buffer = buffer + 1;
260   }
261   *buffer = '\0';
262   return buffer + -(long)param_1;
263 }
264 ```
265
266
267 I also noticed that the  `init_stuff()`,`create()` and `delete()` functions use the functions `secure_init(..)`, `secure_malloc(..)` and `secure_free(..)` from the `libsalloc.so` library, so I took a look at them. The `secure_init` function appears to read `8*8` bytes from `/dev/urandom`, performs a bitwise `and` with the value `0xffffffffffffff00` and saves the result at a fixed address or offset which I named `canary`. As to why, that will be clear shortly.
268 The other two appear to be wrappers for their respective functions of the c library, namely `malloc` and `free`. 
269
270 ```c
271 void secure_init(void)
272 {
273   FILE *__stream;
274   int local_14;
275   __stream = fopen("/dev/urandom","rb");
276   if (__stream == (FILE *)0x0) {
277                     /* WARNING: Subroutine does not return */
278     exit(1);
279   }
280   local_14 = 0;
281   while (local_14 < 8) {
282     fread(&canary,8,1,__stream);
283     local_14 = local_14 + 1;
284   }
285   fclose(__stream);
286   canary = canary & 0xffffffffffffff00;
287   return;
288 }
289 ```
290 `secure_malloc` actually allocates `0x10` bytes more than specified by the user and then returns a pointer that does not point to the start of the memory region but 2 addresses in. This is done because at the beginning, the `size` given from the user is stored. At the end of the memory region ( at `puVar1 + 8 + param_1`, which I think should be enough space for `8 * sizeof(unit)`), the value  at the address `canary` is stored. That is the value that was written by the `secure_init` function.
291 ```c
292 uint * secure_malloc(uint param_1)
293 {
294   uint *puVar1;
295   
296   puVar1 = (uint *)malloc((ulong)(param_1 + 0x10));
297   if (puVar1 == (uint *)0x0) {
298                     /* WARNING: Subroutine does not return */
299     __abort("Resource depletion (secure_malloc)");
300   }
301   *puVar1 = param_1;
302   puVar1[1] = param_1 + 1;
303   *(undefined8 *)((ulong)param_1 + 8 + (long)puVar1) = canary;
304   return puVar1 + 2;
305 }
306 ```
307
308 At the end of the main loop, there is a call to `__heap_chk_fail(pointer)` which is defined in `libsalloc.so`.  This is the function that prints the error message `*** heap smasing detected ***: ...`.
309 It appears that the function checks if the given pointer contains the value of the `canary` at a certain offset. I did not really make sense of all the pointer arithmetics but from that I concluded that  the `secure_*` functions basically implement `stack canaries` but for the heap. That´s also the reason I renamed the variable `canary`.
310
311 ```c
312 void __heap_chk_fail(long param_1)
313 {
314   if (((param_1 != 0) && (*(int *)(param_1 + -4) - *(uint *)(param_1 + -8) == 1)) &&
315      (*(long *)(param_1 + (ulong)*(uint *)(param_1 + -8)) != canary)) {
316                     /* WARNING: Subroutine does not return */
317     __abort("*** heap smashing detected ***: <unknown> terminated");
318   }
319   return;
320 }
321 ```
322
323 To summarise, I new that I could allocate memory of arbitrary size (actually + 0x10 bytes), free the memory and write to it. I could also overflow that buffer by writing more bytes than the actual size. So I had to either somehow leak the canary or otherwise circumvent the heap canary check to exploit the vulnerability.
324 Unfortunately, I did not know what to do with that so I started reading up on how  memory management works and how to do heap exploitations [1] [2] [3] [4] [5].  Understanding how malloc works was relatively easy but took some time. On the other hand, applying the new knowledge proved quite difficult and I did not really know where to start because it looks like there is no holy grail of heap exploits which allows you to perform certain steps which always result in a successful exploit.  So after working on the challenge for about 1 and a half days I saw myself defeated and had to give up.
325
326
327 [1]: https://sourceware.org/glibc/wiki/MallocInternals
328 [2]: https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
329 [3]: https://sploitfun.wordpress.com/2015/02/26/heap-overflow-using-unlink/
330 [4]: https://sploitfun.wordpress.com/2015/03/04/heap-overflow-using-malloc-maleficarum/
331 [5]: https://github.com/shellphish/how2heap
332
333 [menu]: ./asis19/menu.png
334 [segfault]: ./asis19/segfault.png
335 [heapsmash]: ./asis19/heapsmash.png