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